ISSN 100-9825, CODEN RUXUEWE-mail: jos@iscas.ac.cnJournal of Sofware, Vol.17, No.10, October 2006, pp.2069- -2086http://www.jos.org.cnDOI: 10. 1360/jos172069Tel/Fa+86-102562563◎2006 byJournal of Sofware. All rights reserved.XML查詢優(yōu)化研究孟小峰"，王宇’，王小鋒''(中國人民大學(xué)信息學(xué)院,北京100872)(河北大學(xué)計(jì)算中心,保定071002)Research on XML Query OptimizationMENG Xiao-Feng"，WANG Yu, WANG Xiao-Feng''(Information School, Renmin University of China, Beijing 100872, China)"(Computer Center, Hebei University, Baoding 071002, China)+ Corresponding author: Phn: +86-10-62519453, E-mail: xfmeng@ruc.edu.cn, htp://www.ruc.edu.cnMeng XF, Wang Y, Wang XF. Research on XML query optimization. Journal of Software, 2006,17(10):2069- 2086. htp://www.jos.org.cn/1000-9825/17/2069.htmAbstract: XML has become the de-facto standard for data representation and exchange on the World-Wide Web.Due to the nature of information on the Web and the inherent flexibility of XML, it is expected that much of thedata encoded in XML will be semi-structured. Data on the internet is increasingly presented in XML format whichenables researches on various kinds of XML storage model. Meanwhile, XML query optimization has become a hotresearch topic in database field. This paper gives an overview of the current status of technology for XML queryoptimization. The features of XML query optimization and key problems of research are also discussed deeply.Main aspects of current work on XML query optimization include XML algebra, cost model, complex pathselectivity estimation, statistics information, and so on. Finally, this paper prospects future research directions andpresents some viewpoints of XML query optimization.Key words: XML; query optimization摘要:XML已經(jīng)成為網(wǎng)絡(luò)上信息描述和信息交換的標(biāo)準(zhǔn).由于網(wǎng)絡(luò)上信息的本質(zhì)特性和XML數(shù)據(jù)內(nèi)在的靈活性,很多用XML編碼的數(shù)據(jù)都是半結(jié)構(gòu)化的隨著XML應(yīng)用得越來越廣泛，人們提出了多種XML數(shù)據(jù)的存儲(chǔ)模型.與此同時(shí),XML的查詢優(yōu)化也是數(shù)據(jù)庫領(lǐng)域研究的一個(gè)重要課題綜合論述了XML數(shù)據(jù)查詢優(yōu)化技術(shù)的現(xiàn)狀,指出了XML查詢優(yōu)化的特點(diǎn)和研究的關(guān)鍵性問題.描述了查詢優(yōu)化技術(shù)各個(gè)方面的重要研究成果以及存在的問題,進(jìn)一步展望了未來的研究方向,并在此基礎(chǔ)上提出了對(duì)XML查詢優(yōu)化方法的一些觀點(diǎn).關(guān)鍵詞: XML;查 詢優(yōu)化中圖法分類號(hào): TP311文獻(xiàn)標(biāo)識(shí)碼: A●Supported by the National Natural Science Foundation of China under Gr中國煤化工自然科學(xué)基金); theNational Grand Fundamental Research 973 Program of China under Grant No.2:1HCNMH(發(fā)展規(guī)劃(973)); theKey Project of Chinese Ministry of Education under Grant No.03044 (國家教育印中，議小里m灰口) u llugiam for New CenturyExellent Talents in University (國家教育部新世紀(jì)優(yōu)秀人才支持計(jì)劃)Received 2006-01-19; Accepted 2006-04-172070Journal of Sofware軟件學(xué)報(bào)Vol.17, No.10, October 2006XML已經(jīng)成為網(wǎng)絡(luò)上信息描述和信息交換的標(biāo)準(zhǔn).早期的XML數(shù)據(jù)以文檔方式存儲(chǔ),以關(guān)鍵字查詢等信息檢索手段查詢,簡單、易用.由于缺乏系統(tǒng)的存儲(chǔ)和查詢機(jī)制的支持,造成查詢能力低,不能滿足復(fù)雜條件的查詢,更談不上查詢優(yōu)化.一些現(xiàn)有 的商業(yè)數(shù)據(jù)庫系統(tǒng)打充了處理XML數(shù)據(jù)的功能,利用現(xiàn)有數(shù)據(jù)庫成熟的技術(shù)，把XML查詢要求轉(zhuǎn)變?yōu)閿?shù)據(jù)庫查詢表達(dá),由查詢優(yōu)化器優(yōu)化查詢表達(dá)并執(zhí)行,再將查詢的結(jié)果轉(zhuǎn)變?yōu)閄ML數(shù)據(jù):這種方法在一定程度上解決了查詢復(fù)雜性的要求,但多級(jí)轉(zhuǎn)換帶來的問題是效率的降低和查詢語義的混淆.與傳統(tǒng)的數(shù)據(jù)庫數(shù)據(jù)相比,XML數(shù)據(jù)具有如下特點(diǎn):,數(shù)據(jù)是自描述的,內(nèi)容與結(jié)構(gòu)混雜在一起;●數(shù)據(jù)具有完整的嵌套層次;●數(shù)據(jù)是有序的.XML數(shù)據(jù)的不規(guī)則性是對(duì)傳統(tǒng)統(tǒng)計(jì)信息方法的重要挑戰(zhàn)，其數(shù)據(jù)分布情況使得一些傳統(tǒng)的分布假設(shè)難以成立.為了達(dá)到所需的代價(jià)估計(jì)精度,需要更多的統(tǒng)計(jì)信息.而結(jié)構(gòu)的復(fù)雜性又為獲得相對(duì)精確的統(tǒng)計(jì)信息帶來存儲(chǔ)和計(jì)算上的困難.XML的有序性制約了轉(zhuǎn)換規(guī)則的靈活性.XML數(shù)據(jù)的上述問題無論是對(duì)關(guān)系數(shù)據(jù)庫或是對(duì)面向?qū)ο髷?shù)據(jù)庫的現(xiàn)有查詢優(yōu)化技術(shù)都是嚴(yán)峻的挑戰(zhàn).與傳統(tǒng)的查詢需求相比,XML查詢具有如下特點(diǎn):●以長路徑表達(dá)式為查詢的核心語句,路徑復(fù)雜,包含分支路徑;●嵌套的查詢表達(dá),查詢表達(dá)式中加入編程語言的嵌套和條件判斷思想;●路徑中包含不確定因素，這在之前的查詢需求中未出現(xiàn)過;查詢對(duì)象和返回結(jié)果類型不確定.面向?qū)ο髷?shù)據(jù)庫已有一些處理復(fù)雜長 路徑表達(dá)式的經(jīng)驗(yàn),但無法處理XML查詢中的路徑表達(dá)式中的不確定情況;關(guān)系數(shù)據(jù)庫中已有很多處理嵌套查詢的方法,但對(duì)摻雜編程語言風(fēng)格的XML查詢語言卻難以適應(yīng).綜上所述,來自數(shù)據(jù)結(jié)構(gòu)和查詢需求兩方面的問題導(dǎo)致基于關(guān)系和面向?qū)ο髷?shù)據(jù)庫的查詢處理和查詢優(yōu)化技術(shù)均不能適應(yīng)XML查詢的需要.目前,對(duì)XML查詢優(yōu)化的研究正成為熱點(diǎn)本文的內(nèi)容就是對(duì)XML查詢優(yōu)化技術(shù)現(xiàn)狀的綜合論述，指出了XML查詢優(yōu)化的特點(diǎn)和研究的關(guān)鍵性問題,描述了查詢優(yōu)化技術(shù)各個(gè)方面的重要研究成果和有待進(jìn)一步解決的問題.1XML查詢優(yōu)化研究問題查詢優(yōu)化是數(shù)據(jù)庫技術(shù)中重要的研究問題,是實(shí)現(xiàn)高效查詢的關(guān)鍵性因素.對(duì)傳統(tǒng)數(shù)據(jù)庫查詢優(yōu)化的研究已經(jīng)形成相對(duì)成熟的技術(shù)和方法,其中基于代價(jià)的優(yōu)化是主流.查詢語言首先被轉(zhuǎn)換成為一種內(nèi)部表達(dá)形式(通常是某種代數(shù),如關(guān)系代數(shù)等),根據(jù)變換規(guī)則得到等價(jià)表達(dá)式,計(jì)算不同形式的表達(dá)式的執(zhí)行代價(jià),然后選擇一個(gè)最小的執(zhí)行方案.當(dāng)把這種方法用于XML查詢優(yōu)化時(shí),研究者遇到如下問題:(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)化特點(diǎn)是定義完普的代數(shù)運(yùn)算的最大障礙,而XML查詢語言中的不確定性和一些編程思想的引入是另一個(gè)難以克服的困難.(2)精確的代價(jià)估計(jì)關(guān)系模型中,表中的記錄是無序的、大小相等的,代價(jià)計(jì)算時(shí)依據(jù)的一些分布假設(shè)是穩(wěn)定的.而且,由于其記錄大小相等,對(duì)時(shí)間的估計(jì)可以轉(zhuǎn)換為對(duì).10 次數(shù)的估計(jì),進(jìn)而轉(zhuǎn)中國煤化工.而在xML模型中,數(shù)據(jù)是有序的,數(shù)據(jù)聚集的方式不定,每個(gè)數(shù)據(jù)的大小相差懸,間的對(duì)應(yīng)關(guān)系沒有明顯的規(guī)律.簡單地沿用傳統(tǒng)的代價(jià)計(jì)算方法必然導(dǎo)致誤差的YHCNMH G+.(3)足夠的統(tǒng)計(jì)信 息孟小峰等:XML查詢優(yōu)化研究2071足夠精確的統(tǒng)計(jì)信息是保證查詢優(yōu)化有效性的基礎(chǔ);缺乏足夠的統(tǒng)計(jì)信息,是造成估計(jì)與實(shí)際情況產(chǎn)生誤差的重要因素.傳統(tǒng)的統(tǒng)計(jì)信息多是對(duì)值的統(tǒng)計(jì),如對(duì)平均值、最值、記錄個(gè)數(shù)等的統(tǒng)計(jì).這些對(duì)XML查詢是不夠的.XML數(shù)據(jù)本身缺乏模式的支持,對(duì)數(shù)據(jù)結(jié)構(gòu)信息的統(tǒng)計(jì)顯得更加重要XML數(shù)據(jù)中的數(shù)值分布在類似樹狀結(jié)構(gòu)的樹葉上,即使相同類型的數(shù)據(jù),由于半結(jié)構(gòu)化特點(diǎn),其分布情況也可能完全不同.因此需要把對(duì)結(jié)構(gòu)的統(tǒng)計(jì)信息和對(duì)值的統(tǒng)計(jì)信息結(jié)合到一起,才能得到足夠精確的統(tǒng)計(jì)信息.2 XML查詢處理結(jié)構(gòu)與傳統(tǒng)的關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理結(jié)構(gòu)類似,我們可以將XML查詢處理分為4個(gè)大的階段.如圖1所示.中間方框表示查詢處理步驟;左側(cè)方框?yàn)槭褂玫南嚓P(guān)技術(shù)或方法;右側(cè)方框?yàn)椴樵儍?yōu)化和執(zhí)行時(shí)需要的信息.Query←= Statistics, dataQuery algebraParse queryAlgebra expressionTransformation rule Logieal oplimizationPattern informationPhysical exccution strategy、Execution algorthim Query executionData, indexQuery resuts↓Fig.1 Query processing圖1查詢處理過程第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é)中將會(huì)介紹目前流行的幾種XML代數(shù).第2階段邏輯優(yōu)化,利用模式信息,規(guī)范和簡化內(nèi)部表達(dá)式.在這一階段中,系統(tǒng)不考慮實(shí)際數(shù)據(jù)的值和數(shù)據(jù)的存儲(chǔ)情況同一查詢請求,可以轉(zhuǎn)換成不同的等價(jià)表達(dá)方式,其中有-些比原有查詢更高效.為了進(jìn)行這種轉(zhuǎn)換,優(yōu)化器需要-些轉(zhuǎn)換規(guī)則,我們將在第4節(jié)中討論這些轉(zhuǎn)換規(guī)則.第3階段物理優(yōu)化，利用代價(jià)模型和統(tǒng)計(jì)信息計(jì)算不同表達(dá)式、不同算法的執(zhí)行代價(jià),選擇最低代價(jià)的查詢計(jì)劃.在這一-階段中,需要解決兩個(gè)問題:確定表達(dá)式執(zhí)行順序和決定每步操作的具體算法，對(duì)于XML查詢樹而言,首先需要將查詢表達(dá)式分解為可執(zhí)行的片斷,然后選擇合適的執(zhí)行順序和執(zhí)行算法并執(zhí)行.中間結(jié)果集的大小是決定執(zhí)行策略是否高效的關(guān)鍵因素與實(shí)際的數(shù)據(jù)分布密切相關(guān).綜合考慮數(shù)據(jù)的存儲(chǔ)、索引和數(shù)據(jù)值的分布情況,準(zhǔn)確地估計(jì)復(fù)雜路徑選擇性是其中的難點(diǎn)對(duì)于一個(gè)給定的執(zhí)行策略,通常會(huì)有多個(gè)可能的執(zhí)行算法,產(chǎn)生所有的執(zhí)行算法的組合造成選擇本身的代價(jià)過大因此,會(huì)有-些啟發(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ù)訪問算法.中國煤化工MHCNMHG3 XML 代數(shù)XML代數(shù)是對(duì)遵循一定數(shù)據(jù)模型的XML文檔集合的操作集.XML代數(shù)提供根據(jù)請求在文檔集合中選擇2072Journal of Sofware軟件學(xué)報(bào)Vol.17, No.10, October 2006一個(gè)或多個(gè)文檔或者文檔片段的能力.XML代數(shù)應(yīng)支持對(duì)查詢結(jié)果的重構(gòu).目前對(duì)XML代數(shù)的研究主要集中在對(duì)查詢代數(shù)的定義和從查詢語言到查詢代數(shù)的轉(zhuǎn)換方面.查詢代數(shù)定義查詢對(duì)象的類型,可以執(zhí)行的操作和不同操作之間的轉(zhuǎn)換規(guī)則.查詢語言經(jīng)分解轉(zhuǎn)換為由查詢代數(shù)的操作表達(dá)構(gòu)成的操作樹或者操作序列.不同的代數(shù)表達(dá)可以有相同的語義和執(zhí)行結(jié)果,構(gòu)成代價(jià)空間.3.1 XML代數(shù)定義目前產(chǎn)生很多種XML代數(shù),風(fēng)格各異，其主要思想來源于關(guān)系代數(shù)、面向?qū)ο蟠鷶?shù)、半結(jié)構(gòu)化代數(shù)和功能化編程語言等.由于篇幅有限,不能在這里----介紹,我們介紹其中具有代表性和影響力的幾種,表1列出了不同代數(shù)之間特點(diǎn)的比較.Table 1 Comparisons among XML query algebra表1 XML 查詢代數(shù)比較DataDocument Node Reference LogicalPhysical Transformationstructureordersupported operation_ operationruleAT&T Directed graphIBMDirected graphSXquery data modelSeldomLoreOEMTAXOracle,IBM和MS聯(lián)合提出的-一個(gè)XML代數(shù)標(biāo)準(zhǔn)是文獻(xiàn)[1].該標(biāo)準(zhǔn)把XML文檔看作有向標(biāo)記圖(如果忽略引用,可以看作有向標(biāo)記樹).用五元組G(V,E,A,R,O)表示.其中:V表示結(jié)點(diǎn),有兩種類型:element和value.E 表示element到element;A表示element到value,即屬性;R表示引用..上述3種為邊的類型.0表示次序在這個(gè)模型上,規(guī)定了導(dǎo)航、選擇、連接、構(gòu)造等操作,其導(dǎo)航操作提供在有向標(biāo)記圖中的遍歷操作,包括正向遍歷和反向遍歷;其連接操作語義類似關(guān)系代數(shù)中的連接操作,根據(jù)相同的值連接不同的文檔.該代數(shù)采用類似關(guān)系代數(shù)的表達(dá)形式.Bell Labs.和AT&T Labs.的Mary等人提出的XML查詢代數(shù)[,基于簡化的XSLT數(shù)據(jù)模型},增加了引用結(jié)點(diǎn),合并了屬性和元素結(jié)點(diǎn),刪除了注釋結(jié)點(diǎn)其主要思想來源于曾用于半結(jié)構(gòu)化和面向?qū)ο髷?shù)據(jù)庫的代數(shù)-嵌套關(guān)系代數(shù),并增加了對(duì)正則表達(dá)式的操作.在嵌套關(guān)系中,數(shù)據(jù)由多個(gè)元組和多個(gè)鏈表組成,并可多級(jí)嵌套,其采用list comprehension方法表達(dá)導(dǎo)航、笛卡爾積、嵌套和連接操作.List comprehension根據(jù)-系列過濾和generator操作,得到滿足條件的結(jié)果鏈表.Generator操作與導(dǎo)航操作相對(duì)應(yīng).該代數(shù)還支持結(jié)構(gòu)遞歸等程序語言特點(diǎn)用Haskell程序語言作為表達(dá)形式.上述兩種代數(shù)還僅停留在邏輯層次,沒有考慮與之相對(duì)應(yīng)的物理代數(shù)和查詢優(yōu)化策略，其優(yōu)勢是具有較高的描述性和豐富的語義與查詢語言有密切的轉(zhuǎn)換關(guān)系;但其操作中對(duì)路徑的處理并不完善,形成過多的遞歸結(jié)構(gòu)叫或者遍歷操作叫,給下一步的優(yōu)化帶來困難,但其處理XML查詢的方法和思路被后來的XML代數(shù)規(guī)則大量采用.基于文獻(xiàn)[2,3]等,W3C于2001年公布了一- 個(gè)XML查詢代數(shù)標(biāo)準(zhǔn)XQuery 1.0 Formal Semanticsl(',用于規(guī)范查詢語言語義.該標(biāo)準(zhǔn)遵循簡化的XQuery 1.0和Xpath 2.0 Data Mode!'l].比照關(guān)系代數(shù)給出了XML數(shù)據(jù)模型的投影、選擇和連接等操作的定義,還引入結(jié)構(gòu)遞歸、條件判斷等編程語言的概念.Formal Semantics的一個(gè)特點(diǎn)是代數(shù)表達(dá)與XQuery查詢語言相同,成為XQuery的核心語法;另-一個(gè)特點(diǎn)是操作有不同的層次,高層次的操作可以轉(zhuǎn)換為低層次的操作.標(biāo)準(zhǔn)中還給出了少量表達(dá)式轉(zhuǎn)換規(guī)則,有待近一步擴(kuò)充.目前已經(jīng)有了應(yīng)用該標(biāo)準(zhǔn)的XML查詢引擎,如Galaxl6.Standford大學(xué)開發(fā)的XML數(shù)據(jù)庫Lore系統(tǒng)[7針對(duì)系統(tǒng)中國煤化工青況,提出了-套獨(dú)特的代數(shù)操作,包括邏輯代數(shù)、物理代數(shù)和相應(yīng)的轉(zhuǎn)換規(guī)則.Lo:MHCNMH(了查詢優(yōu)化方法同,但由于代數(shù)操作定義過多地依賴于Lore本身獨(dú)特的數(shù)據(jù)存儲(chǔ)和系引僅不,以八雙很難應(yīng)用于其他系統(tǒng).Timber數(shù)據(jù)庫[9]中應(yīng)用的TAX代數(shù)["0,其數(shù)據(jù)模型為無序的樹的集合,樹中的數(shù)據(jù)是有序的.直接針對(duì)樹和孟小峰等:XML查詢優(yōu)化研究2073樹枝規(guī)定了一系列操作無須中間結(jié)構(gòu)的轉(zhuǎn)換.把XML數(shù)據(jù)模式看作樹,把查詢語句也看作樹,二者之間作模式匹配，得到滿足查詢樹條件的結(jié)果樹集合.IAX在處理連接操作時(shí)對(duì)操作的順序未做明確規(guī)定不適應(yīng)嚴(yán)格要求文檔順序的情況.XAL"基于集合概念構(gòu)造了邏輯代數(shù)操作集,其操作分為3種:抽取操作從XML文檔中獲得必要的數(shù)據(jù),如選擇、投影等;元操作控制表達(dá)式求值過程,并非針對(duì)XML數(shù)據(jù)的抽取或者構(gòu)造操作,而是為其他操作符準(zhǔn)備輸入或者控制其他操作的操作,如映射、迭代等;構(gòu)造操作用于構(gòu)造查詢結(jié)果.XAL為查詢優(yōu)化提供了一組啟發(fā)式轉(zhuǎn)換規(guī)則.其他如XOM代數(shù)(!21,是完整的操作集,包含6種對(duì)象操作,但不支持優(yōu)化;OPAL代數(shù)13]基于半結(jié)構(gòu)化數(shù)據(jù)模型,操作對(duì)象為多個(gè)鏈表,將有限狀態(tài)自動(dòng)機(jī)用于生成執(zhí)行計(jì)劃;還有SAL等104-17.根據(jù)代數(shù)的操作方式,可將上述不同的方法分為兩種:一種是面向集合的代數(shù),其操作對(duì)象是某種類型的集合,如樹的集合、值的集合等.這種方法具有很好的優(yōu)化基礎(chǔ),但可能丟失數(shù)據(jù)的順序;另一種稱為導(dǎo)航的代數(shù),其操作對(duì)象是單個(gè)的數(shù)據(jù)這種方法不利于進(jìn)一步的優(yōu)化.代數(shù)定義應(yīng)是邏輯操作與物理操作的有機(jī)結(jié)合.但目前的XML代數(shù)研究或是把他們混合在一起,或是雖然分開但缺乏相應(yīng)的轉(zhuǎn)換規(guī)則.早期對(duì)XML代數(shù)的研究工作重點(diǎn)在于規(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)在任意地方.謂詞是有作用域的,同--個(gè)謂詞在不同的地方會(huì)產(chǎn)生不同的查詢結(jié)果基于集合的代數(shù)需要將嵌套的查詢轉(zhuǎn)換為邏輯樹形式,不可避免地面臨嵌套結(jié)構(gòu)的非嵌套化問題.雖然在關(guān)系數(shù)據(jù)庫中有一些方法可以借鑒,但由于XML數(shù)據(jù)結(jié)構(gòu)的復(fù)雜性,解決這個(gè)問題變得更加困難.其次是XML數(shù)據(jù)的有序性問題除非查詢語句特別指定,否則應(yīng)該保持結(jié)點(diǎn)在源文檔中的結(jié)點(diǎn)順序.而原來- -些處理連 接的算法,比如排序連接、Hash連接等會(huì)打亂結(jié)點(diǎn)順序,在連接完成后,需要對(duì)連接結(jié)果做- -個(gè)額外的根據(jù)結(jié)點(diǎn)順序的排序操作如果用nest-loop連接算法，則可以省去這趟額外的排序在進(jìn)行代價(jià)估計(jì)的過程中,這個(gè)額外的排序操作要被考慮在內(nèi),這就給進(jìn)行查詢優(yōu)化的過程帶來新的考慮因素.-種可能的解決方法是在所有操作中，忽略結(jié)點(diǎn)的有序性,在最后構(gòu)造結(jié)果的時(shí)候再對(duì)結(jié)點(diǎn)按照文檔順序排序.究竟是使用nestloop,還是最后增加額外的排序的方法,這是查詢優(yōu)化的一個(gè)研究點(diǎn).最后,不同的代數(shù)標(biāo)準(zhǔn)在XML代數(shù)研究中一個(gè)值得重視的問題是:目前已經(jīng)出現(xiàn)了-些查詢代數(shù)標(biāo)準(zhǔn),這些標(biāo)準(zhǔn)在風(fēng)格上相去甚遠(yuǎn),很難有共通性.而對(duì)執(zhí)行方法的研究還遠(yuǎn)遠(yuǎn)不夠,不能形成完整的系統(tǒng).而且從邏輯代數(shù)到物理代數(shù)的轉(zhuǎn)換也將是未來研究的一個(gè)重要問題.3.2 復(fù)雜路徑表達(dá)式分解目前的XML查詢語言有很多,如XatlI81,Queuy19,XMLQL*Q,Q"Quit2等它們的一個(gè)共同的特點(diǎn)就是對(duì)復(fù)雜路徑表達(dá)式的支持.路徑表達(dá)式分解是根據(jù)一定的轉(zhuǎn)換規(guī)則,把用查詢語句表達(dá)的、復(fù)雜的、不確定的路徑表達(dá)式轉(zhuǎn)換為簡單的、明確的、系統(tǒng)可識(shí)別的方式，如XML代數(shù)路徑表達(dá)式分解是查詢轉(zhuǎn)換的難點(diǎn)也是查詢優(yōu)化的重要一步,是代價(jià)估計(jì)的前提條件根據(jù)不同的規(guī)則,路徑表達(dá)式可能分解為不同的等價(jià)形式,其中有的代價(jià)高,有的代價(jià)低,形成代價(jià)空間.路徑分解的原則是能夠產(chǎn)生有限的代價(jià)空間,有利于利用分解的結(jié)果搜索代價(jià)最小的執(zhí)行方案.在路徑分解時(shí),有兩種不同的思路:--種思路是把路徑細(xì)分為兩兩的祖牛后代成少子對(duì)t如lore,1sS2)等.這樣做分解算法簡單,可利用數(shù)據(jù)物理存儲(chǔ)信息,分解的結(jié)果容易MYH中國煤化工系統(tǒng)提供的各種索引.如果查詢語句中出現(xiàn)通配符(如*,2,/,可以利用索引直接C N M H G息確定通配符所代表的各種可能情況擴(kuò)展路徑.經(jīng)過分解,路徑表達(dá)式轉(zhuǎn)換為連接、投影、選擇、導(dǎo)航等不同的代數(shù)運(yùn)算;另一種思路叫9是將復(fù)雜路徑表達(dá)式用樹的方式表示:從根開始,在樹中搜索最長的確定路徑(不含*或/I稱為一次分2074Journal of Sofware軟件學(xué)報(bào)Vol.17, No.l0, October 2006解,其路徑構(gòu)成樹的一個(gè)子串.以這個(gè)點(diǎn)為起點(diǎn)用上述原則再分解路徑,得到確定路徑(子串)的集合,稱為- -個(gè)最小分解.在XML文檔的查詢中,確定路徑的查詢是相對(duì)容易的;而不確定路徑的查詢是比較困難的,尤其是在沒有模式或索引的情況下，可能要將中間結(jié)果合并才能得到全部的結(jié)果.將復(fù)雜的、不確定的路徑分解為確定的、簡單的路徑處理這種分解方法在沒有模式信息的情況下處理不確定路徑具有一定的優(yōu)勢.4邏輯優(yōu)化在傳統(tǒng)數(shù)據(jù)庫技術(shù)中,邏輯優(yōu)化是指通過一系列轉(zhuǎn)換規(guī)則,將原始的查詢表達(dá)式轉(zhuǎn)換為等價(jià)且更高效的形式，關(guān)系代數(shù)表達(dá)式求解時(shí),操作順序是影響效率的關(guān)鍵.因此,邏輯優(yōu)化研究的重點(diǎn)并不在于對(duì)冗余操作的分析,而是對(duì)操作順序的調(diào)整.而XML代數(shù)的核心是由路徑表達(dá)式轉(zhuǎn)換的查詢樹,查詢效率依賴于查詢樹的規(guī)模.因此,查詢樹的最小化是XML邏輯優(yōu)化研究的重點(diǎn),也是目前研究的熱點(diǎn)問題.而對(duì)操作順序的調(diào)整因?yàn)楦嗟匾蕾囉谖锢泶鎯?chǔ)的情況,因此與物理優(yōu)化相關(guān)聯(lián).從層次上看,邏輯優(yōu)化可分為兩個(gè)層次:語法層次和語義層次.語法層次的優(yōu)化是指不依靠任何其他信息,獨(dú)立地分析查詢表達(dá)式中分支或結(jié)點(diǎn)間的邏輯包含關(guān)系,刪除冗余部分;語義層次的優(yōu)化是指通過數(shù)據(jù)庫提供的模式信息，如DTD,XML Schema等,或者語義包含、結(jié)構(gòu)包含等完整性約束,查找查詢表達(dá)式中的冗余分支或結(jié)點(diǎn)下面的例子進(jìn)一步說明二者之間的區(qū)別.若有如下的XQuery查詢表達(dá)式:for $a in reference/book,for $b in Sa/author, Sc in $a/author/ name, $d in $a/author/emailwhere $b and $c and Sdreturn 其Pattern Tree(以下簡稱PTQ)如圖2(a)所示,其中,實(shí)心圓為查詢返回結(jié)點(diǎn)若數(shù)據(jù)滿足Sc,同時(shí)必然滿足$b,$b分支對(duì)查詢返回結(jié)果沒有任何影響,是冗余結(jié)點(diǎn)我們稱這種冗余結(jié)點(diǎn)為語法冗余結(jié)點(diǎn)經(jīng)語法優(yōu)化后的PTQ如圖2(b)所示.若從模式可知任- - author 均有name,則v6為冗余結(jié)點(diǎn)我們稱這種冗余結(jié)點(diǎn)為語義冗余結(jié)點(diǎn)經(jīng)語義優(yōu)化后的PTQ如圖2(c)所示.凹0 ReferenceO Reference0 ReferenceBook以● Book的●Book以6 Author s只AuthorVs a Authorvs 8 AuthorVvs OE-mailngOName vd E-mail V6 ONamevsO E-maila)(b(C)Fig.2 Syntax and semantic optimization圖2語法優(yōu)化和語 義優(yōu)化下面我們分別介紹語法優(yōu)化和語義優(yōu)化的研究現(xiàn)狀.4.1語法優(yōu)化.對(duì)PTQ 語法優(yōu)化問題基于對(duì)路徑等價(jià)性問題[25 281的研究.最早提出XPath 最小化的Woodl29)指 出:- -個(gè)Xpath可以表示為合取范式，對(duì)XPath等價(jià)性檢查的復(fù)雜度等價(jià)干對(duì)取蘆式的筆價(jià)性檢查.而這已經(jīng)證明是一個(gè)NP完全問題.如果對(duì)XPath路徑表達(dá)式的復(fù)雜程度加以一中國煤化工的復(fù)雜度可以達(dá)到多項(xiàng)式級(jí).目前已經(jīng)提出了對(duì)不同類型的PTQ的最小化方法.MYHCNMHG(1) 簡單PTQ{,D,*}文獻(xiàn)[29]中提出了對(duì)只包含{/,0,*}的簡單路徑的最小化方法其思想為:設(shè)原始PTQ為P,在所有與之等價(jià)孟小峰等:XML查詢優(yōu)化研究2075的PTQ中找到Q,使得e中的結(jié)點(diǎn)個(gè)數(shù)|NQ[最小,則Q為P的最小化PTQ.這種方法的關(guān)鍵是通過對(duì)包含映射(containment mapping)的判斷完成PTQ的等價(jià)性判斷.不存在祖先后代關(guān)系(/)的簡單PTQ的最小化PTQ為其子樹.查找等價(jià)PTQ的范圍限制在其子樹的范圍內(nèi),是保證最小化算法的復(fù)雜度為多項(xiàng)式級(jí)的關(guān)鍵因素.文獻(xiàn)[22]中給出了復(fù)雜性證明,雖然并未給出算法細(xì)節(jié).(2) PTQ/{,/,Q]}文獻(xiàn)[30]提出了PTQ的CIM(constraint independent minimization)算法與文獻(xiàn)[29]相同,其算法的基礎(chǔ)也是包含映射路徑中缺少“*”的PTQ的最小化問題,仍舊可以在其子樹范圍內(nèi)解決.CIM算法的思想為:從葉結(jié)點(diǎn)開始,判斷結(jié)點(diǎn)在PTQ中是否冗余:若某結(jié)點(diǎn)是冗余結(jié)點(diǎn)則刪除這個(gè)結(jié)點(diǎn),繼續(xù)處理其他葉結(jié)點(diǎn)直到所有葉結(jié)點(diǎn)判斷完畢;若PTQ中結(jié)點(diǎn)個(gè)數(shù)為n,則CIM算法的最大復(fù)雜度為0(n).文獻(xiàn)[31]提出了一-種 最大復(fù)雜度為0()的改進(jìn)算法,通過結(jié)點(diǎn)間的二元關(guān)系Simultion 判斷冗余性改進(jìn)的CIM算法與CIM算法最大的不同點(diǎn)在于:前者只關(guān)心后代結(jié)點(diǎn)之間是否相同;而后者還要關(guān)心祖先結(jié)點(diǎn)之間是否相同.改進(jìn)的CIM算法通過正向遍歷查找冗余結(jié)點(diǎn),如果某結(jié)點(diǎn)的一個(gè)兒子結(jié)點(diǎn)與另外兒子結(jié)點(diǎn)之間有Simulation關(guān)系，則這個(gè)兒子結(jié)點(diǎn)為冗余結(jié)點(diǎn)這樣,在一次遍 歷可以對(duì)多個(gè)結(jié)點(diǎn)的冗佘性進(jìn)行判斷,從而提高了PTQ最小化的效率.(3) PTQ/{,/,D,*}與限制條件下PTQ所不同的是,普遍意義下的PTQ在語法優(yōu)化時(shí)遇到的一個(gè)關(guān)鍵問題是:最小化PTQ并非原始PTQ的子樹,而是由以原始PTQ的根為根,連接多個(gè)PTQ子樹構(gòu)成的PTQ.其中每個(gè)子樹均為原始子樹的最小化部分.這個(gè)問題也是導(dǎo)致其復(fù)雜度上升的關(guān)鍵.文獻(xiàn)[32]給出普遍意義下的PTQ最小化算法.其算法思想是:遞歸地在原始PTQ的子樹中查找最小子樹并連接它們,在這個(gè)過程中冗余的分支被刪除了.文獻(xiàn)[32]證明其算法的復(fù)雜度為NP完全,并指出:在對(duì)PTQ的分支個(gè)數(shù)加以--定限制的情況下,改進(jìn)的算法復(fù)雜度可以達(dá)到多項(xiàng)式級(jí)但我們有理由相信,這樣的改進(jìn)意義并不大,因?yàn)檫@要求用戶在寫查詢語句時(shí)必須注意查詢的分支情況,否則將導(dǎo)致某些查詢無法優(yōu)化.目前,語法優(yōu)化都以判斷結(jié)點(diǎn)之間的包含映射關(guān)系為基礎(chǔ),分析路徑等價(jià)性在查詢樹中不斷地修剪冗余的分支或結(jié)點(diǎn),達(dá)到減少查詢樹規(guī)模的目的.普遍意義的PTQ語法優(yōu)化是一個(gè)NP完全問題,研究者通過對(duì)pTQ復(fù)雜度加以一定限制,提出 了多種高效的算法.語法優(yōu)化不涉及XML模式信息,可以利用模式信息進(jìn)一步簡化PTQ,這種優(yōu)化稱為語義優(yōu)化.4.2語義優(yōu)化最早提出語義優(yōu)化的是關(guān)系數(shù)據(jù)庫系統(tǒng),利用表格屬性值之間的約束關(guān)系把查詢表達(dá)式轉(zhuǎn)換為等價(jià)但更高效的形式.chase方法是其中的代表其思想為:把完整性約束作為冗余條件插入到查詢表達(dá)式中,與已存在的冗余操作合并,使得組合后的條件符合某些事先定義好的等價(jià)轉(zhuǎn)換規(guī)則,利用這些等價(jià)轉(zhuǎn)換規(guī)則重寫查詢表達(dá)式以達(dá)到優(yōu)化的目的.這是一個(gè)巧妙的先膨脹再收縮的方法.但是,應(yīng)用Chase方法于XML查詢的語義優(yōu)化時(shí)面臨下述嚴(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é)點(diǎn)可以出現(xiàn)在不同的位置,可以有不同的子結(jié)點(diǎn).傳統(tǒng)的轉(zhuǎn)換規(guī)則的應(yīng)用方法不適應(yīng)這種情況,引發(fā)的問題就是產(chǎn)生遞歸的轉(zhuǎn)換,導(dǎo)致路徑的無限增長.查詢語句的復(fù)雜性:SQL語句清晰、明確,關(guān)系代數(shù)操作均為輸入?yún)⑵擅鞔_的一中國煤化工=運(yùn)算.而XML查詢語句中包含/等不確定因素,并以包含多個(gè)分支長路徑為特點(diǎn)EML語義優(yōu)化.基于上述挑戰(zhàn),一些研究者 提出改進(jìn)的Chase 方法,而另一MYHC N M H G的角度出發(fā),研究XML查詢的語義優(yōu)化問題.(1)改進(jìn)的 Chase方法2076Journal of Sofware軟件學(xué)報(bào)Vol.17, No.10, October 2006Wood等人(29]最早將Chase 方法引入簡單XPath 語義優(yōu)化.文獻(xiàn)[29]在DTD上定義了3種結(jié)構(gòu)約束關(guān)系,分別為兒子約束、父親約束和兄弟約束.若某個(gè)查詢樹中結(jié)點(diǎn)n為上述約束關(guān)系中的主體,且其約束的結(jié)點(diǎn)不在查詢樹中,則在查詢樹中相應(yīng)位置加入客體結(jié)點(diǎn).當(dāng)所有約束關(guān)系應(yīng)用完畢,再用語法優(yōu)化的方法對(duì)查詢樹進(jìn)行修剪,得到最小化查詢樹.為了討論簡單起見,文獻(xiàn)[29]中方法只適用于不包含“*”和/”的簡單路徑,其復(fù)雜度為多項(xiàng)式級(jí).文獻(xiàn)[30]則認(rèn)為,XML數(shù)據(jù)中的結(jié)構(gòu)完整性約束可用兒子約束、后代約束和類型約束概括.為了得到正確的優(yōu)化結(jié)果,他們對(duì)Chase方法做了3個(gè)方面的改進(jìn):首先,假設(shè)約束集合是閉包的;其次,為了保證優(yōu)化能夠完成,約束條件只應(yīng)用于PTQ中原有結(jié)點(diǎn),如果某結(jié)點(diǎn)是由于應(yīng)用某約束條件加入PTQ的,則不對(duì)其應(yīng)用任何約束條件;最后,由于應(yīng)用約束條件加入的結(jié)點(diǎn)是冗余的,因此,需要在算法結(jié)束時(shí)刪除這些臨時(shí)結(jié)點(diǎn).ACIM算法分為3個(gè)步驟:首先,應(yīng)用約束集合中的約束條件放大PTQ;然后,應(yīng)用CIM算法語法刪除冗余結(jié)點(diǎn),在刪除時(shí)保證不檢查被加入臨時(shí)結(jié)點(diǎn)的冗余性;最后,刪除所有在第-步中加入的臨時(shí)結(jié)點(diǎn)若PTQ中結(jié)點(diǎn)個(gè)數(shù)為n,則ACIM算法的最壞計(jì)算復(fù)雜度為0(n).-些冗余結(jié)點(diǎn)是容易識(shí)別的,如果提前刪除這些容易識(shí)別的冗余結(jié)點(diǎn)然后再應(yīng)用ACIM算法,可以有效地提高優(yōu)化的效率.算法CDM在PTQ中遍歷地查找并刪除這樣的冗余結(jié)點(diǎn)其計(jì)算復(fù)雜度為0(n3).實(shí)驗(yàn)證明,在使用ACIM之前使用CDM,比直接應(yīng)用ACIM可更為有效地節(jié)省時(shí)間..文獻(xiàn)[31]在文獻(xiàn)[30]的基礎(chǔ)上擴(kuò)充了子類約束，并利用語法優(yōu)化中的TPQSimulation和TPQMinimization改進(jìn)了ACIM算法,使計(jì)算復(fù)雜度達(dá)到0(n).(2)基于 DTD的路徑等價(jià)類方法文獻(xiàn)[34]提出了一種基于模式的XPath 路徑表達(dá)式的語義優(yōu)化方法.其思想是:把XML文檔模式(DTD)劃分為若干個(gè)路徑等價(jià)類,每個(gè)類中的路徑等價(jià);將XPath轉(zhuǎn)換為由簡單路徑構(gòu)成的合取范式形式,利用路徑等價(jià)類中的最短路徑代替表達(dá)式中的路徑.通過這種方法,可以實(shí)現(xiàn)3個(gè)方面的優(yōu)化:首先,刪除冗余的謂詞條件;其次簡化路徑;最后,判斷表達(dá)式的條件是否滿足如果某個(gè)分支的條件不滿足模式中的約束關(guān)系則整個(gè)表達(dá)式的查詢結(jié)果為空.整個(gè)優(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)點(diǎn)是:語法優(yōu)化與語義優(yōu)化相結(jié)合,優(yōu)化過程無須對(duì)PTQ進(jìn)行轉(zhuǎn)換.問題是難以保證徹底的優(yōu)化:首先,PTQ中存在非葉冗余結(jié)點(diǎn),而語法優(yōu)化只能在刪除葉結(jié)點(diǎn)后,讓非葉結(jié)點(diǎn)變?yōu)槿~結(jié)點(diǎn)的情況下才能判斷其冗余性.加入約束條件后的PTQ. 語法優(yōu)化,不能在不刪除葉結(jié)點(diǎn)的情況下,判斷非葉結(jié)點(diǎn)的冗余性;其次,膨脹后的PTQ難以壓縮,采用對(duì)轉(zhuǎn)換規(guī)則加以-定限制的方法限制膨脹后PTQ規(guī)模的方法,會(huì)導(dǎo)致優(yōu)化的不徹底.目前改進(jìn)的Chase方法都是針對(duì)一定復(fù)雜程度的PTQ的優(yōu)化策略,普遍意義上的PTQ的語義優(yōu)化研究還需深入;最后，從DTD中獲得的約束條件并不充分,這也是導(dǎo)致優(yōu)化不徹底的一個(gè)因素. 如何抽取更多的語義約束條件,是未來研究的- -個(gè)重要問題.基于DTD的優(yōu)化方法的優(yōu)點(diǎn)是:不但能夠刪除冗余分支,還能夠縮短路徑長度和直接判斷路徑是否滿足.問題主要是:首先,需要對(duì)PTQ進(jìn)行轉(zhuǎn)換，占用大量優(yōu)化時(shí)間;其次,需要不確定路徑的確定化,這實(shí)際上也是一-種路徑膨脹,難以保證優(yōu)化的結(jié)果小于優(yōu)化之前.兩種方法都需要首先擴(kuò)大路徑規(guī)模造成優(yōu)化的不徹底和效率的喪失,這是目前語義優(yōu)化面臨的一一個(gè)重要問題5物理優(yōu)化邏輯優(yōu)化的結(jié)果是一個(gè)或多個(gè)查詢樹.如何確定其中不同查詢片斷的執(zhí)行次序,是XML物理優(yōu)化的核心問題.確定執(zhí)行次序的主要因素是中間結(jié)果集的大小復(fù)雜路徑表中國煤化工計(jì)結(jié)果集規(guī)模的其主導(dǎo)思想是:統(tǒng)計(jì)XML數(shù)據(jù)的分布情況,基于一定假設(shè)估計(jì)路YHCN MH G小這種方法一般忽略執(zhí)行算法的不同和數(shù)據(jù)的物理存儲(chǔ).本節(jié)從統(tǒng)計(jì)信息抽取、存儲(chǔ)、壓縮、維護(hù)和統(tǒng)計(jì)信息計(jì)算等幾個(gè)方面論述目前這一技術(shù)的發(fā)展情況和所面臨的問題.孟小峰等:XML查詢優(yōu)化研究20775.1代價(jià)估計(jì)方法研究代價(jià)估計(jì)是對(duì)查詢物理運(yùn)算時(shí)間的估計(jì).目前,代價(jià)計(jì)算方法主要有3種:基于參數(shù)的方法、基于取樣的方法和基于統(tǒng)計(jì)信息計(jì)算的方法基于參數(shù)的方法31無須統(tǒng)計(jì)數(shù)據(jù)信息，根據(jù)數(shù)據(jù)分布情況假定其滿足包含某些參數(shù)的分布函數(shù),通過計(jì)算函數(shù)的值估計(jì)查詢計(jì)劃的執(zhí)行代價(jià).這種方法在處理有規(guī)律分布的數(shù)據(jù)(如學(xué)生成績)時(shí),可以大量節(jié)省統(tǒng)計(jì)信息空間和I/O代價(jià),但對(duì)分布無明顯規(guī)律的數(shù)據(jù)會(huì)有很大的誤差;基于取樣的方法16.3)也無須統(tǒng)計(jì)數(shù)據(jù)信息,做法是從數(shù)據(jù)集中提取具有代表性的樣本,比較不同的查詢計(jì)劃的執(zhí)行情況,獲得代價(jià)最小的方案.這種方法的精確性決定于取樣的代表性.最簡單的方法是隨機(jī)取樣, -些優(yōu)化的方法根據(jù)數(shù)據(jù)的密度取樣取樣方法的缺點(diǎn)是代價(jià)估計(jì)本身占用時(shí)間可能很大;最常用也是研究最多的方法是基于統(tǒng)計(jì)信息的方法8,需要統(tǒng)計(jì)估計(jì)所用的各種信息,利用統(tǒng)計(jì)信息計(jì)算不同方案的執(zhí)行代價(jià).這種方法的精確性取決于統(tǒng)計(jì)信息的正確性.但是統(tǒng)計(jì)信息過大又會(huì)導(dǎo)致統(tǒng)計(jì)時(shí)間過長.利用有限的時(shí)間和空間得到相對(duì)小的執(zhí)行方案,是代價(jià)統(tǒng)計(jì)的基本原則.不同的系統(tǒng)支持的物理運(yùn)算算法不同,代價(jià)模型也不同.在關(guān)系模型中,進(jìn)行代價(jià)估計(jì)時(shí)有兩個(gè)通用的前提:獨(dú)立性假設(shè)和均勻分布假設(shè)前者是指各謂詞之間沒有相互依賴關(guān)系;后者是指如果關(guān)系在某個(gè)屬性上沒有直方圖,則認(rèn)為該屬性的各值在數(shù)據(jù)庫中均勻出現(xiàn).XML數(shù)據(jù)的不規(guī)則性是對(duì)傳統(tǒng)統(tǒng)計(jì)信息方法的重要挑戰(zhàn)其數(shù)據(jù)分布情況使得-些傳統(tǒng)分布假設(shè)難以成立.在XML中相同名字的結(jié)點(diǎn)可能在同-一個(gè)文檔的不同部分出現(xiàn)但卻具有截然不同的語義如同為name結(jié)點(diǎn),在person下和在city下出現(xiàn)其意義就完全不同,這可以稱為元素之間的結(jié)構(gòu)依賴性;同時(shí),在XML文檔中,嵌套在不同祖先下的同類結(jié)點(diǎn)的個(gè)數(shù)差別也很大,如book結(jié)點(diǎn)下的author個(gè)數(shù)是不確定的,這可以稱為元素之間的結(jié)構(gòu)相關(guān)性.為了達(dá)到所需的代價(jià)估計(jì)精度,需要更多的統(tǒng)計(jì)信息而結(jié)構(gòu)的復(fù)雜性又為獲得相對(duì)精確的統(tǒng)計(jì)信息帶來存儲(chǔ)和計(jì)算上的困難.XML的有序性制約了轉(zhuǎn)換規(guī)則的靈活性.所有這些問題,都使得在XML中采用傳統(tǒng)的代價(jià)估計(jì)方法不切實(shí)際，會(huì)帶來很大的誤差.針對(duì)XML數(shù)據(jù)的特點(diǎn),我們應(yīng)該尋求一種新的代價(jià)估計(jì)方法.5.1.1代價(jià)模型查詢計(jì)劃的執(zhí)行代價(jià)主要來自3方面的因素:CPU計(jì)算代價(jià)、I/O代價(jià)和數(shù)據(jù)傳輸代價(jià).CPU,磁盤和網(wǎng)絡(luò)的速度差距懸殊.當(dāng)不考慮數(shù)據(jù)的分布性因素時(shí),影響代價(jià)的決定性因素是IO代價(jià).I/0代價(jià)受眾多因素制約,主要來自3個(gè)方面: -是數(shù)據(jù)庫系統(tǒng)參數(shù),如頁面大小、內(nèi)存使用情況等;二是數(shù)據(jù)集本身因素,如數(shù)據(jù)存儲(chǔ)空間大小、索引情況、每個(gè)元素占用空間情況和元素的聚集情況等;三是查詢請求因素,如查詢條件的選擇性等.目前,對(duì)XML代價(jià)模型的研究并不充分,代價(jià)模型相對(duì)簡單，這也是造成代價(jià)估計(jì)誤差的一個(gè)原因.Lore的代價(jià)模型沒有考慮聚集情況,不能判定不同的數(shù)據(jù)是否在同一頁面上,因此,其假設(shè)每次I/O操作只能獲得-一個(gè)對(duì)象,把對(duì)I0時(shí)間的估計(jì)轉(zhuǎn)換為對(duì)中間結(jié)果大小的估計(jì)由于Lore中數(shù)據(jù)本身無聚集,這種方法可以獲得較好的效果,但對(duì)其他XML數(shù)據(jù)庫系統(tǒng)參考意義并不大.文獻(xiàn)[39]提出了一種新的代價(jià)模型,其基本思想是利用查詢反饋信息來調(diào)整參數(shù).如圖3所示,在用戶提交查詢之前,先人工找出影響查詢執(zhí)行時(shí)間的特征,再利用線性回歸模型計(jì)算出各個(gè)特征對(duì)查詢代價(jià)的影響系數(shù),即得到-一個(gè)形如cos(+.,..)的函數(shù)模型,當(dāng)用戶提交查詢時(shí),利用函數(shù)和事先統(tǒng)計(jì)的特征值進(jìn)行計(jì)算.但是,文中提出的方法只是針對(duì)CPU代價(jià)估計(jì)的,沒有擴(kuò)展到1/o代價(jià)的估計(jì);而且只考慮了一-個(gè) XNav操作符,至于如何擴(kuò)展到其他情況,文獻(xiàn)[39]中并未提及.人工抽取特征具有主觀性,如何讓系統(tǒng)自動(dòng)地抽取特征是下一步研究的重點(diǎn).User queriesOptimizerQuery planRuntime engineTraining queriesCoMET| Training d中國煤化工:fYHCNMHGFig.3 CoMET optimization system圖3 CoMET 優(yōu)化系統(tǒng)2078Journal of Sofware軟件學(xué)報(bào)Vol.17, No.10, October 20065.1.2代價(jià)空間搜索 技術(shù)代價(jià)空間搜索算法首先通過某種計(jì)算方法量化代價(jià)空間、構(gòu)造搜索函數(shù),根據(jù)函數(shù)值的變化判斷是否繼續(xù)搜索在眾多的空間搜索技術(shù)中,最簡單的是隨機(jī)搜索方法,隨機(jī)地或者按照某個(gè)順序在搜索空間中計(jì)算代價(jià).但這種方法效率低下,在實(shí)際的系統(tǒng)中很少被采用,爬山算法是應(yīng)用廣泛的一種搜索算法,在以某步長對(duì)函數(shù)進(jìn)行搜索的過程中按照逐步接近的方式,定位局部最優(yōu)執(zhí)行計(jì)劃,搜索的效率與初始值和步長相關(guān)當(dāng)搜索函數(shù)非單調(diào)時(shí),這種方法找到的是局部極值,而非全局最值遺傳算法是解決局部最優(yōu)的一種新穎的空間搜索方法,用雜交的方法搜索不同的最優(yōu)執(zhí)行計(jì)劃，適用于有多個(gè)極值的搜索函數(shù).這種方法在關(guān)系數(shù)據(jù)庫查詢優(yōu)化中有一定的應(yīng)用意義,在XML查詢優(yōu)化的代價(jià)空間搜索技術(shù)中應(yīng)用遺傳算法的難點(diǎn)在于適應(yīng)度函數(shù)的構(gòu)造.單個(gè)查詢物理計(jì)劃形成的代價(jià)空間可能非常龐大,尤其是對(duì)路徑很長的情況，其代價(jià)空間呈冪次級(jí)增長.為了減少代價(jià)估計(jì)時(shí)間,需要利用啟發(fā)性規(guī)則約束代價(jià)空間.Lore的做法是:分別將每一個(gè)邏輯操作轉(zhuǎn)換為最優(yōu)物理子計(jì)劃,并在轉(zhuǎn)換時(shí)應(yīng)用啟發(fā)性規(guī)則.例如:TargetSet操作只在路徑表達(dá)式的起始結(jié)點(diǎn)是標(biāo)記名并且只在路徑結(jié)束結(jié)點(diǎn)上有變量約束時(shí)使用;當(dāng)查詢中有多個(gè)路徑表達(dá)式時(shí),不改變其間的順序值得注意的一條規(guī)則是選擇操作總在最后做.這條規(guī)則和關(guān)系查詢優(yōu)化的啟發(fā)性規(guī)則正好相反.這是由于在Lore中,選擇運(yùn)算總是基于變量綁定運(yùn)算.在XML代價(jià)估計(jì)研究中,路徑表達(dá)式選擇性代價(jià)估計(jì)是核心問題,也是在XML查詢優(yōu)化研究中份量最重的一個(gè)領(lǐng)域,值得我們特別關(guān)注在第5.2節(jié)中我們將做專門的論述.5.2路徑表達(dá)式選擇性代價(jià)估計(jì)XML路徑表達(dá)式可視為一棵樹,其中的一個(gè)主支為從起點(diǎn)到目標(biāo)點(diǎn)的主路徑,其余分支為約束主支的謂詞條件(如圖4所示)，表示為P=p.]....I.J.其中:1為結(jié)點(diǎn)名;p:為謂詞默認(rèn)存在量詞布爾表達(dá)式.路徑表達(dá)式的選擇性估計(jì)是對(duì)滿足分支條件的主支數(shù)據(jù)個(gè)數(shù)的估計(jì).對(duì)XML路徑表達(dá)式的估計(jì)需要數(shù)據(jù)結(jié)構(gòu)的統(tǒng)計(jì)信息與分布在結(jié)構(gòu)內(nèi)部的值的統(tǒng)計(jì)信息的結(jié)合，以計(jì)算路徑的選擇性.只lab中/*/e口lg1d (占If8 leFig.4 /albJ///*/*/f/f圖4 /a(l///e/e/f//*/*/ff5.2.1數(shù)值 統(tǒng)計(jì)Chen等人(40把數(shù)值結(jié)點(diǎn)作為普通結(jié)點(diǎn)看待,這樣,估計(jì)a=3與a.3是等價(jià)的,簡化統(tǒng)計(jì)結(jié)構(gòu),，適用于數(shù)值量較少的情況.如果數(shù)值量龐大,統(tǒng)計(jì)每一-個(gè)數(shù)值的個(gè)數(shù)會(huì)占據(jù)大量的空間,導(dǎo)致統(tǒng)計(jì)信息過多,影響查詢代價(jià)估計(jì)的效率.這種方法對(duì)等值的定點(diǎn)查詢可以使用,卻很難估計(jì)范圍查詢的代價(jià).如估計(jì)a>3的代價(jià),需要遍歷統(tǒng)計(jì)信息中所有同類數(shù)值結(jié)點(diǎn),判斷其值是否滿足條件.中國煤化工Freire 等人(4"用 直方圖等方法分別統(tǒng)計(jì)不同類型的數(shù)值信|YHCNMHG值、個(gè)數(shù)等信息.即適用于范圍查詢,也適用于點(diǎn)查詢.其缺點(diǎn)是:數(shù)據(jù)類型過多會(huì)導(dǎo)致統(tǒng)計(jì)信息的膨脹;并且,XML數(shù)據(jù)的特點(diǎn)是自描述性,其值和結(jié)構(gòu)有密切的語義關(guān)系,分開統(tǒng)計(jì)必然導(dǎo)致分別估計(jì)，造成估計(jì)誤差,在文獻(xiàn)[41]中有關(guān)于這方孟小峰等:XML查詢優(yōu)化研究2079面的詳細(xì)論述.5.2.2數(shù)據(jù)結(jié)構(gòu)抽取XML數(shù)據(jù)為有序有向圖.對(duì)圖的結(jié)構(gòu)抽取有兩種極端的方法1(21:標(biāo)記分裂圖(label-split graph)方法粗略地統(tǒng)計(jì)模式信息,其思想是合并所有的標(biāo)記名相同的結(jié)點(diǎn)為一個(gè)結(jié)點(diǎn)記錄合并結(jié)點(diǎn)的個(gè)數(shù)作為標(biāo)記的統(tǒng)計(jì)信息.這種方法占用空間相對(duì)較小，但不能精確地反映數(shù)據(jù)分布的真實(shí)情況,尤其是同名結(jié)點(diǎn)出現(xiàn)在不同位置上時(shí),可能包含錯(cuò)誤的路徑或者圈信息;B/F類似圖(B/F-bisimiar graph)中 ,只有所有入邊和出邊集合相同時(shí)才合并同名的結(jié)點(diǎn),保證準(zhǔn)確地統(tǒng)計(jì)路徑表達(dá)式所有的分支情況.這種方法的缺點(diǎn)是占用空間大.查詢優(yōu)化的統(tǒng)計(jì)信息控制在-定的范圍內(nèi),現(xiàn)有系統(tǒng)的抽取方法都是介于兩個(gè)極端的情況之間.Lore的DataGuidel43]抽取 模式的方法是保證每條路徑只出現(xiàn)一次,其最小模式是標(biāo)記分裂圖的一一個(gè)例子.文獻(xiàn)[43]指出:這種方法統(tǒng)計(jì)路徑信息能夠精確判斷路徑是否存在,但并不能更精確地統(tǒng)計(jì)不同結(jié)點(diǎn)的值在不同路徑中的分布情況.如圖5所示:圖5(c)為圖5(a)的最小DataGuide.如果對(duì)結(jié)點(diǎn)19的統(tǒng)計(jì)信息為t,根據(jù)圖5(c)無法判斷是路徑A.C或者B.C的結(jié)點(diǎn)個(gè)數(shù);圖5(b)為圖5(a)的強(qiáng)壯DataGuide.如果對(duì)結(jié)點(diǎn)12 和13的統(tǒng)計(jì)信息為12和13,根據(jù)圖5(b)判斷路徑A.C的個(gè)數(shù)為1z,B.C的個(gè)數(shù)為13.)'BBA\Bc自尚尚2|DD|pD面面面(a)b)(c)Fig.5 XML data and its corresponding DataGuides圖5 XML 數(shù)據(jù)和DataGuidesStatixX[4]根據(jù) XML Schema統(tǒng)計(jì)結(jié)構(gòu)信息,它是-種折衷的方法出邊不同但同類型的結(jié)點(diǎn)合并為一個(gè),系統(tǒng)對(duì)不同類型的結(jié)點(diǎn)標(biāo)記以不同區(qū)域的值,按照區(qū)域分別統(tǒng)計(jì)不同路徑的結(jié)點(diǎn)個(gè)數(shù),保留了分支結(jié)點(diǎn)的路徑分布信息兒子結(jié)點(diǎn)的分布情況保留在父親結(jié)點(diǎn)的統(tǒng)計(jì)信息中.每個(gè)結(jié)點(diǎn)的統(tǒng)計(jì)信息不再是單個(gè)的值,而是一個(gè)復(fù)雜的結(jié)構(gòu).導(dǎo)致的問題一是代價(jià)信息的增長,二是代價(jià)估計(jì)算法的復(fù)雜性.Xsketchl421也是一種折衷 的方法,但只統(tǒng)計(jì)結(jié)構(gòu)中每個(gè)結(jié)點(diǎn)對(duì)應(yīng)數(shù)據(jù)中結(jié)點(diǎn)的個(gè)數(shù)信息.其特別之處在于對(duì)結(jié)點(diǎn)入邊和出邊的信息的統(tǒng)計(jì).如果對(duì)任意結(jié)點(diǎn)v∈V,存在ueU,在數(shù)據(jù)集中都有邊(,),則V對(duì)U向后固定,如果對(duì)任意結(jié)點(diǎn)u∈U,存在v∈V,在數(shù)據(jù)集中都有邊(u,),則U對(duì)V向前固定.這種統(tǒng)計(jì)信息用于在合并不同分支與主支之間選擇性代價(jià)估計(jì)的計(jì)算.上述方法統(tǒng)計(jì)的只是路徑中父子之間的關(guān)系，而沒有統(tǒng)計(jì)同父的兄弟之間的相關(guān)性.為了便于計(jì)算相對(duì)路徑的代價(jià)和統(tǒng)計(jì)路徑之間的相關(guān)性,Chen等人[401吸收了信息檢索中在文檔中檢索子串的采用后綴樹的方法144統(tǒng)計(jì)路徑信息,稱為相關(guān)子路徑樹(orrelated subpath tre).從XML數(shù)據(jù)中抽取所有到葉子的可能路徑,形成路徑集合,其中間結(jié)點(diǎn)的結(jié)點(diǎn)名為不可分割子串;葉結(jié)點(diǎn)為數(shù)值或者字符串值,為可分割子串.每個(gè)結(jié)點(diǎn)存儲(chǔ)子路徑在數(shù)據(jù)中出現(xiàn)的次數(shù)和路徑特征矢量.我們將在后面的選擇性V中國煤化工代價(jià)計(jì)算方法;在信息統(tǒng)計(jì)部分介紹后綴樹信息的存儲(chǔ)和修剪維護(hù)方法.THCNMHGXSketchesl45.46]在 文獻(xiàn)[42]的基礎(chǔ)上增加了對(duì)邊的信息和值時(shí)信息的統(tǒng),MlU任一定心圍內(nèi)(TSN)能夠處理結(jié)構(gòu)和值或值和值的相關(guān)性問題.但增加信息的同時(shí),也使得構(gòu)造XSketches結(jié)構(gòu)代價(jià)加大.在XSEED4T中提2080Journal of Sofrware軟件學(xué)報(bào)Vol.17, No.10, October 2006到:為100M的XMarkl(8文檔構(gòu)造一個(gè)XSketches 結(jié)構(gòu)需要超過一天的時(shí) 間,這在實(shí)際中變得不可接受.針對(duì)XSketches的缺點(diǎn),XSED47提出了一種新的處理思路,即抽取最粗略的信息,稱為XSEED內(nèi)核,-般只占文檔大小的2%左右;然后,再利用查詢反饋的信息把誤差最大的那部分路徑選擇率的精確值存儲(chǔ)起來,而這部分存儲(chǔ)的信息的多少是根據(jù)內(nèi)存大小來確定的.但是,這種方法只能處理XPath.如果把XML數(shù)據(jù)看作樹,對(duì)樹中的結(jié)點(diǎn)按照(start,end)49編碼，以start為橫坐標(biāo),end為縱坐標(biāo),則樹中所有結(jié)點(diǎn)可看作是平面空間.上的點(diǎn),路徑上的祖先和后代關(guān)系滿足xtncoerdrmeSedrsndmsSncrsrn把整個(gè)空間區(qū)域分成多個(gè)方格,統(tǒng)計(jì)結(jié)點(diǎn)在每個(gè)格中的分布個(gè)數(shù);Wu等人50的思想是:把不同結(jié)點(diǎn)映射為-維坐標(biāo)上的線段,祖先線段和后代線段的起點(diǎn)及長度滿足某種偏序關(guān)系,把整個(gè)區(qū)間分成多個(gè)小區(qū)間,分別計(jì)算落在不同區(qū)間內(nèi)的線段之間的關(guān)系這種方法減少了稀疏分布時(shí)的誤差,但不能完全避免.這兩種統(tǒng)計(jì)方法適用于對(duì)結(jié)構(gòu)連接運(yùn)算的代價(jià)估計(jì).5.2.3選擇性計(jì)算當(dāng)XML數(shù)據(jù)結(jié)構(gòu)復(fù)雜、每個(gè)文檔的數(shù)據(jù)量很大時(shí)，精確地統(tǒng)計(jì)信息是不可能的.在計(jì)算查詢代價(jià)時(shí),需要用一些假設(shè)來彌補(bǔ)統(tǒng)計(jì)信息的不足.目前的路徑選擇性計(jì)算方法分為3種:(1)基于 馬爾可夫鏈的方法.Lorel4)的方法基于馬爾可夫鏈思想,用于計(jì)算沒有分支條件的簡單路徑.系統(tǒng)中只保留短路徑的選擇性統(tǒng)計(jì)信息，基于父子結(jié)點(diǎn)分布的獨(dú)立性假設(shè)計(jì)算長路徑選擇性.如有長路徑t2/2/...其選擇性計(jì)算公式可以是(..+.)=+i Lo4此時(shí),只需保留長度為1和2的路徑信息也可以是(42.1)[..-)x f554).則需保留長度為n- -2和n-1的路徑信息路徑信息越長,組合個(gè)數(shù)越多,占用空間越大,計(jì)算值越精確.實(shí)驗(yàn)表明,當(dāng)路徑信息較短時(shí),加長路徑信息導(dǎo)致明顯的計(jì)算精確性,且空間代價(jià)增長相對(duì)緩慢;當(dāng)路徑信息較長時(shí),加長路徑信息導(dǎo)致空間代價(jià)的爆炸性增長，而精確性提高緩慢如果在路徑的某個(gè)結(jié)點(diǎn)上有對(duì)簡單值的選擇,則根據(jù)兄弟分布獨(dú)立性原則,計(jì)算不同選擇性再做交集運(yùn)算.Aboulnaga等人1對(duì)Lore的方法進(jìn)行了改進(jìn),提出了路徑(path)樹和Markov表來估計(jì)簡單路徑的選擇性.用路徑樹可以表示原文檔的結(jié)構(gòu),樹中的每一個(gè)結(jié)點(diǎn)代表了從文檔的根結(jié)點(diǎn)開始的路徑,并記錄了相應(yīng)結(jié)點(diǎn)出現(xiàn)的次數(shù).但當(dāng)樹變得很大以至于不能放在內(nèi)存的時(shí)候,就需要對(duì)樹進(jìn)行剪枝,根據(jù)一定的算法,刪去那些出現(xiàn)不頻繁的結(jié)點(diǎn)，然后在這個(gè)剪枝過的樹上進(jìn)行選擇率的估算.Markov表存儲(chǔ)長度為m (m>=2)的不同路徑,如果查詢的長度和m相等,直接就可以從表中讀出相應(yīng)的值,誤差為0;當(dāng)長度大于m時(shí),用公式f/.../t.)= /.1+...)x.)進(jìn)行計(jì)算.同樣地,當(dāng)表不能放入內(nèi)存時(shí),刪除那些不頻繁路徑.Xsketch142]增加 了對(duì)邊的固定性統(tǒng)計(jì)信息,并對(duì)Lore 的方法做了改進(jìn),以適用于更- -般的路徑表達(dá)式代價(jià)估計(jì).如果主路徑是向后固定的,則統(tǒng)計(jì)信息為精確信息,無須進(jìn)-步計(jì)算;如果主路徑中有些點(diǎn)不是向后固定的，則在這些點(diǎn)上把主路徑分為多個(gè)子路徑根據(jù)路徑獨(dú)立性假設(shè),用類似Lore的公式,以子路徑統(tǒng)計(jì)信息為參數(shù),計(jì)算長路徑的選擇性.如果分支路徑是向前固定的,則其選擇性為1,無須參與計(jì)算;如果分支路徑中有些點(diǎn)不是向前固定的,則在這些點(diǎn)上把分支路徑分為多個(gè)子路徑,計(jì)算不同選擇性,再做交集運(yùn)算.為了提高計(jì)算的精確性,其代價(jià)路徑分解方法為最大交叉方法.Xketches45.46對(duì)文獻(xiàn)[42]的工作進(jìn)行了擴(kuò)展,可以計(jì)算twicMH中國煤化工模型的基礎(chǔ)上增加了邊的分布信息,從而能夠從細(xì)節(jié)上把握數(shù)據(jù)的分布.這種CNMHG文檔的結(jié)構(gòu)建立.XSketches,然后利用邊的穩(wěn)定性和邊的分布概率來估計(jì)twig的匹配個(gè)數(shù),如果邊的確是分布均勻的話，那么這孟小峰等:XML查詢優(yōu)化研究2081種方法的準(zhǔn)確率就比較高.XSEED47方法在XSEED核結(jié)構(gòu)上增加了對(duì)遞歸結(jié)點(diǎn)的處理,遞歸結(jié)點(diǎn)是指在DTD中有類似A(+,B*)的定義,則A結(jié)點(diǎn)是一-個(gè)遞歸結(jié)點(diǎn).XSEED核結(jié)構(gòu)在邊上記錄了在遞歸的不同層相應(yīng)的父親、孩子的結(jié)點(diǎn)個(gè)數(shù).因此,這種方法可以很好地處理帶有遞歸表達(dá)式的XPath查詢.馬爾可夫鏈思想中的一一個(gè)關(guān)鍵性假設(shè)是父子結(jié)點(diǎn)分布獨(dú)立性和兄弟結(jié)點(diǎn)分布獨(dú)立性假設(shè).而實(shí)際上,很多XML數(shù)據(jù)的父子結(jié)點(diǎn)、兄弟結(jié)點(diǎn)之間的相關(guān)性非常強(qiáng),應(yīng)用上述計(jì)算方法會(huì)導(dǎo)致誤差集合哈希方法統(tǒng)計(jì)相同分支之間的相關(guān)性信息，更準(zhǔn)確地計(jì)算分支路徑的選擇性.(2)集合哈希方法集合哈希方法(0的核心思想來自蒙特卡羅技術(shù)的Min-Wise independent permutionsl4!.這種方法用于估計(jì)兩個(gè)集合之間的相似性,集合的特征通過設(shè)置哈希函數(shù)的集合獲得.其優(yōu)勢在于集合的哈希函數(shù)值占用存儲(chǔ)空間很小.對(duì)集合A,其特征矢量為stg(4=(min({m(),min({])..min({(4)).其中,U-/{,..n};z是U的排列;1是哈希函數(shù)的個(gè)數(shù).sigau.uhs [的= mni{jg.....[i}.假設(shè)Ay為勢最大的集合,則j=;|A!而|A∪...UA.|4..∪A |=|{min{z()}=.. =min{/(4)}}1014|關(guān)于集合哈希函數(shù)的構(gòu)造方法在文獻(xiàn)[44]中有詳細(xì)的論述.利用集合哈希方法計(jì)算路徑表達(dá)式的代價(jià)的方法為:用后綴樹統(tǒng)計(jì)所有可能出現(xiàn)在查詢中的子路徑的特征矢量;分解查詢?yōu)槎鄠€(gè)相關(guān)子路徑;應(yīng)用公式計(jì)算選擇性.文獻(xiàn)(40]中提供了3種路徑分解的方法,并比較了不同方法之間的優(yōu)劣這種代價(jià)計(jì)算的精度對(duì)路徑的長度敏感:隨路徑長度的增長,統(tǒng)計(jì)精度下降，并且，特征矢量本身是一種信息壓縮的方法,用來計(jì)算相關(guān)性時(shí)的精確性是值得商榷的.上述兩種算法都是根據(jù)確定路徑上的父子關(guān)系統(tǒng)計(jì)信息計(jì)算路徑表達(dá)式中后代結(jié)點(diǎn)的選擇性,沒有直接計(jì)算后代,也沒有根據(jù)某些后代估計(jì)滿足條件的祖先結(jié)點(diǎn)的選擇性在執(zhí)行計(jì)劃中,存在大量的向前遍歷的算法，如何估計(jì)這些算法的代價(jià),是一個(gè)需要解決的問題.上面所提到的各種方法的處理能力各有不同,僅從方法能夠支持的各種情R(Xpath, xqu//,value)來看,可以總結(jié)為表2.Table 2 Comparison among various methods' processing表2各種方 法處理能力比較QueryBranchValueCorrelationStatixSimple twig + valueSimple pathNCSTSimple twig + prefix string matchingPrefix string matching Y (set hashing)Path treMarkov ItableXsketchSimple twigXsketchesY (md methods)XSEEDPath(3)位置直方圖方法Wu等人(50采用位置直方圖的方法統(tǒng)計(jì)組先后代的分布信息其代價(jià)計(jì)算分為基于祖先的代價(jià)估計(jì)和基于后代的代價(jià)估計(jì)基于祖先的代價(jià)估計(jì)根據(jù)每一個(gè)祖先的格,累計(jì)中國煤化工結(jié)點(diǎn)個(gè)數(shù);基于后代的代價(jià)估計(jì)則與其正好相反根據(jù)不同區(qū)域的祖先后代結(jié)點(diǎn)的YHCNMHGT:A為某祖先格，則B區(qū)域中所有的格的所有結(jié)點(diǎn)均為A中所有結(jié)點(diǎn)的后代;C,E區(qū)域中所有格的部分結(jié)點(diǎn)為A中部分結(jié)點(diǎn)的后代;而D,F區(qū)域中只有左上半角區(qū)域中存在結(jié)點(diǎn)且部分結(jié)點(diǎn)為A中部分結(jié)點(diǎn)的后代如果考慮自身的嵌套,則A2082Journal of Sofiware 軟件學(xué)報(bào)Vol.17, No.10, October 2006中部分結(jié)點(diǎn)是A中部分結(jié)點(diǎn)的后代.據(jù)上所述，,滿足條件P的A的滿足條件P2的后代個(gè)數(shù)估計(jì)公式為Es1A.[]= Hist[4]x{-x His,[4]+ Hist,[B]+ Hist,[C]+ Hisp[E]+一x (Hist[D]+ Hists[F])} .對(duì)每個(gè)格而言，其后代格限定在較小區(qū)域內(nèi),避免多余的統(tǒng)計(jì)和計(jì)算但在計(jì)算區(qū)域的邊緣,并非所有結(jié)點(diǎn)滿足上述關(guān)系.根據(jù)平均分布的假設(shè)給計(jì)算結(jié)果加以某個(gè)系數(shù)是產(chǎn)生誤差的主要因素,誤差在空間結(jié)點(diǎn)分布稀疏時(shí)變得很大.一個(gè)改進(jìn)的方法是分別統(tǒng)計(jì)不同類型的結(jié)點(diǎn)的分布情況,但統(tǒng)計(jì)信息占用空間很大.這種方法解決的問題是已知集合間的祖先后代關(guān)系的估價(jià),未涉及路徑中單個(gè)謂詞的選擇性計(jì)算問題。positionHdABVEStart postionFig.6 Two-Dimention histogram圖6二維直方 圖示例Jiang 等人[521的思想是:把不同的結(jié)點(diǎn)映射為- -維坐標(biāo)上的線段,祖先線段和后代線段的起點(diǎn)和長度滿足某種偏序關(guān)系.把整個(gè)編碼空間[cmin,cmax]分成多個(gè)小區(qū)間,然后在每個(gè)小區(qū)間內(nèi)估計(jì)覆蓋的線段/起始點(diǎn)的對(duì)數(shù).如圖7所示:統(tǒng)計(jì)信息n表示每個(gè)桶中的線段/起始點(diǎn)的對(duì)數(shù);wss表示桶的起始坐標(biāo);wse表示桶的終點(diǎn)坐標(biāo);1表示桶中線段的平均長度;匹配的祖先_后代個(gè)數(shù)在圖中用X表示.這種方法減少了稀疏分布時(shí)的誤差,但不能完全避免.wsswsek a2》上”IMdD)dd2 ds( 1，Isjsna( wswsn。ins .Fig.T PL histogram and statistics圖7 PL直方圖及統(tǒng)計(jì)信息上述方法在計(jì)算路徑選擇性時(shí),只考慮有謂詞約束的結(jié)點(diǎn),躍過其他結(jié)點(diǎn),直接估計(jì)后代或祖先的代價(jià),簡化了計(jì)算的復(fù)雜度,在對(duì)模糊路徑的代價(jià)估計(jì)中有-定的優(yōu)勢.與馬爾可夫方法相同的是:當(dāng)路徑中出現(xiàn)多個(gè)謂詞時(shí),假設(shè)不同的謂詞條件是獨(dú)立的,沒有計(jì)算不同的謂詞之間的相關(guān)性集合哈希方法計(jì)算不同謂詞之間的相關(guān)性,但后綴樹占用空間過大,尤其是在XML數(shù)據(jù)中包含大中國煤化工i則就是在有限的時(shí)間和空間內(nèi)精確地估計(jì)代價(jià).這時(shí),必須對(duì)統(tǒng)計(jì)信息進(jìn)行壓縮,中YHCNMHG盂小峰等:XML 查詢優(yōu)化研究20835.3統(tǒng)計(jì)信息研究XML數(shù)據(jù)結(jié)構(gòu)復(fù)雜,分布不均勻.數(shù)據(jù)量龐大時(shí),在有限的空間內(nèi)統(tǒng)計(jì)足夠多的信息是統(tǒng)計(jì)信息研究的難點(diǎn).當(dāng)數(shù)據(jù)更新頻繁時(shí)高效的信息維護(hù)技術(shù)顯得更為重要.5.3.1統(tǒng)計(jì)信 息存儲(chǔ)在前文介紹數(shù)值統(tǒng)計(jì)和數(shù)據(jù)結(jié)構(gòu)抽取時(shí),已經(jīng)涉及到統(tǒng)計(jì)信息的存儲(chǔ)問題,但討論集中在邏輯層,并未涉及存儲(chǔ)的形式.XML數(shù)據(jù)統(tǒng)計(jì)信息的存儲(chǔ)結(jié)構(gòu)主要有以下幾種:樹或圖1(042):用于存儲(chǔ)模式信息,如在文獻(xiàn)[42]中模式樹中每個(gè)結(jié)點(diǎn)的個(gè)數(shù),或者文獻(xiàn)[40]中結(jié)點(diǎn)之間的固定關(guān)系等由于其數(shù)據(jù)結(jié)構(gòu)與XML原始數(shù)據(jù)相同,可用對(duì)數(shù)據(jù)本身的存取方法存取統(tǒng)計(jì)信息.如果XML數(shù)據(jù)模式結(jié)點(diǎn)個(gè)數(shù)為n,則樹方法存儲(chǔ)的代價(jià)為0(n);后綴樹的存儲(chǔ)代價(jià)為0(n).馬爾可夫表1!:用于存儲(chǔ)路徑信息,不同的路徑對(duì)應(yīng)其在數(shù)據(jù)中出現(xiàn)的次數(shù).為了查找方便,-般在表上再加以-定的索引.如果 只統(tǒng)計(jì)小于k長度的路徑，則其存儲(chǔ)代價(jià)為O(nk).直方圖158:關(guān)系數(shù)據(jù)庫中曾遍應(yīng)用的一種統(tǒng)計(jì)信息方法將某屬性的值域劃分為多個(gè)連續(xù)或不連續(xù)的部分，分別統(tǒng)計(jì)不同部分區(qū)域內(nèi)數(shù)據(jù)的分布情況對(duì)于簡單數(shù)據(jù),采用一維直方圖方法;若統(tǒng)計(jì)相關(guān)的不同屬性的分布情況,需要二維或者更多維數(shù)的直方圖.在對(duì)XML數(shù)據(jù)作統(tǒng)計(jì)時(shí),主要采用直方圖和樹相結(jié)合的方法.如果某個(gè)結(jié)點(diǎn)的值為樹值型,則用直方圖統(tǒng)計(jì)這個(gè)結(jié)點(diǎn)數(shù)值的分布情況.文獻(xiàn)[41]中,對(duì)于結(jié)點(diǎn)之間的父子關(guān)系也采用直方圖的方法統(tǒng)計(jì).必須首先唯-地標(biāo)記所有的數(shù)據(jù)結(jié)點(diǎn)并且,不同類型結(jié)點(diǎn)標(biāo)記的值域沒有交叉.當(dāng)路徑中的某些點(diǎn)有謂詞約束時(shí)通過統(tǒng)計(jì)信息無法知道那些滿足條件的結(jié)點(diǎn)的標(biāo)記，從而無法進(jìn)-步估計(jì)其后代的個(gè)數(shù).位置直方圖([50:這是一種二維直方圖,其值是離散的,把結(jié)構(gòu)嵌套轉(zhuǎn)換為平面位置關(guān)系.如果按類型每維分為k格則其存儲(chǔ)代價(jià)為0(nk),文獻(xiàn)[S2]等采用一維直方圖方法保存結(jié)點(diǎn)的位置信息,但需要根據(jù)結(jié)點(diǎn)在連接過程中是祖先或后代來保存不同的統(tǒng)計(jì)信息實(shí)際上冗余很大.5.3.2統(tǒng)計(jì)信 息壓縮對(duì)直方圖壓縮方面的研究在關(guān)系數(shù)據(jù)庫查詢優(yōu)化中已經(jīng)有一定的研究基礎(chǔ),普遍采用的是小波壓縮[$3)和DCT(discrete cosine transform).兩 種方法均能把直方圖中大量的“桶”壓縮為少量的系數(shù),同時(shí)丟失很少的信息.小波壓縮方法在代價(jià)估計(jì)時(shí),要重新構(gòu)造與查詢相關(guān)的部分直方圖.YanB5]等人采用密度函數(shù)方法壓縮直方圖,用數(shù)據(jù)密:度函數(shù)直接模擬實(shí)際的數(shù)據(jù)的分布情況.這種方法適用于離散的或是連續(xù)的數(shù)值型數(shù)據(jù).樹的修剪和馬爾可夫表的壓縮思想是從統(tǒng)計(jì)信息中刪除對(duì)代價(jià)估計(jì)結(jié)果影響相對(duì)較少的結(jié)點(diǎn)結(jié)點(diǎn)在數(shù)據(jù)中出現(xiàn)次數(shù)越少,則越缺乏統(tǒng)計(jì)價(jià)值.文獻(xiàn)[51]中提供了4種不同的方法,并通過實(shí)驗(yàn)分析了幾種方法在不同的數(shù)據(jù)分布情況和查詢情況時(shí)的占用空間和代價(jià)估計(jì)精度關(guān)系,但并未得到相對(duì)穩(wěn)定的方法.5.3.3統(tǒng)計(jì)信 息維護(hù)據(jù)我們所知,目前對(duì)XML統(tǒng)計(jì)信息維護(hù)的研究很少見.文獻(xiàn)[54]提出一種馬爾可夫表的在線維護(hù)方法,其思想是:在查詢開始時(shí)沒有統(tǒng)計(jì)信息,利用查詢反饋逐步生成和細(xì)化統(tǒng)計(jì)信息.其細(xì)化規(guī)則有兩個(gè):重尾規(guī)則(heavy-ail)和增量規(guī)則(delta),重尾規(guī)則是在計(jì)算選擇性時(shí),給接近查詢路徑末端的路徑的選擇性計(jì)算加以較高的權(quán)重.這樣做基于如下考慮:接近路徑末端的路徑選擇性對(duì)整個(gè)路徑的選擇性影響更大;增量規(guī)則是一-種錯(cuò)誤減少學(xué)習(xí)方法.文獻(xiàn)[54]的優(yōu)點(diǎn)在于在線維護(hù)統(tǒng)計(jì)信息文獻(xiàn)([S]提出了基于Stilt"I框架IMAX增量維護(hù)算法,包括結(jié)構(gòu)信息和值信息的增量維護(hù),但是不易擴(kuò)展到其他系統(tǒng)上.6總結(jié)及展望隨著Intermet的發(fā)展,XML數(shù)據(jù)規(guī)模與日劇增,準(zhǔn)確、高效地查詢XML數(shù)據(jù)成為目前研究的熱點(diǎn)問題.近年來,XML查詢優(yōu)化研究方興未艾,主要集中在如下幾個(gè)方面:對(duì)中國煤化工ML代數(shù)分解查詢語句的研究、對(duì)路徑選擇性估計(jì)的研究、對(duì)結(jié)構(gòu)連接代價(jià)估i|YHCNMHG--門綜合性強(qiáng)的研究領(lǐng)域,需要吸收眾多其他技術(shù)的思想其中對(duì)XML查詢優(yōu)化影響深刻的主要有:關(guān)系數(shù)據(jù)庫查詢優(yōu)化技術(shù)、面向?qū)ο髷?shù)據(jù)庫查詢優(yōu)化技術(shù)、信息檢索技術(shù)、數(shù)據(jù)倉庫和數(shù)據(jù)挖掘技術(shù)、圖像處理和壓縮技術(shù)、人工智能2084Journal of Sofware軟件學(xué)報(bào)Vol.17, No.10, October 2006技術(shù)、概率論和統(tǒng)計(jì)技術(shù)等.從查詢優(yōu)化的過程來講,XML查詢優(yōu)化和其他數(shù)據(jù)庫查詢優(yōu)化技術(shù)并無不同之處。從優(yōu)化的不同環(huán)節(jié)的技術(shù)上看,XML查詢優(yōu)化具有其獨(dú)特之處:既要適應(yīng)更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)和更靈活的變化，又要適應(yīng)更豐富的查詢語義.目前對(duì)XML查詢優(yōu)化的研究工作還遠(yuǎn)未成熟,仍有眾多尚待解決的問題或需要完普的技術(shù).因此，未來的XML查詢優(yōu)化研究將以更廣泛、更深入的方式展開.在XML代數(shù)研究中,一個(gè)值得重視的問題是邏輯操作與物理操作的分工不明確.大量的工作在于制定不同的代數(shù)標(biāo)準(zhǔn),這些標(biāo)準(zhǔn)在風(fēng)格上相去甚遠(yuǎn),很難有共通性.而對(duì)真正執(zhí)行的物理代數(shù)的研究還遠(yuǎn)遠(yuǎn)不夠,而且不能形成完整的系統(tǒng)另外,從邏輯代數(shù)到物理代數(shù)的轉(zhuǎn)換也將是未來研究的一個(gè)重要的問題.關(guān)系數(shù)據(jù)庫中--些約定俗成的啟發(fā)式轉(zhuǎn)換規(guī)則是在大量的實(shí)踐基礎(chǔ)上形成的.而目前對(duì)XML數(shù)據(jù)查詢的各種不同的執(zhí)行方法之間的優(yōu)劣比較的工作還剛剛開始,并未形成共識(shí)性的規(guī)則.由于XML數(shù)據(jù)本身的靈活性,找到一些普遍適用的規(guī)律是很困難的.在今后的一段時(shí)間內(nèi)，相信會(huì)有更多的研究工作在這方面展開.復(fù)雜路徑表達(dá)式選擇性代價(jià)估計(jì)是XML查詢優(yōu)化研究的核心問題,目前已有大量的成果,這些研究或?qū)?shù)據(jù)分布進(jìn)行大量的假設(shè),或?qū)Σ樵儽磉_(dá)式的復(fù)雜性加以-定的約束尤其是在相關(guān)路徑選擇性的研究方面,仍有--些尚待解決的關(guān)鍵性問題.一直以來,統(tǒng)計(jì)信 息維護(hù)是代價(jià)估計(jì)的基礎(chǔ).但是,關(guān)于XML數(shù)據(jù)統(tǒng)計(jì)信息的維護(hù)問題的研究還處于起步狀態(tài).由于XML數(shù)據(jù)統(tǒng)計(jì)信息在數(shù)據(jù)結(jié)構(gòu)上與傳統(tǒng)的統(tǒng)計(jì)信息有本質(zhì)的不同,很難直接利用現(xiàn)有的統(tǒng)計(jì)信息維護(hù)的技術(shù).又由于目前在XML統(tǒng)計(jì)信息研究中采用了大量的壓縮技術(shù),為統(tǒng)計(jì)信息維護(hù)增加了難度.Native XML Database的研究是目前在XML研究領(lǐng)域的一個(gè)熱點(diǎn),已經(jīng)出現(xiàn)一批相對(duì)獨(dú)立的系統(tǒng),這些系統(tǒng)采用的查詢和處理方法也將對(duì)XML查詢優(yōu)化技術(shù)產(chǎn)生越來越重要的影響.References:XML Query Working Group. 1999. 1-26. htp://ww.stanford.edu/infoveminar/Archi/e/Fall/9/mahot-iides/iahotra.peoe[2] Fermandez M, Simeon J, Suciu D, Wadler P. A data model and algebra for XML query. 199. ht/w/w.cel labs.com/wadler/topics/xml.html#algebra[3] Kay M. XSL transformations (XSLT), Version 1.0. W3C Recommendation, 1999 ht://www.w.wr/TR/xsl/+4] Fankhauser P, Fermandez M, Malhotra A, Rys M, Simeon I, Wadler P. XQuery 1.0 formal semantics. W3C Working Draft, 2002.htp://www.w3.org/TR/query -semantics/[5] Fernandez M, Robie J. XQuery 1.0 and XPath 2.0 data model. W3C Working Draf, 2002. htp://ww.w.org/TR/query. datamodel/[6] Mary FF, Jerome s, Byron C, Amelie M, Gargi s. Implementing xquery 1.0: The galax experience. In: Freytag JC, Lockemann PC,Abiteboul s, Carey MJ, Selinger PG, Heuer A, eds. Proc. of the 29th In'l Conf. on Very Large Data Bases. Berlin: MorganKaufmann Publishers, 2003. 1077- 1080.[7] McHugh J, Abiteboul s, Goldman R, Quass D, Widom J. Lore: A database management system for semistructured data. SIGMODRecord, 1997,26(3);:54- -66.[8] McHugh J, Widom J. Query optimization for XML. In: Alkinson MP, Orlowska ME, Valduriez P, Zdonik SB, Brodie ML, eds.Proc. of the 25th Int'l Conf. on Very Large Data Bases. Edinburgh: Morgan Kaufmann Publishers, 1999. 315- 326.9] Jagadish VH, Al-Khalifa s, Lakshmanan L, Nierman A, Paparizos s, Patel J, Srivastava D, Wu YQ. Timber: A native XMLdatabase. The VLDB Journal, 2002,1 1(4):274-291.[10] Jagadish VH, Al-Kalifa s, Lakshmanan L, Srivastava D, Thompson K. Tax: A tree algebra for XML. In: Ghelli G, Grahne G, eds.Database Programming Languages, 8th Int'l Workshop, DBPL 2001. Frascati: Springer-Verlag, 2001. 149- 164.[1] Frasincar F, Houben GJ, Pau C. XAL: An algebra for XML query optimization. In: Zhou XF, ed. Proc. of the 13th AustralasianDatabase Conf. (ADC 2002). Melboume: Monash University, 2002.[12] Zhang D, Dong YS. A data model and algebra for the Web. [n: Proc. of the 10th Int'! Workshop on Database & Expert SystemsApplications. Florence: IEEE Computer Society, 1999. 711-714.中國煤化工[13] Lieke H. Horizontal query optimizaion on ordered semistructuredCNMHGof the ACM SIGMODWorkshop on The Web and Databases (WebDB'99). Philadelphia: ACNMYH[14] Mukhopadhyay P, Papakonstantinou Y. Mixing querying and navigation in MIX. In: Agrawal R, Dittrich K, Ngu AH, eds. Proc.of the 18th Int'l Conf. on Data Engineering. San Jose: IEEE Computer Society, 2002. 245- -254.孟小峰等:XML查詢優(yōu)化研究2085[15] Paparizos s, Al-Khalifa s, Jagadish HV, Nierman A, Wu YQ. A physical algebra for XML. Technical Report, University ofMichigan, 2002.[l6] Christophides V, Cluet s, Moerkotte G. Evaluating queries with generalized path expressions. In: Jagadish HV, Mumick IS, eds.Proc. of the 1996 ACM SIGMOD Int'1 Conf. on Management of Data. Montreal: ACM Press, 1996. 413-422..[17] Buneman P, Fan w, Simen J, Weinstein S. Constraints for semistructured data and XML. ACM SIGMOD Record, 2001,30(1):47-45.[18] World Wide Web Consortium. XML path language (XPath) Version 1.0. W3C Recommendation, 1999. htp://ww.w.wr/TR/xpath.html[19] Chamberlin D, Clark I, Florescu D, Robie J, Simeon J, Stefanescu M. XQuery 1.0: An XML query language. Technical Report,World Wide Web Consortium, W3C Working Draft, 2001.[20] Deutsch A, Fermandcz M, Florescu D, Levy A, Suciu D. A query language for XML.2003. ht://www .esercatt.om/fles/final.html[21] Robie J, Lapp , Schach D. XML query language (XQL). htp://www.w3.org/TandS/QL/QL98/pp/xq.html[22] Chamberlin D, Robie J, Florescu D. Quilt: An XML query language for heterogeneous data sources. In: Suciu D, Vossen G, eds.The World Wide Web and Databases, 3rd Int'l Workshop WebDB 2000. LNCS 1997, Springer-Verlag, 2001. 1-25.[23] Li Q, Moon B. Indexing and querying XML data for regular path expressions. In: Apers PMG, Alzeni P, Ceri s, Paraboschi s,Ramamohanarao K, Snodgrass RT, eds. VLDB 2001, Proc. of the 27th Int'l Conf. on Very Large Data Bases. Roma: MorganKaufmann Publishers, 2001. 361-370.[24] Chan C, Felber P, Garofalakis M, Rastogi R. Efficieng filtering of XML documents with Xpath expressions. In: Agrawal R,Ditrich K, Ngu AHH, eds. Proc. of the 18th Int'l Conf. on Data Engineering. San Jose: IEEE Computer Society, 2002. 235-244.[25] Wood PT. On the equivalence of XML ptterns. In: In: John W L, Veronica D, Ulrich F, Manfred K, Kung-K L, Caruscia P, Luis Mp, Ychoshua s, Peter J s, eds. Proc. of the Ist In' Conf. on Computer on Computation Logic LNAI 1861, Berli: Springer-Verlag,2000. 1152-1166.[26] Florescu D, Levy AY Suciu D. Query containment for conjunctive queries with regular expressions. In: Popa L, ed. Proc. of the17th ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems. Seattle: ACM Press, 1998. 139-148.[27] Calvanese D, Giacomo GD, Lenzerini M. On the decidability of query containment ander constraints. In: Popa L, ed. Proc. of the17th ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems. Seattle: ACM Press, 1998. 149-158.[28] Wadier P. A formal semantics of pttemns in XSLT. Markup Languages archive, 999,2(2):183- 202.[29] Wood PT. Minimizing simple XPath expressions. In: Mecca G, Simeon J, eds. Proc. of the 4th Int'l Workshop on the Web andDatabases, WebDB 2001. Santa Barbara: ACM Press, 2001. 13-18.[30] Amer-Yahis s, Cho s, Lakshmanan LV, Srivastava D. Minimization of tree pattern queries. In: Aref WG, ed. Proc. of the SIGMOD2001 Electronic. Santa Barbara: ACM Press, 2001. 497-508.[31] Ramanan P. Efficient algrithms for minimizing tree patterm queries. In: Franklin MJ, Moon B, Ailamaki A, eds. Proc. of the 2002ACM SIGMOD Int'l Conf. on Management of Data. Madison: ACM Press, 2002. 299 -309.(32] Flesca S, Furfaro F, Masciari E. On the minimization for Xpath queries. In: Freytag JC, Lockemann PC, Abiteboul s, Carey MJ,Selinger PG, Heuer A, eds. VLDB 2003, Proc. of the 29th Int'l Conf. on Very Large Data Bases. Berlin: Morgan KaufmannPublishers, 2003. 153-164.[33] Popa L, Deutsch A, Sahuguet A, Tannen v. A chase too far? In: Chen WD, Naughton JF, Bernstein PA, eds. Proc. of the 2000ACM SIGMOD Int'l Conf. on Management of Data. Dallas: ACM Press, 2000. 273-284.[34] Kwong A, Gertz M. Schema-Based optimization of XPath expressions. Technical Report, University of Califonia, 2001.[35] Lynch CA. Selectivity estimation and query optimization in large databases with highly skewed distributions of column values. In:Bancilhon F, DeWitt DJ, eds. 14th Int'l Conf. on Very Large Data Bases. Los Angeles: Morgan Kaufmann Publishers, 1988.240-251.[36] Haas PI, Swami AN. Sequential sampling procedures for query size estimation. SIGMOD Record, 1992,21(2):341-350.[37] Ling Y, Sun W. A supplement to sampling based methods for query size estimation in a database system. ACM SIGMOD Record,1992,21(4):12-15.(38] Muralikrishna M, DeWitt DJ. Equi-Depth histograms for estimating slctivity factors for muli- dimensional querics. SIGMODRecord, 1988,17(3):28-36.[39] Zhang N, Hass PJ, Josifovski V, Lohman GM, Zhang C. Staistial leal中國煤化Iveries. In: Bohm K,Jensen Cs, Haas LM, Kersten ML, Larson PK, Ooi BC, eds. Proc. of t:YHC N M H Ga Bases. Trodheim:ACM Press, 2005. 289- -300.2086Journal of Sofrware 軟件學(xué)報(bào)Vol.17, No.10, October 2006[40] Chen ZY, Jagadish HV, Kom F, Koudas N, Muthukrishnan s, Ng RT, Srivastava D. Counting twig matches in a tee. In: Young DC,ed. Proc. of the 17th Int'l Conf. on Data Engineering Heidelberg: IEEE Computer Society, 2001. 595-604.[41] Freire J, Haritsa JIR, Ramanath M, Roy P, Simton J. StaiX: Making XML count. In: Franklin MJ, Moon B, Ailamaki A, eds. Proc.of the 2002 ACM SIGMOD Int'l Conf. on Management of Data. ACM Press, 2002.181-191.42] Polyzotis N, Garofalakis MN. Statistical synopses for graph-structured XML databases. In: Franklin MJ, Moon B, Ailamaki A, eds.Proc. of the 2002 ACM SIGMOD Int'l Conf. on Management of Data. ACM Press, 2002.358 -369.[43] Goldman R, Widom J. DataGuides: Enabling query formulation and optimization in semistructured databases. In: Jarke M, CareyMJ, Dittrich KR, Lochovsky FH, Loucopoulos P, Jeusfeld MA, eds. VLDB'97, Proc. of the 23rd Int'l Conf. on Very Large DataBases. Athens: Morgan Kaufmann Publishers, 1997. 436-445.[44] Chen zY, Korn F, Koudas N, Muthukrishnan s. Selectivity estimation for Boolean queries. In: Popa L, ed. Proc. of the 19th ACMSIGMOD-SIGACT-SIGART Symp. on Principles of Database Systems. Dallas: ACM Press, 2000. 216-225.[45] Polyzotis N, Garofalakis M. Structure and value synopses for XML data graphs. In: Bressan s, Chaudhri AB, Lee ML, Yu JX,Lacroix z, eds. Proc. of the 28th VLDB Conf. Hong Kong: Morgan Kaufmann Publishers, 2002. 466-477.[46] Polyzotis N, Garfalakis M, Iosnnidis Y. Selectivity estimation for XML twigs. In: Tisworth F, ed. Proc. of the 20th Int'l Conf. onData Engineering, ICDE 2004. Boston: IEEE Computer Society, 2004. 264 -275.[47] Zhang N, Ozsu MT, Aboulnaga A, Ilyas IF. XSEED: Accurate and fast cardinality estimation for XPath queries. In: Ling L,Andreas R, Kyu-Y w, Jianjun Z, eds. Proc. of the 22nd Int'l Conf. on Data Engineering. Atianta: IEEE Computer Society, 2006.51.[48] Schmidt AR, Waas F, Kersten ML, Florescu D, Manolescu 1, Carey MJ, Busse R. The XML benchmark project. Technical Report,INS-R0103, CWI, 2001.[49] Zhang C, Naughton JF, DeWitt DI, Luo Q, Lohman GM. On supporting containment queries in relational database managementsystems. In: Aref WG, ed. Proc. of the 20th ACM SIGMOD Int'l Conf. on Management of Data. Santa Barbara: ACM Press, 2001.425- 436.[50] Wu YQ, Patel JM, Jagadish HV. Estimating answer sizes for XML queries. In: Jensen CS, Jeffery KG, Pokorny J, Salenis S,Bertino E, B8hm K, Jarke M, eds. Proc. of 8th Int'l Conf. on Extending Database Technology. Prague: Springer-Verlag, 2002.590-608.51] Jiang HF, Lu HI, Wang w, Yu JX. Containment join size estimnation: Models and methods. In: Halevy AY, Ives ZG, Doan A, eds.Proc. of the 2003 ACM SIGMOD Int'l Conf. on Management of Data. San Diego: ACM Press, 2003. 145-156.[52] Aboulnaga A, Alameldeen AR, Naughton JF. Estimating the selectivity of XML path expressions for Internet scale applications. In:Apers PMG, Atzeni P, Ceri s, Paraboschi s, Ramamohanarao K, Snodgrass RT, eds. Proc. of the 27th Int'l Conf. on Very LargeData Bases. Roma: Morgan Kaufmann Publishers, 2001. 591-600.[53] Matias Y, Vitter JC, Wang M. Wavelet-Based histograms for setivitiy estimation. In: Haas LM, Tiwary A, eds. SIGMOD'98,Proc. of the ACM SIGMOD Int'l Conf. on Management of Data. Seattlc: ACM Press, 1998. 448-459.[54] Lim L, Wang M, Padmanabhan s, Vitter JS, Par R. Xpath learner: An on-linc sl-tuning Markov histogram for XML pathselectivity estimation. In: Bressan s, Chaudhri AB, Lee ML, Yu JX, Lacroix乙, eds. Proc. of the 28th Int'l Conf. on Very LargeData Bases. Hong Kong: Morgan Kaufimann Publishers, 2002. 442- -453.[55] Ramanath M, Zhang Lz, Freire J. Incremental maintence of schema-based XML stistis. In: Donald F. Shafer, eds. Proc. of the21st IEEE Int'l Conf. on Data Engineering. Tokyo: IEEE Computer Society, 2005. 273-284.孟小峰(1964- ),男,博士,教授,博士生導(dǎo)王小鋒(1980- -),女,碩士生,主要研究領(lǐng)域師,CCF高級(jí)會(huì)員,主要研究領(lǐng)域?yàn)閃eb數(shù)為XML數(shù)據(jù)庫.據(jù)集成,XML數(shù)據(jù)庫,移動(dòng)數(shù)據(jù)管理.王字(1973- ),女,博士,主要研究領(lǐng)域?yàn)閃eb數(shù)據(jù)管理,XML數(shù)據(jù)庫.中國煤化工MYHCNMHG