时态XML索引Txmlsindex

叶小平 ，林衍崇，陈钊滢，郑凡清，彭 鹏

(华南师范大学计算机学院，广州510631)

由于网络数据的格式多样性和语义复杂性，需要有一种统一的数据表示语言进行描述和管理，XML 就是已被广泛认可和使用的一种网络数据语言.由于XML 的半结构化特性，难以像关系数据那样建立完整统一的DBMS 进行相应数据操作，设计和构建XML 索引就成为数据查询的基本技术途径［1］.现有XML 数据索引技术主要有下述几种基本类型:基于常规查询方式处理，例如结点标记类和结构摘要类索引等［2］;基于索引过程中辅助查询方式处理，例如结构概要类、结构连接类和结点序列类索引等［3］;基于经典索引技术的协同与扩展，例如结构摘要与结点编码、结构摘要与树型索引整合等［4］.各类索引的关键都是表述和处理XML 数据的结构信息.数据的时态处理是数据管理技术深入发展的一个重要体现. 时态XML 数据索引已成为XML 数据库技术的一个重要组成部分和研究热点.根据查询，现有工作从时态处理角度可分为2 类:(1)将数据结点的时间标签作为结点常规属性处理，如Mendelzon 等［5］提出的连续路径索引和Baazizi 等［6］提出的基于结点自身编码索引等. (2)将结点时间标签与结点的语义与结构信息分别处理和协调整合，如Rizzolo 和Vaisman［7］提出的基于时态摘要索引、叶小平等［8］提出的基于时态语义协同索引等.时态XML 索引技术基本着力点是时态信息与结构信息的协同整合.时态XML 数据查询主要有基于结构的值查询和基于时刻的快照查询，前者需要显式处理数据结构信息以及时间语义信息，后者特征是突出结点的时间信息同时隐式处理结点的结构信息而无需涉及语义信息.对于时态数据管理来说，快照查询是连接时态数据和常规数据管理的桥梁，在实际中也有广泛应用，时态XML 快照索引是一般时态XML 索引的重要组成部分［5，7，9］. 同时快照查询还突出了时态数据处理基本特征，在时态数据库技术中具有明确的研究价值. 本文讨论一种新的时态XML 快照索引方案Txmlsindex，它建立在时态拟序数据结构基础之上，能够进行“一次一集合”的数据查询，并通过时态编码辅助技术进行结构信息的快速匹配，其相应的技术框架和索引模式也可拓展到一般时态XML 查询过程当中［8］.

1 索引模式

1.1 时态结点数据结构

时态数据结点(Temporal Data Node，TDN)为常规XML 结点D 与有效时间期间标签VT 构成:TDN=＜D，VT ＞，VT=［VTs，VTe)，VTs 和VTe 分别表示VT始、终点(VTs≤VTe).若VTs =VTe，VT =［VTs，VTe)为时刻(instant). TDN 有效时间期间记为VT(TDN).时间期间VT =［VTs，VTe)可看做VTs－VTe 平面上格点，通过映射VT =［VTs，VTe)→P(VTs，VTe)，时间期间集合Γ 和VTs－VTe 平面格点集合H(Γ)建立1－1 对应.不引起混淆时，本文有时不区分Γ 和H(Γ).

定义1 (拟序关系)设E 是时态结点集合，定义E 上关系:TDN1，TDN2E，TDN1TDN2⇔VT(TDN1)⊆VT(TDN2)，并称“”是E 上满足自反和传递的时态拟序(temporal quasi-order). 若TDN1，TDN2不存在“”关系，则记为TDN1≼≽TDN2.

在平面点集Γ 上建立一个划分Σ，Σ 上一个全序分枝称为Γ 的一个线序分枝(Linear Order Branch，LOB)，称为线序划分，Σ 是Γ 上一个线序划分(Linear Order Partition，LOP)，记为LOP(Γ).LOB 中元素具有“”关系，从大到小排列. 相关定义及构造算法见文献［9］.

1.2 扩展的深度优先编码Tcodes

作为一种复杂型数据，时态XML 数据需要进行三方面的描述:①语义信息:即语义标签，语义标签间关联表现为标签路径;②结构信息:即结点之间父/子关系以及衍生的祖先/子孙关系，表现形式是结构路径;③时间信息:即时间标签，通常为时间期间(period).为有效处理XML 数据的结构信息，通常对其结点进行编码.时态XML 中编码方案需反映结点关联和时态约束，同时也应为更新“预留”编码空间.本文在文献［10］的基础上建立了一种扩展的深度优先编码方案，其中祖先结点编码小于子孙结点编码，并且可以通过预留编码gap 实现更新友好(update friendly).

