（計算機軟件與理論專業(yè)論文）原生數(shù)據(jù)庫動態(tài)編碼方案探討.pdf

a b s t r a c t ab s t r a c t wi t h t h e r a p i d d e v e l o p m e n t o f n e tw o r k t e c h n o l o g i e s a n d n e t w o r k s e r v i c e s in r e c e n t y e a r s , x ml ( e x t e n s i b l e m a r k u p l a n g u a g e ) h a s b e e n in c r e a s i n g l y a n d p o p u l a r l y u s e d i n s o c i e t y , a n d m a k e i t s e lf a s ta n d a r d f o r d a t a e x c h a n g e a n d d a t a d e s c r i p t i o n o f c r o s s - p l a t f o r m a n d c r o s s - la n g u a g e . t h e e m e r g e n c e o f l a r g e a m o u n t o f x m l d a t a p o s e s a n e w c h a l l e n g e t o d a t a b a s e f o r s t o r i n g a n d q u e ry i n g x m l d a t a . a n d n a t i v e x m l d a t a b a s e r i s e s i n r e s p o n s e t o t h e p r o p e r t i m e a n d c o n d it i o n s . s t o r a g e a n d q u e r y i n g i s t h e p r i m a ry f u n c t i o n o f n a t i v e x ml d a ta b a s e , a n d t h e y p l a y a k e y r o l e i n t h e in t e g r a l p e r f o r m a n c e o f t h e d a ta b a s e . s o t h e s t u d y o f n u m b e r i n g s c h e m e o f n a t i v e x m l d a t a b a s e i s v e ry i m p o r ta n t , a n d s t o r a g e n u m b e r i n g s c h e m e t o o . o n t h e b a s is o f a n a l y z i n g n a t i v e x ml d a t a b a s e re s e a r c h i n g r e s u l t s b o t h a t h o m e a n d a b ro a d , t h i s p a p e r m a k e s a d e e p re s e a r c h o n t h e n u m b e r i n g s c h e m e o f n a t i v e x ml d a ta b a s e a n d p u t s f o r w a r d a n e w n u m b e r in g s c h e m e , w h i c h i s n a m e d a s d o n . b e s i d e s t h e c h a r a c t e r i s t i c s o f p re fi x a n d d y n a m i c s , d o n a l s o p o s s e s s e s t h e v i r tu e s o f o r d e r a n d r e c o n s tr u c t i o n , w h i c h e ff e c t i v e l y s u p p o rt x ml s t r u c t u r e q u e r y i n g o f v a r i o u s e x t e n s i o n s . a ft e r a n a l y z i n g s t o r a g e e n c o d i n g re s e a r c h i n g re s u l t s , t h i s p a p e r s u g g e s t a s t o r a g e e n c o d i n g s c h e m e f o r d o n , m a k d i n g a c o m p a r i s o n w it h t h e o t h e r o n s t o r a g e p e r f o r m a n c e o b j e c t i v e l y . f i n a l l y , t h e t h e s i s r o u g h l y d i s c u s s e s d o n q u e r y i n g s c h e m e a n d n o d e r e c o n s t r u c t i o n a l g o r it h m s , a n a l y z i n g a n d c o m p a ri n g t h e p e r f o r m a n c e v i s i t i n g d i s k 1 / o o f d o n w i t h p re f i x n u m b e r i n g s c h e m e w h i le e x t e n s i b l y q u e ry i n g x ml d a t a . k e y w o r d s : n a t i v e x ml d a t a b a s e , n u m b e ri n g s h c e m e , n o d e r e c o n s tr u c t i o n , e x t e n s i b l e q u e ry i n g 1 1 南開大學學位論文版權使用授權書 本人完全了 解南開大學關于收集、保存、使用學位論文的規(guī)定，同意如下 各項內容:按照學校要求提交學位論文的印 刷本和電子版本;學校有權保存學 位論文的印刷本和電子版，并采用影印、縮印、掃描、數(shù)字化或其它手段保存 論 文;學校有權提供目 錄檢索以 及提供本學位論文全文或者部分的閱覽服務; 學 校有權按有關規(guī)定向國家有關部門或者機構送交論文的復印件和電 子版;在 不以 贏利為目 的的前提下，學?？梢?適當復制論文的部分或全部內容用于學術 活動。 學位論文作者簽名: 年s月 材日 四 經指導教師 同意，本學位論文屬于保密，在 年解密后適用本授權書。 指導教師簽名:學位論文作者簽名: 解密時間: 年月日 各密級的最長保密年限及書寫格式規(guī)定如下: 內部5 年 ( 最 民 5年，可少于5 年) 秘密*1 0年 ( 最長1 0年，可少于 1 0年) 機密2 0年 ( 最長 2 0年，可少于 2 0年) 南開大學學位論文原創(chuàng)性聲明 本人鄭重聲明:所呈交的學位論文，是本人在導師指導下， 進行研究工作 所取得的成果。除文中已經注明引用的內 容外，本學位論文的研究成果不包含 任何他人創(chuàng)作的、己 公開發(fā)表或者沒有公開發(fā)表的作品的內 容。 對本論文所涉 及的研究工作做出貢獻的其他個人和集體，均已 在文中以明確方式標明。 本學 位論文原 創(chuàng)性聲明的 法律責任由本人承擔。 學位論文作者簽名 第一章緒論 第一章緒論 第一節(jié)課題研究背景 i n t e r n e t 發(fā)展初期， h t m l扮演了相當重要的角色，為i n t e rn e t 的蓬勃發(fā)展 發(fā)揮了 突出的作用。隨著網 絡信息的不斷擴充膨脹，使得h t m l無法滿足海量 結構化和半結構化數(shù)據(jù)更復雜、 更大規(guī)模的需求。 1 9 %年， 全球信息網協(xié)會( wo r d w i d e w e b c o n s o r ti u m , w 3 c ) 開始制定x m l ( e x t e n s i b l e m a r k u p l a n g u a g e ， 可擴 展 標記 語言) 1 ) ， 希望它 能 具備比h t m l 更嚴謹?shù)?架構， 同時 又比s g m l ( s t a n d m r d g e n e r a li z e d m a r k u p l a n g u a g e ) 更 容易 使 用。 在 這 種背 景 下， 新的 標 準 標 記語言 x m l應用而生。 x ml 是一種自 描述的、 半結構化、 可擴展的標記語言。 它是一套無限延伸、 用來設計各式各樣標注語言的準則，是一種自 我描述的語言。目前它已經成為 i n t e rn e t 上數(shù)據(jù)交換和數(shù)據(jù)描述的事實標準， 使基于w e b 服務的互操作性變得簡 單可行; 將語義內容和外觀顯示相分離使得x m l更專注于數(shù)據(jù)的語義信息; 基 于x ml 通用高 效的x m l 解析器和訪問 接口 在各個平臺 上都易于獲取，開發(fā)基 于x ml的應用變得異常簡單:用戶自 定義標簽和無限嵌套的能力賦予x ml 無 限擴張能力，幾乎可以 清晰自 然表達各類數(shù)據(jù)。 由于x ml的各種優(yōu)勢，使得x ml在各個領域得到廣泛的支持和應用。如 電 子 商 務 全 球 化 標 準e b x m l t2 1( e c ) ， 中 國 國 情 的 電 子 政 務 語 言 規(guī) 范c n g x m l (3 1 數(shù)學領 域的m a t h m l 0 1 等 等比比皆 是。 隨 著x m l 和w e b 技術的 廣泛應用和發(fā)展， s e n m a t i c w e b提出了一種通用框架，使數(shù)據(jù)能跨企業(yè)、地域、平臺的得到共享 和重用， 但是這些信息資 源通常以半結構化數(shù)據(jù)的形式特別是x ml數(shù)據(jù)的形式 存在.半結構化數(shù)據(jù)成了人們獲取、傳播和交換信息的重要途徑，整個we b形 成了一個巨大的異構數(shù)據(jù)環(huán)境。 但是將數(shù)據(jù)表示為x m l只是第一步， 如何對海 量的x ml文檔數(shù)據(jù)進行有效存儲和管理，如何實現(xiàn)更快、更精確的x ml查詢 等己經成為迫切需要解決的研究課題。 第一章緒論 x ml 數(shù)據(jù)量隨著x m l的廣泛應用呈指數(shù)級增長， 對這些海量的x ml 數(shù)據(jù)， 至少可以利用四 種方式來進行存儲和管理， 但前兩種管理系統(tǒng)并非針對x m l 設 計， 在管理x m l 數(shù)據(jù)時有一定的局限性。 第一種方式是文件系統(tǒng)， 它不提供事 務索引查詢、事務管理、并發(fā)控制、 安全恢復機制等技術，無法保證數(shù)據(jù)的完 整 性 和 一 致 性 ; 第 二 種 方 式 是x m l e n a b l e d ls l數(shù) 據(jù) 庫 ( x e d 瑪 ， 在 關 系 或 面 向 對 象數(shù)據(jù)庫基礎上擴充相應的功能， 使其能夠勝任x ml 數(shù)據(jù)的處理。 它的局限性 在于對于格式復雜的x m l 數(shù)據(jù)支持程度較差，而且不支持x ml 標準的查詢語 言x p a th 161 , x q u e ry 7) ， 更 新 語 言x u p d a te e 1等 各 種 技 術 。 這 種 方 式 使 得 在 處 理 x m l 數(shù)據(jù)的時候要經過多級復雜的轉換，這必將帶來效率的降低:第三種方式 是n a ti v e x m l d a t a b a s e 9 1( 又 名 原 生 數(shù) 據(jù) 庫 ， 文 中 簡 稱 為n x d ) ， 它 是 應 用 需 要 推動誕生和發(fā)展出 來的新技術。它充分考慮到x m l 數(shù)據(jù)的特點，將x m l 文檔 和元素作為 基本結構， 是專門 設計用于存儲和管理x m l 文檔的數(shù)據(jù)庫， 從各個 方面都很好支持x m l的查詢和存儲等各項功能。第四種方式是x e d b和n x d 的 混 合方 式h y b ri d x m l d a t a b a s e ( h x d ) ， 即 混 合x m l 數(shù) 據(jù) 庫， 它 將 傳 統(tǒng)數(shù) 據(jù) 庫 和n x d結 合 起 來， 典 型 的 例 子 是o z o n e ll o ) e 第二節(jié) n a t i v e x ml數(shù)據(jù)庫的發(fā)展 n x d是最 近幾年才提出的概念，是一個比 較嶄新的發(fā)展領域， 主要是為了 解決大量x m l 數(shù)據(jù)的存儲和管理問題。 許多公司和研究機構都紛紛致力于n x d 的研究和發(fā)布，目 前就n x d的產品情況來看， 學術界的原型系統(tǒng)和商業(yè)產品之 間存在微妙差別，盡管主流技術是一致的。 工業(yè)界的n x d產品強調實用，這與學術界原型系統(tǒng)特點不同: ( 1 ) 在底層 提供“ 集合” 的 數(shù)據(jù)結 構， 以 存儲x m l 元素結點， 通過b - 樹結 構建立索引。 “ 集合”之上一般還會一級或二級索引，加快了查詢處理速度，顯 得更加高效使用。 ( 2 ) 引入日 志管理， 建立完善的事務處理機制。 這些事務處理功能包括提交、 回滾和日 志文件， 保證系統(tǒng)出 現(xiàn)問題后的完全恢復。 口 ) 異構數(shù)據(jù)的 集成管理。 市場n x d擁有集成異構數(shù)據(jù)源的強大能力， 克 服樹型結構數(shù)據(jù)難以管理的局面。 學術界的原型系統(tǒng)有如下特點: 第一章緒論 ( 1 ) 強調平臺 無關性。在n x l 研究早 期， 業(yè)界曾爭論x m l數(shù)據(jù)是存儲在 關系數(shù)據(jù)庫中， 還是另外在開發(fā)存 儲)ml的 物理數(shù)據(jù)庫。 這影響了大多數(shù)學者 的研究，在設計時必須考慮索引過的x m l數(shù)據(jù)可以存儲在多種數(shù)據(jù)庫結構中。 ( 2 ) 強調存 儲與 查詢性能的提高. 為提高 查詢效率， 學 術界相比工業(yè)界更注 意索引結構的設計。 ( 3 ) 強 調研究 n x d 的 模式設計規(guī)范 化的 數(shù)據(jù)理論模型，在如 何優(yōu)化 x m l 數(shù)據(jù)庫設計、消除數(shù)據(jù)冗余和一致方面有了一些實質上的進展。 目前市場上大約至少有三十多種不同的 n x d 產品。其中商業(yè)數(shù)據(jù)庫包括 t a m in o ,x -h iv e / d b 和e x c e lo n 等 。 另 外 還 有 開 放 源 代 碼 的 數(shù) 據(jù) 庫， 包 括a p a c h e 的b e r k e l e y d b x m l , d b x m l , x i n d i c e , c x i ，和o z o n e 等。 還有些是基于關系 數(shù) 據(jù)庫的， 如d b d o m, e y i s t . e x t c , x d b , x p s q l等，還 有些是基于面向 對 象數(shù) 據(jù)庫的， 如b i r d s t e p r d m x m l , o z o n e , s o n i c x m l s e r v e r , x - h i v e / d b 等; 還 有些 基于其他專 用的 存儲格式， 比 如d b x m l , x i n d i c e , i p e d o , l o r e , t e r a t e x t d b s等。目 前一些主流數(shù)據(jù)庫廠商已經實現(xiàn)了對 x ml的支持，如 o r a c l e 公司 的o r a c l e 數(shù) 據(jù)庫軟 件， i b m公司的d b 2 x m l e x t e n d e r , s y b a s e 公司的a s e ， 微 軟公司的s q l s e r v e r 等，他們也開始 將目 光專注n x d數(shù)據(jù)庫。 國外對 n x d的研究比國內早一些，國內目前的研究剛剛開始，目前己有了 一些產品，比如中國人民大學的 i d k e實驗室開發(fā)的 o r i e n t x，支持了x ml數(shù) 據(jù)庫的存 儲、 查詢、更 新等操作。國內n x d理論 研究1 1 相對較少。 第三節(jié)n a t i v e x m i l 編碼方案面臨的挑戰(zhàn) 在早期，數(shù)據(jù)庫編碼被認為一一個頗具有挑戰(zhàn)性的研究課題，吸引了眾多 研究者。對于編碼方案，從是否支持文檔更新來說，可以分為兩類:靜態(tài)編碼 方案和動態(tài)編碼方案;從設計思想和編碼特點來說可以分為三類:基于區(qū)間的 編碼p 2 - 1 5 1 、 基于 路徑的 編碼 1 6 - 2 0 】 和基于數(shù)學 計算的 編碼2 1 - 2 5 1 。 基于區(qū) 間的編 碼 方案能快速支持文檔結點結構關系判定，通過預留區(qū)間來支持動態(tài)更新，但隨 著結點插入會發(fā)生結點重新編碼，造成效率低下;基于路徑策編碼方案，通過 增加字典有序性，既能支持文檔結構關系的快速判定，也能很好支持文檔的動 態(tài) 更新， 但是 對于擴展的次 序敏感性結構查 詢的 效率有待提高，編碼存儲代 價 較大;基于數(shù)學計算的編碼方案是存儲代價小，查詢速度快，但也存在上述兩 第一章緒論 種方案的類似缺點。 編碼方案直 接關 系到x m l 數(shù)據(jù)庫的 存儲代價、 查詢 速度和更新速度。 繼承 現(xiàn)有數(shù)據(jù)庫編碼方案的 優(yōu)點，避開它們的缺點， 這是數(shù)據(jù) 庫編碼 方案的研究者 們所面臨的難題。 第四節(jié)本文主 要研究工作及內 容安排 本 文在國內 外現(xiàn)有的n x d的編碼方 案進行了深入的分析 研究， 總結了 這些 編碼方案的優(yōu)缺點，提出了一種功能更強更全的動態(tài)編碼方案和相應的存儲編 碼方案， 探討了在 此基礎之上的 擴展結構查 詢的1 / 0性能。 主要研究工 作和創(chuàng)新 成果如下: ( 1 ) 對國內 外己 有的 各種經典n x d編碼方案進行了 全面總 結和分析，總結 出三種類 型的 編碼方案，并比 較了 各自 的 優(yōu)缺點。 ( 2 ) 提出 一種新的動態(tài)有序編碼方案 d o n ， 它不僅具備前 綴編碼方案的 優(yōu) 點，而且還具備結點重構的能力。d o n很好地支持了擴展性的結構查詢，也提 高了 次序敏感性 結構查詢的速 度。 侈 ) 在 分 析 現(xiàn) 有 存儲 編 碼 技 術 基 礎 之 上 ， 提 出 適 合d o n的 存 儲 編 碼 方 案， 并進行了存儲性能的對比。 () 探 討 了d o n 的 重構 算 法， 舉 例 分 析了d o n 和 前 綴 編 碼 的 擴 展 性結 構 查 詢的u o性能，最后給出了二者的擴展結構性查詢的u o性能對比結果。 論文的組織結構和內容安排如下: 第一章主要介紹課題研究背景， 描述n x d發(fā)展現(xiàn)狀和編碼方案所 面臨的 挑 戰(zhàn); 第二 章是對n x d編碼方案的 一個概述， 分析了國內 外現(xiàn)有的 各類編碼 方案， 并總結了它們的各自優(yōu)缺點.第三章主要內容是根據(jù)編碼方案的設計要求，提 出新的編碼方案 d o n。第四章主要總結了現(xiàn)有存儲編碼技術，提出適合 d o n 的 存儲編碼方案， 并對它們進行了 存儲 性能 對比。 第五章主要分析d o n和前 綴 編碼方 案的 查詢處理性能， 并給出 擴展查詢時的1 / 0性能對比結果。 最后對全文 進行了總結，并闡述需要進一步研究的問題。 第二章 n a t i v e x m l 數(shù)據(jù)庫編碼方案概述 第二章 n a t i v e x ml數(shù)據(jù)庫編碼方案概述 第一節(jié)n a t i v e x b ii . 數(shù)據(jù)庫概述 2 . 1 . 1 ) c a l繪述 w 3 c的x m l工 作 組 是 這 樣 描 述) c iv il的 (2 6 1 : ) c m l是s g m l ( s t a n d a r d g e n e r a liz e d m a r k u p l a n g u a g e ， 標 準 通用 標 記 語言 ) 的 子 集。 它的目 標是 允 許 普 通 的s g m l 在w e b 上以目 前的h t m l ( h y p e rt e x t m a r k u p l a n g u a g e . 超文本標記 語言) 方式被服務、 接受和處理. x m l被設計成易于實現(xiàn)，并且可在s g ml 和 h t m l 之間互相操作氣 x m l是一種自 描述、半結構化和可擴展化的標記語言，是一種定義語言的 語言，也就是一種元語言。作為s g m l的一個簡化子集，它將s g m l 的豐富功 能和h t m l的易用性結合到一起，具有如下的特性: ( 1 )可擴展性。 x m l 允許使用者創(chuàng)建和使用他們自己的標記， 因此x m l 允許 開發(fā)各種不同專業(yè)的特定領域的標記語言。 ( 2 )可分離性。 x m l 提供了 一種結構化的 數(shù)據(jù)表示方式， 實現(xiàn)了數(shù)據(jù)內 容和 外觀形式的真正分離。因此w e b 用戶所追求的許多先進功能在x m l 環(huán)境下更容 易實現(xiàn)。 ( 3 )自 描述性。 x m l 文檔通常包含一個文檔類型聲明， 它是自 我描述的。 x m l 這種表示數(shù)據(jù)的方式真正做到了獨立于應用系統(tǒng)，并且數(shù)據(jù)能夠重用。 ( 4 )可移植性。由于 x m l是以文本形式描述的， 所以適合各種平臺 環(huán)境的 數(shù)據(jù)交換，在一種平臺上編寫的x m l 文檔無須任何更改即可移植到其它平臺上。 ( 5 )半結構化。 x m l 文檔的結構可以 通過模式來描述， 通過模式驗證文檔的 有效性會非常容易。 2 . 1 .2 x ml文檔結構和類型 x ml文檔可以劃分為兩種類型:以數(shù)據(jù)為中心的文檔和以文檔為中心的文 第二章 n a t i v e x 1 4 . 數(shù)據(jù)庫編碼方案概述 檔。 ( i ) 以 數(shù)據(jù)為中 心的文檔 以數(shù)據(jù)為中心的文檔就是將x m l 用作數(shù)據(jù)的傳輸載體， 只提供給機器消費 的文檔，如公司銷售訂單、航班時刻表、科研數(shù)據(jù)及股市匯率等。這種文檔的 特點 是: 結構相當 規(guī) 整， 數(shù)據(jù)粒 度精 細伍 n e - g r a in e d d a t a ) ( 即 最小的 獨立數(shù)據(jù) 單位只存在于p c d a t a元素或屬性這一級別) ， 很少或沒有混合內容。 除非在對 文檔進行驗證的時候，同級元素或p c d a t a的出現(xiàn)次序一般來說并不重要。 這 類數(shù)據(jù)可以 來自 數(shù)據(jù)庫 ( 此時要輸入給 x m l ) 或在數(shù)據(jù)庫之外 ( 此時要將其存 入數(shù)據(jù)庫). ( 2 )以 文檔為中 心的 文檔 以 文檔為中心的文檔通常是供人消費的。例如書籍、e m a il 、廣告以及幾乎 所有人工寫成的x h t m l 文件. 其特性為結構不太或根本不規(guī)則、數(shù)據(jù)粒度大， 混合內容多。同級元素或p c d a t a出現(xiàn)的次序一般來說總是非常重要的。以文 檔為中心的文檔通常是以x m l 手工寫成， 或從其他格式( 如r t f , p d f , s g m l ) 轉換到x m l ，與以 數(shù)據(jù)為中心的文檔不同，它們的來源通常不是數(shù)據(jù)庫。 在現(xiàn)實中以數(shù)據(jù)為中心和以文檔為中心的文檔之間的差別不一定很明顯。 例 如，一種以 數(shù)據(jù)為中心的文檔比 如發(fā)票， 可能含有大粒度的、結構不規(guī)則的數(shù) 據(jù)，比如零件說明:另一種以文檔文中心的文件如用戶手冊，可能包含細粒度 的結構規(guī)則的數(shù)據(jù) ( 通常為元數(shù)據(jù))比如作者和修訂日期。 2 . 1 . 3 n a t i v e x i a l數(shù)據(jù)庫的定義 n a t v i e x ml數(shù)據(jù)庫” 這個術語首先在s o f t w a re a g為t a m i n o 所做的營銷 宜傳中露面。r o n a ld 日 o u r r e t 在 “ x ml a n d d a t a b a s e s 一文中給出了n x d的定 義2 7 j 。一個純x m l 數(shù)據(jù)庫是指: ( 1 ) 為x m l 文檔定義了 一 個 ( 邏輯) 模型， x m l 數(shù)據(jù)的存儲和查詢都基于 這個模型.這個的模型至少應該包括元素、屬性、p c d a t a等，并保持文檔順 序。如x p a t h 數(shù)據(jù)模型， x m l i n f o s e t 以 及d o m和s a x 1 .0 的事件所隱含的模 型都是這類數(shù)據(jù)模型。 ( 2 ) 以x m l 文檔 作為邏 輯 存儲的 基 本單 位， 就像關系數(shù)據(jù) 庫以 行( 元組 ) 作為 表的邏輯存儲基本單位一樣。 第二章 n a t i v e x m l 數(shù)據(jù)庫編碼方案概述 ( 3 ) 不要求任 何特殊的基本物理存 儲模型，它可以建 立在關系層次上或面向 對象的數(shù)據(jù) 庫之上， 或者使 用諸如 索引文 件、 壓縮文件此類的專門 存儲格式。 從這個至少可以簡單地總結一下三點:n x d是專門用來存儲 x m l 數(shù)據(jù)的， 而且完整無缺的存儲 x m l 模型的所有成分。不過， n x d 實際所能存儲的信息比模 型中定義的要多: n x d的基本存儲單位是x m l 文檔?；敬鎯挝痪褪强梢匀?納一份數(shù)據(jù)的最低級的上下 0文( c o n t e x t ) ，相當于關系數(shù)據(jù)庫中的行:q 3 n x d 可能根本就不是真正的獨立的數(shù)據(jù)庫。 n x d 底層的數(shù)據(jù)存儲格式并不重要，正如 關系數(shù)據(jù)庫所用的物理存儲格式與數(shù)據(jù)庫是不是關系型之間毫無關系。 2 . 1 . 4 n a t i v e x ml數(shù)據(jù)庫特性 n x d作為專用于存儲 x m l文 檔的 數(shù)據(jù)庫， 應該具有一般數(shù)據(jù)庫的 特征， 比 如事務 管理、并發(fā)控制、查詢語言、安 全機制、 二次開 發(fā)接口 等。 一般來說， x x d具有 如下幾個特性: ( 1 ) 文 檔集合 “ 文檔集合”的概念比文檔更高一層.一般來說，一個 “ 文檔集合”關聯(lián) 一種模式，它把一類文檔聚集在一起。將文檔加入到有模式的 “ 文檔集合”時， 會對要加入的文檔進行模式檢查，只有符合 “ 文檔集合”模式的文檔才可以加 入。 集合可以 方便用戶操作，這種級別上的查詢、 修改操作都會反映到集合內 的 每個文檔中。 “ 文檔集合” 與“ 文檔” 的關系 類似于關系數(shù)據(jù)庫中“ 關系模式” 與“ 關系” 的 關系。 不同于 關系數(shù)據(jù)庫管 理系統(tǒng)中 模式的嚴格 特性， 純x m l 數(shù) 據(jù)庫還提供 “ 無模式”的文檔集合.即將一個文檔放入該集合時，不必驗證該 文檔的模式。 這 種文檔一般用來存放 存儲格式很難統(tǒng)一、 半結構化的x m l文 檔。 ( 2 ) 查詢語言 n x d至少 要支持某種或者幾種查 詢語言，這些語言可以 是專有的， 也可以 由標準化組織制定的。目前 x p a t h是主流的查詢語言，各種產品都提供了或多 或少的 支持， 但 x p a t h作為數(shù)據(jù)庫查 詢語言還有不少缺陷，比 如不能分組、排 序、 連接等。作為x p a t h 的替代品， x q u e ry功能要強大的多， 它支持循 環(huán)、分 組、排序、連接等，是 w3 c推薦的針對x ml文檔的查詢語言。 ( 3 ) 更新 語言 大多數(shù)n x d對 x ml文檔的更新是通過調用其提供的 a p i 完成，或者通過 第二章 n a t i v e x 6 1 l 數(shù)據(jù)庫編碼方案概述 簡單的替換整個文檔來實現(xiàn)。 一些n x d提供專用的更新語言來允許數(shù)據(jù)更新， 同時 也有不少開放源代碼的n x d支持x u p d a t e o ( 4 ) 事務處理和并發(fā)控制 幾乎所有n x d都支持事務處理和并發(fā)控制。目 前n x d產品雖然都提供了 一定程度的支持，但是鎖的粒度通常都比 較大，所以多用戶并發(fā)性的支持相對 較低， 這方面遠不像關系數(shù)據(jù)庫那樣令人滿意。 ( 5 ) 編程接口 良 好的編程接口 是一個數(shù)據(jù)庫系統(tǒng)成熟的重要標志。 一個好的n x d系統(tǒng)應 該提供類似于o d b c或j d b c那樣的數(shù)據(jù)庫連接的接口， 還應提供瀏覽元數(shù)據(jù)、 執(zhí)行查詢和返回結果的方法。 6 . 往返存取( r o u n d - t r ip p i n g ) n x d一個重要特性是它為x m l 文檔提供了“ 往返存取即 功能: 可以 將x m l 文檔存放在n x d中，而且能再取回“ 同樣的”文檔。這種性質對于以“ 文檔為 中 心” 的應用程序來說非常重要， 因為易被忽略的c d a t a部分， 實體應用、 注 釋和處理指令是這些文檔不可缺少的組成部分，特別是對于法律和醫(yī)學領域中 格式不允許隨意篡改的數(shù)據(jù)文檔。 第二節(jié)編碼方案的引入 提高存儲和查詢x m l數(shù)據(jù)的性能是當前研究的一個熱點。 x ml查詢通常 應包括兩種查詢: ( 1 ) 值查詢: 在元素內 容上的查詢， 即 通過限定在元素內 容或屬性值上的取 值而進行的選擇查詢，稱為值查詢。 ( 2 ) 結構查詢: 通過路徑表達式， 對文檔中 標記的元素之間的結構關系進行 查詢，稱為結構查詢。 x m l 元素有兩類基本結構關系。 x m l 文檔元素結點之間的基本結構關系包 括: 祖先/ 后代關系( a n c e s t o r / d e s c e n d a n t ) 、 雙親/ 孩子關系( p a r e n t/ c h i l d ) 、之前 / 之 后關 系 ( p re c e d i n g / f o l l o w i n g ) 、 左兄 弟 / 右 兄弟關系( p r e c e d i n g - s ib l i n g / f o l l o w i n g - s i b l i n g ) 等。 前兩者稱為包含關系， 后兩者稱為文檔位置關系。 查詢可以 利用路徑表 達式來導航x m l文檔樹中的任意長度的路徑。 但是一個單一路徑步的查詢， 比 如b o o k / a u t h o r ， 將僅查找b o o k 元素的孩子a u t h o r 元素。因此， 對于多個路徑步 第二章 n a t i v e x m 1 . 數(shù)據(jù)庫編碼方案概述 的x m l 文檔結 構查詢， 將導 致 結 構連接1 1 3 1 的 計算。 為了 有效支持x ml 查詢， 特別是結構查詢，研究者提出了) c a l 數(shù)據(jù)的各 種索引技術和編碼方案。 對于x ml結構查詢，一種實現(xiàn)方法是建立x m l文檔 樹的路徑索引， 并通過路徑索引來加速x ml 結構查詢的計算; 另一種方法是對 x m l 文檔樹中的結點進行編碼， 即 給x m l 文檔樹中的 每一 個結點 ( 或邊) 賦予一 個唯一的編碼， 以便能夠通過編碼直接判斷結點之間的結構關系， 而不是對原x m l文檔樹進行遍歷。也就是說，通過編碼將x m l 結構查詢的計算轉化為結構 連接的計算。 第三節(jié) 現(xiàn)有編碼方案的分類 對于x ml的編碼方案， 就文檔樹中是否有結點插入的情況來分， 可以分為 靜態(tài)編碼和動態(tài)編碼兩大類。 但按照其設計思想和編碼特點來分，又可以分為 三大類: 基于區(qū)間的編碼方案、 基于路徑的編碼方案和基于數(shù)學計算的編碼方 案。下面將分類來闡述各類編碼方案。 2 .3 . 1 基于區(qū)間的編碼方案 基于區(qū)間 ( re g i o n - b a s e d ) 的 編碼方案利用x m l 文檔有序的 特點， 根據(jù)一個元 素結點在原x ml 文檔中字典順序的位置給每一個元素結點賦予一個編碼。 第一 種區(qū)間 編碼方 案是d i e t z 編碼【 12 1 。 它的 編碼規(guī) 則 為: 樹t 中 的 每一 個結 點都被賦予 一個先 序遍歷號 和一 個后序遍歷號的 二元 組 p r e , p o s y 。由 于樹中 的一 個祖先結點u 在先序遍歷( 后序遍歷) 中必然出現(xiàn)在它的后裔結點v 之前( 之 后) 。 因 此， 結點u 和v 是 祖 先 / 后 裔關系， 當 且僅當p r e ( u ) p r e ( v ) p o s t ( v ) p o s t ( u ) o 有一種推廣改進， 是在x m l 文檔樹中的每一個結點再賦予一個值p ar ， 表示該 結點的 雙親結點的 先 序遍歷 序 號p re ， 以 反映結點 之間 的 雙 親 / 孩子關系。 區(qū)間 編 碼舉例見圖2 . 1 所示。 第 二 種區(qū) 間 編 碼是q . l i 和b .m o o n 編碼 113 。 它 的 編 碼 規(guī) 則 為 : x m l 文 檔 樹t中的每一個結點都被賦予一個二元組 ，其中，o r d e r 為結點的 擴展先序遍歷序號， 它的取值是非連續(xù)的， 為結點的插入預留序號空間: s i z e 為 結點的后裔范圍。對于該編碼方案，樹結點的 必須滿足如下兩點: 第二章 n a t i v e x m l 數(shù)據(jù)庫編 碼方案 概述 ( 1 ) 對于樹中的 結點y 和它的雙親結點x ， 有。 r d e r ( x ) o r d e r ( y ) o r d e r ( y 卜 s i z e 切- o r d 州x ) + s i z e ( x ) o ( 2 ) 對于 樹中 的兄弟結點x 和y ， 如果在先序遍歷中 結點y 是結點x 的 右兄 弟，則。 r d e r ( x ) + s i z e ( x ) o r d e r ( y ) o 這種編碼方案可以 進一步改 進為 增加一個 層信息， 它相比d i e t z 編碼， 能 更 好支持文檔的修改。 編碼舉例見圖2 . 1 所示。 第 三 種 區(qū) 間 編 碼 是山 a n g 編 碼 141 . 它 的 編 碼 規(guī) 則 為 : x m l 文 檔 樹 中的 每 一 個結點 被賦予一個 二元組 。 對樹中 的所 有結點進 行先序遍歷， 每一 個結點在遍歷時 分別被訪問 兩次并產生兩個序號。 一次是在遍歷該結點的所有 后 裔結 點 前 訪 問 該 結 點 ， 并 產 生 該 結 點的 序號b e g in ; 另 一 次 是 在遍 歷完 該 結 點 的所有后裔結點之后再一次訪問該結點，并產生該結點的另一個序號 e n d 。編碼 舉例見圖2 . 1 所示。 第四 種區(qū)間 編碼稱為w a n 編 碼 15 l ， 它的編碼 規(guī)則 為: x m l 文檔樹種的每一 個結點 被賦予一個二元組 ， 其中， o r d 。為 結點的 擴展先序遍 歷序號， 它與l i - m o o n 編碼的 含義相同; m a x o r d e r 為 結點的 后裔中 最大的擴展 先序遍歷序號，即以該結點為根結點的子樹中 最右下角結點的 擴展先序遍歷序 號。wa i ， 編碼舉例見圖2 . 1 所示。 圖2 . 1 x m l數(shù)據(jù)的各種 編碼方案 1 0 第二章 n a t i v e x 6 1 l 數(shù)據(jù)庫編碼方案概述 2 . 3 .2 基于路徑的編碼方案 基于路徑( p a t h - b a s e d ) 的編碼方案是利用x m l文檔的 嵌套特點， 根據(jù)x m l 文檔的嵌套結構，給從文檔根結點開始所能達到的每個路徑和元素結點賦予一 個編碼。 第一種路徑編碼是n . w ir t h 提出的位向 量編碼11 6 1 : 樹t 中 每個結點被編碼 為一個n 位向量， 其中n 是樹中的結點數(shù)量， 在某個位置i 上的一個 1 ” 位唯 一地表示第i 個結 點; 并且在一 個自 頂向 下 ( 或自 底向 上) 的 編 碼方 案中， 每 一個 結點 繼承標識它祖先 ( 或后裔) 的 所有位上的“ i n . 位向 量編碼舉例說明見圖2 . 1 0 第 二 種 路 徑 編 碼 是 前 綴 編 碼 ， 前 綴 編 碼 也 可 以 稱 為d e w e y 編 碼 【1 71 。 前 綴 編 碼的規(guī)則是直接將一個結點的雙親結點的編碼作為該結點編碼的前綴。例如， 設樹t 的 一 個結點u 的 前 綴編碼 位c ( u ) ， 則結點u 的 孩子結點v 的 前綴編碼c ( v ) = c ( u ) .n ， 這里n 是結點v 在結點u 的所有孩子結點中的 序號。 對于前綴編碼， 要 判斷一個結點v 是否是另一個結點u 的后裔， 只需判斷字符串c ( u ) 是否是字符串 c ( v ) 的前綴。 增加了 字典有序的前綴編碼的一個重要性質， 是它們的字典有序:以結點r 為根的 子 樹中 的 任 意 一個結點u ， 它的前 綴編碼c ( u ) 大于( 小于 ) 左兄弟 子樹( 右兄 弟子樹) 中 所有結點的前 綴編碼。因此，字典 有序的前綴編碼不僅能 夠有效地支 持包 含關系的 計算， 而且 還能 夠有效支持文 檔 位置關 系的計 算。 d e w e y編碼舉 例說明見圖2 . 1 所示。 o r d p a t h 編 碼 方 案 1 18 1在 基 于d e w e y 編 碼 方 案 的 基 礎上 做 了 對 動 態(tài) 更 新 的 改進，以 1 . 5 .9 .9 .5 ”為例: ( 1 ) o r d p a t h是 一 個分級 編 碼方案， 每 個 分 量 值用逗點“ ” 隔開， 它由 多 個分量值構成。 ( 2 ) 文檔根結點總是以勺”開始，子結點 首先從父結點獲得o r d p a t h值， 然后追加一個逗點后，再增加一個由左到右的順序分量值。 ( 3 ) 在d o m樹 初始 化時， o r d p a t h結點 分量 值以 正 奇數(shù)作為 分量值， 它的 個數(shù)表示該結點在樹中的深度。 ( 4 ) 當 在樹的最右邊增加一個新的結點時， 理論上表示兄弟結點順序增加的 分量值沒有限制。當在樹的最左邊增加一個新的結點時，以一個順序減少的方 式完成，可以使用負數(shù)。 第二 章 n a t i v e x 6 1 l 數(shù)據(jù)庫編碼方案概述 ( 5 ) 當 在兩 個兄弟結 點中 插 入一個新結 點時， 如果沒有 可 用的 表 示順序的分 量值時，需要使用 “ 脫字符”的技術，此時需要先插入一個偶數(shù)值，然后再追 加一個奇數(shù)分量值。 注意，偶數(shù)分量值對結點在樹中的深度并沒有貢獻。 d l n 編 碼 方 案 19 1在d e w e y 前 綴 編 碼 方 案 的 基 礎 上 ， 做 了 與 上 述 功 能 雷 同 的 改進，它使用了增加子層分隔符和子分量值的概念.這兩種方案都沒有考慮到 在增加新結點時預留 一定編碼空間的能力， 在特殊情況下， 編碼長度會迅速增 加。 x t c 系 統(tǒng)中 的 動 態(tài) 編 碼 方 案 120)， 吸 收 上d e w e y 編 碼 方 案 優(yōu)點 的 同 時 ， 還 增 加了 一個平均距離參數(shù)( 圖2 .2 中 距離參數(shù)為4 ) ， 通過預測來將來可能插入的結 點附近預留一定的結點編碼空間，從而一定程度上減少了前綴編碼的平均長度. a t t r i b u t e t e x t n o d e t 9 5.5南 1.5.5.9. it o巳 圖2 . 2 x t c系統(tǒng)中的動態(tài)編碼舉例 這三種方案不僅具有基于路徑編碼方案的前綴特點， 而且又具備基于區(qū)間 編碼的文檔位置信息的特點，同時具備了適合更新操作的功能。但是在編碼方 案的最大長度或平均長度方案還有待優(yōu)化，在結點的重構和次序敏感性查詢上 還需要進一步加強。 第 二章 n ati v e 7 d 11 數(shù)據(jù)庫編 碼方案概述 2 . 3 . 3 基于數(shù)學計算的編碼方案 基于數(shù)學計算編碼方案 包括完全完全樹編碼， 素數(shù)編碼， b i r d編碼等。 這 種編碼方案利用了d o m樹的 深度優(yōu)先遍歷對每個結點 進行遍歷， 采取自 底向上 或者 自頂向下的方式進行結點的編碼，然后利用某個數(shù)學理論或者方法約束計 算得到以后遍歷到的結點的編碼。 完全樹編碼方案的核心設計思 想是:先 構造一顆完 全k 叉 樹， 然后將x m i . 文檔轉換為k叉 樹后嵌入到這顆完全k 叉 樹中， 以 結點 在完全k 叉樹中的前序( 后 序) 遍歷號作為其編碼。 文獻 2 1 - 2 3 1 提出的 都是完 全樹編碼方案及其 變型。 素數(shù)編碼標識方案 24 1 基于素數(shù)的 特性， 對x m i . 文檔樹進行遍歷時， 對每個 結點賦予一個素數(shù)。 這個編碼方案確保每一個編碼能僅僅被它自 己的祖先結點 整除。結點無序的 素數(shù)編碼標識 方案有自 頂向下和自 底向上兩種方式。 下面將 以自 頂向 下的方式為例。 無序素數(shù)編碼標識方案對每個結點的編碼為父結點編 碼和自身編碼兩部分編碼的乘積， 根結點編碼為1 = 1 x1 ， 它的左結點則編碼為: 1 ( 父結點 編碼) x 2 ( 自 編碼片 。 如圖2 . 3 所示。 (3 票 3 ) 圖2 .3 自 頂向下基 本素數(shù)編碼方案 這種無序素數(shù)編碼標識方案 在樹的深度加 深時， 編碼的整數(shù) 值上升的極 快。 而且，不 能很 好的 處理 三種次 序敏感性 (p r e c e d in g - s ib lin g if o llo w in g - s ib lin g , p o s i ti o n = n , p r e c e d i n g / f o l l o w i n g ) 的 查詢。 為了 解決 次序敏感性的查詢問題，該 文提出一種結點有序的素數(shù)編碼標識方案， 該方法充分利用了中國 剩余定理12 3 1 來解決素數(shù) 編碼方案中 的次序問 題，也以 較小的 代價來處理動態(tài)更新問題。 先介紹中國 剩余定理: 設函數(shù)g c d ( m , ,m 2 , . . . m k ) 表示為 一組整數(shù)m ( , m 2 , . . . m k 的最大公約數(shù);m= m i , m 2 , . . . m k l 和 n = n ( , n 2 , . . . n k 表示為兩個整數(shù)序列。如果 g c d ( m , , m 2 , . . . m k ) = 1 ， 則聯(lián)立同余數(shù)s c ( m, n ) = x o 第二章 n a t i v e 1 m l 數(shù)據(jù) 庫編碼方案概述 聯(lián)立同余式: m o d m , 二 n i m o d m 2 =氣 x m o d m , = a t k c = i z m i i =1 k x = e ( c / m i) * r4 * 4, ( m ) ) m o d c i=1 甘幾va c 和x的 公 式 如 上 所示 ， x 值 在。 與c 之 間 。 該 文 獻 中小( m i) 是歐拉商 函數(shù)，它的復雜度是 0 ( n ) 。它在素數(shù)編碼中的應用舉例如下圖 2 . 4 所示。 . ， 腸日巨崢 翻 .側 卜甘 圖2 . 4