時態(tài)XML索引Txmlsindex

葉小平 ，林衍崇，陳釗瀅，鄭凡清，彭 鵬

(華南師范大學計算機學院，廣州510631)

由于網絡數(shù)據(jù)的格式多樣性和語義復雜性，需要有一種統(tǒng)一的數(shù)據(jù)表示語言進行描述和管理，XML 就是已被廣泛認可和使用的一種網絡數(shù)據(jù)語言.由于XML 的半結構化特性，難以像關系數(shù)據(jù)那樣建立完整統(tǒng)一的DBMS 進行相應數(shù)據(jù)操作，設計和構建XML 索引就成為數(shù)據(jù)查詢的基本技術途徑［1］.現(xiàn)有XML 數(shù)據(jù)索引技術主要有下述幾種基本類型:基于常規(guī)查詢方式處理，例如結點標記類和結構摘要類索引等［2］;基于索引過程中輔助查詢方式處理，例如結構概要類、結構連接類和結點序列類索引等［3］;基于經典索引技術的協(xié)同與擴展，例如結構摘要與結點編碼、結構摘要與樹型索引整合等［4］.各類索引的關鍵都是表述和處理XML 數(shù)據(jù)的結構信息.數(shù)據(jù)的時態(tài)處理是數(shù)據(jù)管理技術深入發(fā)展的一個重要體現(xiàn). 時態(tài)XML 數(shù)據(jù)索引已成為XML 數(shù)據(jù)庫技術的一個重要組成部分和研究熱點.根據(jù)查詢，現(xiàn)有工作從時態(tài)處理角度可分為2 類:(1)將數(shù)據(jù)結點的時間標簽作為結點常規(guī)屬性處理，如Mendelzon 等［5］提出的連續(xù)路徑索引和Baazizi 等［6］提出的基于結點自身編碼索引等. (2)將結點時間標簽與結點的語義與結構信息分別處理和協(xié)調整合，如Rizzolo 和Vaisman［7］提出的基于時態(tài)摘要索引、葉小平等［8］提出的基于時態(tài)語義協(xié)同索引等.時態(tài)XML 索引技術基本著力點是時態(tài)信息與結構信息的協(xié)同整合.時態(tài)XML 數(shù)據(jù)查詢主要有基于結構的值查詢和基于時刻的快照查詢，前者需要顯式處理數(shù)據(jù)結構信息以及時間語義信息，后者特征是突出結點的時間信息同時隱式處理結點的結構信息而無需涉及語義信息.對于時態(tài)數(shù)據(jù)管理來說，快照查詢是連接時態(tài)數(shù)據(jù)和常規(guī)數(shù)據(jù)管理的橋梁，在實際中也有廣泛應用，時態(tài)XML 快照索引是一般時態(tài)XML 索引的重要組成部分［5，7，9］. 同時快照查詢還突出了時態(tài)數(shù)據(jù)處理基本特征，在時態(tài)數(shù)據(jù)庫技術中具有明確的研究價值. 本文討論一種新的時態(tài)XML 快照索引方案Txmlsindex，它建立在時態(tài)擬序數(shù)據(jù)結構基礎之上，能夠進行“一次一集合”的數(shù)據(jù)查詢，并通過時態(tài)編碼輔助技術進行結構信息的快速匹配，其相應的技術框架和索引模式也可拓展到一般時態(tài)XML 查詢過程當中［8］.

1 索引模式

1.1 時態(tài)結點數(shù)據(jù)結構

時態(tài)數(shù)據(jù)結點(Temporal Data Node，TDN)為常規(guī)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 對應.不引起混淆時，本文有時不區(qū)分Γ 和H(Γ).

定義1 (擬序關系)設E 是時態(tài)結點集合，定義E 上關系:TDN1，TDN2E，TDN1TDN2?VT(TDN1)?VT(TDN2)，并稱“”是E 上滿足自反和傳遞的時態(tài)擬序(temporal quasi-order). 若TDN1，TDN2不存在“”關系，則記為TDN1??TDN2.

