基于復(fù)雜模式索引的ＸＭＬ查詢優(yōu)化

摘要：分析了XML模式與XML文檔之間的關(guān)系以及XML查詢的特點(diǎn)，提出了一種基于復(fù)雜模式索引的XML查詢優(yōu)化方法。該方法對(duì)XML模式中的節(jié)點(diǎn)建立索引，查詢時(shí)考慮XML模式中帶有環(huán)的情況。首先對(duì)查詢樹(shù)進(jìn)行去除重復(fù)元素的預(yù)處理，并將查詢樹(shù)分解成主路徑和分支路徑；然后利用索引查找潛在目標(biāo)節(jié)點(diǎn)的XML模式編號(hào)；最后在XML文檔中對(duì)對(duì)應(yīng)節(jié)點(diǎn)進(jìn)行篩選，找到目標(biāo)節(jié)點(diǎn)。該方法可以減少連接操作的次數(shù)，提高查詢操作的效率，能處理較復(fù)雜的XML模式。

關(guān)鍵詞：復(fù)雜模式； 索引；擴(kuò)展標(biāo)記語(yǔ)言； 查詢優(yōu)化； 路徑表達(dá)式

中圖分類號(hào)：TP311文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001－3695(2007)08－0100－06

0引言

XML[1]成為互聯(lián)網(wǎng)上數(shù)據(jù)交換的標(biāo)準(zhǔn)，對(duì)XML的查詢處理是目前數(shù)據(jù)庫(kù)領(lǐng)域研究的熱點(diǎn)問(wèn)題之一。現(xiàn)已提出多種查詢語(yǔ)言，如XPath、XQuery、XMLQL等，這些語(yǔ)言均是通過(guò)路徑表達(dá)式實(shí)現(xiàn)對(duì)XML文檔的查詢[2~4]。一般的XML查詢優(yōu)化都是通過(guò)有效處理路徑表達(dá)式來(lái)實(shí)現(xiàn)的。按照查詢處理方式，這些優(yōu)化方法基本上可以分為四類：

a）圖的遍歷方法。把XML文檔看成圖，對(duì)給定的查詢，通過(guò)對(duì)XML文檔圖進(jìn)行遍歷來(lái)實(shí)現(xiàn)查找過(guò)程。按照遍歷方式不同分為自頂向下遍歷、自底向上遍歷和混合遍歷三種。該類方法搜索空間較大，查詢的時(shí)間開(kāi)銷和空間開(kāi)銷均較大[5]。

b）路徑連接方法，針對(duì)圖的遍歷方法搜索空間較大的問(wèn)題。為了減小搜索空間，通過(guò)對(duì)XML文檔中的節(jié)點(diǎn)進(jìn)行編碼，根據(jù)編碼判斷節(jié)點(diǎn)之間的父子關(guān)系和祖先/后代關(guān)系。查詢時(shí)，將查詢路徑分解成一系列簡(jiǎn)單路徑，通過(guò)節(jié)點(diǎn)間的包含/擁有關(guān)系連接來(lái)求滿足所求關(guān)系的節(jié)點(diǎn)集合，然后將多條簡(jiǎn)單路徑的查詢結(jié)果連接起來(lái)[6~13]。這種方法雖然不需要對(duì)整個(gè)搜索空間進(jìn)行遍歷，但對(duì)于長(zhǎng)度為n的路徑，需要進(jìn)行n-1次連接操作，系統(tǒng)開(kāi)銷較大。c）路徑索引方法。對(duì)于沒(méi)有模式信息的XML文檔，根據(jù)文檔內(nèi)容提取模式信息，建立路徑索引，查詢時(shí)利用路徑索引來(lái)減小搜索空間。DataGuides就是路徑索引的典型代表[14]。該方法對(duì)于文檔內(nèi)容變化不大的情況是高效的，當(dāng)文檔內(nèi)容經(jīng)常發(fā)生變化時(shí)，需要?jiǎng)討B(tài)重新提取模式信息，模式信息的維護(hù)代價(jià)較大。另一方面，DataGuides中的合法路徑必須是從根開(kāi)始的，這樣不便于進(jìn)行任意路徑的查詢。

