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