XML Twig查詢優(yōu)化研究.pdf

1、XML因其具有自描述性，可擴展性以及開放性等優(yōu)點已經(jīng)成為網(wǎng)絡(luò)上信息表達(dá)和數(shù)據(jù)交換的事實標(biāo)準(zhǔn)。隨著XML數(shù)據(jù)的不斷增長，尤其是大規(guī)模XML數(shù)據(jù)的出現(xiàn)(如XML數(shù)據(jù)庫)，對XML數(shù)據(jù)的查詢正在成為學(xué)術(shù)界和工業(yè)界的研究熱點。但同時由于XML文檔具有的半結(jié)構(gòu)的特性，使得傳統(tǒng)的對關(guān)系數(shù)據(jù)庫的查詢算法對其不適用，因此如何高效地查詢XML數(shù)據(jù)成為新的研究課題。 為了實現(xiàn)XML的查詢優(yōu)化，近年來人們提出了各種算法，主要有基于路徑索引的樹遍歷、基

2、于序列的方法以及結(jié)構(gòu)連接和整體twig查詢，其中整體twig查詢可以避免結(jié)構(gòu)連接產(chǎn)生大量的中間結(jié)果而具有很大的優(yōu)越性，得到了廣泛的研究。 本文對整體twig查詢優(yōu)化展開研究，主要做了以下幾個方面的工作： (1)提出了DBL排序算法，用于決定葉子查詢結(jié)點的處理順序，更重要的是在構(gòu)造與查詢結(jié)點相關(guān)聯(lián)的列表中起到過濾對查詢結(jié)果沒有貢獻的元素的作用。 (2)提出了一種新型的整體twig查詢算法TWigStackFast，

3、它是個單階段算法，采用Extended Dewey編碼，能夠處理帶A-D關(guān)系、P-C關(guān)系的查詢，而且是CPU和I/O最優(yōu)的。IWigStackFast算法沒有第二階段的合并連接操作，因而可以消除了大量的時間和空間開銷。 (3)通過把TwigStackFast算法與四個經(jīng)典的twig查詢算法TwigStack、HolisticTwigStack、Twig2Stack、TJFast進行實驗對比后可以看出，TwigStackFast具