d）基于XML模式的方法。目前多數(shù)XML文檔都具有模式，DTD是XML模式的早期版本[15]。學(xué)者們發(fā)現(xiàn)可以利用DTD優(yōu)化XML查詢。這種方法是利用DTD中對(duì)XML結(jié)構(gòu)的定義建立DTD中的節(jié)點(diǎn)與XML文檔中節(jié)點(diǎn)的對(duì)應(yīng)關(guān)系；先在DTD中查找節(jié)點(diǎn)，根據(jù)與文檔中節(jié)點(diǎn)的對(duì)應(yīng)關(guān)系進(jìn)一步查找。該方法可大大減小搜索空間，但現(xiàn)有的基于DTD的方法均沒(méi)有考慮DTD中帶有環(huán)這一復(fù)雜情況，應(yīng)用領(lǐng)域受到一定限制。

1相關(guān)工作分析

XML模式是用于限制XML文檔中元素和屬性結(jié)構(gòu)以及數(shù)據(jù)類型的框架。目前多數(shù)XML文檔均符合一定的XML模式，XML文檔中的任意一個(gè)結(jié)構(gòu)一定對(duì)應(yīng)XML模式中的一個(gè)結(jié)構(gòu)。如果在XML模式中不能滿足的結(jié)構(gòu)，在XML文檔中肯定不能滿足，而XML模式要遠(yuǎn)遠(yuǎn)小于XML文檔。所以，為了減小搜索空間，利用XML模式進(jìn)行XML查詢優(yōu)化的一類方法被提了出來(lái)[16~18]。TaeSun Chung等人[16]構(gòu)建了一個(gè)DTD自動(dòng)機(jī)，把每個(gè)元素e的子元素標(biāo)簽分為兩類：不受影響的標(biāo)簽和受影響的標(biāo)簽。不受影響的標(biāo)簽是指元素e中一定包含的子元素標(biāo)簽；受影響的標(biāo)簽是指帶有“*”“|”或“？”的子元素標(biāo)簽。例如，〈!ELEMENT person(name， email*，(school|company)〉中不受影響的標(biāo)簽集合為{name}， 受影響的標(biāo)簽集合為{ email*，school，company }。然后根據(jù)受影響的標(biāo)簽組合建立該元素的分類表。對(duì)于上面的元素person，可以建立如表1所示的分類表。XML文檔中的person元素只能滿足這四類中的一類，對(duì)文檔中的person元素標(biāo)注其分類號(hào)。

基于該分類信息表提出了兩種查詢方法，即nodeInfo和mergeNodeInfo。NodeInfo方法中，XML文檔中的每個(gè)節(jié)點(diǎn)對(duì)象均包含該元素節(jié)點(diǎn)的分類信息。查找時(shí)，在滿足標(biāo)簽約束的節(jié)點(diǎn)集中查找相應(yīng)的節(jié)點(diǎn)，根據(jù)查找路徑的下一個(gè)標(biāo)簽和相應(yīng)節(jié)點(diǎn)的分類信息就可以判斷那些滿足標(biāo)簽約束的節(jié)點(diǎn)是潛在目標(biāo)節(jié)點(diǎn)，從而可以砍掉不滿足條件的子樹(shù)，以減小搜索空間。MergeNodeInfo方法中，XML文檔中的每個(gè)節(jié)點(diǎn)對(duì)象均包含該元素所有后代節(jié)點(diǎn)的分類信息。查找時(shí)，在滿足標(biāo)簽約束的節(jié)點(diǎn)集中查找相應(yīng)的節(jié)點(diǎn)，根據(jù)查找路徑當(dāng)前節(jié)點(diǎn)的所有后代標(biāo)簽集合和相應(yīng)節(jié)點(diǎn)的mergeNodeInfo信息就可以判斷那些滿足標(biāo)簽約束的節(jié)點(diǎn)是潛在目標(biāo)節(jié)點(diǎn)，從而可以砍掉不滿足條件的子樹(shù)，大大減小搜索空間。NodeInfo只能處理父/子關(guān)系，不能處理祖先/后代關(guān)系。MergeNodeInfo方法雖然能處理祖先/后代關(guān)系，但對(duì)后代節(jié)點(diǎn)標(biāo)簽重名較多的情況，搜索空間減小幅度不大。Chiyoung Seo等人[17]對(duì)DTD中的路徑進(jìn)行編號(hào)，建立路徑表path(path，pathID)，對(duì)XML文檔中的每個(gè)元素建立路徑索引表pathIndex(pathID，docID)，對(duì)XML文檔中的文本建立文本表term(term， termID)，對(duì)每個(gè)文本節(jié)點(diǎn)建立文本索引表termIndex(termID，docID，pathID，position)，將這四個(gè)索引表保存在RDBMS中。對(duì)給定查詢的路徑表達(dá)式先進(jìn)行預(yù)處理，將其中的“//”處理成“%/”以便于在SQL查詢中用like謂詞實(shí)現(xiàn)模糊查詢。對(duì)于不含關(guān)鍵字的路徑表達(dá)式，在path表中查找滿足條件路徑的pathID，然后在pathIndex表中查找滿足條件的目標(biāo)節(jié)點(diǎn)集合；對(duì)于含有關(guān)鍵字的查詢，將路徑表達(dá)式分成路徑部分和文本部分，路徑部分用上面的方法查找相應(yīng)的pathID，文本部分在term表中查找相應(yīng)的termID，最后在termIndex中查找具有指定pathID和termID的元組集合。利用這四個(gè)索引表實(shí)現(xiàn)對(duì)XML的查詢，可以大大減小搜索空間。但是，該方法不能處理DTD有環(huán)的情況：DTD中有環(huán)時(shí)元素的path不確定；另外，如果元素及其子元素的標(biāo)簽同源（如book和books，section和sections等），處理查詢路徑時(shí)用“%/”代替“//”可能查出的結(jié)果是錯(cuò)誤的。例如，如果“books”是帶有環(huán)的元素，books和book均有子元素“family”，那么，查詢路徑表達(dá)式“/books/book//family”，本意是查找根元素“books”的第一代子元素“book”的所有后代元素“family”，該表達(dá)式會(huì)被處理成“/books/book%/family”，查找結(jié)果為：根元素“books”的第一代子元素“book”或“books”的所有后代元素“family”，因此會(huì)產(chǎn)生錯(cuò)誤的查詢結(jié)果。另外，該方法只能處理簡(jiǎn)單路徑，不能處理復(fù)雜路徑。路燕等人[18]提出了DBXI(DTD based XML index)方法。該方法對(duì)DTD和XML文檔分別編碼，DTD中的元素采用文獻(xiàn)[19]中的前后序編碼方案；XML文檔中的元素采用文獻(xiàn)[20]中的編碼方案，每個(gè)XML文檔中的元素節(jié)點(diǎn)都記錄該元素節(jié)點(diǎn)在DTD中的編碼。DBXI分別對(duì)DTD和XML文檔建立索引。DTD索引的第一級(jí)索引是DTD元素/屬性列表；第二級(jí)索引是DTD樹(shù)中同名元素/屬性列表；第三級(jí)索引是DTD元素/屬性節(jié)點(diǎn)記錄。XML文檔索引的第一級(jí)索引是DTD樹(shù)中的節(jié)點(diǎn)前序遍歷編碼列表；第二級(jí)索引是XML文檔編號(hào)列表；第三級(jí)索引是對(duì)應(yīng)DTD中相同節(jié)點(diǎn)、文檔編號(hào)的XML文檔元素/屬性列表；第四級(jí)是XML元素/屬性節(jié)點(diǎn)記錄。進(jìn)行路徑查詢時(shí)，首先將路徑分解成多個(gè)只含有一個(gè)謂詞約束的子路徑，對(duì)每個(gè)子路徑，先與DTD樹(shù)進(jìn)行結(jié)構(gòu)匹配，然后對(duì)相應(yīng)的XML文檔進(jìn)行查詢處理。如果在DTD樹(shù)中找不到給定路徑，則可以直接給出“無(wú)查詢結(jié)果”的結(jié)論，無(wú)須查找XML文檔；如果在DTD樹(shù)中找到給定路徑，則能夠確定該路徑的目標(biāo)節(jié)點(diǎn)在DTD中的編碼，根據(jù)該編碼查找XML文檔中節(jié)點(diǎn)的DTD編碼為該編碼的XML節(jié)點(diǎn)。由于DBXI利用了DTD信息，可大大減小搜索空間。對(duì)一個(gè)由N個(gè)元素/屬性組成的具有一個(gè)謂詞約束的路徑表達(dá)式，處理XML文檔需要的結(jié)構(gòu)連接次數(shù)為0或1。但是，DBXI存在以下問(wèn)題：不能處理DTD中帶環(huán)的情況，如〈!ELEMENT manager(name，(manager |department |employee))〉；由于將整個(gè)路徑分成了許多含有一個(gè)謂詞的子路徑，如果DTD中不同路徑存在相同子路徑，則依然會(huì)存在不必要的搜索；不同子路徑之間需要進(jìn)行連接運(yùn)算，在約束謂詞較多的情況下連接操作的次數(shù)會(huì)很多。

以上方法均利用DTD減小搜索空間，但這些方法中依然存在不必要的連接操作，而且這些方法都沒(méi)考慮DTD中帶環(huán)的情況，該種情況普遍存在。本文重點(diǎn)是利用XML模式進(jìn)一步減小搜索空間并研究XML模式中帶有環(huán)的復(fù)雜情況。

2本文方法

本文算法的基本思想：將XML模式和XML文檔分別映射為模式樹(shù)和文檔樹(shù)；元素/屬性映射為樹(shù)的節(jié)點(diǎn)；元素/元素或元素/屬性之間的包含關(guān)系或擁有關(guān)系映射為樹(shù)的邊。對(duì)于XML模式中帶環(huán)的節(jié)點(diǎn)(本文不考慮XML模式中存在間接遞歸的情況)進(jìn)行去除環(huán)的處理，使之成為樹(shù)結(jié)構(gòu)。建立XML文檔樹(shù)中的節(jié)點(diǎn)與XML模式樹(shù)中節(jié)點(diǎn)的對(duì)應(yīng)關(guān)系。查詢時(shí)，對(duì)于XML模式中帶環(huán)的情況先對(duì)查詢表達(dá)式進(jìn)行預(yù)處理并將其分解成主路徑和分支路徑；然后用分解后的路徑查找XML模式樹(shù)。如果找不到滿足條件的模式，則無(wú)查詢結(jié)果，否則利用模式樹(shù)中的查詢結(jié)果在文檔樹(shù)中進(jìn)行查找，得到最終的查詢結(jié)果。

通過(guò)對(duì)帶環(huán)的XML模式結(jié)構(gòu)進(jìn)行分析發(fā)現(xiàn)，XML模式結(jié)構(gòu)中的元素分為三類。為方便問(wèn)題的討論，先給出這些元素的定義。

2．1XML模式處理

1）XML模式樹(shù)編碼方案

為了惟一標(biāo)志XML模式樹(shù)中的每一個(gè)節(jié)點(diǎn)，采用樹(shù)的前序遍歷方法來(lái)對(duì)模式樹(shù)中的節(jié)點(diǎn)進(jìn)行編碼。該編碼就是樹(shù)中節(jié)點(diǎn)的惟一編碼。由于對(duì)不同類型的節(jié)點(diǎn)要進(jìn)行不同的處理，需要在節(jié)點(diǎn)編碼中對(duì)不同的節(jié)點(diǎn)加以標(biāo)志。XML模式樹(shù)中的節(jié)點(diǎn)編碼方案為（preorder， type， no， effectNode）。其中：preorder是節(jié)點(diǎn)在模式樹(shù)中的前序遍歷值，它能惟一標(biāo)志樹(shù)中的每一個(gè)節(jié)點(diǎn)；type是節(jié)點(diǎn)類型（取值為n表示不穩(wěn)定節(jié)點(diǎn)；h表示半穩(wěn)定節(jié)點(diǎn)；s表示穩(wěn)定節(jié)點(diǎn)）；因?yàn)橐獙?duì)查詢中的不穩(wěn)定節(jié)點(diǎn)進(jìn)行特殊處理，需要為模式樹(shù)中的不穩(wěn)定節(jié)點(diǎn)重新編號(hào)，no表示不穩(wěn)定節(jié)點(diǎn)的編號(hào)，編號(hào)方法是按照其前序遍歷值由小到大的順序進(jìn)行，穩(wěn)定節(jié)點(diǎn)和半穩(wěn)定節(jié)點(diǎn)的no為空；effectNode是不穩(wěn)定節(jié)點(diǎn)和半穩(wěn)定節(jié)點(diǎn)中影響節(jié)點(diǎn)穩(wěn)定性的節(jié)點(diǎn)集合。例如，圖1中節(jié)點(diǎn)的編碼如表2所示。

