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

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

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

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

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