XML結(jié)構(gòu)連接算法研究.pdf

1、本論文目的是對(duì)XML結(jié)構(gòu)連接算法進(jìn)行研究，分析它們的時(shí)間和空間效率。主要的算法包括傳統(tǒng)的遍歷樹(shù)算法、樹(shù)合并算法、隊(duì)列樹(shù)算法、棧樹(shù)算法，所有這些算法都分為按祖先有序和按后裔有序，其中的隊(duì)列樹(shù)算法在本論文中首次提出。在論文的最后還實(shí)現(xiàn)了文獻(xiàn)[33]所提出的單枝查詢算法，并將該算法與先生成基本二元結(jié)構(gòu)關(guān)系，再將其拼接形成的單枝查詢算法進(jìn)行了比較。最后我們還對(duì)在數(shù)據(jù)庫(kù)中引入索引和未引入索引時(shí)讀數(shù)據(jù)庫(kù)所用的時(shí)間進(jìn)行了比較。 以上所有這些算

2、法我們均編程實(shí)現(xiàn)，實(shí)現(xiàn)程序所用的語(yǔ)言是Java，操作系統(tǒng)平臺(tái)為Windows2000Server，數(shù)據(jù)庫(kù)系統(tǒng)為SQL_Server2000。除了在本論文的“引入索引”部分主要研究讀數(shù)據(jù)庫(kù)所用時(shí)間外，其它部分在算法實(shí)現(xiàn)中都略去了讀取數(shù)據(jù)所用的時(shí)間。程序中我們采取的策略是將我們需要的數(shù)據(jù)一次性的從數(shù)據(jù)庫(kù)中讀出，或是放在鏈表中，或是先放在靜態(tài)數(shù)組中，然后通過(guò)指針的移動(dòng)在需要時(shí)讀入鏈表，這樣可以減少因讀數(shù)據(jù)庫(kù)造成的系統(tǒng)誤差對(duì)研究結(jié)果所造成的影響

3、。另外，我們事先并不知道程序一次所處理的數(shù)據(jù)量有多大，故采用動(dòng)態(tài)鏈表方式讓鏈表動(dòng)態(tài)延長(zhǎng)。在用Java語(yǔ)言實(shí)現(xiàn)的算法中，我們定義了一個(gè)類，每一個(gè)結(jié)點(diǎn)是該類的一個(gè)實(shí)例，每當(dāng)需要新增一個(gè)結(jié)點(diǎn)時(shí)，只需進(jìn)行一次類的實(shí)例化，然后將其鏈上鏈表即可。 XML查詢是一種基于樹(shù)結(jié)構(gòu)的查詢，樹(shù)結(jié)構(gòu)有雙親-孩子和祖先-后裔等結(jié)構(gòu)關(guān)系，在一個(gè)XML數(shù)據(jù)庫(kù)中發(fā)現(xiàn)所有滿足這種結(jié)構(gòu)關(guān)系的結(jié)點(diǎn)對(duì)是對(duì)XML查詢的核心操作，它被稱為結(jié)構(gòu)查詢或結(jié)構(gòu)連接。但如何判斷兩結(jié)

4、點(diǎn)存在雙親-孩子或祖先-后裔結(jié)構(gòu)關(guān)系呢(以后將其統(tǒng)稱為祖先-后裔結(jié)構(gòu)關(guān)系)?既然XML文檔可以表示為一棵倒掛的樹(shù)，我們就可以利用數(shù)據(jù)結(jié)構(gòu)中樹(shù)的知識(shí)對(duì)祖先-后裔結(jié)構(gòu)關(guān)系進(jìn)行查詢，對(duì)該樹(shù)進(jìn)行先根遍歷就可以得到按祖先或按后裔有序的祖先-后裔結(jié)點(diǎn)對(duì)。然而在數(shù)據(jù)結(jié)構(gòu)中對(duì)樹(shù)的遍歷采用的是遞歸調(diào)用，遞歸調(diào)用會(huì)導(dǎo)致壓棧，這是一種即耗時(shí)間又耗空間的處理方式。從另外一個(gè)角度來(lái)考慮，XML文檔是由標(biāo)記和數(shù)據(jù)組成的，文檔中被標(biāo)記包圍的內(nèi)容就是數(shù)據(jù)，標(biāo)記和數(shù)據(jù)之