2）XML模式索引結(jié)構(gòu)對(duì)XML模式樹(shù)建立兩個(gè)索引：父子關(guān)系索引和祖先/后代關(guān)系索引。父子關(guān)系索引是非葉節(jié)點(diǎn)的子節(jié)點(diǎn)索引；祖先/后代關(guān)系索引是非葉節(jié)點(diǎn)的后代節(jié)點(diǎn)索引。圖1所示的模式樹(shù)對(duì)應(yīng)的索引如圖2所示。

圖2XML模式索引

2．2查詢預(yù)處理

XML查詢均是以路徑表達(dá)式的形式給出，要用給定的路徑表達(dá)式查詢XML文檔，需要先對(duì)給定的查詢表達(dá)式進(jìn)行預(yù)處理。處理算法基本思想如下：

3實(shí)驗(yàn)

為了測(cè)試算法性能，進(jìn)行了實(shí)驗(yàn)研究。實(shí)驗(yàn)的硬件環(huán)境為Pentium 43.2 GHz CPU， 768 MB RAM和80 GB 硬盤(pán)；操作系統(tǒng)為Windows 2000 server，算法采用Java實(shí)現(xiàn)。

為了對(duì)算法的整體性能進(jìn)行評(píng)價(jià)，分別用不帶環(huán)的XML模式和帶環(huán)的XML模式進(jìn)行實(shí)驗(yàn)，并進(jìn)行算法的可擴(kuò)展性實(shí)驗(yàn)。