在平面點集Γ 上建立一個劃分Σ，Σ 上一個全序分枝稱為Γ 的一個線序分枝(Linear Order Branch，LOB)，稱為線序劃分，Σ 是Γ 上一個線序劃分(Linear Order Partition，LOP)，記為LOP(Γ).LOB 中元素具有“”關系，從大到小排列. 相關定義及構造算法見文獻［9］.

1.2 擴展的深度優(yōu)先編碼Tcodes

作為一種復雜型數(shù)據(jù)，時態(tài)XML 數(shù)據(jù)需要進行三方面的描述:①語義信息:即語義標簽，語義標簽間關聯(lián)表現(xiàn)為標簽路徑;②結構信息:即結點之間父/子關系以及衍生的祖先/子孫關系，表現(xiàn)形式是結構路徑;③時間信息:即時間標簽，通常為時間期間(period).為有效處理XML 數(shù)據(jù)的結構信息，通常對其結點進行編碼.時態(tài)XML 中編碼方案需反映結點關聯(lián)和時態(tài)約束，同時也應為更新“預留”編碼空間.本文在文獻［10］的基礎上建立了一種擴展的深度優(yōu)先編碼方案，其中祖先結點編碼小于子孫結點編碼，并且可以通過預留編碼gap 實現(xiàn)更新友好(update friendly).

例1 時態(tài)XML 實例和相應結點對應的擴展的深度優(yōu)先編碼如圖1 所示.

圖1 時態(tài)XML 有根分層圖與擴展的深度優(yōu)先編碼Tcodes Figure 1 Temporal XML Graph and Tcodes

1.3 Txmlsindex

定義2 (時態(tài)XML 快照索引模式Txmlsindex)基于時態(tài)擬序XML 快照索引(Temporal XML Snapshot index，Txmlsindex)為二元組Txmlsindex(T0)=＜Code(T0)，LOP(T0)＞，T0是XML 文檔數(shù)據(jù).

①Code(T0):結點Tcodes 編碼列表，其中結點編碼存儲指向其父結點的指針.

②LOP(T0):LOP(T0)為XML 中數(shù)據(jù)結點時間期間集合上線序劃分.

例2 例1 實例對應Txmlsindex 如圖2 所示.

圖2 Txmlsindex(T0)Figure 2 Txmlsindex(T0)

1.4 數(shù)據(jù)操作

時間處理是時態(tài)數(shù)據(jù)管理的中心課題.不同于基于“代數(shù)”的常規(guī)模式，論文研究的時態(tài)XML 索引基于“擬序”關系基礎之上建立. 時態(tài)XML 查詢過程是首先處理結點的時間標簽(算法1)，然后再處理相應的結構配置(算法2)

算法1 (基于LOP 時態(tài)包含查詢)設需查詢時間約束為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，后續(xù)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 進行時態(tài)查詢，得到結果集＜N0＞= ＜Code1，…，Codem＞，其中Codej為Tcodes 編碼;

Step 2 若＜No ＞≠?，?。糔o ＞中第1個Codei，若為根結點，記為root，否則，通過指針找到父節(jié)點Codej，＜No ＞= ＜No ＞Codei，轉Step 3;若＜No ＞=?，轉Step 4;

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

Step 4 若root≠?，取root 為根節(jié)點作為入口，由Tcodes 和XML 結點的映射及childeList 依次輸出完整的時態(tài)XML 快照查詢結果子樹.

2 仿真與評估

