XML查詢(xún)優(yōu)化研究

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查詢(xún)優(yōu)化研究孟小峰"，王宇’，王小鋒''(中國人民大學(xué)信息學(xué)院,北京100872)(河北大學(xué)計算中心,保定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ò )上信息描述和信息交換的標準.由于網(wǎng)絡(luò )上信息的本質(zhì)特性和XML數據內在的靈活性,很多用XML編碼的數據都是半結構化的隨著(zhù)XML應用得越來(lái)越廣泛，人們提出了多種XML數據的存儲模型.與此同時(shí),XML的查詢(xún)優(yōu)化也是數據庫領(lǐng)域研究的一個(gè)重要課題綜合論述了XML數據查詢(xún)優(yōu)化技術(shù)的現狀,指出了XML查詢(xún)優(yōu)化的特點(diǎn)和研究的關(guān)鍵性問(wèn)題.描述了查詢(xún)優(yōu)化技術(shù)各個(gè)方面的重要研究成果以及存在的問(wèn)題,進(jìn)一步展望了未來(lái)的研究方向,并在此基礎上提出了對XML查詢(xún)優(yōu)化方法的一些觀(guān)點(diǎn).關(guān)鍵詞: XML;查 詢(xún)優(yōu)化中圖法分類(lèi)號: TP311文獻標識碼: 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ā)展規劃(973)); theKey Project of Chinese Ministry of Education under Grant No.03044 (國家教育印中，議小里m灰口) u llugiam for New CenturyExellent Talents in University (國家教育部新世紀優(yōu)秀人才支持計劃)Received 2006-01-19; Accepted 2006-04-172070Journal of Sofware軟件學(xué)報Vol.17, No.10, October 2006XML已經(jīng)成為網(wǎng)絡(luò )上信息描述和信息交換的標準.早期的XML數據以文檔方式存儲,以關(guān)鍵字查詢(xún)等信息檢索手段查詢(xún),簡(jiǎn)單、易用.由于缺乏系統的存儲和查詢(xún)機制的支持,造成查詢(xún)能力低,不能滿(mǎn)足復雜條件的查詢(xún),更談不上查詢(xún)優(yōu)化.一些現有 的商業(yè)數據庫系統打充了處理XML數據的功能,利用現有數據庫成熟的技術(shù)，把XML查詢(xún)要求轉變?yōu)閿祿觳樵?xún)表達,由查詢(xún)優(yōu)化器優(yōu)化查詢(xún)表達并執行,再將查詢(xún)的結果轉變?yōu)閄ML數據:這種方法在一定程度上解決了查詢(xún)復雜性的要求,但多級轉換帶來(lái)的問(wèn)題是效率的降低和查詢(xún)語(yǔ)義的混淆.與傳統的數據庫數據相比,XML數據具有如下特點(diǎn):,數據是自描述的,內容與結構混雜在一起;●數據具有完整的嵌套層次;●數據是有序的.XML數據的不規則性是對傳統統計信息方法的重要挑戰，其數據分布情況使得一些傳統的分布假設難以成立.為了達到所需的代價(jià)估計精度,需要更多的統計信息.而結構的復雜性又為獲得相對精確的統計信息帶來(lái)存儲和計算上的困難.XML的有序性制約了轉換規則的靈活性.XML數據的上述問(wèn)題無(wú)論是對關(guān)系數據庫或是對面向對象數據庫的現有查詢(xún)優(yōu)化技術(shù)都是嚴峻的挑戰.與傳統的查詢(xún)需求相比,XML查詢(xún)具有如下特點(diǎn):●以長(cháng)路徑表達式為查詢(xún)的核心語(yǔ)句,路徑復雜,包含分支路徑;●嵌套的查詢(xún)表達,查詢(xún)表達式中加入編程語(yǔ)言的嵌套和條件判斷思想;●路徑中包含不確定因素，這在之前的查詢(xún)需求中未出現過(guò);查詢(xún)對象和返回結果類(lèi)型不確定.面向對象數據庫已有一些處理復雜長(cháng) 路徑表達式的經(jīng)驗,但無(wú)法處理XML查詢(xún)中的路徑表達式中的不確定情況;關(guān)系數據庫中已有很多處理嵌套查詢(xún)的方法,但對摻雜編程語(yǔ)言風(fēng)格的XML查詢(xún)語(yǔ)言卻難以適應.綜上所述,來(lái)自數據結構和查詢(xún)需求兩方面的問(wèn)題導致基于關(guān)系和面向對象數據庫的查詢(xún)處理和查詢(xún)優(yōu)化技術(shù)均不能適應XML查詢(xún)的需要.目前,對XML查詢(xún)優(yōu)化的研究正成為熱點(diǎn)本文的內容就是對XML查詢(xún)優(yōu)化技術(shù)現狀的綜合論述，指出了XML查詢(xún)優(yōu)化的特點(diǎn)和研究的關(guān)鍵性問(wèn)題,描述了查詢(xún)優(yōu)化技術(shù)各個(gè)方面的重要研究成果和有待進(jìn)一步解決的問(wèn)題.1XML查詢(xún)優(yōu)化研究問(wèn)題查詢(xún)優(yōu)化是數據庫技術(shù)中重要的研究問(wèn)題,是實(shí)現高效查詢(xún)的關(guān)鍵性因素.對傳統數據庫查詢(xún)優(yōu)化的研究已經(jīng)形成相對成熟的技術(shù)和方法,其中基于代價(jià)的優(yōu)化是主流.查詢(xún)語(yǔ)言首先被轉換成為一種內部表達形式(通常是某種代數,如關(guān)系代數等),根據變換規則得到等價(jià)表達式,計算不同形式的表達式的執行代價(jià),然后選擇一個(gè)最小的執行方案.當把這種方法用于XML查詢(xún)優(yōu)化時(shí),研究者遇到如下問(wèn)題:(1)完善 的查詢(xún)代數標準眾所周知,關(guān)系數據庫統治數據管理領(lǐng)域長(cháng)盛不衰的法寶就是描述性查詢(xún)語(yǔ)言sQL及其運行基礎關(guān)系代數.關(guān)系代數的目的之一是給 出明確的查詢(xún)語(yǔ)義,之二是用于支持查詢(xún)優(yōu)化關(guān)系代數的優(yōu)勢來(lái)自于簡(jiǎn)單、明確的數據模型一-關(guān)系,具 有完善的數學(xué)基礎和系統的轉換規則.后來(lái)的數據模型都以關(guān)系代數為藍本,定義了不同的運算,如面向對象數據模型等,但效果并不盡如人意.XML數據模型本身具有的半結構化特點(diǎn)是定義完普的代數運算的最大障礙,而XML查詢(xún)語(yǔ)言中的不確定性和一些編程思想的引入是另一個(gè)難以克服的困難.(2)精確的代價(jià)估計關(guān)系模型中,表中的記錄是無(wú)序的、大小相等的,代價(jià)計算時(shí)依據的一些分布假設是穩定的.而且,由于其記錄大小相等,對時(shí)間的估計可以轉換為對.10 次數的估計,進(jìn)而轉中國煤化工.而在xML模型中,數據是有序的,數據聚集的方式不定,每個(gè)數據的大小相差懸,間的對應關(guān)系沒(méi)有明顯的規律.簡(jiǎn)單地沿用傳統的代價(jià)計算方法必然導致誤差的YHCNMH G+.(3)足夠的統計信 息孟小峰等:XML查詢(xún)優(yōu)化研究2071足夠精確的統計信息是保證查詢(xún)優(yōu)化有效性的基礎;缺乏足夠的統計信息,是造成估計與實(shí)際情況產(chǎn)生誤差的重要因素.傳統的統計信息多是對值的統計,如對平均值、最值、記錄個(gè)數等的統計.這些對XML查詢(xún)是不夠的.XML數據本身缺乏模式的支持,對數據結構信息的統計顯得更加重要XML數據中的數值分布在類(lèi)似樹(shù)狀結構的樹(shù)葉上,即使相同類(lèi)型的數據,由于半結構化特點(diǎn),其分布情況也可能完全不同.因此需要把對結構的統計信息和對值的統計信息結合到一起,才能得到足夠精確的統計信息.2 XML查詢(xún)處理結構與傳統的關(guān)系數據庫系統的查詢(xún)處理結構類(lèi)似,我們可以將XML查詢(xún)處理分為4個(gè)大的階段.如圖1所示.中間方框表示查詢(xún)處理步驟;左側方框為使用的相關(guān)技術(shù)或方法;右側方框為查詢(xún)優(yōu)化和執行時(shí)需要的信息.Query←= Statistics, dataQuery algebraParse queryAlgebra expressionTransformation rule Logieal oplimizationPattern informationPhysical exccution strategy、Execution algorthim Query executionData, indexQuery resuts↓Fig.1 Query processing圖1查詢(xún)處理過(guò)程第1階段查詢(xún)解析,將查詢(xún)轉換為某種內部表達方式,以便于機器處理,并為下一步的優(yōu)化過(guò)程鋪平道路.這種內部表達方式通常以一種抽象語(yǔ)法樹(shù)或者查詢(xún)樹(shù)的形式出現以傳統數據庫為基礎的查詢(xún)引擎的做法是轉換成關(guān)系代數,然后由關(guān)系數據庫優(yōu)化器完成剩下的優(yōu)化工作.而Native的數據庫系統則采用不同的XML代數系統.我們在第3節中將會(huì )介紹目前流行的幾種XML代數.第2階段邏輯優(yōu)化,利用模式信息,規范和簡(jiǎn)化內部表達式.在這一階段中,系統不考慮實(shí)際數據的值和數據的存儲情況同一查詢(xún)請求,可以轉換成不同的等價(jià)表達方式,其中有-些比原有查詢(xún)更高效.為了進(jìn)行這種轉換,優(yōu)化器需要-些轉換規則,我們將在第4節中討論這些轉換規則.第3階段物理優(yōu)化，利用代價(jià)模型和統計信息計算不同表達式、不同算法的執行代價(jià),選擇最低代價(jià)的查詢(xún)計劃.在這一-階段中,需要解決兩個(gè)問(wèn)題:確定表達式執行順序和決定每步操作的具體算法，對于XML查詢(xún)樹(shù)而言,首先需要將查詢(xún)表達式分解為可執行的片斷,然后選擇合適的執行順序和執行算法并執行.中間結果集的大小是決定執行策略是否高效的關(guān)鍵因素與實(shí)際的數據分布密切相關(guān).綜合考慮數據的存儲、索引和數據值的分布情況,準確地估計復雜路徑選擇性是其中的難點(diǎn)對于一個(gè)給定的執行策略,通常會(huì )有多個(gè)可能的執行算法,產(chǎn)生所有的執行算法的組合造成選擇本身的代價(jià)過(guò)大因此,會(huì )有-些啟發(fā)式規則用來(lái)控制其空間規模,并采用-些空間搜索技術(shù)加速選擇的過(guò)程我們將在第5節中詳細加以討論.第4階段查詢(xún)執行,根據物理優(yōu)化確定的執行策略和算法,訪(fǎng)問(wèn)數據并得到查詢(xún)結果.由于XML數據復雜和變化的結構,需要高效的數據訪(fǎng)問(wèn)算法.中國煤化工MHCNMHG3 XML 代數XML代數是對遵循一定數據模型的XML文檔集合的操作集.XML代數提供根據請求在文檔集合中選擇2072Journal of Sofware軟件學(xué)報Vol.17, No.10, October 2006一個(gè)或多個(gè)文檔或者文檔片段的能力.XML代數應支持對查詢(xún)結果的重構.目前對XML代數的研究主要集中在對查詢(xún)代數的定義和從查詢(xún)語(yǔ)言到查詢(xún)代數的轉換方面.查詢(xún)代數定義查詢(xún)對象的類(lèi)型,可以執行的操作和不同操作之間的轉換規則.查詢(xún)語(yǔ)言經(jīng)分解轉換為由查詢(xún)代數的操作表達構成的操作樹(shù)或者操作序列.不同的代數表達可以有相同的語(yǔ)義和執行結果,構成代價(jià)空間.3.1 XML代數定義目前產(chǎn)生很多種XML代數,風(fēng)格各異，其主要思想來(lái)源于關(guān)系代數、面向對象代數、半結構化代數和功能化編程語(yǔ)言等.由于篇幅有限,不能在這里----介紹,我們介紹其中具有代表性和影響力的幾種,表1列出了不同代數之間特點(diǎn)的比較.Table 1 Comparisons among XML query algebra表1 XML 查詢(xún)代數比較DataDocument Node Reference LogicalPhysical Transformationstructureordersupported operation_ operationruleAT&T Directed graphIBMDirected graphSXquery data modelSeldomLoreOEMTAXOracle,IBM和MS聯(lián)合提出的-一個(gè)XML代數標準是文獻[1].該標準把XML文檔看作有向標記圖(如果忽略引用,可以看作有向標記樹(shù)).用五元組G(V,E,A,R,O)表示.其中:V表示結點(diǎn),有兩種類(lèi)型:element和value.E 表示element到element;A表示element到value,即屬性;R表示引用..上述3種為邊的類(lèi)型.0表示次序在這個(gè)模型上,規定了導航、選擇、連接、構造等操作,其導航操作提供在有向標記圖中的遍歷操作,包括正向遍歷和反向遍歷;其連接操作語(yǔ)義類(lèi)似關(guān)系代數中的連接操作,根據相同的值連接不同的文檔.該代數采用類(lèi)似關(guān)系代數的表達形式.Bell Labs.和AT&T Labs.的Mary等人提出的XML查詢(xún)代數[,基于簡(jiǎn)化的XSLT數據模型},增加了引用結點(diǎn),合并了屬性和元素結點(diǎn),刪除了注釋結點(diǎn)其主要思想來(lái)源于曾用于半結構化和面向對象數據庫的代數-嵌套關(guān)系代數,并增加了對正則表達式的操作.在嵌套關(guān)系中,數據由多個(gè)元組和多個(gè)鏈表組成,并可多級嵌套,其采用list comprehension方法表達導航、笛卡爾積、嵌套和連接操作.List comprehension根據-系列過(guò)濾和generator操作,得到滿(mǎn)足條件的結果鏈表.Generator操作與導航操作相對應.該代數還支持結構遞歸等程序語(yǔ)言特點(diǎn)用Haskell程序語(yǔ)言作為表達形式.上述兩種代數還僅停留在邏輯層次,沒(méi)有考慮與之相對應的物理代數和查詢(xún)優(yōu)化策略，其優(yōu)勢是具有較高的描述性和豐富的語(yǔ)義與查詢(xún)語(yǔ)言有密切的轉換關(guān)系;但其操作中對路徑的處理并不完善,形成過(guò)多的遞歸結構叫或者遍歷操作叫,給下一步的優(yōu)化帶來(lái)困難,但其處理XML查詢(xún)的方法和思路被后來(lái)的XML代數規則大量采用.基于文獻[2,3]等,W3C于2001年公布了一- 個(gè)XML查詢(xún)代數標準XQuery 1.0 Formal Semanticsl(',用于規范查詢(xún)語(yǔ)言語(yǔ)義.該標準遵循簡(jiǎn)化的XQuery 1.0和Xpath 2.0 Data Mode!'l].比照關(guān)系代數給出了XML數據模型的投影、選擇和連接等操作的定義,還引入結構遞歸、條件判斷等編程語(yǔ)言的概念.Formal Semantics的一個(gè)特點(diǎn)是代數表達與XQuery查詢(xún)語(yǔ)言相同,成為XQuery的核心語(yǔ)法;另-一個(gè)特點(diǎn)是操作有不同的層次,高層次的操作可以轉換為低層次的操作.標準中還給出了少量表達式轉換規則,有待近一步擴充.目前已經(jīng)有了應用該標準的XML查詢(xún)引擎,如Galaxl6.Standford大學(xué)開(kāi)發(fā)的XML數據庫Lore系統[7針對系統中國煤化工青況,提出了-套獨特的代數操作,包括邏輯代數、物理代數和相應的轉換規則.Lo:MHCNMH(了查詢(xún)優(yōu)化方法同,但由于代數操作定義過(guò)多地依賴(lài)于Lore本身獨特的數據存儲和系引僅不,以八雙很難應用于其他系統.Timber數據庫[9]中應用的TAX代數["0,其數據模型為無(wú)序的樹(shù)的集合,樹(shù)中的數據是有序的.直接針對樹(shù)和孟小峰等:XML查詢(xún)優(yōu)化研究2073樹(shù)枝規定了一系列操作無(wú)須中間結構的轉換.把XML數據模式看作樹(shù),把查詢(xún)語(yǔ)句也看作樹(shù),二者之間作模式匹配，得到滿(mǎn)足查詢(xún)樹(shù)條件的結果樹(shù)集合.IAX在處理連接操作時(shí)對操作的順序未做明確規定不適應嚴格要求文檔順序的情況.XAL"基于集合概念構造了邏輯代數操作集,其操作分為3種:抽取操作從XML文檔中獲得必要的數據,如選擇、投影等;元操作控制表達式求值過(guò)程,并非針對XML數據的抽取或者構造操作,而是為其他操作符準備輸入或者控制其他操作的操作,如映射、迭代等;構造操作用于構造查詢(xún)結果.XAL為查詢(xún)優(yōu)化提供了一組啟發(fā)式轉換規則.其他如XOM代數(!21,是完整的操作集,包含6種對象操作,但不支持優(yōu)化;OPAL代數13]基于半結構化數據模型,操作對象為多個(gè)鏈表,將有限狀態(tài)自動(dòng)機用于生成執行計劃;還有SAL等104-17.根據代數的操作方式,可將上述不同的方法分為兩種:一種是面向集合的代數,其操作對象是某種類(lèi)型的集合,如樹(shù)的集合、值的集合等.這種方法具有很好的優(yōu)化基礎,但可能丟失數據的順序;另一種稱(chēng)為導航的代數,其操作對象是單個(gè)的數據這種方法不利于進(jìn)一步的優(yōu)化.代數定義應是邏輯操作與物理操作的有機結合.但目前的XML代數研究或是把他們混合在一起,或是雖然分開(kāi)但缺乏相應的轉換規則.早期對XML代數的研究工作重點(diǎn)在于規范XML查詢(xún)語(yǔ)義,并未考慮查詢(xún)優(yōu)化因素,這些代數具有明顯的程序化思想,很難進(jìn)一步優(yōu)化,只能利用遍歷方法求解查詢(xún),造成查詢(xún)效率的低下,不適應大規模XML數據的查詢(xún)需求.而基于數據庫思想提出的一些面 向“集合”的代數,具有很好的優(yōu)化基礎.因此,目前查詢(xún)優(yōu)化的研究工作也多以這些代數為背景,但也存在一些問(wèn)題.首先是表達式嵌套問(wèn)題.在XQuery查詢(xún)中,由于表達式可以任意嵌套,謂詞可以出現在任意地方.謂詞是有作用域的,同--個(gè)謂詞在不同的地方會(huì )產(chǎn)生不同的查詢(xún)結果基于集合的代數需要將嵌套的查詢(xún)轉換為邏輯樹(shù)形式,不可避免地面臨嵌套結構的非嵌套化問(wèn)題.雖然在關(guān)系數據庫中有一些方法可以借鑒,但由于XML數據結構的復雜性,解決這個(gè)問(wèn)題變得更加困難.其次是XML數據的有序性問(wèn)題除非查詢(xún)語(yǔ)句特別指定,否則應該保持結點(diǎn)在源文檔中的結點(diǎn)順序.而原來(lái)- -些處理連 接的算法,比如排序連接、Hash連接等會(huì )打亂結點(diǎn)順序,在連接完成后,需要對連接結果做- -個(gè)額外的根據結點(diǎn)順序的排序操作如果用nest-loop連接算法，則可以省去這趟額外的排序在進(jìn)行代價(jià)估計的過(guò)程中,這個(gè)額外的排序操作要被考慮在內,這就給進(jìn)行查詢(xún)優(yōu)化的過(guò)程帶來(lái)新的考慮因素.-種可能的解決方法是在所有操作中，忽略結點(diǎn)的有序性,在最后構造結果的時(shí)候再對結點(diǎn)按照文檔順序排序.究竟是使用nestloop,還是最后增加額外的排序的方法,這是查詢(xún)優(yōu)化的一個(gè)研究點(diǎn).最后,不同的代數標準在XML代數研究中一個(gè)值得重視的問(wèn)題是:目前已經(jīng)出現了-些查詢(xún)代數標準,這些標準在風(fēng)格上相去甚遠,很難有共通性.而對執行方法的研究還遠遠不夠,不能形成完整的系統.而且從邏輯代數到物理代數的轉換也將是未來(lái)研究的一個(gè)重要問(wèn)題.3.2 復雜路徑表達式分解目前的XML查詢(xún)語(yǔ)言有很多,如XatlI81,Queuy19,XMLQL*Q,Q"Quit2等它們的一個(gè)共同的特點(diǎn)就是對復雜路徑表達式的支持.路徑表達式分解是根據一定的轉換規則,把用查詢(xún)語(yǔ)句表達的、復雜的、不確定的路徑表達式轉換為簡(jiǎn)單的、明確的、系統可識別的方式，如XML代數路徑表達式分解是查詢(xún)轉換的難點(diǎn)也是查詢(xún)優(yōu)化的重要一步,是代價(jià)估計的前提條件根據不同的規則,路徑表達式可能分解為不同的等價(jià)形式,其中有的代價(jià)高,有的代價(jià)低,形成代價(jià)空間.路徑分解的原則是能夠產(chǎn)生有限的代價(jià)空間,有利于利用分解的結果搜索代價(jià)最小的執行方案.在路徑分解時(shí),有兩種不同的思路:--種思路是把路徑細分為兩兩的祖牛后代成少子對t如lore,1sS2)等.這樣做分解算法簡(jiǎn)單,可利用數據物理存儲信息,分解的結果容易MYH中國煤化工系統提供的各種索引.如果查詢(xún)語(yǔ)句中出現通配符(如*,2,/,可以利用索引直接C N M H G息確定通配符所代表的各種可能情況擴展路徑.經(jīng)過(guò)分解,路徑表達式轉換為連接、投影、選擇、導航等不同的代數運算;另一種思路叫9是將復雜路徑表達式用樹(shù)的方式表示:從根開(kāi)始,在樹(shù)中搜索最長(cháng)的確定路徑(不含*或/I稱(chēng)為一次分2074Journal of Sofware軟件學(xué)報Vol.17, No.l0, October 2006解,其路徑構成樹(shù)的一個(gè)子串.以這個(gè)點(diǎn)為起點(diǎn)用上述原則再分解路徑,得到確定路徑(子串)的集合,稱(chēng)為- -個(gè)最小分解.在XML文檔的查詢(xún)中,確定路徑的查詢(xún)是相對容易的;而不確定路徑的查詢(xún)是比較困難的,尤其是在沒(méi)有模式或索引的情況下，可能要將中間結果合并才能得到全部的結果.將復雜的、不確定的路徑分解為確定的、簡(jiǎn)單的路徑處理這種分解方法在沒(méi)有模式信息的情況下處理不確定路徑具有一定的優(yōu)勢.4邏輯優(yōu)化在傳統數據庫技術(shù)中,邏輯優(yōu)化是指通過(guò)一系列轉換規則,將原始的查詢(xún)表達式轉換為等價(jià)且更高效的形式，關(guān)系代數表達式求解時(shí),操作順序是影響效率的關(guān)鍵.因此,邏輯優(yōu)化研究的重點(diǎn)并不在于對冗余操作的分析,而是對操作順序的調整.而XML代數的核心是由路徑表達式轉換的查詢(xún)樹(shù),查詢(xún)效率依賴(lài)于查詢(xún)樹(shù)的規模.因此,查詢(xún)樹(shù)的最小化是XML邏輯優(yōu)化研究的重點(diǎn),也是目前研究的熱點(diǎn)問(wèn)題.而對操作順序的調整因為更多地依賴(lài)于物理存儲的情況,因此與物理優(yōu)化相關(guān)聯(lián).從層次上看,邏輯優(yōu)化可分為兩個(gè)層次:語(yǔ)法層次和語(yǔ)義層次.語(yǔ)法層次的優(yōu)化是指不依靠任何其他信息,獨立地分析查詢(xún)表達式中分支或結點(diǎn)間的邏輯包含關(guān)系,刪除冗余部分;語(yǔ)義層次的優(yōu)化是指通過(guò)數據庫提供的模式信息，如DTD,XML Schema等,或者語(yǔ)義包含、結構包含等完整性約束,查找查詢(xún)表達式中的冗余分支或結點(diǎn)下面的例子進(jìn)一步說(shuō)明二者之間的區別.若有如下的XQuery查詢(xún)表達式: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(以下簡(jiǎn)稱(chēng)PTQ)如圖2(a)所示,其中,實(shí)心圓為查詢(xún)返回結點(diǎn)若數據滿(mǎn)足Sc,同時(shí)必然滿(mǎn)足$b,$b分支對查詢(xún)返回結果沒(méi)有任何影響,是冗余結點(diǎn)我們稱(chēng)這種冗余結點(diǎn)為語(yǔ)法冗余結點(diǎn)經(jīng)語(yǔ)法優(yōu)化后的PTQ如圖2(b)所示.若從模式可知任- - author 均有name,則v6為冗余結點(diǎn)我們稱(chēng)這種冗余結點(diǎn)為語(yǔ)義冗余結點(diǎn)經(jīng)語(yǔ)義優(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ǔ)法優(yōu)化和語(yǔ) 義優(yōu)化下面我們分別介紹語(yǔ)法優(yōu)化和語(yǔ)義優(yōu)化的研究現狀.4.1語(yǔ)法優(yōu)化.對PTQ 語(yǔ)法優(yōu)化問(wèn)題基于對路徑等價(jià)性問(wèn)題[25 281的研究.最早提出XPath 最小化的Woodl29)指 出:- -個(gè)Xpath可以表示為合取范式，對XPath等價(jià)性檢查的復雜度等價(jià)干對取蘆式的筆價(jià)性檢查.而這已經(jīng)證明是一個(gè)NP完全問(wèn)題.如果對XPath路徑表達式的復雜程度加以一中國煤化工的復雜度可以達到多項式級.目前已經(jīng)提出了對不同類(lèi)型的PTQ的最小化方法.MYHCNMHG(1) 簡(jiǎn)單PTQ{,D,*}文獻[29]中提出了對只包含{/,0,*}的簡(jiǎn)單路徑的最小化方法其思想為:設原始PTQ為P,在所有與之等價(jià)孟小峰等:XML查詢(xún)優(yōu)化研究2075的PTQ中找到Q,使得e中的結點(diǎn)個(gè)數|NQ[最小,則Q為P的最小化PTQ.這種方法的關(guān)鍵是通過(guò)對包含映射(containment mapping)的判斷完成PTQ的等價(jià)性判斷.不存在祖先后代關(guān)系(/)的簡(jiǎn)單PTQ的最小化PTQ為其子樹(shù).查找等價(jià)PTQ的范圍限制在其子樹(shù)的范圍內,是保證最小化算法的復雜度為多項式級的關(guān)鍵因素.文獻[22]中給出了復雜性證明,雖然并未給出算法細節.(2) PTQ/{,/,Q]}文獻[30]提出了PTQ的CIM(constraint independent minimization)算法與文獻[29]相同,其算法的基礎也是包含映射路徑中缺少“*”的PTQ的最小化問(wèn)題,仍舊可以在其子樹(shù)范圍內解決.CIM算法的思想為:從葉結點(diǎn)開(kāi)始,判斷結點(diǎn)在PTQ中是否冗余:若某結點(diǎn)是冗余結點(diǎn)則刪除這個(gè)結點(diǎn),繼續處理其他葉結點(diǎn)直到所有葉結點(diǎn)判斷完畢;若PTQ中結點(diǎn)個(gè)數為n,則CIM算法的最大復雜度為0(n).文獻[31]提出了一-種 最大復雜度為0()的改進(jìn)算法,通過(guò)結點(diǎn)間的二元關(guān)系Simultion 判斷冗余性改進(jìn)的CIM算法與CIM算法最大的不同點(diǎn)在于:前者只關(guān)心后代結點(diǎn)之間是否相同;而后者還要關(guān)心祖先結點(diǎn)之間是否相同.改進(jìn)的CIM算法通過(guò)正向遍歷查找冗余結點(diǎn),如果某結點(diǎn)的一個(gè)兒子結點(diǎn)與另外兒子結點(diǎn)之間有Simulation關(guān)系，則這個(gè)兒子結點(diǎn)為冗余結點(diǎn)這樣,在一次遍 歷可以對多個(gè)結點(diǎn)的冗佘性進(jìn)行判斷,從而提高了PTQ最小化的效率.(3) PTQ/{,/,D,*}與限制條件下PTQ所不同的是,普遍意義下的PTQ在語(yǔ)法優(yōu)化時(shí)遇到的一個(gè)關(guān)鍵問(wèn)題是:最小化PTQ并非原始PTQ的子樹(shù),而是由以原始PTQ的根為根,連接多個(gè)PTQ子樹(shù)構成的PTQ.其中每個(gè)子樹(shù)均為原始子樹(shù)的最小化部分.這個(gè)問(wèn)題也是導致其復雜度上升的關(guān)鍵.文獻[32]給出普遍意義下的PTQ最小化算法.其算法思想是:遞歸地在原始PTQ的子樹(shù)中查找最小子樹(shù)并連接它們,在這個(gè)過(guò)程中冗余的分支被刪除了.文獻[32]證明其算法的復雜度為NP完全,并指出:在對PTQ的分支個(gè)數加以--定限制的情況下,改進(jìn)的算法復雜度可以達到多項式級但我們有理由相信,這樣的改進(jìn)意義并不大,因為這要求用戶(hù)在寫(xiě)查詢(xún)語(yǔ)句時(shí)必須注意查詢(xún)的分支情況,否則將導致某些查詢(xún)無(wú)法優(yōu)化.目前,語(yǔ)法優(yōu)化都以判斷結點(diǎn)之間的包含映射關(guān)系為基礎,分析路徑等價(jià)性在查詢(xún)樹(shù)中不斷地修剪冗余的分支或結點(diǎn),達到減少查詢(xún)樹(shù)規模的目的.普遍意義的PTQ語(yǔ)法優(yōu)化是一個(gè)NP完全問(wèn)題,研究者通過(guò)對pTQ復雜度加以一定限制,提出 了多種高效的算法.語(yǔ)法優(yōu)化不涉及XML模式信息,可以利用模式信息進(jìn)一步簡(jiǎn)化PTQ,這種優(yōu)化稱(chēng)為語(yǔ)義優(yōu)化.4.2語(yǔ)義優(yōu)化最早提出語(yǔ)義優(yōu)化的是關(guān)系數據庫系統,利用表格屬性值之間的約束關(guān)系把查詢(xún)表達式轉換為等價(jià)但更高效的形式.chase方法是其中的代表其思想為:把完整性約束作為冗余條件插入到查詢(xún)表達式中,與已存在的冗余操作合并,使得組合后的條件符合某些事先定義好的等價(jià)轉換規則,利用這些等價(jià)轉換規則重寫(xiě)查詢(xún)表達式以達到優(yōu)化的目的.這是一個(gè)巧妙的先膨脹再收縮的方法.但是,應用Chase方法于XML查詢(xún)的語(yǔ)義優(yōu)化時(shí)面臨下述嚴重的挑戰:數據結構的變化:與平面表結構不同,XML數據具有嵌套性.原有的主鍵、外鍵等完整性約束不能表達結構上的嵌套關(guān)系,缺乏匹配的轉換規則.數據類(lèi)型的變化:關(guān)系模型中,數據有嚴格的類(lèi)型;而在XML半結構化模型中,數據沒(méi)有嚴格的類(lèi)型約束,同名的結點(diǎn)可以出現在不同的位置,可以有不同的子結點(diǎn).傳統的轉換規則的應用方法不適應這種情況,引發(fā)的問(wèn)題就是產(chǎn)生遞歸的轉換,導致路徑的無(wú)限增長(cháng).查詢(xún)語(yǔ)句的復雜性:SQL語(yǔ)句清晰、明確,關(guān)系代數操作均為輸入參粕明確的一中國煤化工=運算.而XML查詢(xún)語(yǔ)句中包含/等不確定因素,并以包含多個(gè)分支長(cháng)路徑為特點(diǎn)EML語(yǔ)義優(yōu)化.基于上述挑戰,一些研究者 提出改進(jìn)的Chase 方法,而另一MYHC N M H G的角度出發(fā),研究XML查詢(xún)的語(yǔ)義優(yōu)化問(wèn)題.(1)改進(jìn)的 Chase方法2076Journal of Sofware軟件學(xué)報Vol.17, No.10, October 2006Wood等人(29]最早將Chase 方法引入簡(jiǎn)單XPath 語(yǔ)義優(yōu)化.文獻[29]在DTD上定義了3種結構約束關(guān)系,分別為兒子約束、父親約束和兄弟約束.若某個(gè)查詢(xún)樹(shù)中結點(diǎn)n為上述約束關(guān)系中的主體,且其約束的結點(diǎn)不在查詢(xún)樹(shù)中,則在查詢(xún)樹(shù)中相應位置加入客體結點(diǎn).當所有約束關(guān)系應用完畢,再用語(yǔ)法優(yōu)化的方法對查詢(xún)樹(shù)進(jìn)行修剪,得到最小化查詢(xún)樹(shù).為了討論簡(jiǎn)單起見(jiàn),文獻[29]中方法只適用于不包含“*”和/”的簡(jiǎn)單路徑,其復雜度為多項式級.文獻[30]則認為,XML數據中的結構完整性約束可用兒子約束、后代約束和類(lèi)型約束概括.為了得到正確的優(yōu)化結果,他們對Chase方法做了3個(gè)方面的改進(jìn):首先,假設約束集合是閉包的;其次,為了保證優(yōu)化能夠完成,約束條件只應用于PTQ中原有結點(diǎn),如果某結點(diǎn)是由于應用某約束條件加入PTQ的,則不對其應用任何約束條件;最后,由于應用約束條件加入的結點(diǎn)是冗余的,因此,需要在算法結束時(shí)刪除這些臨時(shí)結點(diǎn).ACIM算法分為3個(gè)步驟:首先,應用約束集合中的約束條件放大PTQ;然后,應用CIM算法語(yǔ)法刪除冗余結點(diǎn),在刪除時(shí)保證不檢查被加入臨時(shí)結點(diǎn)的冗余性;最后,刪除所有在第-步中加入的臨時(shí)結點(diǎn)若PTQ中結點(diǎn)個(gè)數為n,則ACIM算法的最壞計算復雜度為0(n).-些冗余結點(diǎn)是容易識別的,如果提前刪除這些容易識別的冗余結點(diǎn)然后再應用ACIM算法,可以有效地提高優(yōu)化的效率.算法CDM在PTQ中遍歷地查找并刪除這樣的冗余結點(diǎn)其計算復雜度為0(n3).實(shí)驗證明,在使用ACIM之前使用CDM,比直接應用ACIM可更為有效地節省時(shí)間..文獻[31]在文獻[30]的基礎上擴充了子類(lèi)約束，并利用語(yǔ)法優(yōu)化中的TPQSimulation和TPQMinimization改進(jìn)了ACIM算法,使計算復雜度達到0(n).(2)基于 DTD的路徑等價(jià)類(lèi)方法文獻[34]提出了一種基于模式的XPath 路徑表達式的語(yǔ)義優(yōu)化方法.其思想是:把XML文檔模式(DTD)劃分為若干個(gè)路徑等價(jià)類(lèi),每個(gè)類(lèi)中的路徑等價(jià);將XPath轉換為由簡(jiǎn)單路徑構成的合取范式形式,利用路徑等價(jià)類(lèi)中的最短路徑代替表達式中的路徑.通過(guò)這種方法,可以實(shí)現3個(gè)方面的優(yōu)化:首先,刪除冗余的謂詞條件;其次簡(jiǎn)化路徑;最后,判斷表達式的條件是否滿(mǎn)足如果某個(gè)分支的條件不滿(mǎn)足模式中的約束關(guān)系則整個(gè)表達式的查詢(xún)結果為空.整個(gè)優(yōu)化過(guò)程分為4部分:分解、擴展、優(yōu)化和重構.在分解過(guò)程中,XPath表達式被轉換為合取樹(shù)(XCT);重構XPath表達式則將優(yōu)化的XCT轉換為XPath 路徑表達式.改進(jìn)的Chase方法的優(yōu)點(diǎn)是:語(yǔ)法優(yōu)化與語(yǔ)義優(yōu)化相結合,優(yōu)化過(guò)程無(wú)須對PTQ進(jìn)行轉換.問(wèn)題是難以保證徹底的優(yōu)化:首先,PTQ中存在非葉冗余結點(diǎn),而語(yǔ)法優(yōu)化只能在刪除葉結點(diǎn)后,讓非葉結點(diǎn)變?yōu)槿~結點(diǎn)的情況下才能判斷其冗余性.加入約束條件后的PTQ. 語(yǔ)法優(yōu)化,不能在不刪除葉結點(diǎn)的情況下,判斷非葉結點(diǎn)的冗余性;其次,膨脹后的PTQ難以壓縮,采用對轉換規則加以-定限制的方法限制膨脹后PTQ規模的方法,會(huì )導致優(yōu)化的不徹底.目前改進(jìn)的Chase方法都是針對一定復雜程度的PTQ的優(yōu)化策略,普遍意義上的PTQ的語(yǔ)義優(yōu)化研究還需深入;最后，從DTD中獲得的約束條件并不充分,這也是導致優(yōu)化不徹底的一個(gè)因素. 如何抽取更多的語(yǔ)義約束條件,是未來(lái)研究的- -個(gè)重要問(wèn)題.基于DTD的優(yōu)化方法的優(yōu)點(diǎn)是:不但能夠刪除冗余分支,還能夠縮短路徑長(cháng)度和直接判斷路徑是否滿(mǎn)足.問(wèn)題主要是:首先,需要對PTQ進(jìn)行轉換，占用大量?jì)?yōu)化時(shí)間;其次,需要不確定路徑的確定化,這實(shí)際上也是一-種路徑膨脹,難以保證優(yōu)化的結果小于優(yōu)化之前.兩種方法都需要首先擴大路徑規模造成優(yōu)化的不徹底和效率的喪失,這是目前語(yǔ)義優(yōu)化面臨的一一個(gè)重要問(wèn)題5物理優(yōu)化邏輯優(yōu)化的結果是一個(gè)或多個(gè)查詢(xún)樹(shù).如何確定其中不同查詢(xún)片斷的執行次序,是XML物理優(yōu)化的核心問(wèn)題.確定執行次序的主要因素是中間結果集的大小復雜路徑表中國煤化工計結果集規模的其主導思想是:統計XML數據的分布情況,基于一定假設估計路YHCN MH G小這種方法一般忽略執行算法的不同和數據的物理存儲.本節從統計信息抽取、存儲、壓縮、維護和統計信息計算等幾個(gè)方面論述目前這一技術(shù)的發(fā)展情況和所面臨的問(wèn)題.孟小峰等:XML查詢(xún)優(yōu)化研究20775.1代價(jià)估計方法研究代價(jià)估計是對查詢(xún)物理運算時(shí)間的估計.目前,代價(jià)計算方法主要有3種:基于參數的方法、基于取樣的方法和基于統計信息計算的方法基于參數的方法31無(wú)須統計數據信息，根據數據分布情況假定其滿(mǎn)足包含某些參數的分布函數,通過(guò)計算函數的值估計查詢(xún)計劃的執行代價(jià).這種方法在處理有規律分布的數據(如學(xué)生成績(jì))時(shí),可以大量節省統計信息空間和I/O代價(jià),但對分布無(wú)明顯規律的數據會(huì )有很大的誤差;基于取樣的方法16.3)也無(wú)須統計數據信息,做法是從數據集中提取具有代表性的樣本,比較不同的查詢(xún)計劃的執行情況,獲得代價(jià)最小的方案.這種方法的精確性決定于取樣的代表性.最簡(jiǎn)單的方法是隨機取樣, -些優(yōu)化的方法根據數據的密度取樣取樣方法的缺點(diǎn)是代價(jià)估計本身占用時(shí)間可能很大;最常用也是研究最多的方法是基于統計信息的方法8,需要統計估計所用的各種信息,利用統計信息計算不同方案的執行代價(jià).這種方法的精確性取決于統計信息的正確性.但是統計信息過(guò)大又會(huì )導致統計時(shí)間過(guò)長(cháng).利用有限的時(shí)間和空間得到相對小的執行方案,是代價(jià)統計的基本原則.不同的系統支持的物理運算算法不同,代價(jià)模型也不同.在關(guān)系模型中,進(jìn)行代價(jià)估計時(shí)有兩個(gè)通用的前提:獨立性假設和均勻分布假設前者是指各謂詞之間沒(méi)有相互依賴(lài)關(guān)系;后者是指如果關(guān)系在某個(gè)屬性上沒(méi)有直方圖,則認為該屬性的各值在數據庫中均勻出現.XML數據的不規則性是對傳統統計信息方法的重要挑戰其數據分布情況使得-些傳統分布假設難以成立.在XML中相同名字的結點(diǎn)可能在同-一個(gè)文檔的不同部分出現但卻具有截然不同的語(yǔ)義如同為name結點(diǎn),在person下和在city下出現其意義就完全不同,這可以稱(chēng)為元素之間的結構依賴(lài)性;同時(shí),在XML文檔中,嵌套在不同祖先下的同類(lèi)結點(diǎn)的個(gè)數差別也很大,如book結點(diǎn)下的author個(gè)數是不確定的,這可以稱(chēng)為元素之間的結構相關(guān)性.為了達到所需的代價(jià)估計精度,需要更多的統計信息而結構的復雜性又為獲得相對精確的統計信息帶來(lái)存儲和計算上的困難.XML的有序性制約了轉換規則的靈活性.所有這些問(wèn)題,都使得在XML中采用傳統的代價(jià)估計方法不切實(shí)際，會(huì )帶來(lái)很大的誤差.針對XML數據的特點(diǎn),我們應該尋求一種新的代價(jià)估計方法.5.1.1代價(jià)模型查詢(xún)計劃的執行代價(jià)主要來(lái)自3方面的因素:CPU計算代價(jià)、I/O代價(jià)和數據傳輸代價(jià).CPU,磁盤(pán)和網(wǎng)絡(luò )的速度差距懸殊.當不考慮數據的分布性因素時(shí),影響代價(jià)的決定性因素是IO代價(jià).I/0代價(jià)受眾多因素制約,主要來(lái)自3個(gè)方面: -是數據庫系統參數,如頁(yè)面大小、內存使用情況等;二是數據集本身因素,如數據存儲空間大小、索引情況、每個(gè)元素占用空間情況和元素的聚集情況等;三是查詢(xún)請求因素,如查詢(xún)條件的選擇性等.目前,對XML代價(jià)模型的研究并不充分,代價(jià)模型相對簡(jiǎn)單，這也是造成代價(jià)估計誤差的一個(gè)原因.Lore的代價(jià)模型沒(méi)有考慮聚集情況,不能判定不同的數據是否在同一頁(yè)面上,因此,其假設每次I/O操作只能獲得-一個(gè)對象,把對I0時(shí)間的估計轉換為對中間結果大小的估計由于Lore中數據本身無(wú)聚集,這種方法可以獲得較好的效果,但對其他XML數據庫系統參考意義并不大.文獻[39]提出了一種新的代價(jià)模型,其基本思想是利用查詢(xún)反饋信息來(lái)調整參數.如圖3所示,在用戶(hù)提交查詢(xún)之前,先人工找出影響查詢(xún)執行時(shí)間的特征,再利用線(xiàn)性回歸模型計算出各個(gè)特征對查詢(xún)代價(jià)的影響系數,即得到-一個(gè)形如cos(+.,..)的函數模型,當用戶(hù)提交查詢(xún)時(shí),利用函數和事先統計的特征值進(jìn)行計算.但是,文中提出的方法只是針對CPU代價(jià)估計的,沒(méi)有擴展到1/o代價(jià)的估計;而且只考慮了一-個(gè) XNav操作符,至于如何擴展到其他情況,文獻[39]中并未提及.人工抽取特征具有主觀(guān)性,如何讓系統自動(dòng)地抽取特征是下一步研究的重點(diǎn).User queriesOptimizerQuery planRuntime engineTraining queriesCoMET| Training d中國煤化工:fYHCNMHGFig.3 CoMET optimization system圖3 CoMET 優(yōu)化系統2078Journal of Sofware軟件學(xué)報Vol.17, No.10, October 20065.1.2代價(jià)空間搜索 技術(shù)代價(jià)空間搜索算法首先通過(guò)某種計算方法量化代價(jià)空間、構造搜索函數,根據函數值的變化判斷是否繼續搜索在眾多的空間搜索技術(shù)中,最簡(jiǎn)單的是隨機搜索方法,隨機地或者按照某個(gè)順序在搜索空間中計算代價(jià).但這種方法效率低下,在實(shí)際的系統中很少被采用,爬山算法是應用廣泛的一種搜索算法,在以某步長(cháng)對函數進(jìn)行搜索的過(guò)程中按照逐步接近的方式,定位局部最優(yōu)執行計劃,搜索的效率與初始值和步長(cháng)相關(guān)當搜索函數非單調時(shí),這種方法找到的是局部極值,而非全局最值遺傳算法是解決局部最優(yōu)的一種新穎的空間搜索方法,用雜交的方法搜索不同的最優(yōu)執行計劃，適用于有多個(gè)極值的搜索函數.這種方法在關(guān)系數據庫查詢(xún)優(yōu)化中有一定的應用意義,在XML查詢(xún)優(yōu)化的代價(jià)空間搜索技術(shù)中應用遺傳算法的難點(diǎn)在于適應度函數的構造.單個(gè)查詢(xún)物理計劃形成的代價(jià)空間可能非常龐大,尤其是對路徑很長(cháng)的情況，其代價(jià)空間呈冪次級增長(cháng).為了減少代價(jià)估計時(shí)間,需要利用啟發(fā)性規則約束代價(jià)空間.Lore的做法是:分別將每一個(gè)邏輯操作轉換為最優(yōu)物理子計劃,并在轉換時(shí)應用啟發(fā)性規則.例如:TargetSet操作只在路徑表達式的起始結點(diǎn)是標記名并且只在路徑結束結點(diǎn)上有變量約束時(shí)使用;當查詢(xún)中有多個(gè)路徑表達式時(shí),不改變其間的順序值得注意的一條規則是選擇操作總在最后做.這條規則和關(guān)系查詢(xún)優(yōu)化的啟發(fā)性規則正好相反.這是由于在Lore中,選擇運算總是基于變量綁定運算.在XML代價(jià)估計研究中,路徑表達式選擇性代價(jià)估計是核心問(wèn)題,也是在XML查詢(xún)優(yōu)化研究中份量最重的一個(gè)領(lǐng)域,值得我們特別關(guān)注在第5.2節中我們將做專(zhuān)門(mén)的論述.5.2路徑表達式選擇性代價(jià)估計XML路徑表達式可視為一棵樹(shù),其中的一個(gè)主支為從起點(diǎn)到目標點(diǎn)的主路徑,其余分支為約束主支的謂詞條件(如圖4所示)，表示為P=p.]....I.J.其中:1為結點(diǎn)名;p:為謂詞默認存在量詞布爾表達式.路徑表達式的選擇性估計是對滿(mǎn)足分支條件的主支數據個(gè)數的估計.對XML路徑表達式的估計需要數據結構的統計信息與分布在結構內部的值的統計信息的結合，以計算路徑的選擇性.只lab中/*/e口lg1d (占If8 leFig.4 /albJ///*/*/f/f圖4 /a(l///e/e/f//*/*/ff5.2.1數值 統計Chen等人(40把數值結點(diǎn)作為普通結點(diǎn)看待,這樣,估計a=3與a.3是等價(jià)的,簡(jiǎn)化統計結構,，適用于數值量較少的情況.如果數值量龐大,統計每一-個(gè)數值的個(gè)數會(huì )占據大量的空間,導致統計信息過(guò)多,影響查詢(xún)代價(jià)估計的效率.這種方法對等值的定點(diǎn)查詢(xún)可以使用,卻很難估計范圍查詢(xún)的代價(jià).如估計a>3的代價(jià),需要遍歷統計信息中所有同類(lèi)數值結點(diǎn),判斷其值是否滿(mǎn)足條件.中國煤化工Freire 等人(4"用 直方圖等方法分別統計不同類(lèi)型的數值信|YHCNMHG值、個(gè)數等信息.即適用于范圍查詢(xún),也適用于點(diǎn)查詢(xún).其缺點(diǎn)是:數據類(lèi)型過(guò)多會(huì )導致統計信息的膨脹;并且,XML數據的特點(diǎn)是自描述性,其值和結構有密切的語(yǔ)義關(guān)系,分開(kāi)統計必然導致分別估計，造成估計誤差,在文獻[41]中有關(guān)于這方孟小峰等:XML查詢(xún)優(yōu)化研究2079面的詳細論述.5.2.2數據結構抽取XML數據為有序有向圖.對圖的結構抽取有兩種極端的方法1(21:標記分裂圖(label-split graph)方法粗略地統計模式信息,其思想是合并所有的標記名相同的結點(diǎn)為一個(gè)結點(diǎn)記錄合并結點(diǎn)的個(gè)數作為標記的統計信息.這種方法占用空間相對較小，但不能精確地反映數據分布的真實(shí)情況,尤其是同名結點(diǎn)出現在不同位置上時(shí),可能包含錯誤的路徑或者圈信息;B/F類(lèi)似圖(B/F-bisimiar graph)中 ,只有所有入邊和出邊集合相同時(shí)才合并同名的結點(diǎn),保證準確地統計路徑表達式所有的分支情況.這種方法的缺點(diǎn)是占用空間大.查詢(xún)優(yōu)化的統計信息控制在-定的范圍內,現有系統的抽取方法都是介于兩個(gè)極端的情況之間.Lore的DataGuidel43]抽取 模式的方法是保證每條路徑只出現一次,其最小模式是標記分裂圖的一一個(gè)例子.文獻[43]指出:這種方法統計路徑信息能夠精確判斷路徑是否存在,但并不能更精確地統計不同結點(diǎn)的值在不同路徑中的分布情況.如圖5所示:圖5(c)為圖5(a)的最小DataGuide.如果對結點(diǎn)19的統計信息為t,根據圖5(c)無(wú)法判斷是路徑A.C或者B.C的結點(diǎn)個(gè)數;圖5(b)為圖5(a)的強壯DataGuide.如果對結點(diǎn)12 和13的統計信息為12和13,根據圖5(b)判斷路徑A.C的個(gè)數為1z,B.C的個(gè)數為13.)'BBA\Bc自尚尚2|DD|pD面面面(a)b)(c)Fig.5 XML data and its corresponding DataGuides圖5 XML 數據和DataGuidesStatixX[4]根據 XML Schema統計結構信息,它是-種折衷的方法出邊不同但同類(lèi)型的結點(diǎn)合并為一個(gè),系統對不同類(lèi)型的結點(diǎn)標記以不同區域的值,按照區域分別統計不同路徑的結點(diǎn)個(gè)數,保留了分支結點(diǎn)的路徑分布信息兒子結點(diǎn)的分布情況保留在父親結點(diǎn)的統計信息中.每個(gè)結點(diǎn)的統計信息不再是單個(gè)的值,而是一個(gè)復雜的結構.導致的問(wèn)題一是代價(jià)信息的增長(cháng),二是代價(jià)估計算法的復雜性.Xsketchl421也是一種折衷 的方法,但只統計結構中每個(gè)結點(diǎn)對應數據中結點(diǎn)的個(gè)數信息.其特別之處在于對結點(diǎn)入邊和出邊的信息的統計.如果對任意結點(diǎn)v∈V,存在ueU,在數據集中都有邊(,),則V對U向后固定,如果對任意結點(diǎn)u∈U,存在v∈V,在數據集中都有邊(u,),則U對V向前固定.這種統計信息用于在合并不同分支與主支之間選擇性代價(jià)估計的計算.上述方法統計的只是路徑中父子之間的關(guān)系，而沒(méi)有統計同父的兄弟之間的相關(guān)性.為了便于計算相對路徑的代價(jià)和統計路徑之間的相關(guān)性,Chen等人[401吸收了信息檢索中在文檔中檢索子串的采用后綴樹(shù)的方法144統計路徑信息,稱(chēng)為相關(guān)子路徑樹(shù)(orrelated subpath tre).從XML數據中抽取所有到葉子的可能路徑,形成路徑集合,其中間結點(diǎn)的結點(diǎn)名為不可分割子串;葉結點(diǎn)為數值或者字符串值,為可分割子串.每個(gè)結點(diǎn)存儲子路徑在數據中出現的次數和路徑特征矢量.我們將在后面的選擇性V中國煤化工代價(jià)計算方法;在信息統計部分介紹后綴樹(shù)信息的存儲和修剪維護方法.THCNMHGXSketchesl45.46]在 文獻[42]的基礎上增加了對邊的信息和值時(shí)信息的統,MlU任一定心圍內(TSN)能夠處理結構和值或值和值的相關(guān)性問(wèn)題.但增加信息的同時(shí),也使得構造XSketches結構代價(jià)加大.在XSEED4T中提2080Journal of Sofrware軟件學(xué)報Vol.17, No.10, October 2006到:為100M的XMarkl(8文檔構造一個(gè)XSketches 結構需要超過(guò)一天的時(shí) 間,這在實(shí)際中變得不可接受.針對XSketches的缺點(diǎn),XSED47提出了一種新的處理思路,即抽取最粗略的信息,稱(chēng)為XSEED內核,-般只占文檔大小的2%左右;然后,再利用查詢(xún)反饋的信息把誤差最大的那部分路徑選擇率的精確值存儲起來(lái),而這部分存儲的信息的多少是根據內存大小來(lái)確定的.但是,這種方法只能處理XPath.如果把XML數據看作樹(shù),對樹(shù)中的結點(diǎn)按照(start,end)49編碼，以start為橫坐標,end為縱坐標,則樹(shù)中所有結點(diǎn)可看作是平面空間.上的點(diǎn),路徑上的祖先和后代關(guān)系滿(mǎn)足xtncoerdrmeSedrsndmsSncrsrn把整個(gè)空間區域分成多個(gè)方格,統計結點(diǎn)在每個(gè)格中的分布個(gè)數;Wu等人50的思想是:把不同結點(diǎn)映射為-維坐標上的線(xiàn)段,祖先線(xiàn)段和后代線(xiàn)段的起點(diǎn)及長(cháng)度滿(mǎn)足某種偏序關(guān)系,把整個(gè)區間分成多個(gè)小區間,分別計算落在不同區間內的線(xiàn)段之間的關(guān)系這種方法減少了稀疏分布時(shí)的誤差,但不能完全避免.這兩種統計方法適用于對結構連接運算的代價(jià)估計.5.2.3選擇性計算當XML數據結構復雜、每個(gè)文檔的數據量很大時(shí)，精確地統計信息是不可能的.在計算查詢(xún)代價(jià)時(shí),需要用一些假設來(lái)彌補統計信息的不足.目前的路徑選擇性計算方法分為3種:(1)基于 馬爾可夫鏈的方法.Lorel4)的方法基于馬爾可夫鏈思想,用于計算沒(méi)有分支條件的簡(jiǎn)單路徑.系統中只保留短路徑的選擇性統計信息，基于父子結點(diǎn)分布的獨立性假設計算長(cháng)路徑選擇性.如有長(cháng)路徑t2/2/...其選擇性計算公式可以是(..+.)=+i Lo4此時(shí),只需保留長(cháng)度為1和2的路徑信息也可以是(42.1)[..-)x f554).則需保留長(cháng)度為n- -2和n-1的路徑信息路徑信息越長(cháng),組合個(gè)數越多,占用空間越大,計算值越精確.實(shí)驗表明,當路徑信息較短時(shí),加長(cháng)路徑信息導致明顯的計算精確性,且空間代價(jià)增長(cháng)相對緩慢;當路徑信息較長(cháng)時(shí),加長(cháng)路徑信息導致空間代價(jià)的爆炸性增長(cháng)，而精確性提高緩慢如果在路徑的某個(gè)結點(diǎn)上有對簡(jiǎn)單值的選擇,則根據兄弟分布獨立性原則,計算不同選擇性再做交集運算.Aboulnaga等人1對Lore的方法進(jìn)行了改進(jìn),提出了路徑(path)樹(shù)和Markov表來(lái)估計簡(jiǎn)單路徑的選擇性.用路徑樹(shù)可以表示原文檔的結構,樹(shù)中的每一個(gè)結點(diǎn)代表了從文檔的根結點(diǎn)開(kāi)始的路徑,并記錄了相應結點(diǎn)出現的次數.但當樹(shù)變得很大以至于不能放在內存的時(shí)候,就需要對樹(shù)進(jìn)行剪枝,根據一定的算法,刪去那些出現不頻繁的結點(diǎn)，然后在這個(gè)剪枝過(guò)的樹(shù)上進(jìn)行選擇率的估算.Markov表存儲長(cháng)度為m (m>=2)的不同路徑,如果查詢(xún)的長(cháng)度和m相等,直接就可以從表中讀出相應的值,誤差為0;當長(cháng)度大于m時(shí),用公式f/.../t.)= /.1+...)x.)進(jìn)行計算.同樣地,當表不能放入內存時(shí),刪除那些不頻繁路徑.Xsketch142]增加 了對邊的固定性統計信息,并對Lore 的方法做了改進(jìn),以適用于更- -般的路徑表達式代價(jià)估計.如果主路徑是向后固定的,則統計信息為精確信息,無(wú)須進(jìn)-步計算;如果主路徑中有些點(diǎn)不是向后固定的，則在這些點(diǎn)上把主路徑分為多個(gè)子路徑根據路徑獨立性假設,用類(lèi)似Lore的公式,以子路徑統計信息為參數,計算長(cháng)路徑的選擇性.如果分支路徑是向前固定的,則其選擇性為1,無(wú)須參與計算;如果分支路徑中有些點(diǎn)不是向前固定的,則在這些點(diǎn)上把分支路徑分為多個(gè)子路徑,計算不同選擇性,再做交集運算.為了提高計算的精確性,其代價(jià)路徑分解方法為最大交叉方法.Xketches45.46對文獻[42]的工作進(jìn)行了擴展,可以計算twicMH中國煤化工模型的基礎上增加了邊的分布信息,從而能夠從細節上把握數據的分布.這種CNMHG文檔的結構建立.XSketches,然后利用邊的穩定性和邊的分布概率來(lái)估計twig的匹配個(gè)數,如果邊的確是分布均勻的話(huà)，那么這孟小峰等:XML查詢(xún)優(yōu)化研究2081種方法的準確率就比較高.XSEED47方法在XSEED核結構上增加了對遞歸結點(diǎn)的處理,遞歸結點(diǎn)是指在DTD中有類(lèi)似A(+,B*)的定義,則A結點(diǎn)是一-個(gè)遞歸結點(diǎn).XSEED核結構在邊上記錄了在遞歸的不同層相應的父親、孩子的結點(diǎn)個(gè)數.因此,這種方法可以很好地處理帶有遞歸表達式的XPath查詢(xún).馬爾可夫鏈思想中的一一個(gè)關(guān)鍵性假設是父子結點(diǎn)分布獨立性和兄弟結點(diǎn)分布獨立性假設.而實(shí)際上,很多XML數據的父子結點(diǎn)、兄弟結點(diǎn)之間的相關(guān)性非常強,應用上述計算方法會(huì )導致誤差集合哈希方法統計相同分支之間的相關(guān)性信息，更準確地計算分支路徑的選擇性.(2)集合哈希方法集合哈希方法(0的核心思想來(lái)自蒙特卡羅技術(shù)的Min-Wise independent permutionsl4!.這種方法用于估計兩個(gè)集合之間的相似性,集合的特征通過(guò)設置哈希函數的集合獲得.其優(yōu)勢在于集合的哈希函數值占用存儲空間很小.對集合A,其特征矢量為stg(4=(min({m(),min({])..min({(4)).其中,U-/{,..n};z是U的排列;1是哈希函數的個(gè)數.sigau.uhs [的= mni{jg.....[i}.假設Ay為勢最大的集合,則j=;|A!而|A∪...UA.|4..∪A |=|{min{z()}=.. =min{/(4)}}1014|關(guān)于集合哈希函數的構造方法在文獻[44]中有詳細的論述.利用集合哈希方法計算路徑表達式的代價(jià)的方法為:用后綴樹(shù)統計所有可能出現在查詢(xún)中的子路徑的特征矢量;分解查詢(xún)?yōu)槎鄠€(gè)相關(guān)子路徑;應用公式計算選擇性.文獻(40]中提供了3種路徑分解的方法,并比較了不同方法之間的優(yōu)劣這種代價(jià)計算的精度對路徑的長(cháng)度敏感:隨路徑長(cháng)度的增長(cháng),統計精度下降，并且，特征矢量本身是一種信息壓縮的方法,用來(lái)計算相關(guān)性時(shí)的精確性是值得商榷的.上述兩種算法都是根據確定路徑上的父子關(guān)系統計信息計算路徑表達式中后代結點(diǎn)的選擇性,沒(méi)有直接計算后代,也沒(méi)有根據某些后代估計滿(mǎn)足條件的祖先結點(diǎn)的選擇性在執行計劃中,存在大量的向前遍歷的算法，如何估計這些算法的代價(jià),是一個(gè)需要解決的問(wèn)題.上面所提到的各種方法的處理能力各有不同,僅從方法能夠支持的各種情R(Xpath, xqu//,value)來(lái)看,可以總結為表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采用位置直方圖的方法統計組先后代的分布信息其代價(jià)計算分為基于祖先的代價(jià)估計和基于后代的代價(jià)估計基于祖先的代價(jià)估計根據每一個(gè)祖先的格,累計中國煤化工結點(diǎn)個(gè)數;基于后代的代價(jià)估計則與其正好相反根據不同區域的祖先后代結點(diǎn)的YHCNMHGT:A為某祖先格，則B區域中所有的格的所有結點(diǎn)均為A中所有結點(diǎn)的后代;C,E區域中所有格的部分結點(diǎn)為A中部分結點(diǎn)的后代;而D,F區域中只有左上半角區域中存在結點(diǎn)且部分結點(diǎn)為A中部分結點(diǎn)的后代如果考慮自身的嵌套,則A2082Journal of Sofiware 軟件學(xué)報Vol.17, No.10, October 2006中部分結點(diǎn)是A中部分結點(diǎn)的后代.據上所述，,滿(mǎn)足條件P的A的滿(mǎn)足條件P2的后代個(gè)數估計公式為Es1A.[]= Hist[4]x{-x His,[4]+ Hist,[B]+ Hist,[C]+ Hisp[E]+一x (Hist[D]+ Hists[F])} .對每個(gè)格而言，其后代格限定在較小區域內,避免多余的統計和計算但在計算區域的邊緣,并非所有結點(diǎn)滿(mǎn)足上述關(guān)系.根據平均分布的假設給計算結果加以某個(gè)系數是產(chǎn)生誤差的主要因素,誤差在空間結點(diǎn)分布稀疏時(shí)變得很大.一個(gè)改進(jìn)的方法是分別統計不同類(lèi)型的結點(diǎn)的分布情況,但統計信息占用空間很大.這種方法解決的問(wèn)題是已知集合間的祖先后代關(guān)系的估價(jià),未涉及路徑中單個(gè)謂詞的選擇性計算問(wèn)題。positionHdABVEStart postionFig.6 Two-Dimention histogram圖6二維直方 圖示例Jiang 等人[521的思想是:把不同的結點(diǎn)映射為- -維坐標上的線(xiàn)段,祖先線(xiàn)段和后代線(xiàn)段的起點(diǎn)和長(cháng)度滿(mǎn)足某種偏序關(guān)系.把整個(gè)編碼空間[cmin,cmax]分成多個(gè)小區間,然后在每個(gè)小區間內估計覆蓋的線(xiàn)段/起始點(diǎn)的對數.如圖7所示:統計信息n表示每個(gè)桶中的線(xiàn)段/起始點(diǎn)的對數;wss表示桶的起始坐標;wse表示桶的終點(diǎn)坐標;1表示桶中線(xiàn)段的平均長(cháng)度;匹配的祖先_后代個(gè)數在圖中用X表示.這種方法減少了稀疏分布時(shí)的誤差,但不能完全避免.wsswsek a2》上”IMdD)dd2 ds( 1，Isjsna( wswsn。ins .Fig.T PL histogram and statistics圖7 PL直方圖及統計信息上述方法在計算路徑選擇性時(shí),只考慮有謂詞約束的結點(diǎn),躍過(guò)其他結點(diǎn),直接估計后代或祖先的代價(jià),簡(jiǎn)化了計算的復雜度,在對模糊路徑的代價(jià)估計中有-定的優(yōu)勢.與馬爾可夫方法相同的是:當路徑中出現多個(gè)謂詞時(shí),假設不同的謂詞條件是獨立的,沒(méi)有計算不同的謂詞之間的相關(guān)性集合哈希方法計算不同謂詞之間的相關(guān)性,但后綴樹(shù)占用空間過(guò)大,尤其是在XML數據中包含大中國煤化工i則就是在有限的時(shí)間和空間內精確地估計代價(jià).這時(shí),必須對統計信息進(jìn)行壓縮,中YHCNMHG盂小峰等:XML 查詢(xún)優(yōu)化研究20835.3統計信息研究XML數據結構復雜,分布不均勻.數據量龐大時(shí),在有限的空間內統計足夠多的信息是統計信息研究的難點(diǎn).當數據更新頻繁時(shí)高效的信息維護技術(shù)顯得更為重要.5.3.1統計信 息存儲在前文介紹數值統計和數據結構抽取時(shí),已經(jīng)涉及到統計信息的存儲問(wèn)題,但討論集中在邏輯層,并未涉及存儲的形式.XML數據統計信息的存儲結構主要有以下幾種:樹(shù)或圖1(042):用于存儲模式信息,如在文獻[42]中模式樹(shù)中每個(gè)結點(diǎn)的個(gè)數,或者文獻[40]中結點(diǎn)之間的固定關(guān)系等由于其數據結構與XML原始數據相同,可用對數據本身的存取方法存取統計信息.如果XML數據模式結點(diǎn)個(gè)數為n,則樹(shù)方法存儲的代價(jià)為0(n);后綴樹(shù)的存儲代價(jià)為0(n).馬爾可夫表1!:用于存儲路徑信息,不同的路徑對應其在數據中出現的次數.為了查找方便,-般在表上再加以-定的索引.如果 只統計小于k長(cháng)度的路徑，則其存儲代價(jià)為O(nk).直方圖158:關(guān)系數據庫中曾遍應用的一種統計信息方法將某屬性的值域劃分為多個(gè)連續或不連續的部分，分別統計不同部分區域內數據的分布情況對于簡(jiǎn)單數據,采用一維直方圖方法;若統計相關(guān)的不同屬性的分布情況,需要二維或者更多維數的直方圖.在對XML數據作統計時(shí),主要采用直方圖和樹(shù)相結合的方法.如果某個(gè)結點(diǎn)的值為樹(shù)值型,則用直方圖統計這個(gè)結點(diǎn)數值的分布情況.文獻[41]中,對于結點(diǎn)之間的父子關(guān)系也采用直方圖的方法統計.必須首先唯-地標記所有的數據結點(diǎn)并且,不同類(lèi)型結點(diǎn)標記的值域沒(méi)有交叉.當路徑中的某些點(diǎn)有謂詞約束時(shí)通過(guò)統計信息無(wú)法知道那些滿(mǎn)足條件的結點(diǎn)的標記，從而無(wú)法進(jìn)-步估計其后代的個(gè)數.位置直方圖([50:這是一種二維直方圖,其值是離散的,把結構嵌套轉換為平面位置關(guān)系.如果按類(lèi)型每維分為k格則其存儲代價(jià)為0(nk),文獻[S2]等采用一維直方圖方法保存結點(diǎn)的位置信息,但需要根據結點(diǎn)在連接過(guò)程中是祖先或后代來(lái)保存不同的統計信息實(shí)際上冗余很大.5.3.2統計信 息壓縮對直方圖壓縮方面的研究在關(guān)系數據庫查詢(xún)優(yōu)化中已經(jīng)有一定的研究基礎,普遍采用的是小波壓縮[$3)和DCT(discrete cosine transform).兩 種方法均能把直方圖中大量的“桶”壓縮為少量的系數,同時(shí)丟失很少的信息.小波壓縮方法在代價(jià)估計時(shí),要重新構造與查詢(xún)相關(guān)的部分直方圖.YanB5]等人采用密度函數方法壓縮直方圖,用數據密:度函數直接模擬實(shí)際的數據的分布情況.這種方法適用于離散的或是連續的數值型數據.樹(shù)的修剪和馬爾可夫表的壓縮思想是從統計信息中刪除對代價(jià)估計結果影響相對較少的結點(diǎn)結點(diǎn)在數據中出現次數越少,則越缺乏統計價(jià)值.文獻[51]中提供了4種不同的方法,并通過(guò)實(shí)驗分析了幾種方法在不同的數據分布情況和查詢(xún)情況時(shí)的占用空間和代價(jià)估計精度關(guān)系,但并未得到相對穩定的方法.5.3.3統計信 息維護據我們所知,目前對XML統計信息維護的研究很少見(jiàn).文獻[54]提出一種馬爾可夫表的在線(xiàn)維護方法,其思想是:在查詢(xún)開(kāi)始時(shí)沒(méi)有統計信息,利用查詢(xún)反饋逐步生成和細化統計信息.其細化規則有兩個(gè):重尾規則(heavy-ail)和增量規則(delta),重尾規則是在計算選擇性時(shí),給接近查詢(xún)路徑末端的路徑的選擇性計算加以較高的權重.這樣做基于如下考慮:接近路徑末端的路徑選擇性對整個(gè)路徑的選擇性影響更大;增量規則是一-種錯誤減少學(xué)習方法.文獻[54]的優(yōu)點(diǎn)在于在線(xiàn)維護統計信息文獻([S]提出了基于Stilt"I框架IMAX增量維護算法,包括結構信息和值信息的增量維護,但是不易擴展到其他系統上.6總結及展望隨著(zhù)Intermet的發(fā)展,XML數據規模與日劇增,準確、高效地查詢(xún)XML數據成為目前研究的熱點(diǎn)問(wèn)題.近年來(lái),XML查詢(xún)優(yōu)化研究方興未艾,主要集中在如下幾個(gè)方面:對中國煤化工ML代數分解查詢(xún)語(yǔ)句的研究、對路徑選擇性估計的研究、對結構連接代價(jià)估i|YHCNMHG--門(mén)綜合性強的研究領(lǐng)域,需要吸收眾多其他技術(shù)的思想其中對XML查詢(xún)優(yōu)化影響深刻的主要有:關(guān)系數據庫查詢(xún)優(yōu)化技術(shù)、面向對象數據庫查詢(xún)優(yōu)化技術(shù)、信息檢索技術(shù)、數據倉庫和數據挖掘技術(shù)、圖像處理和壓縮技術(shù)、人工智能2084Journal of Sofware軟件學(xué)報Vol.17, No.10, October 2006技術(shù)、概率論和統計技術(shù)等.從查詢(xún)優(yōu)化的過(guò)程來(lái)講,XML查詢(xún)優(yōu)化和其他數據庫查詢(xún)優(yōu)化技術(shù)并無(wú)不同之處。從優(yōu)化的不同環(huán)節的技術(shù)上看,XML查詢(xún)優(yōu)化具有其獨特之處:既要適應更復雜的數據結構和更靈活的變化，又要適應更豐富的查詢(xún)語(yǔ)義.目前對XML查詢(xún)優(yōu)化的研究工作還遠未成熟,仍有眾多尚待解決的問(wèn)題或需要完普的技術(shù).因此，未來(lái)的XML查詢(xún)優(yōu)化研究將以更廣泛、更深入的方式展開(kāi).在XML代數研究中,一個(gè)值得重視的問(wèn)題是邏輯操作與物理操作的分工不明確.大量的工作在于制定不同的代數標準,這些標準在風(fēng)格上相去甚遠,很難有共通性.而對真正執行的物理代數的研究還遠遠不夠,而且不能形成完整的系統另外,從邏輯代數到物理代數的轉換也將是未來(lái)研究的一個(gè)重要的問(wèn)題.關(guān)系數據庫中--些約定俗成的啟發(fā)式轉換規則是在大量的實(shí)踐基礎上形成的.而目前對XML數據查詢(xún)的各種不同的執行方法之間的優(yōu)劣比較的工作還剛剛開(kāi)始,并未形成共識性的規則.由于XML數據本身的靈活性,找到一些普遍適用的規律是很困難的.在今后的一段時(shí)間內，相信會(huì )有更多的研究工作在這方面展開(kāi).復雜路徑表達式選擇性代價(jià)估計是XML查詢(xún)優(yōu)化研究的核心問(wèn)題,目前已有大量的成果,這些研究或對數據分布進(jìn)行大量的假設,或對查詢(xún)表達式的復雜性加以-定的約束尤其是在相關(guān)路徑選擇性的研究方面,仍有--些尚待解決的關(guān)鍵性問(wèn)題.一直以來(lái),統計信 息維護是代價(jià)估計的基礎.但是,關(guān)于XML數據統計信息的維護問(wèn)題的研究還處于起步狀態(tài).由于XML數據統計信息在數據結構上與傳統的統計信息有本質(zhì)的不同,很難直接利用現有的統計信息維護的技術(shù).又由于目前在XML統計信息研究中采用了大量的壓縮技術(shù),為統計信息維護增加了難度.Native XML Database的研究是目前在XML研究領(lǐng)域的一個(gè)熱點(diǎn),已經(jīng)出現一批相對獨立的系統,這些系統采用的查詢(xún)和處理方法也將對XML查詢(xún)優(yōu)化技術(shù)產(chǎn)生越來(lái)越重要的影響.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查詢(xún)優(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é)報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- ),男,博士,教授,博士生導王小鋒(1980- -),女,碩士生,主要研究領(lǐng)域師,CCF高級會(huì )員,主要研究領(lǐng)域為Web數為XML數據庫.據集成,XML數據庫,移動(dòng)數據管理.王字(1973- ),女,博士,主要研究領(lǐng)域為Web數據管理,XML數據庫.中國煤化工MYHCNMHG