XML路徑表達(dá)式的查詢優(yōu)化技術(shù)

摘要：XML查詢語(yǔ)言的共同特點(diǎn)是利用路徑表達(dá)式來(lái)導(dǎo)航XML文檔的查詢并返回指定路徑所能訪問(wèn)到的節(jié)點(diǎn)集，因此路徑表達(dá)式的查詢優(yōu)化是XML數(shù)據(jù)庫(kù)查詢優(yōu)化的關(guān)鍵，本文詳細(xì)分析了當(dāng)前路徑表達(dá)式查詢的幾種優(yōu)化技術(shù)，指出了它們要解決的關(guān)鍵問(wèn)題和主要技術(shù)特點(diǎn)。

中圖分類號(hào)：TP311.1 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1000-8136(2009)23-0015-03

1 基本概念

1.1 XML數(shù)據(jù)模型和XML數(shù)據(jù)模式

一個(gè)XML文檔樹(shù)是一個(gè)有序標(biāo)簽樹(shù)(如果考慮元素之間的應(yīng)用關(guān)系則以XML文檔的基本結(jié)構(gòu)為圖)，每個(gè)節(jié)點(diǎn)與一個(gè)元素或值(文本)相對(duì)應(yīng)，邊表示元素和子元素(或值)之間的嵌套關(guān)系。XML文檔的數(shù)據(jù)模式是一個(gè)有向圖，它為XML數(shù)據(jù)提供完整性約束。

1.2 XML數(shù)據(jù)的編碼方法

到目前為止處理路徑表達(dá)式查詢有兩種方法：一種是基于樹(shù)遍歷的方法，另一種不遍歷文檔樹(shù)就可以快速?zèng)Q定節(jié)點(diǎn)之間結(jié)構(gòu)關(guān)系的方法，元素之間結(jié)構(gòu)關(guān)系的確定主要依賴于有效的XML節(jié)點(diǎn)編碼方法。

1.2.1 基于區(qū)域的編碼方案

目前，最常用的編碼方法是區(qū)域編碼方法，最先使用區(qū)域編碼確定樹(shù)節(jié)點(diǎn)之間的結(jié)構(gòu)關(guān)系的是Dietz。它給每個(gè)節(jié)點(diǎn)賦予一個(gè)(pre，post)編碼，其中，pre是節(jié)點(diǎn)的前序遍歷值，post是節(jié)點(diǎn)的后序遍歷值，對(duì)于任意兩個(gè)不同的節(jié)點(diǎn)x和y，x是y的一個(gè)祖先當(dāng)且僅當(dāng)x.pre

文獻(xiàn)。給每個(gè)節(jié)點(diǎn)賦予一個(gè)(start，end)編碼，一個(gè)節(jié)點(diǎn)的start和end值是該元素的開(kāi)始和結(jié)尾的絕對(duì)物理或邏輯位移，如果一個(gè)節(jié)點(diǎn)的編碼所覆蓋的區(qū)域被另一個(gè)節(jié)點(diǎn)的編碼所覆蓋的區(qū)域完全包含，則這個(gè)節(jié)點(diǎn)是另一個(gè)節(jié)點(diǎn)的后代節(jié)點(diǎn)。……