1）不帶環(huán)的XML模式實(shí)驗(yàn)

從實(shí)驗(yàn)結(jié)果可以看出，總體上，本文算法性能要優(yōu)于4Relation算法；另外，4Relation算法Q4的查詢結(jié)果不正確，把PLAY下的PERSONA元素作為查詢結(jié)果顯示出來(lái)，這與前面的分析是吻合的。

2）帶環(huán)的XML模式實(shí)驗(yàn)

采用人工生成的數(shù)據(jù)集，其模式結(jié)構(gòu)示意圖如例1所示。相應(yīng)地，XML文檔用TOXgene[21]生成，文檔大小為80 MB，模式大小為3 KB。因?yàn)槲墨I(xiàn)[17]中的算法不能處理模式中有環(huán)的情況，將本文算法與文獻(xiàn)[16]中的mergeNodeInfo算法進(jìn)行比較。因?yàn)槲墨I(xiàn)[16]已經(jīng)證明mergeNodeInfo算法的性能要優(yōu)于NodeInfo算法的性能，所以就不比較本文算法與NodeInfo算法的性能。查詢用例如表4所示。圖6給出了兩種算法的查詢時(shí)間。圖中時(shí)間數(shù)據(jù)取五次運(yùn)行的平均值。從圖6可以看出，本文算法的查詢時(shí)間要遠(yuǎn)遠(yuǎn)小于mergeNodeInfo算法。