本文實驗環(huán)境為:Inter(R)Core(TM)2 Duo CPU P8600，主頻2.40 G，主存4 GB，操作系統(tǒng)Windows7，開發(fā)環(huán)境MyEclipse 8.5. 據(jù)我們所掌握資料，現(xiàn)有相關工作主要是TempIndex［7］和TempSum-Index［9］，而后者性能優(yōu)于前者［9］，因此，本文采用TempSumIndex 作為比較對象.索引構建部分采用隨機生成的較大規(guī)模集(5 ～55 萬)，索引查詢部分采用美國NBA 時態(tài)XML 用例數(shù)據(jù)集［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 數(shù)據(jù)的結構路徑數(shù)目與數(shù)據(jù)結點個數(shù)成正比;另外，Txmlsindex 構建過程只涉及所給時態(tài)XML 數(shù)據(jù)的原始信息，而TempSumIndex 還需要描述、存儲和識別諸如結構路徑和層次等額外信息.正是這兩方面原因使得兩者在時間和空間開銷上存在著較為明顯的差異.

2.2 數(shù)據(jù)查詢

從圖5 和圖6 可知，隨著數(shù)據(jù)量增大，Txmlsindex 對比于TempSumIndex 查詢效率明顯提升. 其中主要原因是Txmlsindex 主要基于XML 的時間信息構建索引，TempSumIndex 則需要基于結構路徑組織索引.事實上，由于XML 快照查詢的特殊性，與索引構建類似，基于索引查詢并不需要額外的結構和語義信息.因此，對于不同數(shù)據(jù)量快照查詢，Txmlsindex 直接進行一次時態(tài)篩選就可得到結果，即只需進行一次LOP 搜索，從而提高查詢效率. TempSum-Index 則需查找所有路徑結構下滿足時態(tài)約束的結點，即需要對多條LOP 進行搜索. 對于不同快照查詢時刻，當時刻值較小時，滿足時態(tài)約束的結點相應也較少，Txmlsindex 效率比TempSumIndex 高，隨著時刻變大，滿足時態(tài)約束的結點較多，Txmlsindex 效率和TempSumIndex 趨近相同，這主要是由于LOP時態(tài)結構自身特性所致.

圖5 不同數(shù)據(jù)量快照查詢時間開銷Figure 5 Querying at various data quantities

圖6 不同快照查詢時刻時間開銷Figure 6 Querying at various query instants

TempSumIndex 對所有結點的時間區(qū)間按照結構路徑進行劃分以得到多個LOP. 假設路徑結構數(shù)目為m，則基于TempSumIndex 的時態(tài)XML 快照查詢算法復雜度為m* O(log n)［9］. 而Txmlsindex 對所有結點的時間區(qū)間進行一次劃分以得到單一LOP，基于Txmlsindex 的時態(tài)XML 快照查詢算法復雜度為m* O(log n).

3 結語

論文研究時態(tài)XML 快照索引Txmlsindex. 首先建立基于時態(tài)擬序的數(shù)據(jù)結構用以處理時間信息和建立時態(tài)編碼用于處理結構信息;其次是通過時態(tài)XML 的時間與結構信息建立時態(tài)索引模式Txmlsindex;另外通過與現(xiàn)有基本工作進行仿真評估以表明論文工作的可行性與有效性. 快照查詢是時態(tài)數(shù)據(jù)查詢的重要組成部分，也是連接常規(guī)非時態(tài)查詢與時態(tài)查詢的技術橋梁，在時態(tài)XML 中為一般查詢的基礎.論文討論的索引框架可以推廣到更為一般情形，同時討論的擬序時態(tài)數(shù)據(jù)結構和時態(tài)編碼可以進行增量式更新，限于篇幅，相關內容將另文討論或參考文獻［9］.

［1］孟小峰. XML 數(shù)據(jù)管理概念與技術［M］. 北京:清華大學出版社，2009.

［2］孔令波，唐世渭，楊冬青，等. XML 數(shù)據(jù)索引技術［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 數(shù)據(jù)庫技術［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］葉小平，湯庸，張智博，等.語義協(xié)同時態(tài)XML 索引研究與實現(xiàn)［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］郭歡，葉小平，湯庸，等. 基于時態(tài)編碼和線序劃分的時態(tài)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 數(shù)據(jù)擴展前序編碼的更新方法［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.