xml數(shù)據(jù)查詢優(yōu)化技術(shù)綜述

xml數(shù)據(jù)查詢優(yōu)化技術(shù)綜述

xml已成為網(wǎng)絡(luò)信息描述和信息交換的參考。xml數(shù)據(jù)在文檔模式下存儲，并通過數(shù)據(jù)搜索進(jìn)行檢索，這非常簡單。由于缺乏系統(tǒng)的存儲和檢索機(jī)制，搜索能力低，無法滿足復(fù)雜條件下的搜索，不用說，搜索優(yōu)化。一些現(xiàn)有的商業(yè)信息系統(tǒng)擴(kuò)展了處理xml數(shù)據(jù)的功能，并使用現(xiàn)有的數(shù)據(jù)庫成熟度技術(shù)將xml搜索需求轉(zhuǎn)換為數(shù)據(jù)庫搜索表達(dá)，這需要由搜索優(yōu)化器優(yōu)化搜索表達(dá)并執(zhí)行，然后將搜索結(jié)果轉(zhuǎn)換為xml數(shù)據(jù)。該方法在一定程度上解決了搜索復(fù)雜性的要求，但多級轉(zhuǎn)換的問題是效率低下，對搜索意義的混淆。與傳統(tǒng)的數(shù)據(jù)庫數(shù)據(jù)相比,XML數(shù)據(jù)具有如下特點:·數(shù)據(jù)是自描述的,內(nèi)容與結(jié)構(gòu)混雜在一起;·數(shù)據(jù)具有完整的嵌套層次;·數(shù)據(jù)是有序的.XML數(shù)據(jù)的不規(guī)則性是對傳統(tǒng)統(tǒng)計信息方法的重要挑戰(zhàn),其數(shù)據(jù)分布情況使得一些傳統(tǒng)的分布假設(shè)難以成立.為了達(dá)到所需的代價估計精度,需要更多的統(tǒng)計信息.而結(jié)構(gòu)的復(fù)雜性又為獲得相對精確的統(tǒng)計信息帶來存儲和計算上的困難.XML的有序性制約了轉(zhuǎn)換規(guī)則的靈活性.XML數(shù)據(jù)的上述問題無論是對關(guān)系數(shù)據(jù)庫或是對面向?qū)ο髷?shù)據(jù)庫的現(xiàn)有查詢優(yōu)化技術(shù)都是嚴(yán)峻的挑戰(zhàn).與傳統(tǒng)的查詢需求相比,XML查詢具有如下特點:·以長路徑表達(dá)式為查詢的核心語句,路徑復(fù)雜,包含分支路徑;·嵌套的查詢表達(dá),查詢表達(dá)式中加入編程語言的嵌套和條件判斷思想;·路徑中包含不確定因素,這在之前的查詢需求中未出現(xiàn)過;·查詢對象和返回結(jié)果類型不確定.面向?qū)ο髷?shù)據(jù)庫已有一些處理復(fù)雜長路徑表達(dá)式的經(jīng)驗,但無法處理XML查詢中的路徑表達(dá)式中的不確定情況;關(guān)系數(shù)據(jù)庫中已有很多處理嵌套查詢的方法,但對摻雜編程語言風(fēng)格的XML查詢語言卻難以適應(yīng).綜上所述,來自數(shù)據(jù)結(jié)構(gòu)和查詢需求兩方面的問題導(dǎo)致基于關(guān)系和面向?qū)ο髷?shù)據(jù)庫的查詢處理和查詢優(yōu)化技術(shù)均不能適應(yīng)XML查詢的需要.目前,對XML查詢優(yōu)化的研究正成為熱點.本文的內(nèi)容就是對XML查詢優(yōu)化技術(shù)現(xiàn)狀的綜合論述,指出了XML查詢優(yōu)化的特點和研究的關(guān)鍵性問題,描述了查詢優(yōu)化技術(shù)各個方面的重要研究成果和有待進(jìn)一步解決的問題.1sql數(shù)據(jù)模型查詢優(yōu)化是數(shù)據(jù)庫技術(shù)中重要的研究問題,是實現(xiàn)高效查詢的關(guān)鍵性因素.對傳統(tǒng)數(shù)據(jù)庫查詢優(yōu)化的研究已經(jīng)形成相對成熟的技術(shù)和方法,其中基于代價的優(yōu)化是主流.查詢語言首先被轉(zhuǎn)換成為一種內(nèi)部表達(dá)形式(通常是某種代數(shù),如關(guān)系代數(shù)等),根據(jù)變換規(guī)則得到等價表達(dá)式,計算不同形式的表達(dá)式的執(zhí)行代價,然后選擇一個最小的執(zhí)行方案.當(dāng)把這種方法用于XML查詢優(yōu)化時,研究者遇到如下問題:(1)完善的查詢代數(shù)標(biāo)準(zhǔn)眾所周知,關(guān)系數(shù)據(jù)庫統(tǒng)治數(shù)據(jù)管理領(lǐng)域長盛不衰的法寶就是描述性查詢語言SQL及其運(yùn)行基礎(chǔ)關(guān)系代數(shù).關(guān)系代數(shù)的目的之一是給出明確的查詢語義,之二是用于支持查詢優(yōu)化.關(guān)系代數(shù)的優(yōu)勢來自于簡單、明確的數(shù)據(jù)模型——關(guān)系,具有完善的數(shù)學(xué)基礎(chǔ)和系統(tǒng)的轉(zhuǎn)換規(guī)則.后來的數(shù)據(jù)模型都以關(guān)系代數(shù)為藍(lán)本,定義了不同的運(yùn)算,如面向?qū)ο髷?shù)據(jù)模型等,但效果并不盡如人意.XML數(shù)據(jù)模型本身具有的半結(jié)構(gòu)化特點是定義完善的代數(shù)運(yùn)算的最大障礙.而XML查詢語言中的不確定性和一些編程思想的引入是另一個難以克服的困難.(2)精確的代價估計關(guān)系模型中,表中的記錄是無序的、大小相等的,代價計算時依據(jù)的一些分布假設(shè)是穩(wěn)定的.而且,由于其記錄大小相等,對時間的估計可以轉(zhuǎn)換為對I/O次數(shù)的估計,進(jìn)而轉(zhuǎn)換為對中間結(jié)果大小的估計.而在XML模型中,數(shù)據(jù)是有序的,數(shù)據(jù)聚集的方式不定,每個數(shù)據(jù)的大小相差懸殊,中間結(jié)果大小與I/O次數(shù)之間的對應(yīng)關(guān)系沒有明顯的規(guī)律.簡單地沿用傳統(tǒng)的代價計算方法必然導(dǎo)致誤差的產(chǎn)生,從而影響精確的代價估計.(3)足夠的統(tǒng)計信息足夠精確的統(tǒng)計信息是保證查詢優(yōu)化有效性的基礎(chǔ);缺乏足夠的統(tǒng)計信息,是造成估計與實際情況產(chǎn)生誤差的重要因素.傳統(tǒng)的統(tǒng)計信息多是對值的統(tǒng)計,如對平均值、最值、記錄個數(shù)等的統(tǒng)計.這些對XML查詢是不夠的.XML數(shù)據(jù)本身缺乏模式的支持,對數(shù)據(jù)結(jié)構(gòu)信息的統(tǒng)計顯得更加重要.XML數(shù)據(jù)中的數(shù)值分布在類似樹狀結(jié)構(gòu)的樹葉上,即使相同類型的數(shù)據(jù),由于半結(jié)構(gòu)化特點,其分布情況也可能完全不同.因此,需要把對結(jié)構(gòu)的統(tǒng)計信息和對值的統(tǒng)計信息結(jié)合到一起,才能得到足夠精確的統(tǒng)計信息.2在關(guān)系數(shù)據(jù)庫系統(tǒng)中的應(yīng)用與傳統(tǒng)的關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理結(jié)構(gòu)類似,我們可以將XML查詢處理分為4個大的階段.如圖1所示中間方框表示查詢處理步驟;左側(cè)方框為使用的相關(guān)技術(shù)或方法;右側(cè)方框為查詢優(yōu)化和執(zhí)行時需要的信息.第1階段查詢解析,將查詢轉(zhuǎn)換為某種內(nèi)部表達(dá)方式,以便于機(jī)器處理,并為下一步的優(yōu)化過程鋪平道路.這種內(nèi)部表達(dá)方式通常以一種抽象語法樹或者查詢樹的形式出現(xiàn).以傳統(tǒng)數(shù)據(jù)庫為基礎(chǔ)的查詢引擎的做法是轉(zhuǎn)換成關(guān)系代數(shù),然后由關(guān)系數(shù)據(jù)庫優(yōu)化器完成剩下的優(yōu)化工作.而Native的數(shù)據(jù)庫系統(tǒng)則采用不同的XML代數(shù)系統(tǒng).我們在第3節(jié)中將會介紹目前流行的幾種XML代數(shù).第2階段邏輯優(yōu)化,利用模式信息,規(guī)范和簡化內(nèi)部表達(dá)式.在這一階段中,系統(tǒng)不考慮實際數(shù)據(jù)的值和數(shù)據(jù)的存儲情況.同一查詢請求,可以轉(zhuǎn)換成不同的等價表達(dá)方式,其中有一些比原有查詢更高效.為了進(jìn)行這種轉(zhuǎn)換,優(yōu)化器需要一些轉(zhuǎn)換規(guī)則,我們將在第4節(jié)中討論這些轉(zhuǎn)換規(guī)則.第3階段物理優(yōu)化,利用代價模型和統(tǒng)計信息計算不同表達(dá)式、不同算法的執(zhí)行代價,選擇最低代價的查詢計劃.在這一階段中,需要解決兩個問題:確定表達(dá)式執(zhí)行順序和決定每步操作的具體算法.對于XML查詢樹而言,首先需要將查詢表達(dá)式分解為可執(zhí)行的片斷,然后選擇合適的執(zhí)行順序和執(zhí)行算法并執(zhí)行.中間結(jié)果集的大小是決定執(zhí)行策略是否高效的關(guān)鍵因素,與實際的數(shù)據(jù)分布密切相關(guān).綜合考慮數(shù)據(jù)的存儲、索引和數(shù)據(jù)值的分布情況,準(zhǔn)確地估計復(fù)雜路徑選擇性是其中的難點.對于一個給定的執(zhí)行策略,通常會有多個可能的執(zhí)行算法,產(chǎn)生所有的執(zhí)行算法的組合造成選擇本身的代價過大.因此,會有一些啟發(fā)式規(guī)則用來控制其空間規(guī)模,并采用一些空間搜索技術(shù)加速選擇的過程.我們將在第5節(jié)中詳細(xì)加以討論.第4階段查詢執(zhí)行,根據(jù)物理優(yōu)化確定的執(zhí)行策略和算法,訪問數(shù)據(jù)并得到查詢結(jié)果.由于XML數(shù)據(jù)復(fù)雜和變化的結(jié)構(gòu),需要高效的數(shù)據(jù)訪問算法.3查詢分辨率與查詢分辨率XML代數(shù)是對遵循一定數(shù)據(jù)模型的XML文檔集合的操作集.XML代數(shù)提供根據(jù)請求在文檔集合中選擇一個或多個文檔或者文檔片段的能力.XML代數(shù)應(yīng)支持對查詢結(jié)果的重構(gòu).目前對XML代數(shù)的研究主要集中在對查詢代數(shù)的定義和從查詢語言到查詢代數(shù)的轉(zhuǎn)換方面.查詢代數(shù)定義查詢對象的類型,可以執(zhí)行的操作和不同操作之間的轉(zhuǎn)換規(guī)則.查詢語言經(jīng)分解轉(zhuǎn)換為由查詢代數(shù)的操作表達(dá)構(gòu)成的操作樹或者操作序列.不同的代數(shù)表達(dá)可以有相同的語義和執(zhí)行結(jié)果,構(gòu)成代價空間.3.1正交定位與嵌套關(guān)系的編碼技術(shù)目前產(chǎn)生很多種XML代數(shù),風(fēng)格各異,其主要思想來源于關(guān)系代數(shù)、面向?qū)ο蟠鷶?shù)、半結(jié)構(gòu)化代數(shù)和功能化編程語言等.由于篇幅有限,不能在這里一一介紹,我們介紹其中具有代表性和影響力的幾種.表1列出了不同代數(shù)之間特點的比較.Oracle,IBM和MS聯(lián)合提出的一個XML代數(shù)標(biāo)準(zhǔn)是文獻(xiàn).該標(biāo)準(zhǔn)把XML文檔看作有向標(biāo)記圖(如果忽略引用,可以看作有向標(biāo)記樹).用五元組G(V,E,A,R,O)表示.其中:V表示結(jié)點,有兩種類型:element和value.E表示element到element;A表示element到value,即屬性;R表示引用.上述3種為邊的類型.O表示次序.在這個模型上,規(guī)定了導(dǎo)航、選擇、連接、構(gòu)造等操作,其導(dǎo)航操作提供在有向標(biāo)記圖中的遍歷操作,包括正向遍歷和反向遍歷;其連接操作語義類似關(guān)系代數(shù)中的連接操作,根據(jù)相同的值連接不同的文檔.該代數(shù)采用類似關(guān)系代數(shù)的表達(dá)形式.BellLabs.和AT&TLabs.的Mary等人提出的XML查詢代數(shù),基于簡化的XSLT數(shù)據(jù)模型,增加了引用結(jié)點,合并了屬性和元素結(jié)點,刪除了注釋結(jié)點.其主要思想來源于曾用于半結(jié)構(gòu)化和面向?qū)ο髷?shù)據(jù)庫的代數(shù)——嵌套關(guān)系代數(shù),并增加了對正則表達(dá)式的操作.在嵌套關(guān)系中,數(shù)據(jù)由多個元組和多個鏈表組成,并可多級嵌套,其采用listcomprehension方法表達(dá)導(dǎo)航、笛卡爾積、嵌套和連接操作.Listcomprehension根據(jù)一系列過濾和generator操作,得到滿足條件的結(jié)果鏈表.Generator操作與導(dǎo)航操作相對應(yīng).該代數(shù)還支持結(jié)構(gòu)遞歸等程序語言特點,用Haskell程序語言作為表達(dá)形式.上述兩種代數(shù)還僅停留在邏輯層次,沒有考慮與之相對應(yīng)的物理代數(shù)和查詢優(yōu)化策略,其優(yōu)勢是具有較高的描述性和豐富的語義,與查詢語言有密切的轉(zhuǎn)換關(guān)系;但其操作中對路徑的處理并不完善,形成過多的遞歸結(jié)構(gòu)或者遍歷操作,給下一步的優(yōu)化帶來困難,但其處理XML查詢的方法和思路被后來的XML代數(shù)規(guī)則大量采用.基于文獻(xiàn)等,W3C于2001年公布了一個XML查詢代數(shù)標(biāo)準(zhǔn)XQuery1.0FormalSemantics,用于規(guī)范查詢語言語義.該標(biāo)準(zhǔn)遵循簡化的XQuery1.0和Xpath2.0DataModel.比照關(guān)系代數(shù)給出了XML數(shù)據(jù)模型的投影、選擇和連接等操作的定義,還引入結(jié)構(gòu)遞歸、條件判斷等編程語言的概念.FormalSemantics的一個特點是代數(shù)表達(dá)與XQuery查詢語言相同,成為XQuery的核心語法;另一個特點是操作有不同的層次,高層次的操作可以轉(zhuǎn)換為低層次的操作.標(biāo)準(zhǔn)中還給出了少量表達(dá)式轉(zhuǎn)換規(guī)則,有待近一步擴(kuò)充.目前已經(jīng)有了應(yīng)用該標(biāo)準(zhǔn)的XML查詢引擎,如Galax.Standford大學(xué)開發(fā)的XML數(shù)據(jù)庫Lore系統(tǒng)針對系統(tǒng)本身提供的訪問操作和索引情況,提出了一套獨特的代數(shù)操作,包括邏輯代數(shù)、物理代數(shù)和相應(yīng)的轉(zhuǎn)換規(guī)則.Lore以該代數(shù)系統(tǒng)為基礎(chǔ)提出了查詢優(yōu)化方法,但由于代數(shù)操作定義過多地依賴于Lore本身獨特的數(shù)據(jù)存儲和索引技術(shù),該代數(shù)很難應(yīng)用于其他系統(tǒng).Timber數(shù)據(jù)庫中應(yīng)用的TAX代數(shù),其數(shù)據(jù)模型為無序的樹的集合,樹中的數(shù)據(jù)是有序的.直接針對樹和樹枝規(guī)定了一系列操作無須中間結(jié)構(gòu)的轉(zhuǎn)換.把XML數(shù)據(jù)模式看作樹,把查詢語句也看作樹,二者之間作模式匹配,得到滿足查詢樹條件的結(jié)果樹集合.TAX在處理連接操作時對操作的順序未做明確規(guī)定,不適應(yīng)嚴(yán)格要求文檔順序的情況.XAL基于集合概念構(gòu)造了邏輯代數(shù)操作集,其操作分為3種:抽取操作從XML文檔中獲得必要的數(shù)據(jù)如選擇、投影等;元操作控制表達(dá)式求值過程,并非針對XML數(shù)據(jù)的抽取或者構(gòu)造操作,而是為其他操作符準(zhǔn)備輸入或者控制其他操作的操作,如映射、迭代等;構(gòu)造操作用于構(gòu)造查詢結(jié)果.XAL為查詢優(yōu)化提供了一組啟發(fā)式轉(zhuǎn)換規(guī)則.其他如XOM代數(shù),是完整的操作集,包含6種對象操作,但不支持優(yōu)化;OPAL代數(shù)基于半結(jié)構(gòu)化數(shù)據(jù)模型,操作對象為多個鏈表,將有限狀態(tài)自動機(jī)用于生成執(zhí)行計劃;還有SAL等.根據(jù)代數(shù)的操作方式,可將上述不同的方法分為兩種:一種是面向集合的代數(shù),其操作對象是某種類型的集合,如樹的集合、值的集合等.這種方法具有很好的優(yōu)化基礎(chǔ),但可能丟失數(shù)據(jù)的順序;另一種稱為導(dǎo)航的代數(shù),其操作對象是單個的數(shù)據(jù).這種方法不利于進(jìn)一步的優(yōu)化.代數(shù)定義應(yīng)是邏輯操作與物理操作的有機(jī)結(jié)合.但目前的XML代數(shù)研究或是把他們混合在一起,或是雖然分開但缺乏相應(yīng)的轉(zhuǎn)換規(guī)則.早期對XML代數(shù)的研究工作重點在于規(guī)范XML查詢語義,并未考慮查詢優(yōu)化因素,這些代數(shù)具有明顯的程序化思想,很難進(jìn)一步優(yōu)化,只能利用遍歷方法求解查詢,造成查詢效率的低下,不適應(yīng)大規(guī)模XML數(shù)據(jù)的查詢需求.而基于數(shù)據(jù)庫思想提出的一些面向“集合”的代數(shù),具有很好的優(yōu)化基礎(chǔ).因此,目前查詢優(yōu)化的研究工作也多以這些代數(shù)為背景,但也存在一些問題.首先是表達(dá)式嵌套問題.在XQuery查詢中,由于表達(dá)式可以任意嵌套,謂詞可以出現(xiàn)在任意地方.謂詞是有作用域的,同一個謂詞在不同的地方會產(chǎn)生不同的查詢結(jié)果.基于集合的代數(shù)需要將嵌套的查詢轉(zhuǎn)換為邏輯樹形式,不可避免地面臨嵌套結(jié)構(gòu)的非嵌套化問題.雖然在關(guān)系數(shù)據(jù)庫中有一些方法可以借鑒,但由于XML數(shù)據(jù)結(jié)構(gòu)的復(fù)雜性,解決這個問題變得更加困難.其次是XML數(shù)據(jù)的有序性問題.除非查詢語句特別指定,否則應(yīng)該保持結(jié)點在源文檔中的結(jié)點順序.而原來一些處理連接的算法,比如排序連接、Hash連接等,會打亂結(jié)點順序,在連接完成后,需要對連接結(jié)果做一個額外的根據(jù)結(jié)點順序的排序操作.如果用nest-loop連接算法,則可以省去這趟額外的排序.在進(jìn)行代價估計的過程中,這個額外的排序操作要被考慮在內(nèi),這就給進(jìn)行查詢優(yōu)化的過程帶來新的考慮因素.一種可能的解決方法是在所有操作中,忽略結(jié)點的有序性,在最后構(gòu)造結(jié)果的時候再對結(jié)點按照文檔順序排序.究竟是使用nest-loop,還是最后增加額外的排序的方法,這是查詢優(yōu)化的一個研究點.最后,不同的代數(shù)標(biāo)準(zhǔn).在XML代數(shù)研究中一個值得重視的問題是:目前已經(jīng)出現(xiàn)了一些查詢代數(shù)標(biāo)準(zhǔn),這些標(biāo)準(zhǔn)在風(fēng)格上相去甚遠(yuǎn),很難有共通性.而對執(zhí)行方法的研究還遠(yuǎn)遠(yuǎn)不夠,不能形成完整的系統(tǒng).而且從邏輯代數(shù)到物理代數(shù)的轉(zhuǎn)換也將是未來研究的一個重要問題.3.2路徑分解的一般思路目前的XML查詢語言有很多,如XPath,XQuery,XML-QL,XQL,Quilt等.它們的一個共同的特點就是對復(fù)雜路徑表達(dá)式的支持.路徑表達(dá)式分解是根據(jù)一定的轉(zhuǎn)換規(guī)則,把用查詢語句表達(dá)的、復(fù)雜的、不確定的路徑表達(dá)式轉(zhuǎn)換為簡單的、明確的、系統(tǒng)可識別的方式,如XML代數(shù).路徑表達(dá)式分解是查詢轉(zhuǎn)換的難點,也是查詢優(yōu)化的重要一步,是代價估計的前提條件.根據(jù)不同的規(guī)則,路徑表達(dá)式可能分解為不同的等價形式,其中有的代價高,有的代價低,形成代價空間.路徑分解的原則是能夠產(chǎn)生有限的代價空間,有利于利用分解的結(jié)果搜索代價最小的執(zhí)行方案.在路徑分解時,有兩種不同的思路:一種思路是把路徑細(xì)分為兩兩的祖先后代或父子對,如lore,XISS等這樣做分解算法簡單,可利用數(shù)據(jù)物理存儲信息,分解的結(jié)果容易轉(zhuǎn)換為結(jié)構(gòu)連接運(yùn)算或者運(yùn)用系統(tǒng)提供的各種索引.如果查詢語句中出現(xiàn)通配符(如*,?,//),可以利用索引直接定位數(shù)據(jù),也可以借助模式信息確定通配符所代表的各種可能情況擴(kuò)展路徑.經(jīng)過分解,路徑表達(dá)式轉(zhuǎn)換為連接、投影、選擇、導(dǎo)航等不同的代數(shù)運(yùn)算;另一種思路是將復(fù)雜路徑表達(dá)式用樹的方式表示:從根開始,在樹中搜索最長的確定路徑(不含*或//)稱為一次分解,其路徑構(gòu)成樹的一個子串.以這個點為起點,用上述原則再分解路徑,得到確定路徑(子串)的集合,稱為一個最小分解.在XML文檔的查詢中,確定路徑的查詢是相對容易的;而不確定路徑的查詢是比較困難的,尤其是在沒有模式或索引的情況下,可能要將中間結(jié)果合并才能得到全部的結(jié)果.將復(fù)雜的、不確定的路徑分解為確定的、簡單的路徑處理.這種分解方法在沒有模式信息的情況下處理不確定路徑具有一定的優(yōu)勢.4轉(zhuǎn)化時代轉(zhuǎn)化應(yīng)用于邏輯優(yōu)化在傳統(tǒng)數(shù)據(jù)庫技術(shù)中,邏輯優(yōu)化是指通過一系列轉(zhuǎn)換規(guī)則,將原始的查詢表達(dá)式轉(zhuǎn)換為等價且更高效的形式.關(guān)系代數(shù)表達(dá)式求解時,操作順序是影響效率的關(guān)鍵.因此,邏輯優(yōu)化研究的重點并不在于對冗余操作的分析,而是對操作順序的調(diào)整.而XML代數(shù)的核心是由路徑表達(dá)式轉(zhuǎn)換的查詢樹,查詢效率依賴于查詢樹的規(guī)模.因此,查詢樹的最小化是XML邏輯優(yōu)化研究的重點,也是目前研究的熱點問題.而對操作順序的調(diào)整因為更多地依賴于物理存儲的情況,因此與物理優(yōu)化相關(guān)聯(lián).從層次上看,邏輯優(yōu)化可分為兩個層次:語法層次和語義層次.語法層次的優(yōu)化是指不依靠任何其他信息,獨立地分析查詢表達(dá)式中分支或結(jié)點間的邏輯包含關(guān)系,刪除冗余部分;語義層次的優(yōu)化是指通過數(shù)據(jù)庫提供的模式信息,如DTD,XMLSchema等,或者語義包含、結(jié)構(gòu)包含等完整性約束,查找查詢表達(dá)式中的冗余分支或結(jié)點.下面的例子進(jìn)一步說明二者之間的區(qū)別.若有如下的XQuery查詢表達(dá)式:其PatternTree(以下簡稱PTQ)如圖2(a)所示,其中,實心圓為查詢返回結(jié)點.若數(shù)據(jù)滿足$c,同時必然滿足$b,$b分支對查詢返回結(jié)果沒有任何影響,是冗余結(jié)點.我們稱這種冗余結(jié)點為語法冗余結(jié)點.經(jīng)語法優(yōu)化后的PTQ如圖2(b)所示.若從模式可知任一author均有name,則v6為冗余結(jié)點.我們稱這種冗余結(jié)點為語義冗余結(jié)點.經(jīng)語義優(yōu)化后的PTQ如圖2(c)所示.下面我們分別介紹語法優(yōu)化和語義優(yōu)化的研究現(xiàn)狀.4.1改進(jìn)的cim算法對PTQ語法優(yōu)化問題基于對路徑等價性問題的研究.最早提出XPath最小化的Wood指出:一個Xpath可以表示為合取范式,對XPath等價性檢查的復(fù)雜度等價于對合取范式的等價性檢查.而這已經(jīng)證明是一個NP完全問題.如果對XPath路徑表達(dá)式的復(fù)雜程度加以一定的限制,XPath最小化問題的復(fù)雜度可以達(dá)到多項式級.目前已經(jīng)提出了對不同類型的PTQ的最小化方法.(1)簡單PTQ{/,,*}文獻(xiàn)中提出了對只包含{/,,*}的簡單路徑的最小化方法.其思想為:設(shè)原始PTQ為P,在所有與之等價的PTQ中找到Q,使得Q中的結(jié)點個數(shù)|NQ|最小,則Q為P的最小化PTQ.這種方法的關(guān)鍵是通過對包含映射(containmentmapping)的判斷完成PTQ的等價性判斷.不存在祖先后代關(guān)系(//)的簡單PTQ的最小化PTQ為其子樹.查找等價PTQ的范圍限制在其子樹的范圍內(nèi),是保證最小化算法的復(fù)雜度為多項式級的關(guān)鍵因素.文獻(xiàn)中給出了復(fù)雜性證明,雖然并未給出算法細(xì)節(jié).文獻(xiàn)提出了PTQ的CIM(constraintindependentminimization)算法.與文獻(xiàn)相同,其算法的基礎(chǔ)也是包含映射.路徑中缺少“*”的PTQ的最小化問題,仍舊可以在其子樹范圍內(nèi)解決.CIM算法的思想為:從葉結(jié)點開始,判斷結(jié)點在PTQ中是否冗余:若某結(jié)點是冗余結(jié)點,則刪除這個結(jié)點,繼續(xù)處理其他葉結(jié)點直到所有葉結(jié)點判斷完畢;若PTQ中結(jié)點個數(shù)為n,則CIM算法的最大復(fù)雜度為O(n4).文獻(xiàn)提出了一種最大復(fù)雜度為O(n2)的改進(jìn)算法,通過結(jié)點間的二元關(guān)系Simulation判斷冗余性.改進(jìn)的CIM算法與CIM算法最大的不同點在于:前者只關(guān)心后代結(jié)點之間是否相同;而后者還要關(guān)心祖先結(jié)點之間是否相同.改進(jìn)的CIM算法通過正向遍歷查找冗余結(jié)點,如果某結(jié)點的一個兒子結(jié)點與另外兒子結(jié)點之間有Simulation關(guān)系,則這個兒子結(jié)點為冗余結(jié)點.這樣,在一次遍歷可以對多個結(jié)點的冗余性進(jìn)行判斷,從而提高了PTQ最小化的效率.與限制條件下PTQ所不同的是,普遍意義下的PTQ在語法優(yōu)化時遇到的一個關(guān)鍵問題是:最小化PTQ并非原始PTQ的子樹,而是由以原始PTQ的根為根,連接多個PTQ子樹構(gòu)成的PTQ.其中每個子樹均為原始子樹的最小化部分.這個問題也是導(dǎo)致其復(fù)雜度上升的關(guān)鍵.文獻(xiàn)給出普遍意義下的PTQ最小化算法.其算法思想是:遞歸地在原始PTQ的子樹中查找最小子樹并連接它們,在這個過程中冗余的分支被刪除了.文獻(xiàn)證明其算法的復(fù)雜度為NP完全,并指出:在對PTQ的分支個數(shù)加以一定限制的情況下,改進(jìn)的算法復(fù)雜度可以達(dá)到多項式級.但我們有理由相信,這樣的改進(jìn)意義并不大,因為這要求用戶在寫查詢語句時必須注意查詢的分支情況,否則將導(dǎo)致某些查詢無法優(yōu)化.目前,語法優(yōu)化都以判斷結(jié)點之間的包含映射關(guān)系為基礎(chǔ),分析路徑等價性.在查詢樹中不斷地修剪冗余的分支或結(jié)點,達(dá)到減少查詢樹規(guī)模的目的.普遍意義的PTQ語法優(yōu)化是一個NP完全問題,研究者通過對PTQ復(fù)雜度加以一定限制,提出了多種高效的算法.語法優(yōu)化不涉及XML模式信息,可以利用模式信息進(jìn)一步簡化PTQ,這種優(yōu)化稱為語義優(yōu)化.4.2基于acim的語義優(yōu)化方法最早提出語義優(yōu)化的是關(guān)系數(shù)據(jù)庫系統(tǒng),利用表格屬性值之間的約束關(guān)系把查詢表達(dá)式轉(zhuǎn)換為等價但更高效的形式.chase方法是其中的代表.其思想為:把完整性約束作為冗余條件插入到查詢表達(dá)式中,與已存在的冗余操作合并,使得組合后的條件符合某些事先定義好的等價轉(zhuǎn)換規(guī)則,利用這些等價轉(zhuǎn)換規(guī)則重寫查詢表達(dá)式以達(dá)到優(yōu)化的目的.這是一個巧妙的先膨脹再收縮的方法.但是,應(yīng)用Chase方法于XML查詢的語義優(yōu)化時面臨下述嚴(yán)重的挑戰(zhàn):數(shù)據(jù)結(jié)構(gòu)的變化:與平面表結(jié)構(gòu)不同,XML數(shù)據(jù)具有嵌套性.原有的主鍵、外鍵等完整性約束不能表達(dá)結(jié)構(gòu)上的嵌套關(guān)系,缺乏匹配的轉(zhuǎn)換規(guī)則.數(shù)據(jù)類型的變化:關(guān)系模型中,數(shù)據(jù)有嚴(yán)格的類型;而在XML半結(jié)構(gòu)化模型中,數(shù)據(jù)沒有嚴(yán)格的類型約束,同名的結(jié)點可以出現(xiàn)在不同的位置,可以有不同的子結(jié)點.傳統(tǒng)的轉(zhuǎn)換規(guī)則的應(yīng)用方法不適應(yīng)這種情況,引發(fā)的問題就是產(chǎn)生遞歸的轉(zhuǎn)換,導(dǎo)致路徑的無限增長.查詢語句的復(fù)雜性:SQL語句清晰、明確,關(guān)系代數(shù)操作均為輸入?yún)?shù)明確的一元或二元運(yùn)算.而XML查詢語句中包含//,*等不確定因素,并以包含多個分支長路徑為特點,原有的轉(zhuǎn)換規(guī)則不適應(yīng)于XML語義優(yōu)化.基于上述挑戰(zhàn),一些研究者提出改進(jìn)的Chase方法,而另一些研究者則從對圖分析處理的角度出發(fā),研究XML查詢的語義優(yōu)化問題.(1)改進(jìn)的Chase方法Wood等人最早將Chase方法引入簡單XPath語義優(yōu)化.文獻(xiàn)在DTD上定義了3種結(jié)構(gòu)約束關(guān)系分別為兒子約束、父親約束和兄弟約束.若某個查詢樹中結(jié)點n為上述約束關(guān)系中的主體,且其約束的結(jié)點不在查詢樹中,則在查詢樹中相應(yīng)位置加入客體結(jié)點.當(dāng)所有約束關(guān)系應(yīng)用完畢,再用語法優(yōu)化的方法對查詢樹進(jìn)行修剪,得到最小化查詢樹.為了討論簡單起見,文獻(xiàn)中方法只適用于不包含“*”和“//”的簡單路徑,其復(fù)雜度為多項式級.文獻(xiàn)則認(rèn)為,XML數(shù)據(jù)中的結(jié)構(gòu)完整性約束可用兒子約束、后代約束和類型約束概括.為了得到正確的優(yōu)化結(jié)果,他們對Chase方法做了3個方面的改進(jìn):首先,假設(shè)約束集合是閉包的;其次,為了保證優(yōu)化能夠完成,約束條件只應(yīng)用于PTQ中原有結(jié)點,如果某結(jié)點是由于應(yīng)用某約束條件加入PTQ的,則不對其應(yīng)用任何約束條件;最后,由于應(yīng)用約束條件加入的結(jié)點是冗余的,因此,需要在算法結(jié)束時刪除這些臨時結(jié)點.ACIM算法分為3個步驟:首先,應(yīng)用約束集合中的約束條件放大PTQ;然后,應(yīng)用CIM算法語法刪除冗余結(jié)點,在刪除時保證不檢查被加入臨時結(jié)點的冗余性;最后,刪除所有在第一步中加入的臨時結(jié)點.若PTQ中結(jié)點個數(shù)為n,則ACIM算法的最壞計算復(fù)雜度為O(n6).一些冗余結(jié)點是容易識別的,如果提前刪除這些容易識別的冗余結(jié)點然后再應(yīng)用ACIM算法,可以有效地提高優(yōu)化的效率.算法CDM在PTQ中遍歷地查找并刪除這樣的冗余結(jié)點,其計算復(fù)雜度為O(n2).實驗證明,在使用ACIM之前使用CDM,比直接應(yīng)用ACIM可更為有效地節(jié)省時間.文獻(xiàn)在文獻(xiàn)的基礎(chǔ)上擴(kuò)充了子類約束,并利用語法優(yōu)化中的TPQSimulation和TPQMinimization改進(jìn)了ACIM算法,使計算復(fù)雜度達(dá)到O(n4).(2)基于DTD的路徑等價類方法文獻(xiàn)提出了一種基于模式的XPath路徑表達(dá)式的語義優(yōu)化方法.其思想是:把XML文檔模式(DTD)劃分為若干個路徑等價類,每個類中的路徑等價;將XPath轉(zhuǎn)換為由簡單路徑構(gòu)成的合取范式形式,利用路徑等價類中的最短路徑代替表達(dá)式中的路徑.通過這種方法,可以實現(xiàn)3個方面的優(yōu)化:首先,刪除冗余的謂詞條件;其次簡化路徑;最后,判斷表達(dá)式的條件是否滿足.如果某個分支的條件不滿足模式中的約束關(guān)系,則整個表達(dá)式的查詢結(jié)果為空.整個優(yōu)化過程分為4部分:分解、擴(kuò)展、優(yōu)化和重構(gòu).在分解過程中,XPath表達(dá)式被轉(zhuǎn)換為合取樹(XCT);重構(gòu)XPath表達(dá)式則將優(yōu)化的XCT轉(zhuǎn)換為XPath路徑表達(dá)式.改進(jìn)的Chase方法的優(yōu)點是:語法優(yōu)化與語義優(yōu)化相結(jié)合,優(yōu)化過程無須對PTQ進(jìn)行轉(zhuǎn)換.問題是難以保證徹底的優(yōu)化:首先,PTQ中存在非葉冗余結(jié)點,而語法優(yōu)化只能在刪除葉結(jié)點后,讓非葉結(jié)點變?yōu)槿~結(jié)點的情況下才能判斷其冗余性.加入約束條件后的PTQ語法優(yōu)化,不能在不刪除葉結(jié)點的情況下,判斷非葉結(jié)點的冗余性;其次,膨脹后的PTQ難以壓縮,采用對轉(zhuǎn)換規(guī)則加以一定限制的方法限制膨脹后PTQ規(guī)模的方法,會導(dǎo)致優(yōu)化的不徹底.目前改進(jìn)的Chase方法都是針對一定復(fù)雜程度的PTQ的優(yōu)化策略,普遍意義上的PTQ的語義優(yōu)化研究還需深入;最后,從DTD中獲得的約束條件并不充分,這也是導(dǎo)致優(yōu)化不徹底的一個因素.如何抽取更多的語義約束條件,是未來研究的一個重要問題.基于DTD的優(yōu)化方法的優(yōu)點是:不但能夠刪除冗余分支,還能夠縮短路徑長度和直接判斷路徑是否滿足問題主要是:首先,需要對PTQ進(jìn)行轉(zhuǎn)換,占用大量優(yōu)化時間;其次,需要不確定路徑的確定化,這實際上也是一種路徑膨脹,難以保證優(yōu)化的結(jié)果小于優(yōu)化之前.兩種方法都需要首先擴(kuò)大路徑規(guī)模,造成優(yōu)化的不徹底和效率的喪失,這是目前語義優(yōu)化面臨的一個重要問題.5復(fù)雜路徑程式選擇性分析技術(shù)邏輯優(yōu)化的結(jié)果是一個或多個查詢樹.如何確定其中不同查詢片斷的執(zhí)行次序,是XML物理優(yōu)化的核心問題.確定執(zhí)行次序的主要因素是中間結(jié)果集的大小.復(fù)雜路徑表達(dá)式選擇性分析就是用來估計結(jié)果集規(guī)模的.其主導(dǎo)思想是:統(tǒng)計XML數(shù)據(jù)的分布情況,基于一定假設(shè)估計路徑目標(biāo)結(jié)點中間結(jié)果集的大小.這種方法一般忽略執(zhí)行算法的不同和數(shù)據(jù)的物理存儲.本節(jié)從統(tǒng)計信息抽取、存儲、壓縮、維護(hù)和統(tǒng)計信息計算等幾個方面論述目前這一技術(shù)的發(fā)展情況和所面臨的問題.5.1執(zhí)行代價的估計代價估計是對查詢物理運(yùn)算時間的估計.目前,代價計算方法主要有3種:基于參數(shù)的方法、基于取樣的方法和基于統(tǒng)計信息計算的方法.基于參數(shù)的方法無須統(tǒng)計數(shù)據(jù)信息,根據(jù)數(shù)據(jù)分布情況假定其滿足包含某些參數(shù)的分布函數(shù),通過計算函數(shù)的值估計查詢計劃的執(zhí)行代價.這種方法在處理有規(guī)律分布的數(shù)據(jù)(如學(xué)生成績)時,可以大量節(jié)省統(tǒng)計信息空間和I/O代價,但對分布無明顯規(guī)律的數(shù)據(jù)會有很大的誤差;基于取樣的方法也無須統(tǒng)計數(shù)據(jù)信息,做法是從數(shù)據(jù)集中提取具有代表性的樣本,比較不同的查詢計劃的執(zhí)行情況,獲得代價最小的方案.這種方法的精確性決定于取樣的代表性.最簡單的方法是隨機(jī)取樣,一些優(yōu)化的方法根據(jù)數(shù)據(jù)的密度取樣.取樣方法的缺點是代價估計本身占用時間可能很大;最常用也是研究最多的方法是基于統(tǒng)計信息的方法,需要統(tǒng)計估計所用的各種信息,利用統(tǒng)計信息計算不同方案的執(zhí)行代價.這種方法的精確性取決于統(tǒng)計信息的正確性.但是,統(tǒng)計信息過大又會導(dǎo)致統(tǒng)計時間過長.利用有限的時間和空間得到相對小的執(zhí)行方案是代價統(tǒng)計的基本原則.不同的系統(tǒng)支持的物理運(yùn)算算法不同,代價模型也不同.在關(guān)系模型中,進(jìn)行代價估計時有兩個通用的前提:獨立性假設(shè)和均勻分布假設(shè).前者是指各謂詞之間沒有相互依賴關(guān)系;后者是指如果關(guān)系在某個屬性上沒有直方圖,則認(rèn)為該屬性的各值在數(shù)據(jù)庫中均勻出現(xiàn).XML數(shù)據(jù)的不規(guī)則性是對傳統(tǒng)統(tǒng)計信息方法的重要挑戰(zhàn).其數(shù)據(jù)分布情況使得一些傳統(tǒng)分布假設(shè)難以成立.在XML中,相同名字的結(jié)點可能在同一個文檔的不同部分出現(xiàn)但卻具有截然不同的語義.如同為name結(jié)點在person下和在city下出現(xiàn)其意義就完全不同,這可以稱為元素之間的結(jié)構(gòu)依賴性;同時,在XML文檔中,嵌套在不同祖先下的同類結(jié)點的個數(shù)差別也很大,如book結(jié)點下的author個數(shù)是不確定的,這可以稱為元素之間的結(jié)構(gòu)相關(guān)性.為了達(dá)到所需的代價估計精度,需要更多的統(tǒng)計信息.而結(jié)構(gòu)的復(fù)雜性又為獲得相對精確的統(tǒng)計信息帶來存儲和計算上的困難.XML的有序性制約了轉(zhuǎn)換規(guī)則的靈活性.所有這些問題,都使得在XML中采用傳統(tǒng)的代價估計方法不切實際,會帶來很大的誤差.針對XML數(shù)據(jù)的特點,我們應(yīng)該尋求一種新的代價估計方法.5.1.1元素占用及聚集的情況查詢計劃的執(zhí)行代價主要來自3方面的因素:CPU計算代價、I/O代價和數(shù)據(jù)傳輸代價.CPU,磁盤和網(wǎng)絡(luò)的速度差距懸殊.當(dāng)不考慮數(shù)據(jù)的分布性因素時,影響代價的決定性因素是I/O代價.I/O代價受眾多因素制約,主要來自3個方面:一是數(shù)據(jù)庫系統(tǒng)參數(shù),如頁面大小、內(nèi)存使用情況等;二是數(shù)據(jù)集本身因素,如數(shù)據(jù)存儲空間大小、索引情況、每個元素占用空間情況和元素的聚集情況等;三是查詢請求因素,如查詢條件的選擇性等.目前,對XML代價模型的研究并不充分,代價模型相對簡單,這也是造成代價估計誤差的一個原因.Lore的代價模型沒有考慮聚集情況,不能判定不同的數(shù)據(jù)是否在同一頁面上,因此,其假設(shè)每次I/O操作只能獲得一個對象,把對I/O時間的估計轉(zhuǎn)換為對中間結(jié)果大小的估計.由于Lore中數(shù)據(jù)本身無聚集,這種方法可以獲得較好的效果,但對其他XML數(shù)據(jù)庫系統(tǒng)參考意義并不大.文獻(xiàn)提出了一種新的代價模型,其基本思想是利用查詢反饋信息來調(diào)整參數(shù).如圖3所示,在用戶提交查詢之前,先人工找出影響查詢執(zhí)行時間的特征,再利用線性回歸模型計算出各個特征對查詢代價的影響系數(shù),即得到一個形如cost(q)=f(v1,v2,…,vd)的函數(shù)模型,當(dāng)用戶提交查詢時,利用函數(shù)和事先統(tǒng)計的特征值進(jìn)行計算.但是,文中提出的方法只是針對CPU代價估計的,沒有擴(kuò)展到I/O代價的估計;而且只考慮了一個XNav操作符,至于如何擴(kuò)展到其他情況,文獻(xiàn)中并未提及.人工抽取特征具有主觀性,如何讓系統(tǒng)自動地抽取特征是下一步研究的重點.5.1.2遺傳算法求解最優(yōu)物理子計劃代價空間搜索算法首先通過某種計算方法量化代價空間、構(gòu)造搜索函數(shù),根據(jù)函數(shù)值的變化判斷是否繼續(xù)搜索.在眾多的空間搜索技術(shù)中,最簡單的是隨機(jī)搜索方法,隨機(jī)地或者按照某個順序在搜索空間中計算代價但這種方法效率低下,在實際的系統(tǒng)中很少被采用.爬山算法是應(yīng)用廣泛的一種搜索算法,在以某步長對函數(shù)進(jìn)行搜索的過程中按照逐步接近的方式,定位局部最優(yōu)執(zhí)行計劃,搜索的效率與初始值和步長相關(guān).當(dāng)搜索函數(shù)非單調(diào)時,這種方法找到的是局部極值,而非全局最值.遺傳算法是解決局部最優(yōu)的一種新穎的空間搜索方法.用雜交的方法搜索不同的最優(yōu)執(zhí)行計劃,適用于有多個極值的搜索函數(shù).這種方法在關(guān)系數(shù)據(jù)庫查詢優(yōu)化中有一定的應(yīng)用意義,在XML查詢優(yōu)化的代價空間搜索技術(shù)中應(yīng)用遺傳算法的難點在于適應(yīng)度函數(shù)的構(gòu)造.單個查詢物理計劃形成的代價空間可能非常龐大,尤其是對路徑很長的情況,其代價空間呈冪次級增長.為了減少代價估計時間,需要利用啟發(fā)性規(guī)則約束代價空間.Lore的做法是:分別將每一個邏輯操作轉(zhuǎn)換為最優(yōu)物理子計劃,并在轉(zhuǎn)換時應(yīng)用啟發(fā)性規(guī)則.例如:TargetSet操作只在路徑表達(dá)式的起始結(jié)點是標(biāo)記名并且只在路徑結(jié)束結(jié)點上有變量約束時使用;當(dāng)查詢中有多個路徑表達(dá)式時,不改變其間的順序.值得注意的一條規(guī)則是,選擇操作總在最后做.這條規(guī)則和關(guān)系查詢優(yōu)化的啟發(fā)性規(guī)則正好相反.這是由于在Lore中,選擇運(yùn)算總是基于變量綁定運(yùn)算.在XML代價估計研究中,路徑表達(dá)式選擇性代價估計是核心問題,也是在XML查詢優(yōu)化研究中份量最重的一個領(lǐng)域,值得我們特別關(guān)注.在第5.2節(jié)中我們將做專門的論述.5.2[p][pn]XML路徑表達(dá)式可視為一棵樹,其中的一個主支為從起點到目標(biāo)點的主路徑,其余分支為約束主支的謂詞條件(如圖4所示),表示為P=t1[p1]/t2[p2]/…./tn[pn].其中:ti為結(jié)點名;pi為謂詞,默認(rèn)存在量詞布爾表達(dá)式.路徑表達(dá)式的選擇性估計是對滿足分支條件的主支數(shù)據(jù)個數(shù)的估計.對XML路徑表達(dá)式的估計需要數(shù)據(jù)結(jié)構(gòu)的統(tǒng)計信息與分布在結(jié)構(gòu)內(nèi)部的值的統(tǒng)計信息的結(jié)合,以計算路徑的選擇性.5.2.1基于數(shù)據(jù)過多的代價估計方法aChen等人把數(shù)值結(jié)點作為普通結(jié)點看待,這樣,估計a=3與a.3是等價的,簡化統(tǒng)計結(jié)構(gòu),適用于數(shù)值量較少的情況.如果數(shù)值量龐大,統(tǒng)計每一個數(shù)值的個數(shù)會占據(jù)大量的空間,導(dǎo)致統(tǒng)計信息過多,影響查詢代價估計的效率.這種方法對等值的定點查詢可以使用,卻很難估計范圍查詢的代價.如估計a>3的代價,需要遍歷統(tǒng)計信息中所有同類數(shù)值結(jié)點,判斷其值是否滿足條件.Freire等人用直方圖等方法分別統(tǒng)計不同類型的數(shù)值信息,如最大值、最小值、平均值、個數(shù)等信息即適用于范圍查詢,也適用于點查詢.其缺點是:數(shù)據(jù)類型過多會導(dǎo)致統(tǒng)計信息的膨脹;并且,XML數(shù)據(jù)的特點是自描述性,其值和結(jié)構(gòu)有密切的語義關(guān)系,分開統(tǒng)計必然導(dǎo)致分別估計,造成估計誤差,在文獻(xiàn)中有關(guān)于這方面的詳細(xì)論述.5.2.2路徑結(jié)構(gòu)與相關(guān)子路徑樹XML數(shù)據(jù)為有序有向圖.對圖的結(jié)構(gòu)抽取有兩種極端的方法:標(biāo)記分裂圖(label-splitgraph)方法粗略地統(tǒng)計模式信息,其思想是合并所有的標(biāo)記名相同的結(jié)點為一個結(jié)點,記錄合并結(jié)點的個數(shù)作為標(biāo)記的統(tǒng)計信息.這種方法占用空間相對較小,但不能精確地反映數(shù)據(jù)分布的真實情況,尤其是同名結(jié)點出現(xiàn)在不同位置上時,可能包含錯誤的路徑或者圈信息;B/F類似圖(B/F-bisimiargraph)中,只有所有入邊和出邊集合相同時才合并同名的結(jié)點,保證準(zhǔn)確地統(tǒng)計路徑表達(dá)式所有的分支情況.這種方法的缺點是占用空間大.查詢優(yōu)化的統(tǒng)計信息控制在一定的范圍內(nèi),現(xiàn)有系統(tǒng)的抽取方法都是介于兩個極端的情況之間.Lore的DataGuide抽取模式的方法是保證每條路徑只出現(xiàn)一次,其最小模式是標(biāo)記分裂圖的一個例子文獻(xiàn)指出:這種方法統(tǒng)計路徑信息能夠精確判斷路徑是否存在,但并不能更精確地統(tǒng)計不同結(jié)點的值在不同路徑中的分布情況.如圖5所示:圖5(c)為圖5(a)的最小DataGuide.如果對結(jié)點19的統(tǒng)計信息為t,根據(jù)圖5(c)無法判斷是路徑A.C或者B.C的結(jié)點個數(shù);圖5(b)為圖5(a)的強(qiáng)壯DataGuide.如果對結(jié)點12和13的統(tǒng)計信息為t12和t13,根據(jù)圖5(b)判斷路徑A.C的個數(shù)為t12,B.C的個數(shù)為t13.StatiX根據(jù)XMLSchema統(tǒng)計結(jié)構(gòu)信息,它是一種折衷的方法.出邊不同但同類型的結(jié)點合并為一個,系統(tǒng)對不同類型的結(jié)點標(biāo)記以不同區(qū)域的值,按照區(qū)域分別統(tǒng)計不同路徑的結(jié)點個數(shù),保留了分支結(jié)點的路徑分布信息.兒子結(jié)點的分布情況保留在父親結(jié)點的統(tǒng)計信息中.每個結(jié)點的統(tǒng)計信息不再是單個的值,而是一個復(fù)雜的結(jié)構(gòu).導(dǎo)致的問題一是代價信息的增長,二是代價估計算法的復(fù)雜性.Xsketch也是一種折衷的方法,但只統(tǒng)計結(jié)構(gòu)中每個結(jié)點對應(yīng)數(shù)據(jù)中結(jié)點的個數(shù)信息.其特別之處在于對結(jié)點入邊和出邊的信息的統(tǒng)計.如果對任意結(jié)點v∈V,存在u∈U,在數(shù)據(jù)集中都有邊(u,v),則V對U向后固定.如果對任意結(jié)點u∈U,存在v∈V,在數(shù)據(jù)集中都有邊(u,v),則U對V向前固定.這種統(tǒng)計信息用于在合并不同分支與主支之間選擇性代價估計的計算.上述方法統(tǒng)計的只是路徑中父子之間的關(guān)系,而沒有統(tǒng)計同父的兄弟之間的相關(guān)性.為了便于計算相對路徑的代價和統(tǒng)計路徑之間的相關(guān)性,Chen等人吸收了信息檢索中在文檔中檢索子串的采用后綴樹的方法統(tǒng)計路徑信息,稱為相關(guān)子路徑樹(correlatedsubpathtree).從XML數(shù)據(jù)中抽取所有到葉子的可能路徑,形成路徑集合,其中間結(jié)點的結(jié)點名為不可分割子串;葉結(jié)點為數(shù)值或者字符串值,為可分割子串.每個結(jié)點存儲子路徑在數(shù)據(jù)中出現(xiàn)的次數(shù)和路徑特征矢量.我們將在后面的選擇性計算部分介紹后綴樹方法的代價計算方法;在信息統(tǒng)計部分介紹后綴樹信息的存儲和修剪維護(hù)方法.XSketches在文獻(xiàn)的基礎(chǔ)上增加了對邊的信息和值的信息的統(tǒng)計,從而在一定范圍內(nèi)(TSN)能夠處理結(jié)構(gòu)和值或值和值的相關(guān)性問題.但增加信息的同時,也使得構(gòu)造XSketches結(jié)構(gòu)代價加大.在XSEED中提到:為100M的XMark文檔構(gòu)造一個XSketches結(jié)構(gòu)需要超過一天的時間,這在實際中變得不可接受.針對XSketches的缺點,XSEED提出了一種新的處理思路,即抽取最粗略的信息,稱為XSEED內(nèi)核,一般只占文檔大小的2%左右;然后,再利用查詢反饋的信息把誤差最大的那部分路徑選擇率的精確值存儲起來,而這部分存儲的信息的多少是根據(jù)內(nèi)存大小來確定的.但是,這種方法只能處理XPath.如果把XML數(shù)據(jù)看作樹,對樹中的結(jié)點按照(start,end)編碼,以start為橫坐標(biāo),end為縱坐標(biāo),則樹中所有結(jié)點可看作是平面空間上的點,路徑上的祖先和后代關(guān)系滿足:xancestor<xdescendant<ydescendant≤yancestor,把整個空間區(qū)域分成多個方格,統(tǒng)計結(jié)點在每個格中的分布個數(shù);Wu等人的思想是:把不同結(jié)點映射為一維坐標(biāo)上的線段,祖先線段和后代線段的起點及長度滿足某種偏序關(guān)系,把整個區(qū)間分成多個小區(qū)間,分別計算落在不同區(qū)間內(nèi)的線段之間的關(guān)系.這種方法減少了稀疏分布時的誤差,但不能完全避免.這兩種統(tǒng)計方法適用于對結(jié)構(gòu)連接運(yùn)算的代價估計.5.2.3xsketch方法當(dāng)XML數(shù)據(jù)結(jié)構(gòu)復(fù)雜、每個文檔的數(shù)據(jù)量很大時,精確地統(tǒng)計信息是不可能的.在計算查詢代價時,需要用一些假設(shè)來彌補(bǔ)統(tǒng)計信息的不足.目前的路徑選擇性計算方法分為3種:(1)基于馬爾可夫鏈的方法Lore的方法基于馬爾可夫鏈思想,用于計算沒有分支條件的簡單路徑.系統(tǒng)中只保留短路徑的選擇性統(tǒng)計信息,基于父子結(jié)點分布的獨立性假設(shè)計算長路徑選擇性.如有長路徑t1/t2/t3/…/tn,其選擇性計算公式可以是此時,只需保留長度為1和2的路徑信息.也可以是則需保留長度為n-2和n-1的路徑信息.路徑信息越長,組合個數(shù)越多,占用空間越大,計算值越精確.實驗表明當(dāng)路徑信息較短時,加長路徑信息導(dǎo)致明顯的計算精確性,且空間代價增長相對緩慢;當(dāng)路徑信息較長時,加長路徑信息導(dǎo)致空間代價的爆炸性增長,而精確性提高緩慢.如果在路徑的某個結(jié)點上有對簡單值的選擇,則根據(jù)兄弟分布獨立性原則,計算不同選擇性再做交集運(yùn)算.Aboulnaga等人對Lore的方法進(jìn)行了改進(jìn),提出了路徑(path)樹和Markov表來估計簡單路徑的選擇性用路徑樹可以表示原文檔的結(jié)構(gòu),樹中的每一個結(jié)點代表了從文檔的根結(jié)點開始的路徑,并記錄了相應(yīng)結(jié)點出現(xiàn)的次數(shù).但當(dāng)樹變得很大以至于不能放在內(nèi)存的時候,就需要對樹進(jìn)行剪枝,根據(jù)一定的算法,刪去那些出現(xiàn)不頻繁的結(jié)點,然后在這個剪枝過的樹上進(jìn)行選擇率的估算.Markov表存儲長度為m(m>=2)的不同路徑,如果查詢的長度和m相等,直接就可以從表中讀出相應(yīng)的值,誤差為0;當(dāng)長度大于m時,用公式進(jìn)行計算.同樣地,當(dāng)表不能放入內(nèi)存時,刪除那些不頻繁路徑.Xsketch增加了對邊的固定性統(tǒng)計信息,并對Lore的方法做了改進(jìn),以適用于更一般的路徑表達(dá)式代價估計.如果主路徑是向后固定的,則統(tǒng)計信息為精確信息,無須進(jìn)一步計算;如果主路徑中有些點不是向后固定的,則在這些點上把主路徑分為多個子路徑,根據(jù)路徑獨立性假設(shè),用類似Lore的公式,以子路徑統(tǒng)計信息為參數(shù),計算長路徑的選擇性.如果分支路徑是向前固定的,則其選擇性為1,無須參與計算;如果分支路徑中有些點不是向前固定的,則在這些點上把分支路徑分為多個子路徑,計算不同選擇性,再做交集運(yùn)算.為了提高計算的精確性,其代價路徑分解方法為最大交叉方法.XSketches對文獻(xiàn)的工作進(jìn)行了擴(kuò)展,可以計算twig匹配的個數(shù).XSketch在原來模型的基礎(chǔ)上增加了邊的分布信息,從而能夠從細(xì)節(jié)上把握數(shù)據(jù)的分布.這種方法的特點是:先抽取XML文檔的結(jié)構(gòu)建立XSketches,然后利用邊的穩(wěn)定性和邊的分布概率來估計twig的匹配個數(shù),如果邊的確是分布均勻的話,那么這種方法的準(zhǔn)確率就比較高.XSEED方法在XSEED核結(jié)構(gòu)上增加了對遞歸結(jié)點的處理,遞歸結(jié)點是指在DTD中有類似A(A+,B*)的定義,則A結(jié)點是一個遞歸結(jié)點.XSEED核結(jié)構(gòu)在邊上記錄了在遞歸的不同層相應(yīng)的父親、孩子的結(jié)點個數(shù)因此,這種方法可以很好地處理帶有遞歸表達(dá)式的XPath查詢.馬爾可夫鏈思想中的一個關(guān)鍵性假設(shè)是父子結(jié)點分布獨立性和兄弟結(jié)點分布獨立性假設(shè).而實際上,很多XML數(shù)據(jù)的父子結(jié)點、兄弟結(jié)點之間的相關(guān)性非常強(qiáng),應(yīng)用上述計算方法會導(dǎo)致誤差.集合哈希方法統(tǒng)計相同分支之間的相關(guān)性信息,更準(zhǔn)確地計算分支路徑的選擇性.(2)集合哈希方法集合哈希方法的核心思想來自蒙特卡羅技術(shù)的Min-Wiseindependentpermutations.這種方法用于估計兩個集合之間的相似性,集合的特征通過設(shè)置哈希函數(shù)的集合獲得.其優(yōu)勢在于集合的哈希函數(shù)值占用存儲空間很小.對集合A,其特征矢量為其中,U={1,…,n};π是U的排列;l是哈希函數(shù)的個數(shù).關(guān)于集合哈希函數(shù)的構(gòu)造方法在文獻(xiàn)中有詳細(xì)的論述.利用集合哈希方法計算路徑表達(dá)式的代價的方法為:用后綴樹統(tǒng)計所有可能出現(xiàn)在查詢中的子路徑的特征矢量;分解查詢?yōu)槎鄠€相關(guān)子路徑;應(yīng)用公式計算選擇性.文獻(xiàn)中提供了3種路徑分解的方法,并比較了不同方法之間的優(yōu)劣.這種代價計算的精度對路徑的長度敏感:隨路徑長度的增長,統(tǒng)計精度下降.并且,特征矢量本身是一種信息壓縮的方法,用來計算相關(guān)性時的精確性是值得商榷的.上述兩種算法都是根據(jù)確定路徑上的父子關(guān)系統(tǒng)計信息計算路徑表達(dá)式中后代結(jié)點的選擇性,沒有直接計算后代,也沒有根據(jù)某些后代估計滿足條件的祖先結(jié)點的選擇性.在執(zhí)行計劃中,存在大量的向前遍歷的算法.如何估計這些算法的代價,是一個需要解決的問題.上面所提到的各種方法的處理能力各有不同,僅從方法能夠支持的各種情況(Xpath,Xquery,//,*,value)來看可以總結(jié)為表2.(3)位置直方圖方法Wu等人采用位置直方圖的方法統(tǒng)計組先后代的分布信息,其代價計算分為基于祖先的代價估計和基于后代的代價估計.基于祖先的代價估計根據(jù)每一個祖先的格,累計其滿足條件的后代的格中的結(jié)點個數(shù);基于后代的代價估計則與其正好相反.根據(jù)不同區(qū)域的祖先后代結(jié)點的偏序關(guān)系,分別計算.如圖6所示:A為某祖先格則B區(qū)域中所有的格的所有結(jié)點均為A中所有結(jié)點的后代;C,E區(qū)域中所有格的部分結(jié)點為A中部分結(jié)點的后代;而D,F區(qū)域中只有左上半角區(qū)域中存在結(jié)點且部分結(jié)點為A中部分結(jié)點的后代.如果考慮自身的嵌套,則A中部分結(jié)點是A中部分結(jié)點的后代.據(jù)上所述,滿足條件P1的A的滿足條件P2的后代個數(shù)估計公式為對每個格而言,其后代格限定在較小區(qū)域內(nèi),避免多余的統(tǒng)計和計算.但在計算區(qū)域的邊緣,并非所有結(jié)點滿足上述關(guān)系.根據(jù)平均分布的假設(shè)給計算結(jié)果加以某個系數(shù)是產(chǎn)生誤差的主要因素,誤差在空間結(jié)點分布稀疏時變得很大.一個改進(jìn)的方法是分別統(tǒng)計不同類型的結(jié)點的分布情況,但統(tǒng)計信息占用空間很大.這種方法解決的問題是已知集合間的祖先后代關(guān)系的估價,未涉及路徑中單個謂詞的選擇性計算問題.Jiang等人的思想是:把不同的結(jié)點映射為一維坐標(biāo)上的線段,祖先線段和后代線段的起點和長度滿足某種偏序關(guān)系.把整個編碼空間[cmin,cmax]分成多個小區(qū)間,然后在每個小區(qū)間內(nèi)估計覆蓋的線段/起始點的對數(shù).如圖7所示:統(tǒng)計信息n表示每個桶中的線段/起始點的對數(shù);wss表示桶的起始坐標(biāo);wse表示桶的終點坐標(biāo);表示桶中線段的平均長度;匹配的祖先-后代個數(shù)在圖中用X表示.這種方法減少了稀疏分布時的誤差,但不能完全避免.上述方法在計算路徑選擇性時,只考慮有謂詞約束的結(jié)點,躍過其他結(jié)點,直接估計后代或祖先的代價,簡化了計算的復(fù)雜度,在對模糊路徑的代價估計中有一定的優(yōu)勢.與馬爾可夫方法相同的是:當(dāng)路徑中出現(xiàn)多個謂詞時,假設(shè)不同的謂詞條件是獨立的,沒有計算不同的謂詞之間的相關(guān)性.集合哈希方法計算不同謂詞之間的相關(guān)性,但后綴樹占用空間過大,尤其是在XML數(shù)據(jù)中包含大量數(shù)值時.而查詢優(yōu)化的一個原則就是在有限的時間和空間內(nèi)精確地估計代價.這時,必須對統(tǒng)計信息進(jìn)行壓縮,以保證優(yōu)化的效率.5.3數(shù)據(jù)更新頻繁XML數(shù)據(jù)結(jié)構(gòu)復(fù)雜,分布不均勻.數(shù)據(jù)量龐大時,在有限的空間內(nèi)統(tǒng)計足夠多的信息是統(tǒng)計信息研究的難點.當(dāng)數(shù)據(jù)更新頻繁時,高效的信息維護(hù)技術(shù)顯得更為重要.5.3.1樹n存儲代價在前文介紹數(shù)值統(tǒng)計和數(shù)據(jù)結(jié)構(gòu)抽取時,已經(jīng)涉及到統(tǒng)計信息的存儲問題,但討論集中在邏輯層,并未涉及存儲的形式.XML數(shù)據(jù)統(tǒng)計信息的存儲結(jié)構(gòu)主要有以下幾種:樹或圖:用于存儲模式信息,如在文獻(xiàn)中模式樹中每個結(jié)點的個數(shù),或者文獻(xiàn)中結(jié)點之間的固定關(guān)系等.由于其數(shù)據(jù)結(jié)構(gòu)與XML原始數(shù)據(jù)相同,可用對數(shù)據(jù)本身的存取方法存取統(tǒng)計信息.如果XML數(shù)據(jù)模式結(jié)點個數(shù)為n,則樹方法存儲的代價為O(n);后綴樹的存儲代價為O(n!).馬爾可夫表:用于存儲路徑信息,不同的路徑對應(yīng)其在數(shù)據(jù)中出現(xiàn)的次數(shù).為了查找方便,一般在表上再加以一定的索引.如果只統(tǒng)計小于k長度的路徑,則其存儲代價為O(nk).直方圖:關(guān)系數(shù)據(jù)庫中普遍應(yīng)用的一種統(tǒng)計信息方法.將某屬性的值域劃分為多個連續(xù)或不連續(xù)的部分,分別統(tǒng)計不同部分區(qū)域內(nèi)數(shù)據(jù)的分布情況.對于簡單數(shù)據(jù),采用一維直方圖方法;若統(tǒng)計相關(guān)的不同屬性的分布情況,需要二維或者更多維