例1 时态XML 实例和相应结点对应的扩展的深度优先编码如图1 所示.

图1 时态XML 有根分层图与扩展的深度优先编码Tcodes Figure 1 Temporal XML Graph and Tcodes

1.3 Txmlsindex

定义2 (时态XML 快照索引模式Txmlsindex)基于时态拟序XML 快照索引(Temporal XML Snapshot index，Txmlsindex)为二元组Txmlsindex(T0)=＜Code(T0)，LOP(T0)＞，T0是XML 文档数据.

①Code(T0):结点Tcodes 编码列表，其中结点编码存储指向其父结点的指针.

②LOP(T0):LOP(T0)为XML 中数据结点时间期间集合上线序划分.

例2 例1 实例对应Txmlsindex 如图2 所示.

图2 Txmlsindex(T0)Figure 2 Txmlsindex(T0)

1.4 数据操作

时间处理是时态数据管理的中心课题.不同于基于“代数”的常规模式，论文研究的时态XML 索引基于“拟序”关系基础之上建立. 时态XML 查询过程是首先处理结点的时间标签(算法1)，然后再处理相应的结构配置(算法2)

算法1 (基于LOP 时态包含查询)设需查询时间约束为VT(Q)，被查询的LOP = {L0，L1，…，Ln}，Li的“最大元”和“最小元”分别记为max(Li)和min(Li).

输入:VT(Q)，LOP，i=0

输出:result

Step 1 若i ＞=n，转Step 5;

Step 2 若VT(Q)⊆min(Li)，即Q⊆min(Li)，Li都是查询结果，result=result+{Li}，i++，转Step 1;否则，转Step 3;

Step 3 若max(Li). VTs ＞VT(Q).VTs，后续LOB 分支不包含VT(Q)，转Step 5;否则，若VT(Q)max(Li)，Li都不是查询结果，i++，转Step 1;否则，转Step 4;

Step 4 基于VTs(Q)对Li开始进行“二分查找”，确定Li中“第一个”P，满足VT(Q)⊆u(P)，包括u(P)在内的Li中u(P)所有“前面”元素构成的“片段”Li(u)都是查询结果，result=result+{Li(u)};

Step 5 如果result≠∅，返回result.

算法2 (基于Txmlsindex 快照查询算法)

输入:VT=［t0，t0)，Txmlsindex，childeList

输出:时刻t0时的XML 文档

Step 1 在Txmlsindex.LOP 中调用算法1 进行时态查询，得到结果集＜N0＞= ＜Code1，…，Codem＞，其中Codej为Tcodes 编码;

Step 2 若＜No ＞≠∅，取＜No ＞中第1个Codei，若为根结点，记为root，否则，通过指针找到父节点Codej，＜No ＞= ＜No ＞Codei，转Step 3;若＜No ＞=∅，转Step 4;

Step 3 若不存在以Codej命名的孩子列表，新建childList(Codej)，加入childeList，将Codei加入childList(Codej)，转Step 2;

Step 4 若root≠∅，取root 为根节点作为入口，由Tcodes 和XML 结点的映射及childeList 依次输出完整的时态XML 快照查询结果子树.

2 仿真与评估

本文实验环境为:Inter(R)Core(TM)2 Duo CPU P8600，主频2.40 G，主存4 GB，操作系统Windows7，开发环境MyEclipse 8.5. 据我们所掌握资料，现有相关工作主要是TempIndex［7］和TempSum-Index［9］，而后者性能优于前者［9］，因此，本文采用TempSumIndex 作为比较对象.索引构建部分采用随机生成的较大规模集(5 ～55 万)，索引查询部分采用美国NBA 时态XML 用例数据集［7］.

2.1 索引构建

由图3 所示，建立Txmlsindex 索引时间开销小于TempSumIndex 建立开销.同时Txmlsindex 时间开销基本上呈线性变化.由图4 所示，建立Txmlsindex索引空间开销小于TempSumIndex 建立开销.

图3 建立索引时间开销Figure 3 Time overhead of constructing index

图4 建立索引空间开销Figure 4 Space overhead of constructing index

引起上述差异的根本原因在于Txmlsindex 是在对所有结点一次性建立LOP，TempSumIndex 则是对于XML 有根分层图中的每条结构路径上结点集合分别建立LOP，所选用XML 数据的结构路径数目与数据结点个数成正比;另外，Txmlsindex 构建过程只涉及所给时态XML 数据的原始信息，而TempSumIndex 还需要描述、存储和识别诸如结构路径和层次等额外信息.正是这两方面原因使得两者在时间和空间开销上存在着较为明显的差异.