3）可擴(kuò)展性實(shí)驗(yàn)

為了測(cè)試算法的可擴(kuò)展性，對(duì)模式帶有環(huán)的情況進(jìn)行了算法的可擴(kuò)展性實(shí)驗(yàn)。實(shí)驗(yàn)數(shù)據(jù)大小分別為80、100、120、140、160 MB，查詢用例為表4中的Q2。圖7給出了不同規(guī)模的文檔查詢時(shí)間。從圖7可以看出，本文算法對(duì)不同大小文檔的查詢時(shí)間基本呈線性增長(zhǎng)，而且增長(zhǎng)速度比較平穩(wěn)，因此可擴(kuò)展性較好。

4結(jié)束語(yǔ)

本文闡述了基于復(fù)雜模式索引的XML查詢優(yōu)化方法。該方法利用模式索引進(jìn)行XML查詢優(yōu)化，可處理XML模式中帶環(huán)的復(fù)雜情況，通過(guò)XML模式建立父子關(guān)系索引和祖先/后代關(guān)系索引。查詢時(shí)先對(duì)查詢樹(shù)進(jìn)行去環(huán)預(yù)處理，對(duì)有約束謂詞的查詢分解出查詢樹(shù)的主干和分支；然后利用索引查找潛在目標(biāo)節(jié)點(diǎn)在XML模式樹(shù)中的編號(hào)；最后對(duì)文檔中對(duì)應(yīng)節(jié)點(diǎn)進(jìn)行篩選，從中找到符合條件的目標(biāo)節(jié)點(diǎn)集。該方法能處理絕大多數(shù)XML文檔，避免了大量的連接操作，因此，具有較高的效率。實(shí)驗(yàn)結(jié)果表明，該方法具有較好的性能。

但是本文沒(méi)有考慮模式定義中存在回路的情況（即存在間接遞歸定義的情況），因此不能處理所有的XML文檔查詢。下一步的工作將研究模式中帶有回路的XML查詢。

