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

杨佐希 等:基于时序分区的时态索引与查询 3529

询条件,高效地进行时态查询处理.

4 TPindex 索引更新
时态数据库的更新通常包括全量式更新和增量式更新,考虑到全量式更新在面对海量数据时存在难以重
复利用原有索引和效率较低等问题,在 TPindex 中主要以增量式更新为主.接下来,我们讨论 TPindex 索引的时态
数据插入和删除操作.
定义 8(局部域). 在时态平面上,对于׊y 0 ∈H(PГ),根据 y 0 所在的坐标位置,可以将对应的 H(PГ)分成以下 4
个区域.
L Top (y 0 )={y|y∈H(PГ)∧VTs(y)≤VTs(y 0 )∧VTe(y 0 )≤VTe(y)},
L Down (y 0 )={y|y∈H(PГ)∧VTs(y)≤VTs(y 0 )∧VTe(y)≤VTe(y 0 )},
R Top (y 0 )={y|y∈H(PГ)∧VTs(y 0 )≤VTs(y)∧VTe(y 0 )≤VTe(y)},
R Down (y 0 )={y|y∈H(PГ)∧VTs(y 0 )≤VTs(y)∧VTe(y)≤VTe(y 0 )}.
其中,L Top (y 0 ),L Down (y 0 ),R Top (y 0 )和 R Down (y 0 )分别代表 y 0 在 H(PГ)中的“左上区域”“左下区域”“右上区域”“右下区
域”.同时,为了方便相关阐述,将 L Top (y 0 ),L Down (y 0 ),R Top (y 0 )和 R Down (y 0 )的真子集分别定义如下.
SL Top (y 0 )={y|y∈H(PГ)∧VTs(y)<VTs(y 0 )∧VTe(y 0 )<VTe(y)},
SL Down (y 0 )={y|y∈H(PГ)∧VTs(y)<VTs(y 0 )∧VTe(y)<VTe(y 0 )},
SR Top (y 0 )={y|y∈H(PГ)∧VTs(y 0 )<VTs(y)∧VTe(y 0 )<VTe(y)},
SR Down (y 0 )={y|y∈H(PГ)∧VTs(y 0 )<VTs(y)∧VTe(y)<VTe(y 0 )}.
在更新索引之前,通过 4 个局部域的划分,索引结构可以快速地定位的目标数据的所在位置,缩小索引结构
更新的范围.同时.局部域可以保持更新前后时态数据的一致性,避免出现索引“缺失”、“断裂”等情况,为时态索
引的增量式更新提供有效地基础支持.
定义 9(前邻居点和后邻居点). 设 L 0 ∈PLOP,如果׌x 0 ∈L 0 ,且满足 VTS(x 0 )=VTS(y 0 )∧VTe(x 0 )=min{x|VTe(y 0 )≤
VTe(x)}, 则称 x 0 是 y 0 在 L 0 上的 一个前 邻居 点 , 记为 Front(y 0 ); 如果 ׌x 0 ∈L 0 , 且满 足 VTe(x 0 )=VTe(y 0 )∧
VTe(x 0 )=min{x|VTs(y 0 )≤VTs(x)},则称 x 0 是 y 0 在 L 0 上的一个后邻居点,记为 Back(y 0 ).
定义 10(最近下分枝)设 Line(PLOB)是 H(PГ)上从 max(PLOB)到 min(PLOB)遍历 PLOB 的路径,L 0 =<x 1 ,…,
x i–1 ,x i ,x i+1 ,…,x j–1 ,x j ,…,x m >,L next 表示在同一个 PLOP 中,与 L 0 相邻的下一个 PLOB 分枝,称 L next 是 L 0 的最近下
分枝.
通过上述的定义说明,我们将进一步讨论 TPindex 时态索引的动态更新机制,结合 PLOB 的结构特性,我们给
出以下增量式的动态更新算法.
4.1 TPindex插入更新

时态节点 y 0 的插入主要分为 3 种情况:在当前的分枝上新增节点、新增线序分枝、引起当前分枝的变化或
分裂.其主要的思想是:通过插入点 y 0 找到对应的 PLOB,若未找到相应的 PLOB,则将插入点单独新增为一个
PLOB.否则,结合定义 8 找到 SL Down (y 0 ),同时将 PLOB 中 SL Down (y 0 )的分枝部分切除,若该部分不为空,则递归重复
以上操作,将切除的分枝部分插入到相应的 PLOB 中,直至该切除部分为空.新形成的线序分枝中的元素仍满足
拟序关系,具体的算法插入过程如算法 3 所示.
算法 3. 基于 PLOB 的时态数据插入算法.
输入:插入节点 y 0 ,需要插入 PLOB.
输出:更新后的 PLOB.
1. select the corresponding L 0 according to the insert point y 0
2. if PLOPكSR Top (y 0 )∨PLOPكSL Down (y 0 ) then
3. new PLOB={y 0 };
4. end if