5、間存在一種包含關(guān)系，并且這種包含關(guān)系不會(huì)交叉。文獻(xiàn)[30]中ChunZhang等提出了一種機(jī)制，這種機(jī)制先給每個(gè)結(jié)點(diǎn)編號(hào)，然后通過(guò)比較任意兩個(gè)結(jié)點(diǎn)的編號(hào)是否存在包括關(guān)系，就可以判斷它們是否存在祖先-后裔關(guān)系。其中產(chǎn)生編號(hào)的具體作法如下：假定一個(gè)XML文檔己被解析成了一棵樹(shù)，對(duì)該樹(shù)進(jìn)行深度優(yōu)先搜索遍歷，在遍歷過(guò)程中順序地給每一次訪問(wèn)的結(jié)點(diǎn)賦值，因?yàn)榉侨~結(jié)點(diǎn)總是被遍歷兩次，一次是通過(guò)它訪問(wèn)它的孩子，一次是從孩子結(jié)點(diǎn)返回，所以它被賦了兩次值，

6、而葉結(jié)點(diǎn)只有一個(gè)值。所謂包含有點(diǎn)像在數(shù)據(jù)軸上的范圍包含，比如兩結(jié)點(diǎn)編號(hào)分別為(StartPos1，EndPos1)，(StartPos2，EndPos2)，如果StartPos1＜StartPos2且EndPos2＜EndPos1，則第一個(gè)結(jié)點(diǎn)包含第二個(gè)結(jié)點(diǎn)，以后我們會(huì)看到只需判斷條件StartPos1＜StartPos2＜EndPos1即可。 我們對(duì)本論文提出的所有算法都編程實(shí)現(xiàn)，并且每個(gè)程序都重復(fù)執(zhí)行十多次，最終我們得到每個(gè)

7、算法的平均執(zhí)行時(shí)間。我們發(fā)現(xiàn)在基本的二元結(jié)構(gòu)查詢算法中，無(wú)論按祖先有序還是按后裔有序，傳統(tǒng)的遍歷樹(shù)算法執(zhí)行的時(shí)間最長(zhǎng)，因此我們沒(méi)有對(duì)其作進(jìn)一步的研究。在按后裔有序的算法中，棧樹(shù)后裔算法的確如文獻(xiàn)[31]所述，執(zhí)行時(shí)間最短，其次是隊(duì)列樹(shù)后裔算法，樹(shù)合并后裔算法用時(shí)最多。然而在按祖先有序的算法中，棧樹(shù)祖先算法并不像文獻(xiàn)[31]所述的那么好，在某些情況下，其執(zhí)行時(shí)間遠(yuǎn)遠(yuǎn)多于其它兩種祖先有序算法的執(zhí)行時(shí)間，而樹(shù)合并祖先算法和隊(duì)列樹(shù)祖先算法執(zhí)行時(shí)

8、間總體相當(dāng)。在對(duì)由樹(shù)合并算法、隊(duì)列樹(shù)算法、棧樹(shù)算法形成的各自單枝查詢算法的研究中，我們發(fā)現(xiàn)其執(zhí)行時(shí)間的對(duì)比情況與其在對(duì)應(yīng)的基本二元結(jié)構(gòu)查詢算法中的情況基本相同。我們還在引入索引和不引入索引的情況下對(duì)數(shù)據(jù)庫(kù)進(jìn)行了讀取操作，發(fā)現(xiàn)引入索引后讀取數(shù)據(jù)的時(shí)間會(huì)更短。在論文最后，我們實(shí)現(xiàn)了文獻(xiàn)[33]提出的單枝查詢PathStack算法，其最終結(jié)果按后裔有序，執(zhí)行時(shí)間比前述最快的后裔有序單枝查詢算法快上了接近一個(gè)數(shù)量級(jí)的時(shí)間。 最終我們認(rèn)為

9、：在基本的二元結(jié)構(gòu)查詢算法中，文獻(xiàn)[31]所提出的按后裔有序的棧樹(shù)算法在時(shí)間和空間上的確優(yōu)于按后裔有序的樹(shù)合并算法和隊(duì)列樹(shù)算法，所以如果要生成按后裔有序的結(jié)點(diǎn)對(duì)時(shí)，最好采用棧樹(shù)后裔算法。但如果要生成按祖先有序的結(jié)點(diǎn)對(duì)，則最好采用隊(duì)列樹(shù)祖先算法，因?yàn)閷r(shí)間和空間這兩個(gè)因素綜合起來(lái)考慮，隊(duì)列樹(shù)祖先算法是最好的。在單枝查詢算法中，文獻(xiàn)[33]提出的PathStack單枝算法在后裔有序的單枝算法中是最好的，但在祖先有序的單枝算法則最好采用由隊(duì)列