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

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

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

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

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

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

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

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

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

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