2.2 数据查询

从图5 和图6 可知，随着数据量增大，Txmlsindex 对比于TempSumIndex 查询效率明显提升. 其中主要原因是Txmlsindex 主要基于XML 的时间信息构建索引，TempSumIndex 则需要基于结构路径组织索引.事实上，由于XML 快照查询的特殊性，与索引构建类似，基于索引查询并不需要额外的结构和语义信息.因此，对于不同数据量快照查询，Txmlsindex 直接进行一次时态筛选就可得到结果，即只需进行一次LOP 搜索，从而提高查询效率. TempSum-Index 则需查找所有路径结构下满足时态约束的结点，即需要对多条LOP 进行搜索. 对于不同快照查询时刻，当时刻值较小时，满足时态约束的结点相应也较少，Txmlsindex 效率比TempSumIndex 高，随着时刻变大，满足时态约束的结点较多，Txmlsindex 效率和TempSumIndex 趋近相同，这主要是由于LOP时态结构自身特性所致.

图5 不同数据量快照查询时间开销Figure 5 Querying at various data quantities

图6 不同快照查询时刻时间开销Figure 6 Querying at various query instants

TempSumIndex 对所有结点的时间区间按照结构路径进行划分以得到多个LOP. 假设路径结构数目为m，则基于TempSumIndex 的时态XML 快照查询算法复杂度为m* O(log n)［9］. 而Txmlsindex 对所有结点的时间区间进行一次划分以得到单一LOP，基于Txmlsindex 的时态XML 快照查询算法复杂度为m* O(log n).

3 结语

论文研究时态XML 快照索引Txmlsindex. 首先建立基于时态拟序的数据结构用以处理时间信息和建立时态编码用于处理结构信息;其次是通过时态XML 的时间与结构信息建立时态索引模式Txmlsindex;另外通过与现有基本工作进行仿真评估以表明论文工作的可行性与有效性. 快照查询是时态数据查询的重要组成部分，也是连接常规非时态查询与时态查询的技术桥梁，在时态XML 中为一般查询的基础.论文讨论的索引框架可以推广到更为一般情形，同时讨论的拟序时态数据结构和时态编码可以进行增量式更新，限于篇幅，相关内容将另文讨论或参考文献［9］.

［1］孟小峰. XML 数据管理概念与技术［M］. 北京:清华大学出版社，2009.

［2］孔令波，唐世渭，杨冬青，等. XML 数据索引技术［J］. 软件学报，2005，16(12):2063－2079.Kong L B，Tang S W，Yang D Q，et al. XML indices［J］. Journal of Software，2005，16(12):2063－2079.

［3］Catania B，Maddalena A，Vakali A. XML document indexs:A classicifaction［J］. IEEE Internet Computing，2005，9(5):64－71.

［4］万长选，刘喜平. XML 数据库技术［M］. 2 版. 北京:清华大学出版社，2008.

［5］Mendelzon A O，Rizzolo F，Vaisman A A. Indexing temporal XML documents［C］∥Proceedings of the 30th international conference on VLDB endowment. Toronto，Canada，2004，30:216－227.

［6］Baazizi M A，Bidoit N，Colazzo D. Efficient encoding of temporal XML documents［C］∥Proceedings of 18th international symposium on temporal representation and reasoning. Lubeck，Germany，2011:15－22.

［7］Rizzolo F，Vaisman A A. Temporal XML:Modeling，indexing，and query processing［J］. The VLDB Journal，2008，17(5):1179－1212.

［8］叶小平，汤庸，张智博，等.语义协同时态XML 索引研究与实现［J］.计算机学报，2014，37(9):1911－1921.Ye X P，Tang Y，Zhang Z B，et al. Study and implementation on semantics-based cooperative temporal XML index［J］. Chinese Journal of Computers，2014，37(9):1911－1921.

［9］郭欢，叶小平，汤庸，等. 基于时态编码和线序划分的时态XML 索引［J］. 软件学报，2012，23(8):2042－2057.Guo H，Ye X P，Tang Y，et al. Temporal XML index based on temporal encoding and linear order partition［J］. Journal of Software，2012，23(8):2042－2057.

［10］罗道锋，孟小峰，蒋瑜. XML 数据扩展前序编码的更新方法［J］. 软件学报，2005，16(5):810－818.Luo D F，Meng X F，Jiang Y. Updating of extended preorder numbering scheme on XML［J］. Journal of Software，2005，16(5):810－818.