參考文獻(xiàn)：

[1]BRAY T， PAOLI J， SPERBERGMcQUEEN C M，ed al. eXtensible markup language (XML) 1.0:3rd ed[EB/OL]. (2004－02－04)[2006－06－05].http://www.w3.org/TR/2004/RECxml.

[2]BERGLUND A， BOAG S， CHAMBERLIN D. XML path language (XPath) 2.0[EB/OL]. (2005－04－04)[2006－06－08].http:// www.w3.org/TR/2005/WDxpath20.

[3]BOAG S， CHAMBERLIND， FERNNDE M F. XQuery 1.0: an XML query language[EB/OL]. (2005－04－04)[2006－06－08].http://www.w3.org/TR/2005/WDxquery/.

[4]DEUTSCH A， FERNANDEZM， FLORESCU D， XMLQL: a query language for XML[EB/OL].http://www.w3.org/TR/NOTExmlql.

[5]McHUGH J， WIDOM J. Query optimization for XML[C]//Proc of the 25th VLDB Conference. Edinburgh:[s.n.]， 1999:315－326.

[6]ALKHALIFA S， JAGADISH H V， KOUDAS N， et al. Structural joins: a primitive for efficient XML query pattern matching[C]//Proc of ICDE’2002.141152.

[7]JIANG Haifeng， LU Hongjun， WANG Wei， et al. XRTree: indexing XML data for efficient structural joins[C]//Proc of ICDE2003.Bangalore:IEEE Computer Society，2003:253－264.

[8]王靜， 孟小峰， 王珊. 基于區(qū)域劃分的XML結(jié)構(gòu)連接[J]. 軟件學(xué)報(bào)， 2004，15(5):720－729.

[9]CHIEN S Y， VAGENA Z， ZHANG Donghui，et al. Efficient structural joins on indexed XML documents[C]//Proc of VLDB2002. San Francisco:Morgan Kaufmann，2002:263－274.

[10]LI Quanzhong， MOON B.Indexing and querying XML data for regular path expressions[C]//Proc of VLDB2001. San Francisco:Morgan Kaufmann，2001:361－370.

[11]WANG Wei， JIANG Haifeng， LU Hongjun， et al. PbiTree coding and efficient processing of containment joins[C]//Proc of ICDE2003. Los Alamitos:IEEE Press，2003:391－402.

[12]ZHANG C， NAUGHTON J， DeWITT D， et al. On supporting containment queries in relational database management systems[C]//Proc of the 2001 ACM SIGMOD Int’l Conf on Management of Data. New York : ACM Press ， 2001:1425－1436.

[13]萬(wàn)常選， 劉云生， 徐升華，等. 基于區(qū)間編碼的XML索引結(jié)構(gòu)的有效結(jié)構(gòu)連接[J]. 計(jì)算機(jī)學(xué)報(bào)， 2005，28（1）：113－127.

[14]GOLDMAN R， WIDOM J. DataGuides: enabling query formulation and optimization in semistructure databases[C]//Proc of the 23rd VLDB Conference. Athens， Greece:[s.n.]，1997.

[15]THOMPSON H S， BEECH D， MALONEY M. XML schema part 1: structures:2nd ed [EB/OL].(200410－28)[2006－06－05].http://www.w3.org/TR/2004/RECxmlschema1.

[16]CHUNG T S， KIM H J. Extracting indexing information from XML DTDs[J]. Information Processing Letters， 2002，81(2):97103.

[17]SEO C Y， LEE S W， KIM H J. An efficient inverted technique for XML documents using RDBMS[J]. Information and Software Technology， 2003，45(1):11－22.

[18]路燕，張亮，段起陽(yáng)，等. 一種基于DTD的XML索引方法[J]. 計(jì)算機(jī)研究與發(fā)展， 2005，42(1)：30－37.

[19]DIETZ P F. Maintaining order in a linked list[C]//Proc of the 14th Annual ACM Symp on Theory of Computing. New York: ACM Press， 1982：122－127.

[20]SCHLIEDER T. ApproXQL: design and implementation of an appro￣ximate pattern matching language for XML，B01－02[D].Berlin: Freie University，2001.

[21]BARBOSA D，MENDELZON A， KEENLEYSIDE J. ToXgene:the ToX XML data generator[EB/OL]. http://www.cs.toronto.edu/tox/toxgene.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”