Page 209 - 《软件学报》2020年第11期

3524 Journal of Software 软件学报 Vol.31, No.11, November 2020

构建后的结构图如图 1 所示,其中若干条“路径”可以表示为<L 1 ,L 2 ,L 3 ,L 4 ,L 5 >,L 1 ={[1,9],[1,7],[1,6],[1,5],[2,5],[2,3],
[2,2],[3,2],[4,2]},L 2 ={[2,8],[2,7],[3,7],[3,4],[4,4]},L 3 ={[3,8],[4,8],[4,7],[5,7],[5,5]},L 4 ={[5,10],[5,9]},L 5 ={[6,10],[7,10],
[7,9],[7,8],[7,7],[7,6]}.

Fig.1 线序构造
图 1 Linear order building
2.3 时态索引TPindex构建

定义 4(分区线序划分(partition linear order partition,简称 PLOP)). 通过算法 1,我们得到的序列
T(PГ)=<L 1 ,L 2 ,…,L n >满足以下性质:
若׊L i ,L j ∈T∧i≠j⇔L i ∩L j =∅,且∪L i =Г(1≤i,j≤n).这样的 T(PГ)称为 H i (PГ)上的一个分区线序划分 PLOP,记为
PLOP=T(PГ),而 PLOP 中每一个 L i 称为该 PLOP 的一个分区线序分枝,记为 PLOB(partition linear order branch).
每个 PLOP、PLOB 具有以下的基本性质:
1) 每个 PLOP 是 H i (PГ)的划分.
2) 不妨设 VTs(L i )和 VTe(L i )是分别是 L i (1≤i≤n)的起点和终点序列,则 VTs(L i )单调增加,VTe(L i )单调减少.
定义 5(分枝首元和尾元). 对于 L∈PLOP(Г),将每个分枝 L 中第 1 个节点称为分枝首元,记为 max(L),将 L 中
最后一个节点称为尾元,记为 min(L).同时,将 PLOP(Г)中的所有 max(L)集合记为 PГmax,LOP(Г)中的所有 min(L)
集合记为 PГmin.
定义 6(分区时态索引 TPindex). 关于 H(PГ)上时态索引 TPindex 满足下列定义.
(1) 时态分区层(Partition level):Partition=<P1,P2,…,Pn>,用来保存若干个 H(PГ)的分区点 Pi(1≤i≤n–1).在
时序分区操作结束后,对每个分区 H(PГ)进行分区线序划分,由此组成 TPindex 的下层索引结构(2)~(5).
(2) 时态分区根节点层(Partition root Level):<r 1 ,r 2 ,…,r m >,r i =max(L i (PГmax)),1≤i≤m(注:这里以某一具体的
时序分区为例).
(3) PLOP MAX Level 层(PГmax):在 PLOP 上构建 PLOP(PГmax)={L i (PГmax)}(1≤i≤|PLOP(PГmax)|),该层
节点为 L i (PГmax).
(4) PLOP MIN(PГmin)层:上层节点 L i (PГmax)中对应元素 PLOB 集合构建 PLOP(PГmin(L i (PГmax)))(1≤