（計(jì)算機(jī)軟件與理論專業(yè)論文）xml數(shù)據(jù)的twig模式查詢匹配算法研究.pdf

論文題目：x m l 數(shù)據(jù)的t w i g 模式查詢匹配算法研究 專業(yè)：計(jì)算機(jī)軟件與理論 碩士生：雷欣 指導(dǎo)教師：高集榮副教授 摘要 近年來，隨著數(shù)據(jù)庫和網(wǎng)絡(luò)技術(shù)的發(fā)展，x m l 已經(jīng)成為i n t e r n e t 上數(shù)據(jù)表示 和交換的標(biāo)準(zhǔn)。隨著x m l 技術(shù)的不斷普及，i n t e r a c t 上以x m l 技術(shù)作為載體的 數(shù)據(jù)越來越多，從而對這些x m l 數(shù)據(jù)的有效管理和查詢也越來越受到國內(nèi)外研 究者的關(guān)注。 對于x m l 文檔的查詢，目前提出的算法主要是基于如下兩種思想：第一種 是路徑分解思想，這種方法將產(chǎn)生大量的不可避免的無用的中間結(jié)果。另一種是 新近提出的整體小枝( h o l i s t i ct w i g ) 模式查詢匹配方法，它把用樹結(jié)構(gòu)建模的查詢 表達(dá)式刊g 模式( t w i gp a t t e r n ) 作為一個(gè)整體來處理。這種方法往往與一些特 殊的編碼和索引技術(shù)相結(jié)合，避免了大量不必要數(shù)據(jù)節(jié)點(diǎn)的掃描，使得算法的i o 代價(jià)、c p u 時(shí)間復(fù)雜度和空間復(fù)雜度大大降低，從而提高了查詢效率。自從b r u n o n 等人于2 0 0 2 年提出h o l i s t i ct w i g 概念以來，研究者們已經(jīng)提出了一系列t w i g 模式查詢匹配算法。其中t j f a s t 算法基于e x t e n d e dd e w e y 編碼，只要訪問t w i g 模式中的葉子節(jié)點(diǎn)的輸入集合流就可以有效地處理x m l 文檔查詢，是一種效率 較好的h o l i s t i ct w i g 模式查詢匹配算法。但是e x t e n d e dd e w e y 編碼不支持x m l 文檔的動態(tài)更新操作，且t j f a s t 算法設(shè)計(jì)思想上的缺陷也使得算法執(zhí)行效率上 可以進(jìn)一步提高。 本文在總結(jié)和分析了主流的x m l 文檔編碼方案的基礎(chǔ)上改進(jìn)了e x t e n d e d d e w e y 編碼，使其能有效支持x m l 文檔的動態(tài)更新操作。提出了一種新的基于 新e x t e n d e dd e w e y 編碼的t w i g 模式查詢匹配算法州g m a t c h 算法，進(jìn)一步 提高了t w i g 模式查詢匹配算法的效率。該方法分三個(gè)步驟來處理一個(gè)t w i g 查詢 模式，大大減少了查詢路徑匹配操作，提高了查詢效率。同時(shí)本文還重組了傳統(tǒng) 的兩階段算法，恰當(dāng)?shù)剡x擇中間結(jié)果的歸并時(shí)機(jī)，獲得了較好的內(nèi)存利用率。 多組實(shí)驗(yàn)數(shù)據(jù)對比表明，本文的方法在效率上有較大的提高。 關(guān)鍵字；x m l 文檔、t w i g 模式查詢匹配、x m l 編碼、h o l i s t i ct w i g 算法、e x t e n d e d d e w e y 編碼 n t i t l e ：r e s e a r c ho nt w i gp a t t e r nq u e r ym a t c h i n ga l g o r i t h mf o rx m ld a t a m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：x i nl e i s u p e r v i s o r ：j i r o n gg a oa s s o c i a t ep r o f e s s o r a b s t r a c t i nr e c e n ty e a r s ，謝t l lt h ed e v e l o p m e n to fd a t a b a s ea n dn e t w o r kt e c h n o l o g y ，x m l h a sb e c o m et h es t a n d a r do fd a t ar e p r e s e n t a t i o na n de x c h a n g eo nt h ei n t e r n e t w i t ht h e e v e r - g r o w i n gp o p u l a r i t yo fx m lt e c h n o l o g y , t h e r ea r em o r ea n dm o r ed a t aw h i c h e m p l o y sx m l a st h ev e c t o ri nt h ei n t e m e t ，s om a n yd o m e s t i ca n df o r e i g ns c h o l a r s p a ym o r ea n dm o r ea t t e n t i o n st ot h ex m l d a t am a n a g e m e n ta n d q u e r y f o rt h eq u e r yi nx m l d o c u m e n t ，t h ea l g o r i t h mw h i c ha r ea l r e a d yg i v e na th o m e a n da b r o a dn o w a d a y sa l em a i n l yb a s e do nt h ef o l l o w i n gt w oi d e a l s ：1 1 l ef i r s ti st o d e c o m p o s et h eq u e r ye x p r e s s i o nt os e v e r a ls i m p l ep a t h se x p r e s s i o n t m sm e t h o d c a n n o ta v o i dl a r g ea m o u n to fu s e l e s si n t e r m e d i a t er e s u l t s t h eo t h e rm e t h o di sa n e w l yp r o p o s e dh o l i s t i ct w i gq u e r yp a t t e r nm a t c h i n ga p p r o a c h ，w h i c hp r o c e s s e st h e t w i gp a t t e m 嬲aw h o l e t h em e t h o du s u a l l yc o m b i n e s 謝t hs o m es p e c i a le n c o d i n g a n di n d e x i n gt e c h n o l o g y , a v o i d sl a r g ea m o u n to fu n n e c e s s a r ys c a n n i n go fn o d e s ， r e d u c e st h ei oc o s t 、c p uc o m p l e x i t ya n ds p a c ec o m p l e x i t y , i m p r o v e st h ee f f i c i e n c y o fq u e r y f r o mt h ec o n c e p to fh o l i s t i ct w i gw a sp r o p o s e db yb r u n oni n2 0 0 2 ，t h e r e s e a r c h e r sh a v ep r o p o s e das e r i e so ft w i gp a t t e r nq u e r ym a t c h i n ga l g o r i t h m s 1 1 1 e t 腰a s ta l g o r i t h mb a s e so ne x t e n d e dd e w e y e n c o d i n g ，o n l ya c c e s s e st h ei n p u ts t r e a m o fl e a fn o d e si nt h et w i gp a t t e r n ，a n dp r o c e s s e st h ex m ld o c u m e n tq u e r ye f f e c t i v e l y i ti sak i n do fh o l i s t i ct w i gp a t t e r nq u e r ym a t c h i n ga l g o r i t h m 、析t l lb e t t e re f f i c i e n c y b u tt h ee x t e n d e dd e w e ye n c o d i n gf a i l st os u p p o r tt h ed y n a m i cu p d a t eo p e r a t i o ni n t h ex m l d o c u m e n t ，a n dt h et j f a s ta l g o r i t h mh a sb a c k d r o pi nt h ed e s i g na l s om a k e s i tp o s s i b l et oi n c r e a s et h ee f f i c i e n c yo fe x e c u t i o n i nt h i sp a p e r , t h ee x t e n d e dd e w e ye n c o d i n gw a si m p r o v e d ，i tw a sm a d et o s u p p o r tt h ed y n a m i cu p d a t eo p e r a t i o no fx m l d o c u m e n t an o v e lt w i gp a t t e r nq u e r y i h m a t c h i n ga l g o r i t h mn a m e dt w i g m a t c hw a sa l s op r o p o s e d ，w h i c hi s b a s e do nt h e i m p r o v e de x t e n d e dd e w e ye n c o d i n g ，t h ee f f i c i e n c yi si m p r o v e d i td e a l sat w i gq u e r y p a t t e mi nt h r e es t e p s ，r e d u c e st h eq u a n t i t yo fs i n g l ep a t hc o m p a r i s o n , i m p r o v e st h e q u e r ye f f i c i e n c y a tt h es a m et i m e ，t h e t r a d i t i o n a lt w op h a s e sa l g o r i t h mw a s r e c o n s t r u c t e d ，c h o s et h er i g h tt i m ef o rt h em e r g eo p e r a t i o n ，a n dg a i n e db e t t e rm e m o r y u t i l i z a t i o n t h er e l m i v ea n a l y s i so fm u l t i u n i te x p e r i m e n t a ld a t ap r o v e dt h a tt h em e t h o di n t h i sp a p e rh a si m p r o v e m e n ti nt h ee f f i c i e n c y k e y w o r d s ：x m ld o c u m e n t , t w i gp a a e r nq u e r ym a t c h i n g ，x m le n c o d i n g ，h o l i s t i c t w i ga l g o r i t h m ，e x t e n d e dd e w e ye n c o d i n g i v 論文原創(chuàng)性聲明 本人鄭重聲明：所呈交的學(xué)位論文，是本人在導(dǎo)師的指導(dǎo)下，獨(dú) 立進(jìn)行研究工作所取得的成果。除文中已經(jīng)注明引用的內(nèi)容外，本論 文不包含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫過的作品成果。對本文 的研究作出重要貢獻(xiàn)的個(gè)人和集體，均已在文中以明確方式標(biāo)明。本 人完全意識到本聲明的法律結(jié)果由本人承擔(dān)。 學(xué)位論文作者簽名：髯墊一一 一 e l 期：4 些l 一一 i 學(xué)位論文使用授權(quán)聲明 本人完全了解中山大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定，即：學(xué) 校有權(quán)保留學(xué)位論文并向國家主管部門或其指定機(jī)構(gòu)送交論文的電 子版和紙質(zhì)版，有權(quán)將學(xué)位論文用于非贏利目的的少量復(fù)制并允許論 文進(jìn)入學(xué)校圖書館、院系資料室被查閱，有權(quán)將學(xué)位論文的內(nèi)容編入 有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用復(fù)印、縮印或其他方法保存學(xué)位論文。 學(xué)飯論文作者簽名：孳釷 日期。叼吣砌日 導(dǎo)師虢鰳 魄中f 覷 第1 章緒論 近年來，隨著數(shù)據(jù)庫和網(wǎng)絡(luò)技術(shù)的發(fā)展，x m l ( 1 l ( e x t e n s i b l em a r k u pl a n g u a g e ， 可擴(kuò)展標(biāo)記語言) 已經(jīng)成為i n t e m e t 上數(shù)據(jù)表示和交換的標(biāo)準(zhǔn)。隨著x m l 技術(shù)的 不斷普及，i n t e m e t 上以x m l 技術(shù)作為載體的數(shù)據(jù)越來越多，從麗對這些x m l 數(shù)據(jù)的有效管理和查詢也越來越受到因內(nèi)外研究者的關(guān)注。 1 1 研究背景 隨著i n t e m e t 和信息技術(shù)的蓬勃發(fā)展，x m l 被越來越多地運(yùn)用于數(shù)據(jù)交換和 數(shù)據(jù)存儲領(lǐng)域的方方匿面，融成為i n t e m e t 上信息交換和表示的重要標(biāo)準(zhǔn)。x m l 技術(shù)在改變著人們的生活、學(xué)習(xí)和工作方式，拓寬了人們獲得知識和信息的途徑， 并且改變了人們的思維習(xí)慣。它是一種特殊的半結(jié)構(gòu)化數(shù)據(jù)，良其自描述性、支 持文檔內(nèi)容的驗(yàn)證和允許開發(fā)各種不同領(lǐng)域特定標(biāo)記語言等優(yōu)點(diǎn)彌補(bǔ)了 h t m l t 2 1 ( h y p e r t e x tm a r k u pl a n g u a g e ，超文本標(biāo)記語言) 的諸多缺陷，同時(shí)還具備更 好的規(guī)范性、靈活性、可擴(kuò)展性和語畜表達(dá)能力，在替代了傳統(tǒng)的h t m l 的同 時(shí)還具有更廣闊的應(yīng)用領(lǐng)域，如數(shù)字圖書館、電子商務(wù)、w e b 服務(wù)等。x m l 技 術(shù)出現(xiàn)至今，受到了業(yè)界的廣泛關(guān)注。多家知名廠商都參與到了x m l 各項(xiàng)標(biāo)準(zhǔn) 的制定和完善中來，同時(shí)各廠商的主流商用產(chǎn)品都提供了對x m l 的支持，加速 了x m l 技術(shù)的商業(yè)化應(yīng)用。在學(xué)術(shù)科研領(lǐng)域，從1 9 9 8 年至今，已有多家知名 研究機(jī)構(gòu)和高校致力于x m l 數(shù)據(jù)庫技術(shù)的研究，在提高x m l 數(shù)據(jù)的存儲、傳 輸和查詢等方面做了很多有益的探索，取褥了很多研究成果，并成功轉(zhuǎn)化到商用 領(lǐng)域，創(chuàng)造了很好的商業(yè)價(jià)值和社會效益。 x m l 技術(shù)相關(guān)的主要研究方向有x m l 的查詢數(shù)據(jù)模型、查詢語言和查詢 代數(shù)的理論研究，x m l 數(shù)據(jù)的編碼方案和索引結(jié)構(gòu)研究，x m l 查詢處理和查詢 優(yōu)化以及純x m l 數(shù)據(jù)庫系統(tǒng)的研究等l 羹。隨著近年來i n t e m e t 上x m l 數(shù)據(jù)的高 速增長，x m l 數(shù)據(jù)的查詢處理和優(yōu)化已經(jīng)成為x m l 技術(shù)相關(guān)的眾多研究領(lǐng)域 中較為關(guān)鍵的研究燕點(diǎn)。在查詢語言方面，研究者們針對x m l 數(shù)據(jù)特有的樹狀 結(jié)構(gòu)，提出了多種x m l 查詢語言，如x m l q l 4 、x p a t h 5 1 和x q u e r y 6 等。盡 管這些語言各具特點(diǎn)，但是它們都是針對x m l 數(shù)據(jù)的結(jié)構(gòu)特點(diǎn)，以路徑表達(dá)式 作為核心，通過路徑表達(dá)式來描述x m l 文檔樹中的結(jié)構(gòu)信息。因此，x m l 查 詢處理和優(yōu)化的最關(guān)鍵問題就在于路徑表達(dá)式的查詢處理。 對于路徑表達(dá)式的處理，最宜接和簡單的方法就是對x m l 文檔樹進(jìn)行從根 結(jié)點(diǎn)開始沿著文檔樹各邊到各個(gè)結(jié)點(diǎn)的遍歷，在遍歷過程中尋找匹配路徑表達(dá)式 的基標(biāo)結(jié)點(diǎn)。這種方法雖然簡單直觀，但是效率低下也是顯兩易見的。為此，研 究者們提出了許多新的算法來提高路徑表達(dá)式查詢匹配的處理效率。主要可以歸 納力以下三類：結(jié)構(gòu)連接方法f - 翻、基予路徑字符竄匹配的方法【| 3 , 1 4 1 和t w i g 模式 查詢匹配方法【挎1 8 1 。其中t w i g 模式查詢匹配方法是新近的研究成果，總體上較 前兩者具有較高的效率。 薹2 國內(nèi)外研究現(xiàn)狀 近年來，x m l 作為i n t e r n e t 上數(shù)據(jù)表示和交換的事實(shí)上的標(biāo)準(zhǔn)，菠在得到廣 泛的認(rèn)可和應(yīng)用。隨著刪l 應(yīng)用的不斷普及和相關(guān)研究的不斷深入，關(guān)于l 數(shù)據(jù)處理的研究正逐漸成為研究熱點(diǎn)。國外諸多高校和科研機(jī)構(gòu)都在致力于該領(lǐng) 域的研究工作，其中最具代表性的s t a n f o r d 大學(xué)和b e l l 實(shí)驗(yàn)室等都在該領(lǐng)域的研 究中取得了突出的成果。國內(nèi)的中國人民大學(xué)、復(fù)旦大學(xué)等 1 9 - 2 1 】也有研究人員在 該領(lǐng)域進(jìn)行了大量卓有成效的工作。另終，近年來國際重要的數(shù)據(jù)庫學(xué)術(shù)會議( 如 s i g m o d 、i c d e 和v l d b 等) 都收錄了大量關(guān)于x m l 數(shù)據(jù)庫方面的論文，并且 都為該領(lǐng)域開設(shè)了相應(yīng)的專題，該領(lǐng)域的學(xué)術(shù)研究和交流菲?；钴S。 對于x m l 數(shù)據(jù)查詢處理和優(yōu)化的核心問題路徑表達(dá)式處理，越來越受 到研究者們的青睞，成為了研究的熱點(diǎn)之一。早期的傳統(tǒng)方法是直接對x m l 文 檔樹進(jìn)行遍歷操作，從文檔樹的根結(jié)點(diǎn)出發(fā)，按照遍歷順序沿著樹中的邊尋找匹 配路徑表達(dá)式的舀標(biāo)結(jié)點(diǎn)。這種籬單直戲鵑方法不僅效率饕常低，丙且有時(shí)需要 對整棵樹進(jìn)行遍歷。盡管該方法由于其本質(zhì)上的缺陷，不可能在效率上取得較大 2 的提高，研究者們還是進(jìn)行了大量有益的探索，提出了良頂向下、自底向上和兩 者結(jié)合的基于導(dǎo)航的遍歷方式以及借助模式信息和索引的優(yōu)化遍歷方法。 隨著研究的深入，諸多研究者們先將一個(gè)復(fù)雜的路徑表達(dá)式分解為若干個(gè)簡 單的路徑表達(dá)式，再將簡單路徑表達(dá)式的匹配轉(zhuǎn)化成結(jié)點(diǎn)之間的結(jié)構(gòu)連接操作， 最后將各個(gè)簡單路徑表達(dá)式的匹配結(jié)果合并成對應(yīng)復(fù)雜路徑表達(dá)式的匹配結(jié)果。 這樣，對予個(gè)復(fù)雜路徑表達(dá)式的匹配操作就轉(zhuǎn)化為了若干次兩個(gè)結(jié)點(diǎn)列表問的 包含關(guān)系或者文檔位置關(guān)系的結(jié)構(gòu)連接操作。于是，高效的結(jié)構(gòu)連接算法就成為 研究者們關(guān)注的熱點(diǎn)。目前在這方面的研究上國內(nèi)外都提出了一系列有效的結(jié)構(gòu) 連接算法。文獻(xiàn)【7 】于2 0 0 1 年提出了m p m g j n 算法，z h a n g 等人在查詢處理中 弓l 入了區(qū)間編碼，并提出該多謂詞歸并連接算法，該算法在菜些情況下存在多次 重復(fù)掃描后代節(jié)點(diǎn)列表并產(chǎn)生大量中間結(jié)果的情況，因此效率較低。文獻(xiàn) 8 】于 麗年提出了e e - j o i n e a - j o i n 算法，但也存在m p m g j n 算法同樣的重復(fù)掃描看代 列表的問題。文獻(xiàn) 9 】在索引定位技術(shù)、短路技術(shù)和預(yù)偵測技術(shù)的基礎(chǔ)上提出了 i i m g j n 算法，有效建避免了不必要的重復(fù)掃播和搜索，大大減少了連接代價(jià)。 后來的研究者們提出了基于緩存的歸并結(jié)構(gòu)連接算法s t a c k t r e e 算法【1 0 1 ，通過維 護(hù)一個(gè)緩存棧，該算法只需要分別搖搖祖先烈表和后代列表各一次就可以完成連 接操作。文獻(xiàn)【1 1 】沿著前面的思路，利用b + 樹索引跳過許多可以事先判斷并不參 與連接的元素節(jié)點(diǎn)，進(jìn)一步提高了結(jié)構(gòu)連接的性能。文獻(xiàn)【1 2 】中提出的p c j o i h o l d i n g j o i n 算法也可以看作是前面算法思路的延伸，該算法通過在每個(gè)元素節(jié) 點(diǎn)的編碼中加入其雙親結(jié)構(gòu)信息，從而在連接時(shí)根據(jù)雙親結(jié)構(gòu)信息并利用b + 樹 索引盡可能多地跳過后代列表中的不參與連接的結(jié)點(diǎn)，進(jìn)一步提高了連接效率。 與此同時(shí)，研究者們從另一個(gè)思路來研究x m l 路徑表達(dá)式的處理，即基于 路徑字符棗匹配的查詢處理方法。該類方法的關(guān)鍵在于分別將查詢模式樹和 x m l 文檔編碼成字符串，按照某種遍歷順序和編碼方案先將查詢模式樹轉(zhuǎn)換成 路徑字符串，再將x m l 文檔中的各結(jié)點(diǎn)按照某種方式編碼并按對應(yīng)順序連接成 字符串，最后通過字符串匹配和驗(yàn)證盾輸出最終結(jié)果。顯然，該類方法需要進(jìn)行 大量的字符串模式匱配和復(fù)雜的驗(yàn)證操作，效率較低。該類方法的代表有p r i x 算法【1 3 1 和v i s t 算法【1 4 1 。 3 文獻(xiàn)【1 5 】孛b r u n on 等對一今x m l 路徑表達(dá)式中包含的多個(gè)祖先，后代關(guān)系 結(jié)構(gòu)連接進(jìn)行整體考慮，提出了整體t w i g 連接( h o l i s t i ct w i gj o i n ) 的思想和 t w i g s t a c k 算法。該算法將整個(gè)查詢模式樹作為一個(gè)整體來考慮，通過為每個(gè)查 詢節(jié)點(diǎn)維護(hù)一個(gè)祖先節(jié)點(diǎn)棧，t w i g s t a c k 算法僅僅需要對所有參與連接的輸入數(shù) 據(jù)結(jié)點(diǎn)列表分別順序掃描遍就可以實(shí)現(xiàn)整個(gè)x m l 路徑表達(dá)式的計(jì)算，不需要 將路徑表達(dá)式分解成若干個(gè)結(jié)構(gòu)連接操作，減少了輸入數(shù)據(jù)結(jié)點(diǎn)列表的掃描的同 時(shí)也減少了對中間結(jié)果的多次存取，從而獲得更優(yōu)的i o 性能。在t w i g 概念以及 整體t w i g 連接的思想提出后，引起了研究者們的廣泛關(guān)注。研究中們先后提如 了新的t w i g 模式查詢匹配算法。在t w i g s t a c k 算法提出不久之后，j i a n g 等在文 獻(xiàn)【1 6 】中結(jié)合懟囂索芬l 瞄】的思想，提出了t s g e n e r i c + 算法，它能夠跳過許多 可以事先判斷并不參與連接的數(shù)據(jù)結(jié)點(diǎn)。l uj 等在文獻(xiàn) 1 7 】中對前綴編碼d e w e y 編碼進(jìn)行擴(kuò)展，提出了一種擴(kuò)展d e w e y ( e x t e n d e dd e w e y ) 編碼，結(jié)合該編碼以及 有限狀態(tài)自動機(jī)( f s t ) 技術(shù)，他們提出了t j f a s t 算法，該算法只需要訪問t w i g 查 詢模式樹中的葉子節(jié)點(diǎn)，創(chuàng)新之處在于其編碼可以通過一個(gè)f s t f f i n i t es t a t e t r a n s d u c e r , 有限狀態(tài)自動機(jī)) 在需要時(shí)才計(jì)算出某個(gè)數(shù)據(jù)結(jié)點(diǎn)對應(yīng)的從x m l 文檔 樹的根結(jié)點(diǎn)到該數(shù)據(jù)結(jié)點(diǎn)自身的路徑信息，節(jié)省了存儲文檔路徑索引空間的同時(shí) 也降低了路徑表達(dá)式匹配時(shí)的i o 代價(jià)。但t j f a s t 算法過分依賴于以上特性，進(jìn) 行了大量不必要的查詢路徑匹配操作，即大量的字符串模式遙配操作，耗費(fèi)了較 多的時(shí)間。同時(shí)，在求解葉子節(jié)點(diǎn)的公共分支時(shí)，沒能利用到前綴編碼的特性， 也做了過多不必要的字符串比較搡作。 1 3 本文研究內(nèi)容 文獻(xiàn) 1 7 】中提出的t j f a s t 算法在當(dāng)前提出的一系列t w i g 模式查詢匹配算法 中，是較高效的算法，其提出的e x t e n d e dd e w e y 編碼不僅具備前綴編碼的特性， 可以包含一個(gè)數(shù)據(jù)結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)的編碼信息，同時(shí)還可以在耗費(fèi)較小的時(shí) 空開銷的情況下計(jì)算出該結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)的標(biāo)簽名稱，從而褥到從根結(jié)點(diǎn)到 自身的路徑信息。為了克服e x t e n d e dd e w e y 編碼不支持x m l 文檔的動態(tài)更新操 4 佟的缺陷，本文借鑒了l s d x 編碼方案籜3 】的思想，對e x t e n d e dd e w e y 編碼進(jìn)行 了相應(yīng)的改進(jìn)，使之支持x m l 文檔的更新操作而不需要對整個(gè)x m l 文檔重新 編碼。 為了克服目前提出的一些t w i g 模式查詢匹配算法的缺陷，減少不必要的數(shù) 據(jù)結(jié)點(diǎn)比較和查詢路徑匹配操作，本文提出了一種新的t w i g 模式查詢匹配算法。 本文的主要工作可以歸納如下： 1 x m l 文檔的編碼方案研究。本文總結(jié)了主流的x m l 文檔編碼方案，分 析了各種編碼方案的優(yōu)點(diǎn)和缺點(diǎn)。 2 x m l 文檔的t w i g 模式查詢匹配算法研究。本文分析了在b r u n on 等人 提磁整體t w i g 模式查詢概念以來研究者們提出的的多個(gè)t w i g 模式查詢匹 配算法的思想及執(zhí)行過程。 3 u e dx m l 文檔編碼方案的研究。文獻(xiàn)【1 7 】中提遺的e x t e n d e dd e w e y 編 碼在具備前綴編碼特性的同時(shí)還可以通過一個(gè)有限狀態(tài)自動機(jī)f s t 實(shí)時(shí) 計(jì)算每個(gè)數(shù)據(jù)結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)的名稱信息。本文總結(jié)了幾種主流編 碼方案，并借鑒l s d x 編碼方案的思想，對e x t e n d e dd e w e y 編碼進(jìn)行了 相應(yīng)的改進(jìn)，保留原有特性的同時(shí)，使之支持x m l 文檔的動態(tài)更新操 作而不需要對整個(gè)x m l 文檔重新編碼，有效降低了二次編碼率。 4 提出了一個(gè)新的t w i g 模式查詢匹配算法刊g m a t c h 算法。該方法的 輸入包括t w i g 模式中最頂層分支節(jié)點(diǎn)和各葉子節(jié)點(diǎn)的輸入集合流，分三 個(gè)步驟來處理一個(gè)t w i g 查詢模式，先進(jìn)行從t w i g 模式中最頂層分支節(jié)點(diǎn) 到各個(gè)葉予節(jié)點(diǎn)的破裂邊連接，然后再匹配除最頂層分支節(jié)點(diǎn)外的其它 各分支節(jié)點(diǎn)，最后進(jìn)行各葉子節(jié)點(diǎn)對應(yīng)的從t w i g 模式中根節(jié)點(diǎn)到自身的 查詢路徑匹配。同時(shí)本文還重組了傳統(tǒng)的兩階段算法，恰當(dāng)?shù)剡x擇中間 結(jié)果的歸并時(shí)機(jī)，獲得了較好的內(nèi)存利用率。這種方法減少了數(shù)據(jù)結(jié)點(diǎn) 比較和查詢路徑匹配的次數(shù)，提高了查詢效率。 5 構(gòu)建了一個(gè)實(shí)驗(yàn)系統(tǒng)，并在該系統(tǒng)上實(shí)現(xiàn)了本文提出的t w i g 模式查詢匹 配算法和文獻(xiàn)【1 7 件提出的t j f a s t 算法，通過多組實(shí)驗(yàn)對比，結(jié)采表甓 本文的方法在效率上有較大的提高。 5 1 4 論文的組織結(jié)構(gòu) 全文共分為七章，的組織結(jié)構(gòu)如下： 第l 章“緒論掙，課題研究背景、x m l 數(shù)據(jù)查詢處理技術(shù)在國內(nèi)外的研究現(xiàn) 狀、目前提出的x m l 查詢算法簡介以及本文主要研究工作都在本章中做簡要介 紹。最稀還介紹了本文的組織結(jié)構(gòu)。 第2 章“相關(guān)背景知識 ，本章主要介紹x m l 技術(shù)及查詢處理技術(shù)相關(guān)的 知識，包括x m l 文檔的基本構(gòu)成和數(shù)據(jù)模型、x m l 的模式語言、x m l 的查詢 語言以及t w i g 模式查詢的概念。 第3 章“x m l 數(shù)據(jù)庫技術(shù)簡介”，本文在這章中首先總結(jié)了x m l 數(shù)據(jù)的編 碼方案，分析了各自的優(yōu)缺點(diǎn)，并舉出了編碼的實(shí)例，然后重點(diǎn)分析了囂前已經(jīng) 提出的幾個(gè)典型h o l i s t i ct w i g ( 整體小枝) 模式查詢匹配算法，分析了各自的思想和 執(zhí)行過程，并給怨了執(zhí)行實(shí)例。 第4 章“x m l 文檔的u e d 編碼 ，在本章中首先介紹了e x t e n d e dd e w e y 編 碼的原理，然后介紹u e d 編碼對e x t e n d e dd e w e y 編瑪?shù)母倪M(jìn)方法，最后分析了 兩種編碼的動態(tài)性能。 第5 章t w i g 模式查詢匹配算法t w i g m a t c h 捧，本章詳細(xì)介紹了本文提出的 t w i g 模式查詢匹配算法，并對t w i g m a t c h 算法和t j f a s t 做了詳細(xì)的比較分析。 第6 章“實(shí)驗(yàn)與結(jié)果分析打，本章介紹實(shí)驗(yàn)系統(tǒng)的實(shí)現(xiàn)及實(shí)驗(yàn)數(shù)據(jù)的對比分 析。 第7 章“結(jié)束語 ，本章將總結(jié)全文，提出本文存在的不足和將來要做的工 作。 6 第2 章相關(guān)背景知識 作為本文研究內(nèi)容的基礎(chǔ)知識，本章將簡要介紹x m l 相關(guān)的背景知識，包 括x m l 簡介、x m l 數(shù)據(jù)模型、x m l 模式語言和查詢語言等。 2 1x m l 簡介 x m l 是由w 3 c ( w o r l dw i d ew e bc o n s o r t i u m ) 的x m l 工作組與1 9 9 6 年起定 義并維護(hù)的。該工作組對x m l 語言的描述為：x m l 是s g m l ( s t a n d a r d g e n e r a l i z e dm a r k u pl a n g u a g e ，標(biāo)準(zhǔn)通用標(biāo)記語言) 的子集，其目標(biāo)是允許普通的 s g m l 在w e b 上以露前h t m l 的方式被服務(wù)、接收和處理。x m l 被設(shè)計(jì)成易 于實(shí)現(xiàn)，且可以在s g m l 和h t m l 之間互相操作。 1 1 ! e l e m e n tb i b ( b o o k * ) l e l e m e n ts e e t i o n ( # p c d a t a 圖2 - lx m l 文檔示例及對應(yīng)的d t d 文檔 x m l 是一套定義語義標(biāo)記的規(guī)則，這些標(biāo)記將文檔分成許多部件并對這些 部件加以表示。它不像h t m l 語言那樣，定義了一套固定的標(biāo)記來表示頁面元 素的含義。x m l 是一種元標(biāo)記語言，用戶可以定義自己需要的標(biāo)記。這些標(biāo)記 必須根據(jù)某些通用的規(guī)則來創(chuàng)建，x m l 標(biāo)記描述的是文檔內(nèi)容的結(jié)構(gòu)和含義， 7 而不是描述頁面元素的格式化。文檔本身只說明文檔包括什么標(biāo)記，麗不是說明 文檔看起來是什么樣的。 簡單而言，一個(gè)x m l 文檔主要由元素構(gòu)成，元素包含屬性、子元素和文本 內(nèi)容，予元素聞可以層層嵌套，此外，一個(gè)完整的虹文檔還可以包括垤l 聲明、處理指令、注釋和命名空間等部分。圖2 1 c a ) 就是一個(gè)較完整的煳l 文 檔示例，它包含了一個(gè)z m l 文檔基本的元素、屬性和文本內(nèi)容，此羚還包括文 檔開頭的聲明部分。 2 2x m l 數(shù)據(jù)模型 數(shù)據(jù)模型是z m l 數(shù)據(jù)管理研究的核心問題。為了對v i l 數(shù)據(jù)進(jìn)行有效的 管理，就必須對舭數(shù)據(jù)進(jìn)行建模，以正確反映x m l 數(shù)據(jù)的特性。當(dāng)前的研 究工作大都將x m l 數(shù)據(jù)建模為圖模型 2 4 - 2 7 1 或樹模型【2 引。圖模型將垤l 數(shù)據(jù)中 的元素之間、元素和屬性之間的聯(lián)系抽象為有向邊，把整個(gè)捌l 數(shù)據(jù)看成是一 個(gè)復(fù)雜的圖狀結(jié)構(gòu)。樹模型將x m l 數(shù)據(jù)中的元素之間、元素和屬性之間的聯(lián)系 抽象為樹的有向邊，把整個(gè)x m l 數(shù)據(jù)看成是一棵有向的標(biāo)簽樹。相比于圖模型， 樹模型褥到了更廣泛地使用，因此本文的研究也是基于樹模型，以下對樹模型做 進(jìn)一步介紹。 b i b b o o kb o o k i da u t h o r a u t h o rt i t l e c h a p t e r i da u t h o rt i t l e c h a p t e r l l | 1 s u c i uc h e r tc o m p u t e rt i t l e 2 t o n yc o m p u t e r t i t l e 矧曲f 一楸 x m 叱 o p e r a t i n g s y s t e m 圖2 - 2x m l 文檔的樹模型表示 在樹模型中，將舭文檔中的各元素抽象為標(biāo)簽樹中的結(jié)點(diǎn)，結(jié)點(diǎn)的類型 主要有根結(jié)點(diǎn)( r o o tn o d e ) 、元素結(jié)點(diǎn)( e l e m e n tn o d e ) 、文本值結(jié)點(diǎn)( t e x tn o d e ) 和屬性 結(jié)點(diǎn)( a t t r i b u t en o d e ) 等。此外，該樹模型是一棵有序樹，標(biāo)簽樹中的各結(jié)點(diǎn)之間 對應(yīng)順序與每個(gè)結(jié)點(diǎn)在原) ( 】憂l 文檔中出現(xiàn)的順序一致。 例2 1 圖2 。2 所示的就是圖2 1 中x m l 文檔對應(yīng)的樹模型表示形式。在樹 模型表示形式中，整個(gè)x m l 文檔被表示成以標(biāo)簽名為“b i b 的結(jié)點(diǎn)作為根結(jié)點(diǎn) 的標(biāo)簽樹。原文檔中的每個(gè)標(biāo)簽被表示為樹中同名的結(jié)點(diǎn)，而元素之間、元素和 屬性之間的聯(lián)系被抽象表示成模型樹上的有向邊。 2 3x m l 模式語言 x m l 文檔在本質(zhì)上只是一個(gè)保存數(shù)據(jù)的結(jié)構(gòu)化載體，為了得到有效的符合 要求的x m l 文檔，還必須驥確文檔中的數(shù)據(jù)必須符合的結(jié)構(gòu)要求，即需要一靜 用來描述x m l 文檔中數(shù)據(jù)結(jié)構(gòu)的模型。這種數(shù)據(jù)模型不僅建立了x m l 文檔中 可以使用的x m l 譎匯表，還定義了x m l 文檔中元素的順序和元素的嵌套規(guī)則， 并建立了文檔數(shù)據(jù)的數(shù)據(jù)類型。目前應(yīng)用得比較廣泛的是d t d 2 9 l ( d o c u m e n tt y p e d e f i n i t i o n , 文檔類型定義) 和x m ls e k m 0 3 蠲( ) ( m l 模式) 。 2 。3 。ld t d d t d 使用特定的語法來接述并約束x m l 文檔的內(nèi)容和結(jié)構(gòu)。d t d 列出了 可用在對應(yīng)x m l 文檔中的元素、屬性、實(shí)體和符號表示法，以及它們之間的相 互關(guān)系。d t d 通過指定文檔結(jié)構(gòu)的一系列規(guī)則來約束文檔的結(jié)構(gòu)，例如d t d 可 以規(guī)定文檔的根元素必須是b i b ，b i b 元素只能包含一個(gè)或者多個(gè)b o o k 元素，b o o k 元素可以包含一個(gè)或者多個(gè)a u t h o r 元素，t i t l e 元素緊跟在其后，之后可以是0 個(gè) 或者多個(gè)c h a p t e r 元素，這些約束規(guī)則都是在d t d 中定義的。圖2 1 ( b ) 就是一個(gè) 涯l d 陽的例子。 一個(gè)d t d 文檔通過具體說明每一個(gè)元素和屬性的名稱、元素與子元素之間 的嵌套關(guān)系、子元素的賚現(xiàn)順序幫次數(shù)等來定義x m l 文檔的結(jié)構(gòu)模型，箕通過 操作符宰( 元素出現(xiàn)o 次或者多次) 、+ ( o 次或者一次) 、7 ( 0 次或者1 次) 、l ( 符號兩 9 邊的元素出現(xiàn)其一) 來定義子元素的高現(xiàn)次數(shù)。在d t d 文檔中用關(guān)鍵字 e l e m e n t 表示元素，a t t l i s t 表示屬性，# p c d a t a 表示數(shù)據(jù)。 雖然d t d 在表示和約束x m l 文檔結(jié)構(gòu)方面已經(jīng)超到來很好的作用，可以 在x m l 文檔被程序解析時(shí)利用d t d 來驗(yàn)證該x m l 文檔的有效性，但仍存在一 些不足，尤其在一些新興領(lǐng)域應(yīng)用中，體現(xiàn)出了以下幾個(gè)局限性。 首先是d t d 幾乎不具備數(shù)據(jù)類型定義的能力，尤其是對元素的內(nèi)容而言。 在d t d 中一切都被默認(rèn)定義為字符串，不支持?jǐn)?shù)字、復(fù)合類型等數(shù)據(jù)類型。 第二個(gè)問題是d t d 和x m l 文檔使用的是兩種不同的語法。給數(shù)據(jù)處理上 帶來了不必要的麻煩，也使得帆不具備自描述的特性。 第三個(gè)闖題是d t d 的約束定義能力不足，無法對x m l 文檔進(jìn)行更細(xì)致的 語義約束。 最詹一個(gè)問題是d t d 不夠結(jié)構(gòu)化，重用的代價(jià)相對較高。 鑒于d t d 的諸多不足，已經(jīng)不能滿足各種應(yīng)用的需要，促使人們開發(fā)出了 一種更好的模式語言來替代它，這就是x m ls c h e m a 。 2 3 2x m ls c h e m a w 3 c 于1 9 9 8 年開始指定x m ls c h e m a 的第一個(gè)版本，于2 0 0 1 年5 月正式 由官方推薦使用。 例2 - 2 圖2 - 3 是一今完整的x m ls c h e m a 的例子。 下面針對d t d 的不足來介紹x m ls c h e m a 在相應(yīng)方面的改進(jìn)。 在例2 - 2 中共定義了6 個(gè)元素。在x m ls c h e m a 中用x s d ：e l e m e n t 元素來聲 明x m l 元素，用x s d ：a t t r i b u t e 元素來聲明x m l 屬性。這兩個(gè)元素已經(jīng)在前綴所 指向的命名空閬中定義始了。在每個(gè)x s d ：e l e m e n t 或x s d ：a t t r i b u t o 元素中，使用n r m e 和t y p e 屬性來分別說明x m l 文檔的元素或者屬性的名稱和數(shù)據(jù)類型，這樣通過 屬性t y p e 就解決了d t d 中只能使用字符串的單一類型。此外，還可以使用 c o m p l e x t y p e 元素來自定義復(fù)合數(shù)據(jù)類型，從而用戶可以根據(jù)自己的需要自定義 數(shù)據(jù)類型，更好的擴(kuò)充了x m l 文檔可以使用的數(shù)據(jù)類型。在該例子中， c o m p l e x t y p e 元素中包含一個(gè)s e q u e n c e 子元素，它被稱為模型組。通過模型組可 1 0 以把子元素聲明或引用組合起來，從而構(gòu)建更加有意義的內(nèi)容模型。對于d t d 的第二個(gè)問題，x m ls c h e m a 使用標(biāo)準(zhǔn)的x m l 語法，從而x m ls c h e m a 和x m l 之間不存在語法上的差異，x m ls c h e m a 文檔可以像其它x m l 文檔一樣被處理 和解析。對于第三個(gè)問題，x m ls c h e m a 除了使用模型組來限制予元素的出現(xiàn)順 序外，還為e l e m e n t 元素提供m i n o c c u r s 、d e f a u l t 、f i x e d 等屬性來限定該元素的 最少出現(xiàn)次數(shù)、默認(rèn)值、固定取值等。對于元素值的進(jìn)一步約寒x m ls c h e m a 也提供了完備的機(jī)制，如可以將一個(gè)元素的值限定在個(gè)數(shù)值區(qū)間內(nèi)、取特定的 枚舉值、歪則表達(dá)式匹配和字符串的長度限定等。 2 4x m l 查詢語言 圖2 3x m l s c h e m a 示例 在x m l 使用的初期，學(xué)者們就注意到了在包含豐富信息的海量x m l 數(shù)據(jù) 中檢索用戶關(guān)心的有用信息的重要性，從麗很多學(xué)者的研究重點(diǎn)就指向了x m l 查詢語言的研究。由于x m l 文檔是一種半結(jié)構(gòu)化數(shù)據(jù)，無法使用關(guān)系數(shù)據(jù)庫中 已經(jīng)比較成熟的s q l 查詢語言，焉是需要一種新型的x m l 查詢語言來對x m l 文檔進(jìn)行查詢。為此，w 3 c 提出了多種查詢語言，其中最重要的有兩個(gè)：x p a t h 5 】 和x q u e r y 6 1 ，此外還有其它組織提出的l o r e l l 2 4 1 、q u i l t 3 1 l 等，它們的共圓特點(diǎn)是 采用路徑表達(dá)式來對x m l 文檔進(jìn)行定位。下面對技術(shù)上相對成熟，已經(jīng)得到廣 泛使用的x p a t h 和x q u e r y 做簡要介紹。 2 。4 1x p a t h 在x p a t h 語畜中，將x m l 文檔建模成具有樹形結(jié)構(gòu)的文檔樹來訪問。通過 x p a t h 可以定位x m l 文檔樹中的任意結(jié)點(diǎn)。x p a t h 使用路徑表達(dá)式來與x m l 文 檔中的對應(yīng)部分進(jìn)行匹配。表達(dá)式是x p a t h 的主要構(gòu)件，其中最重要的表達(dá)式是 定位路徑( 1 0 c a t i o np a t h ) 表達(dá)式，簡稱路徑表達(dá)式。 定位路徑表達(dá)式分為絕對和相對定位路徑表達(dá)式兩種。每個(gè)定短路徑表達(dá)式 包含一個(gè)或者多個(gè)定位步( 1 0 c a t i o ns t e p ) ，每個(gè)定位步之間用左斜杠“或者雙左 斜杠搿間隔。其中絕對路徑從文檔的根結(jié)點(diǎn)開始定位路徑，以“， 開頭來表 示；相對路徑則以“ 開頭表示，它直接從某個(gè)定位步開始進(jìn)行路徑定位。 定位步是一個(gè)定位路徑表達(dá)式的組成部分，而一個(gè)定位步又包含】以下三個(gè)部 分： 一個(gè)軸，它指定了定位步選擇結(jié)點(diǎn)與上下文結(jié)點(diǎn)之間的樹狀關(guān)系。如c h i l d 軸表示選擇上下文結(jié)點(diǎn)的孩子結(jié)點(diǎn)，x p a t h 共定義了1 3 個(gè)軸以滿足各種操作的 需求。這1 3 個(gè)軸可以分為三大類：自身軸、反向軸和向前軸。其中自身軸包括 s e l f ；反囪軸包括a n c e s t o r 、p a r e n t 、p r e c e d i n g 、p r e c e d i n g s i b l i n g 和a n c e s t o r - o r - s e l f ； 向前軸包括d e s c e n d a n t 、c h i l d 、a t t r i b u t e 、f o l l o w i n g 和f o l l o w i n g - s i b l i n g , 此外還 有n a m e s p a c e 軸。 一個(gè)結(jié)點(diǎn)測試，它用于指定定位步中選擇結(jié)點(diǎn)的結(jié)點(diǎn)類型或結(jié)點(diǎn)名。 0 個(gè)或多個(gè)謂詞，它使用專有的謂詞表達(dá)式進(jìn)一步過濾定位步選擇的結(jié)點(diǎn)集 厶 口。 以上三部分出雙冒號“：和對中括號“口”闋隔，共闋組成一個(gè)定位步， 其中“：用于分隔軸名和結(jié)點(diǎn)測試，“凸用于表示謂詞。例如，在定位步 c h i l d ：c h a p t e r t i t l e = “x m lx p a t h 】中，c h i l d 是軸名，c h a p t e r 是結(jié)點(diǎn)測試，而 t i t l e = “x m lx p a t h ”】就是一個(gè)謂詞。 對于一個(gè)定位步內(nèi)部的計(jì)算先從軸和結(jié)點(diǎn)測試開始，產(chǎn)生初始結(jié)點(diǎn)集合后， 利用其矮的各個(gè)謂詞對初始結(jié)點(diǎn)集合進(jìn)行篩選，最詹得到結(jié)果結(jié)點(diǎn)集合。 1 2 下面簡要介紹在本文中將會用到的幾個(gè)常用的x p a t h 語法。 1 b i b b o o k a u t h o r 這是一個(gè)絕對單路徑表達(dá)式，查詢所有滿足條件的a u t h o r 結(jié)點(diǎn)，該a u t h o r 結(jié)點(diǎn)的雙親結(jié)點(diǎn)為b o o k ，b o o k 結(jié)點(diǎn)的雙親結(jié)點(diǎn)為根結(jié)點(diǎn)b i b 。 2 c h a p t e r t i t l e 這是一個(gè)相對單路徑表達(dá)式，查詢所有雙親結(jié)點(diǎn)為c h a p t e r 的t i t l e 結(jié)點(diǎn)。 3 b o o k i d 這是一個(gè)帶有屬性謂詞的相對單路徑表達(dá)式，查詢所有具有通屬性的b o o k 結(jié)點(diǎn)。 4 。b o o k a u t h o r = ”t o n y 辯 t i t l e 這是一個(gè)帶有分支節(jié)點(diǎn)的復(fù)合路徑表達(dá)式，即t w i g 模式查詢表達(dá)式。查詢 所有滿足條件的t i t l e 結(jié)點(diǎn)，該t i t l e 結(jié)點(diǎn)的雙親結(jié)點(diǎn)b o o k 弱時(shí)也是僮為“t o n y 的a u t h o r 結(jié)點(diǎn)的雙親。 2 4 2x q u e r y x q u e r y 是w 3 c 于2 0 0 1 年首次推出的另一個(gè)被廣泛使用