用DTD優(yōu)化XML遞歸查詢技術(shù).pdf

1、XML已經(jīng)成為現(xiàn)今因特網(wǎng)中儲存和交換信息的標(biāo)準(zhǔn)語言。XML允許你使用任何虛擬型態(tài)的信息，從簡單的單個數(shù)據(jù)到復(fù)雜的數(shù)據(jù)如多媒體數(shù)據(jù)，都可以由XML存儲。隨著XML作為一種存儲數(shù)據(jù)的格式不斷成熟，用于從非結(jié)構(gòu)化格式(如XML文檔)檢索信息的類SQL語言的重要性也就越大。XMLQuery響應(yīng)了這一需求。XMLXQuery(也稱作XQuery)允許開發(fā)人員編寫抽取數(shù)據(jù)以及將結(jié)果結(jié)構(gòu)化成XML的語句。通過XQuery，可以從一個或多個XML文檔選

2、擇非常準(zhǔn)確的數(shù)據(jù)集，并輸出XML結(jié)構(gòu)作為響應(yīng)。 XML具有高度靈活的數(shù)據(jù)結(jié)構(gòu)，使得優(yōu)化基于它的數(shù)據(jù)查詢非常困難，所以現(xiàn)在對這方面的研究非常多。同樣它也很難優(yōu)化基于XML數(shù)據(jù)的各種各樣的遞歸查詢，本文中主要就是定位于優(yōu)化結(jié)構(gòu)化遞歸查詢。XMLQuery遞歸查詢是基于XML結(jié)構(gòu)化數(shù)據(jù)的一個重要查詢分類，因它的遞歸查詢表達(dá)式中包含有多種形式的遞歸調(diào)用，所以XQUERY引擎很難給遞歸查詢表達(dá)式進(jìn)行優(yōu)化。 我們利用文檔類型定義DT

3、D(DocumentTypeDefinitions)信息，通過掃描文檔類型樹，把原有的遞歸查詢表達(dá)式轉(zhuǎn)換為路徑查詢表達(dá)式，從而裁剪與結(jié)果表達(dá)式無關(guān)的分支，避免XQuery引擎對所有節(jié)點進(jìn)行掃描的做法。我們開發(fā)了一種深度掃描路徑生成算法，這個算法可以根據(jù)掃描文檔定義樹(DTD)，生成一個或多個的路徑表達(dá)式，把遞歸查詢轉(zhuǎn)化為路徑查詢，在查詢時即可省去大量的對文檔樹所做的無用的遍歷。我們還設(shè)計了查找目標(biāo)元素的路徑和查找隊列的存儲結(jié)構(gòu)，使其在查

4、找時分層進(jìn)行比較，充分利用了DTD樹和XML文檔樹相似性。同時也設(shè)計了在已知一條或多條路徑的前提下，采用分支限界的思想，搜索目標(biāo)節(jié)點的算法。 平均來說，文檔樹的結(jié)點數(shù)與DTD樹的結(jié)點數(shù)的比越大，我們方法的效率越高，并且我們對路徑的存儲方法，在我們遍歷文檔樹時，不用將當(dāng)前結(jié)點與整個路徑中的所有結(jié)點相比，而只需我們在路徑集合中直接找到某條具體路徑的具體某個結(jié)點，去與之相比即可，這樣，又會節(jié)約大量的時間，且同時又將掃描的每條路徑的可能