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

論文題目：x m l 數(shù)據(jù)的t w i g 模式查詢匹配算法研究 專業(yè)：計算機軟件與理論 碩士生：雷欣 指導教師：高集榮副教授 摘要 近年來，隨著數(shù)據(jù)庫和網(wǎng)絡技術的發(fā)展，x m l 已經(jīng)成為i n t e r n e t 上數(shù)據(jù)表示 和交換的標準。隨著x m l 技術的不斷普及，i n t e r a c t 上以x m l 技術作為載體的 數(shù)據(jù)越來越多，從而對這些x m l 數(shù)據(jù)的有效管理和查詢也越來越受到國內外研 究者的關注。 對于x m l 文檔的查詢，目前提出的算法主要是基于如下兩種思想：第一種 是路徑分解思想，這種方法將產生大量的不可避免的無用的中間結果。另一種是 新近提出的整體小枝( h o l i s t i ct w i g ) 模式查詢匹配方法，它把用樹結構建模的查詢 表達式刊g 模式( t w i gp a t t e r n ) 作為一個整體來處理。這種方法往往與一些特 殊的編碼和索引技術相結合，避免了大量不必要數(shù)據(jù)節(jié)點的掃描，使得算法的i o 代價、c p u 時間復雜度和空間復雜度大大降低，從而提高了查詢效率。自從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é)點的輸入集合流就可以有效地處理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 算法設計思想上的缺陷也使得算法執(zhí)行效率上 可以進一步提高。 本文在總結和分析了主流的x m l 文檔編碼方案的基礎上改進了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 算法，進一步 提高了t w i g 模式查詢匹配算法的效率。該方法分三個步驟來處理一個t w i g 查詢 模式，大大減少了查詢路徑匹配操作，提高了查詢效率。同時本文還重組了傳統(tǒng) 的兩階段算法，恰當?shù)剡x擇中間結果的歸并時機，獲得了較好的內存利用率。 多組實驗數(shù)據(jù)對比表明，本文的方法在效率上有較大的提高。 關鍵字；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)性聲明 本人鄭重聲明：所呈交的學位論文，是本人在導師的指導下，獨 立進行研究工作所取得的成果。除文中已經(jīng)注明引用的內容外，本論 文不包含任何其他個人或集體已經(jīng)發(fā)表或撰寫過的作品成果。對本文 的研究作出重要貢獻的個人和集體，均已在文中以明確方式標明。本 人完全意識到本聲明的法律結果由本人承擔。 學位論文作者簽名：髯墊一一 一 e l 期：4 些l 一一 i 學位論文使用授權聲明 本人完全了解中山大學有關保留、使用學位論文的規(guī)定，即：學 校有權保留學位論文并向國家主管部門或其指定機構送交論文的電 子版和紙質版，有權將學位論文用于非贏利目的的少量復制并允許論 文進入學校圖書館、院系資料室被查閱，有權將學位論文的內容編入 有關數(shù)據(jù)庫進行檢索，可以采用復印、縮印或其他方法保存學位論文。 學飯論文作者簽名：孳釷 日期。叼吣砌日 導師虢鰳 魄中f 覷 第1 章緒論 近年來，隨著數(shù)據(jù)庫和網(wǎng)絡技術的發(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 ， 可擴展標記語言) 已經(jīng)成為i n t e m e t 上數(shù)據(jù)表示和交換的標準。隨著x m l 技術的 不斷普及，i n t e m e t 上以x m l 技術作為載體的數(shù)據(jù)越來越多，從麗對這些x m l 數(shù)據(jù)的有效管理和查詢也越來越受到因內外研究者的關注。 1 1 研究背景 隨著i n t e m e t 和信息技術的蓬勃發(fā)展，x m l 被越來越多地運用于數(shù)據(jù)交換和 數(shù)據(jù)存儲領域的方方匿面，融成為i n t e m e t 上信息交換和表示的重要標準。x m l 技術在改變著人們的生活、學習和工作方式，拓寬了人們獲得知識和信息的途徑， 并且改變了人們的思維習慣。它是一種特殊的半結構化數(shù)據(jù)，良其自描述性、支 持文檔內容的驗證和允許開發(fā)各種不同領域特定標記語言等優(yōu)點彌補了 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 ，超文本標記語言) 的諸多缺陷，同時還具備更 好的規(guī)范性、靈活性、可擴展性和語畜表達能力，在替代了傳統(tǒng)的h t m l 的同 時還具有更廣闊的應用領域，如數(shù)字圖書館、電子商務、w e b 服務等。x m l 技 術出現(xiàn)至今，受到了業(yè)界的廣泛關注。多家知名廠商都參與到了x m l 各項標準 的制定和完善中來，同時各廠商的主流商用產品都提供了對x m l 的支持，加速 了x m l 技術的商業(yè)化應用。在學術科研領域，從1 9 9 8 年至今，已有多家知名 研究機構和高校致力于x m l 數(shù)據(jù)庫技術的研究，在提高x m l 數(shù)據(jù)的存儲、傳 輸和查詢等方面做了很多有益的探索，取褥了很多研究成果，并成功轉化到商用 領域，創(chuàng)造了很好的商業(yè)價值和社會效益。 x m l 技術相關的主要研究方向有x m l 的查詢數(shù)據(jù)模型、查詢語言和查詢 代數(shù)的理論研究，x m l 數(shù)據(jù)的編碼方案和索引結構研究，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 技術相關的眾多研究領域 中較為關鍵的研究燕點。在查詢語言方面，研究者們針對x m l 數(shù)據(jù)特有的樹狀 結構，提出了多種x m l 查詢語言，如x m l q l 4 、x p a t h 5 1 和x q u e r y 6 等。盡 管這些語言各具特點，但是它們都是針對x m l 數(shù)據(jù)的結構特點，以路徑表達式 作為核心，通過路徑表達式來描述x m l 文檔樹中的結構信息。因此，x m l 查 詢處理和優(yōu)化的最關鍵問題就在于路徑表達式的查詢處理。 對于路徑表達式的處理，最宜接和簡單的方法就是對x m l 文檔樹進行從根 結點開始沿著文檔樹各邊到各個結點的遍歷，在遍歷過程中尋找匹配路徑表達式 的基標結點。這種方法雖然簡單直觀，但是效率低下也是顯兩易見的。為此，研 究者們提出了許多新的算法來提高路徑表達式查詢匹配的處理效率。主要可以歸 納力以下三類：結構連接方法f - 翻、基予路徑字符竄匹配的方法【| 3 , 1 4 1 和t w i g 模式 查詢匹配方法【挎1 8 1 。其中t w i g 模式查詢匹配方法是新近的研究成果，總體上較 前兩者具有較高的效率。 薹2 國內外研究現(xiàn)狀 近年來，x m l 作為i n t e r n e t 上數(shù)據(jù)表示和交換的事實上的標準，菠在得到廣 泛的認可和應用。隨著刪l 應用的不斷普及和相關研究的不斷深入，關于l 數(shù)據(jù)處理的研究正逐漸成為研究熱點。國外諸多高校和科研機構都在致力于該領 域的研究工作，其中最具代表性的s t a n f o r d 大學和b e l l 實驗室等都在該領域的研 究中取得了突出的成果。國內的中國人民大學、復旦大學等 1 9 - 2 1 】也有研究人員在 該領域進行了大量卓有成效的工作。另終，近年來國際重要的數(shù)據(jù)庫學術會議( 如 s i g m o d 、i c d e 和v l d b 等) 都收錄了大量關于x m l 數(shù)據(jù)庫方面的論文，并且 都為該領域開設了相應的專題，該領域的學術研究和交流菲常活躍。 對于x m l 數(shù)據(jù)查詢處理和優(yōu)化的核心問題路徑表達式處理，越來越受 到研究者們的青睞，成為了研究的熱點之一。早期的傳統(tǒng)方法是直接對x m l 文 檔樹進行遍歷操作，從文檔樹的根結點出發(fā)，按照遍歷順序沿著樹中的邊尋找匹 配路徑表達式的舀標結點。這種籬單直戲鵑方法不僅效率饕常低，丙且有時需要 對整棵樹進行遍歷。盡管該方法由于其本質上的缺陷，不可能在效率上取得較大 2 的提高，研究者們還是進行了大量有益的探索，提出了良頂向下、自底向上和兩 者結合的基于導航的遍歷方式以及借助模式信息和索引的優(yōu)化遍歷方法。 隨著研究的深入，諸多研究者們先將一個復雜的路徑表達式分解為若干個簡 單的路徑表達式，再將簡單路徑表達式的匹配轉化成結點之間的結構連接操作， 最后將各個簡單路徑表達式的匹配結果合并成對應復雜路徑表達式的匹配結果。 這樣，對予個復雜路徑表達式的匹配操作就轉化為了若干次兩個結點列表問的 包含關系或者文檔位置關系的結構連接操作。于是，高效的結構連接算法就成為 研究者們關注的熱點。目前在這方面的研究上國內外都提出了一系列有效的結構 連接算法。文獻【7 】于2 0 0 1 年提出了m p m g j n 算法，z h a n g 等人在查詢處理中 弓l 入了區(qū)間編碼，并提出該多謂詞歸并連接算法，該算法在菜些情況下存在多次 重復掃描后代節(jié)點列表并產生大量中間結果的情況，因此效率較低。文獻 8 】于 麗年提出了e e - j o i n e a - j o i n 算法，但也存在m p m g j n 算法同樣的重復掃描看代 列表的問題。文獻 9 】在索引定位技術、短路技術和預偵測技術的基礎上提出了 i i m g j n 算法，有效建避免了不必要的重復掃播和搜索，大大減少了連接代價。 后來的研究者們提出了基于緩存的歸并結構連接算法s t a c k t r e e 算法【1 0 1 ，通過維 護一個緩存棧，該算法只需要分別搖搖祖先烈表和后代列表各一次就可以完成連 接操作。文獻【1 1 】沿著前面的思路，利用b + 樹索引跳過許多可以事先判斷并不參 與連接的元素節(jié)點，進一步提高了結構連接的性能。文獻【1 2 】中提出的p c j o i h o l d i n g j o i n 算法也可以看作是前面算法思路的延伸，該算法通過在每個元素節(jié) 點的編碼中加入其雙親結構信息，從而在連接時根據(jù)雙親結構信息并利用b + 樹 索引盡可能多地跳過后代列表中的不參與連接的結點，進一步提高了連接效率。 與此同時，研究者們從另一個思路來研究x m l 路徑表達式的處理，即基于 路徑字符棗匹配的查詢處理方法。該類方法的關鍵在于分別將查詢模式樹和 x m l 文檔編碼成字符串，按照某種遍歷順序和編碼方案先將查詢模式樹轉換成 路徑字符串，再將x m l 文檔中的各結點按照某種方式編碼并按對應順序連接成 字符串，最后通過字符串匹配和驗證盾輸出最終結果。顯然，該類方法需要進行 大量的字符串模式匱配和復雜的驗證操作，效率較低。該類方法的代表有p r i x 算法【1 3 1 和v i s t 算法【1 4 1 。 3 文獻【1 5 】孛b r u n on 等對一今x m l 路徑表達式中包含的多個祖先，后代關系 結構連接進行整體考慮，提出了整體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 算法。該算法將整個查詢模式樹作為一個整體來考慮，通過為每個查 詢節(jié)點維護一個祖先節(jié)點棧，t w i g s t a c k 算法僅僅需要對所有參與連接的輸入數(shù) 據(jù)結點列表分別順序掃描遍就可以實現(xiàn)整個x m l 路徑表達式的計算，不需要 將路徑表達式分解成若干個結構連接操作，減少了輸入數(shù)據(jù)結點列表的掃描的同 時也減少了對中間結果的多次存取，從而獲得更優(yōu)的i o 性能。在t w i g 概念以及 整體t w i g 連接的思想提出后，引起了研究者們的廣泛關注。研究中們先后提如 了新的t w i g 模式查詢匹配算法。在t w i g s t a c k 算法提出不久之后，j i a n g 等在文 獻【1 6 】中結合懟囂索芬l 瞄】的思想，提出了t s g e n e r i c + 算法，它能夠跳過許多 可以事先判斷并不參與連接的數(shù)據(jù)結點。l uj 等在文獻 1 7 】中對前綴編碼d e w e y 編碼進行擴展，提出了一種擴展d e w e y ( e x t e n d e dd e w e y ) 編碼，結合該編碼以及 有限狀態(tài)自動機( f s t ) 技術，他們提出了t j f a s t 算法，該算法只需要訪問t w i g 查 詢模式樹中的葉子節(jié)點，創(chuàng)新之處在于其編碼可以通過一個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)自動機) 在需要時才計算出某個數(shù)據(jù)結點對應的從x m l 文檔 樹的根結點到該數(shù)據(jù)結點自身的路徑信息，節(jié)省了存儲文檔路徑索引空間的同時 也降低了路徑表達式匹配時的i o 代價。但t j f a s t 算法過分依賴于以上特性，進 行了大量不必要的查詢路徑匹配操作，即大量的字符串模式遙配操作，耗費了較 多的時間。同時，在求解葉子節(jié)點的公共分支時，沒能利用到前綴編碼的特性， 也做了過多不必要的字符串比較搡作。 1 3 本文研究內容 文獻 1 7 】中提出的t j f a s t 算法在當前提出的一系列t w i g 模式查詢匹配算法 中，是較高效的算法，其提出的e x t e n d e dd e w e y 編碼不僅具備前綴編碼的特性， 可以包含一個數(shù)據(jù)結點的所有祖先結點的編碼信息，同時還可以在耗費較小的時 空開銷的情況下計算出該結點的所有祖先結點的標簽名稱，從而褥到從根結點到 自身的路徑信息。為了克服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 編碼進行 了相應的改進，使之支持x m l 文檔的更新操作而不需要對整個x m l 文檔重新 編碼。 為了克服目前提出的一些t w i g 模式查詢匹配算法的缺陷，減少不必要的數(shù) 據(jù)結點比較和查詢路徑匹配操作，本文提出了一種新的t w i g 模式查詢匹配算法。 本文的主要工作可以歸納如下： 1 x m l 文檔的編碼方案研究。本文總結了主流的x m l 文檔編碼方案，分 析了各種編碼方案的優(yōu)點和缺點。 2 x m l 文檔的t w i g 模式查詢匹配算法研究。本文分析了在b r u n on 等人 提磁整體t w i g 模式查詢概念以來研究者們提出的的多個t w i g 模式查詢匹 配算法的思想及執(zhí)行過程。 3 u e dx m l 文檔編碼方案的研究。文獻【1 7 】中提遺的e x t e n d e dd e w e y 編 碼在具備前綴編碼特性的同時還可以通過一個有限狀態(tài)自動機f s t 實時 計算每個數(shù)據(jù)結點的所有祖先結點的名稱信息。本文總結了幾種主流編 碼方案，并借鑒l s d x 編碼方案的思想，對e x t e n d e dd e w e y 編碼進行了 相應的改進，保留原有特性的同時，使之支持x m l 文檔的動態(tài)更新操 作而不需要對整個x m l 文檔重新編碼，有效降低了二次編碼率。 4 提出了一個新的t w i g 模式查詢匹配算法刊g m a t c h 算法。該方法的 輸入包括t w i g 模式中最頂層分支節(jié)點和各葉子節(jié)點的輸入集合流，分三 個步驟來處理一個t w i g 查詢模式，先進行從t w i g 模式中最頂層分支節(jié)點 到各個葉予節(jié)點的破裂邊連接，然后再匹配除最頂層分支節(jié)點外的其它 各分支節(jié)點，最后進行各葉子節(jié)點對應的從t w i g 模式中根節(jié)點到自身的 查詢路徑匹配。同時本文還重組了傳統(tǒng)的兩階段算法，恰當?shù)剡x擇中間 結果的歸并時機，獲得了較好的內存利用率。這種方法減少了數(shù)據(jù)結點 比較和查詢路徑匹配的次數(shù)，提高了查詢效率。 5 構建了一個實驗系統(tǒng)，并在該系統(tǒng)上實現(xiàn)了本文提出的t w i g 模式查詢匹 配算法和文獻【1 7 件提出的t j f a s t 算法，通過多組實驗對比，結采表甓 本文的方法在效率上有較大的提高。 5 1 4 論文的組織結構 全文共分為七章，的組織結構如下： 第l 章“緒論掙，課題研究背景、x m l 數(shù)據(jù)查詢處理技術在國內外的研究現(xiàn) 狀、目前提出的x m l 查詢算法簡介以及本文主要研究工作都在本章中做簡要介 紹。最稀還介紹了本文的組織結構。 第2 章“相關背景知識 ，本章主要介紹x m l 技術及查詢處理技術相關的 知識，包括x m l 文檔的基本構成和數(shù)據(jù)模型、x m l 的模式語言、x m l 的查詢 語言以及t w i g 模式查詢的概念。 第3 章“x m l 數(shù)據(jù)庫技術簡介”，本文在這章中首先總結了x m l 數(shù)據(jù)的編 碼方案，分析了各自的優(yōu)缺點，并舉出了編碼的實例，然后重點分析了囂前已經(jīng) 提出的幾個典型h o l i s t i ct w i g ( 整體小枝) 模式查詢匹配算法，分析了各自的思想和 執(zhí)行過程，并給怨了執(zhí)行實例。 第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方法，最后分析了 兩種編碼的動態(tài)性能。 第5 章t w i g 模式查詢匹配算法t w i g m a t c h 捧，本章詳細介紹了本文提出的 t w i g 模式查詢匹配算法，并對t w i g m a t c h 算法和t j f a s t 做了詳細的比較分析。 第6 章“實驗與結果分析打，本章介紹實驗系統(tǒng)的實現(xiàn)及實驗數(shù)據(jù)的對比分 析。 第7 章“結束語 ，本章將總結全文，提出本文存在的不足和將來要做的工 作。 6 第2 章相關背景知識 作為本文研究內容的基礎知識，本章將簡要介紹x m l 相關的背景知識，包 括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 年起定 義并維護的。該工作組對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 ，標準通用標記語言) 的子集，其目標是允許普通的 s g m l 在w e b 上以露前h t m l 的方式被服務、接收和處理。x m l 被設計成易 于實現(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 文檔示例及對應的d t d 文檔 x m l 是一套定義語義標記的規(guī)則，這些標記將文檔分成許多部件并對這些 部件加以表示。它不像h t m l 語言那樣，定義了一套固定的標記來表示頁面元 素的含義。x m l 是一種元標記語言，用戶可以定義自己需要的標記。這些標記 必須根據(jù)某些通用的規(guī)則來創(chuàng)建，x m l 標記描述的是文檔內容的結構和含義， 7 而不是描述頁面元素的格式化。文檔本身只說明文檔包括什么標記，麗不是說明 文檔看起來是什么樣的。 簡單而言，一個x m l 文檔主要由元素構成，元素包含屬性、子元素和文本 內容，予元素聞可以層層嵌套，此外，一個完整的虹文檔還可以包括垤l 聲明、處理指令、注釋和命名空間等部分。圖2 1 c a ) 就是一個較完整的煳l 文 檔示例，它包含了一個z m l 文檔基本的元素、屬性和文本內容，此羚還包括文 檔開頭的聲明部分。 2 2x m l 數(shù)據(jù)模型 數(shù)據(jù)模型是z m l 數(shù)據(jù)管理研究的核心問題。為了對v i l 數(shù)據(jù)進行有效的 管理，就必須對舭數(shù)據(jù)進行建模，以正確反映x m l 數(shù)據(jù)的特性。當前的研 究工作大都將x m l 數(shù)據(jù)建模為圖模型 2 4 - 2 7 1 或樹模型【2 引。圖模型將垤l 數(shù)據(jù)中 的元素之間、元素和屬性之間的聯(lián)系抽象為有向邊，把整個捌l 數(shù)據(jù)看成是一 個復雜的圖狀結構。樹模型將x m l 數(shù)據(jù)中的元素之間、元素和屬性之間的聯(lián)系 抽象為樹的有向邊，把整個x m l 數(shù)據(jù)看成是一棵有向的標簽樹。相比于圖模型， 樹模型褥到了更廣泛地使用，因此本文的研究也是基于樹模型，以下對樹模型做 進一步介紹。 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 文檔的樹模型表示 在樹模型中，將舭文檔中的各元素抽象為標簽樹中的結點，結點的類型 主要有根結點( r o o tn o d e ) 、元素結點( e l e m e n tn o d e ) 、文本值結點( t e x tn o d e ) 和屬性 結點( a t t r i b u t en o d e ) 等。此外，該樹模型是一棵有序樹，標簽樹中的各結點之間 對應順序與每個結點在原) ( 】憂l 文檔中出現(xiàn)的順序一致。 例2 1 圖2 。2 所示的就是圖2 1 中x m l 文檔對應的樹模型表示形式。在樹 模型表示形式中，整個x m l 文檔被表示成以標簽名為“b i b 的結點作為根結點 的標簽樹。原文檔中的每個標簽被表示為樹中同名的結點，而元素之間、元素和 屬性之間的聯(lián)系被抽象表示成模型樹上的有向邊。 2 3x m l 模式語言 x m l 文檔在本質上只是一個保存數(shù)據(jù)的結構化載體，為了得到有效的符合 要求的x m l 文檔，還必須驥確文檔中的數(shù)據(jù)必須符合的結構要求，即需要一靜 用來描述x m l 文檔中數(shù)據(jù)結構的模型。這種數(shù)據(jù)模型不僅建立了x m l 文檔中 可以使用的x m l 譎匯表，還定義了x m l 文檔中元素的順序和元素的嵌套規(guī)則， 并建立了文檔數(shù)據(jù)的數(shù)據(jù)類型。目前應用得比較廣泛的是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 文檔的內容和結構。d t d 列出了 可用在對應x m l 文檔中的元素、屬性、實體和符號表示法，以及它們之間的相 互關系。d t d 通過指定文檔結構的一系列規(guī)則來約束文檔的結構，例如d t d 可 以規(guī)定文檔的根元素必須是b i b ，b i b 元素只能包含一個或者多個b o o k 元素，b o o k 元素可以包含一個或者多個a u t h o r 元素，t i t l e 元素緊跟在其后，之后可以是0 個 或者多個c h a p t e r 元素，這些約束規(guī)則都是在d t d 中定義的。圖2 1 ( b ) 就是一個 涯l d 陽的例子。 一個d t d 文檔通過具體說明每一個元素和屬性的名稱、元素與子元素之間 的嵌套關系、子元素的賚現(xiàn)順序幫次數(shù)等來定義x m l 文檔的結構模型，箕通過 操作符宰( 元素出現(xiàn)o 次或者多次) 、+ ( o 次或者一次) 、7 ( 0 次或者1 次) 、l ( 符號兩 9 邊的元素出現(xiàn)其一) 來定義子元素的高現(xiàn)次數(shù)。在d t d 文檔中用關鍵字 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 文檔結構方面已經(jīng)超到來很好的作用，可以 在x m l 文檔被程序解析時利用d t d 來驗證該x m l 文檔的有效性，但仍存在一 些不足，尤其在一些新興領域應用中，體現(xiàn)出了以下幾個局限性。 首先是d t d 幾乎不具備數(shù)據(jù)類型定義的能力，尤其是對元素的內容而言。 在d t d 中一切都被默認定義為字符串，不支持數(shù)字、復合類型等數(shù)據(jù)類型。 第二個問題是d t d 和x m l 文檔使用的是兩種不同的語法。給數(shù)據(jù)處理上 帶來了不必要的麻煩，也使得帆不具備自描述的特性。 第三個闖題是d t d 的約束定義能力不足，無法對x m l 文檔進行更細致的 語義約束。 最詹一個問題是d t d 不夠結構化，重用的代價相對較高。 鑒于d t d 的諸多不足，已經(jī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 的第一個版本，于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 在相應方面的改進。 在例2 - 2 中共定義了6 個元素。在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 屬性。這兩個元素已經(jīng)在前綴所 指向的命名空閬中定義始了。在每個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 元素來自定義復合數(shù)據(jù)類型，從而用戶可以根據(jù)自己的需要自定義 數(shù)據(jù)類型，更好的擴充了x m l 文檔可以使用的數(shù)據(jù)類型。在該例子中， c o m p l e x t y p e 元素中包含一個s e q u e n c e 子元素，它被稱為模型組。通過模型組可 1 0 以把子元素聲明或引用組合起來，從而構建更加有意義的內容模型。對于d t d 的第二個問題，x m ls c h e m a 使用標準的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 文檔一樣被處理 和解析。對于第三個問題，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ù)、默認值、固定取值等。對于元素值的進一步約寒x m ls c h e m a 也提供了完備的機制，如可以將一個元素的值限定在個數(shù)值區(qū)間內、取特定的 枚舉值、歪則表達式匹配和字符串的長度限定等。 2 4x m l 查詢語言 圖2 3x m l s c h e m a 示例 在x m l 使用的初期，學者們就注意到了在包含豐富信息的海量x m l 數(shù)據(jù) 中檢索用戶關心的有用信息的重要性，從麗很多學者的研究重點就指向了x m l 查詢語言的研究。由于x m l 文檔是一種半結構化數(shù)據(jù)，無法使用關系數(shù)據(jù)庫中 已經(jīng)比較成熟的s q l 查詢語言，焉是需要一種新型的x m l 查詢語言來對x m l 文檔進行查詢。為此，w 3 c 提出了多種查詢語言，其中最重要的有兩個：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 等，它們的共圓特點是 采用路徑表達式來對x m l 文檔進行定位。下面對技術上相對成熟，已經(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 文檔建模成具有樹形結構的文檔樹來訪問。通過 x p a t h 可以定位x m l 文檔樹中的任意結點。x p a t h 使用路徑表達式來與x m l 文 檔中的對應部分進行匹配。表達式是x p a t h 的主要構件，其中最重要的表達式是 定位路徑( 1 0 c a t i o np a t h ) 表達式，簡稱路徑表達式。 定位路徑表達式分為絕對和相對定位路徑表達式兩種。每個定短路徑表達式 包含一個或者多個定位步( 1 0 c a t i o ns t e p ) ，每個定位步之間用左斜杠“或者雙左 斜杠搿間隔。其中絕對路徑從文檔的根結點開始定位路徑，以“， 開頭來表 示；相對路徑則以“ 開頭表示，它直接從某個定位步開始進行路徑定位。 定位步是一個定位路徑表達式的組成部分，而一個定位步又包含】以下三個部 分： 一個軸，它指定了定位步選擇結點與上下文結點之間的樹狀關系。如c h i l d 軸表示選擇上下文結點的孩子結點，x p a t h 共定義了1 3 個軸以滿足各種操作的 需求。這1 3 個軸可以分為三大類：自身軸、反向軸和向前軸。其中自身軸包括 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 軸。 一個結點測試，它用于指定定位步中選擇結點的結點類型或結點名。 0 個或多個謂詞，它使用專有的謂詞表達式進一步過濾定位步選擇的結點集 厶 口。 以上三部分出雙冒號“：和對中括號“口”闋隔，共闋組成一個定位步， 其中“：用于分隔軸名和結點測試，“凸用于表示謂詞。例如，在定位步 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 是結點測試，而 t i t l e = “x m lx p a t h ”】就是一個謂詞。 對于一個定位步內部的計算先從軸和結點測試開始，產生初始結點集合后， 利用其矮的各個謂詞對初始結點集合進行篩選，最詹得到結果結點集合。 1 2 下面簡要介紹在本文中將會用到的幾個常用的x p a t h 語法。 1 b i b b o o k a u t h o r 這是一個絕對單路徑表達式，查詢所有滿足條件的a u t h o r 結點，該a u t h o r 結點的雙親結點為b o o k ，b o o k 結點的雙親結點為根結點b i b 。 2 c h a p t e r t i t l e 這是一個相對單路徑表達式，查詢所有雙親結點為c h a p t e r 的t i t l e 結點。 3 b o o k i d 這是一個帶有屬性謂詞的相對單路徑表達式，查詢所有具有通屬性的b o o k 結點。 4 。b o o k a u t h o r = ”t o n y 辯 t i t l e 這是一個帶有分支節(jié)點的復合路徑表達式，即t w i g 模式查詢表達式。查詢 所有滿足條件的t i t l e 結點，該t i t l e 結點的雙親結點b o o k 弱時也是僮為“t o n y 的a u t h o r 結點的雙親。 2 4 2x q u e r y x q u e r y 是w 3 c 于2 0 0 1 年首次推出的另一個被廣泛使用