XML查詢處理結(jié)構(gòu)中的一種邏輯優(yōu)化算法.pdf

1、隨著XML在信息管理、電子商務(wù)、個性化出版、移動通信、網(wǎng)絡(luò)教育、電子文檔交換等諸多領(lǐng)域中的廣泛的應(yīng)用，它已經(jīng)開始成為數(shù)據(jù)描述和交換的事實上的標(biāo)準(zhǔn)，越來越多的數(shù)據(jù)開始采用XML進(jìn)行描述、存儲、交換和表示。然而由于XML數(shù)據(jù)的半結(jié)構(gòu)化特性以及XML數(shù)據(jù)所特有的路徑表達(dá)的查詢方式不同于現(xiàn)有的關(guān)系數(shù)據(jù)庫查詢，使得利用關(guān)系數(shù)據(jù)庫系統(tǒng)對XML數(shù)據(jù)的管理功能受到極大限制。現(xiàn)在互聯(lián)網(wǎng)上已經(jīng)存在大量以文件形式存放的XML數(shù)據(jù)，這種方法雖然簡單、實用，但是

2、查詢能力低，不能滿足復(fù)雜條件的查詢，更談不上查詢優(yōu)化。因此，如何高效準(zhǔn)確地完成對XML數(shù)據(jù)的查詢還存在著許多尚未解決的問題。 查詢優(yōu)化是數(shù)據(jù)庫技術(shù)中重要的研究問題，是實現(xiàn)高效查詢的關(guān)鍵性因素。查詢語言首先被轉(zhuǎn)換成為一種內(nèi)部表達(dá)形式(通常是某種代數(shù)，如關(guān)系代數(shù)、XML代數(shù)等)。根據(jù)變換規(guī)則得到等價表達(dá)式，計算不同形式的表達(dá)式的執(zhí)行代價，然后選擇一個代價最小的執(zhí)行方案，這就是查詢處理過程。對查詢處理過程的研究是實現(xiàn)查詢優(yōu)化的關(guān)鍵，而

3、查詢處理過程中最重要的是邏輯優(yōu)化階段。因此，本文針對XML查詢處理結(jié)構(gòu)的邏輯優(yōu)化階段，研究了這一階段相應(yīng)的策略與算法。 本文介紹了XML查詢的查詢處理結(jié)構(gòu)，分析了邏輯優(yōu)化的常規(guī)策略，重點研究了如何針對路徑表達(dá)式進(jìn)行優(yōu)化。路徑表達(dá)式是XML數(shù)據(jù)查詢語言的核心部分，但是目前針對路徑表達(dá)式本身進(jìn)行優(yōu)化的研究卻相對較少。本文通過對相關(guān)定理的推理，得出了一種邏輯優(yōu)化的新策略，即路徑縮短優(yōu)化策略，給出了算法的實現(xiàn)。同時用一般的外延連接算法和

4、這種路徑縮短算法進(jìn)行比較，最后用相應(yīng)的評測基準(zhǔn)測試了該算法。 本文研究的重點主要包括以下幾個方面： (1)研究了XML的查詢處理結(jié)構(gòu)，特別是邏輯優(yōu)化階段路徑表達(dá)式的查詢與分解的方法。 (2)相關(guān)定理的推理和一種新的邏輯優(yōu)化算法的提出。 (3)對評測標(biāo)準(zhǔn)的介紹，并且用這些標(biāo)準(zhǔn)來測試路徑縮短算法，最后對測試結(jié)果進(jìn)行了評價。 實驗的結(jié)果表明，路徑縮短算法相對外延連接算法不僅提高了XML的查詢效率而且具有