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

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

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

1 索引模式

1.1 時態(tài)結(jié)點數(shù)據(jù)結(jié)構(gòu)

時態(tài)數(shù)據(jù)結(jié)點(Temporal Data Node，TDN)為常規(guī)XML 結(jié)點D 與有效時間期間標(biāo)簽VT 構(gòu)成: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 對應(yīng).不引起混淆時，本文有時不區(qū)分Γ 和H(Γ).

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

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

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

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

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

圖1 時態(tài)XML 有根分層圖與擴(kuò)展的深度優(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):結(jié)點Tcodes 編碼列表，其中結(jié)點編碼存儲指向其父結(jié)點的指針.

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

例2 例1 實例對應(yīng)Txmlsindex 如圖2 所示.

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

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

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

算法1 (基于LOP 時態(tài)包含查詢)設(shè)需查詢時間約束為VT(Q)，被查詢的LOP = {L0，L1，…，Ln}，Li的“最大元”和“最小元”分別記為max(Li)和min(Li).

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

輸出:result

Step 1 若i ＞=n，轉(zhuǎn)Step 5;

Step 2 若VT(Q)?min(Li)，即Q?min(Li)，Li都是查詢結(jié)果，result=result+{Li}，i++，轉(zhuǎn)Step 1;否則，轉(zhuǎn)Step 3;

Step 3 若max(Li). VTs ＞VT(Q).VTs，后續(xù)LOB 分支不包含VT(Q)，轉(zhuǎn)Step 5;否則，若VT(Q)max(Li)，Li都不是查詢結(jié)果，i++，轉(zhuǎn)Step 1;否則，轉(zhuǎn)Step 4;

Step 4 基于VTs(Q)對Li開始進(jìn)行“二分查找”，確定Li中“第一個”P，滿足VT(Q)?u(P)，包括u(P)在內(nèi)的Li中u(P)所有“前面”元素構(gòu)成的“片段”Li(u)都是查詢結(jié)果，result=result+{Li(u)};

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

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

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

輸出:時刻t0時的XML 文檔

Step 1 在Txmlsindex.LOP 中調(diào)用算法1 進(jìn)行時態(tài)查詢，得到結(jié)果集＜N0＞= ＜Code1，…，Codem＞，其中Codej為Tcodes 編碼;

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

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

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

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)有相關(guān)工作主要是TempIndex［7］和TempSum-Index［9］，而后者性能優(yōu)于前者［9］，因此，本文采用TempSumIndex 作為比較對象.索引構(gòu)建部分采用隨機(jī)生成的較大規(guī)模集(5 ～55 萬)，索引查詢部分采用美國NBA 時態(tài)XML 用例數(shù)據(jù)集［7］.

2.1 索引構(gòu)建

由圖3 所示，建立Txmlsindex 索引時間開銷小于TempSumIndex 建立開銷.同時Txmlsindex 時間開銷基本上呈線性變化.由圖4 所示，建立Txmlsindex索引空間開銷小于TempSumIndex 建立開銷.

圖3 建立索引時間開銷Figure 3 Time overhead of constructing index

圖4 建立索引空間開銷Figure 4 Space overhead of constructing index

引起上述差異的根本原因在于Txmlsindex 是在對所有結(jié)點一次性建立LOP，TempSumIndex 則是對于XML 有根分層圖中的每條結(jié)構(gòu)路徑上結(jié)點集合分別建立LOP，所選用XML 數(shù)據(jù)的結(jié)構(gòu)路徑數(shù)目與數(shù)據(jù)結(jié)點個數(shù)成正比;另外，Txmlsindex 構(gòu)建過程只涉及所給時態(tài)XML 數(shù)據(jù)的原始信息，而TempSumIndex 還需要描述、存儲和識別諸如結(jié)構(gòu)路徑和層次等額外信息.正是這兩方面原因使得兩者在時間和空間開銷上存在著較為明顯的差異.

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

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

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

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

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

3 結(jié)語

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

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

［2］孔令波，唐世渭，楊冬青，等. XML 數(shù)據(jù)索引技術(shù)［J］. 軟件學(xué)報，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ù)庫技術(shù)［M］. 2 版. 北京:清華大學(xué)出版社，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］.計算機(jī)學(xué)報，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］. 軟件學(xué)報，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ù)擴(kuò)展前序編碼的更新方法［J］. 軟件學(xué)報，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.