（計算機應用技術專業(yè)論文）一種改進的xml數(shù)據(jù)管理方案.pdf

蘇州大學學位論文使用授權聲明 本人完全了解蘇州大學關于收集 保存和使用學位論文的規(guī)定 即 學位論文著作權歸屬蘇州大學 本學位論文電子文檔的內容和紙 質論文的內容相一致 蘇州大學有權向國家圖書館 中國社科院文獻 信息情報中心 中國科學技術信息研究所 含萬方數(shù)據(jù)電子出版社 中國學術期刊 光盤版 電子雜志社送交本學位論文的復印件和電子 文檔 允許論文被查閱和借閱 可以采用影印 縮印或其他復制手段 保存和匯編學位論文 可以將學位論文的全部或部分內容編入有關數(shù) 據(jù)庫進行檢索 涉密論文口 本學位論文屬在 年二月解密后適用本規(guī)定 非涉密論文口 論文作者簽名 墊至焦 日 期 旦 旦 z 導師簽名 種改進的x m l 數(shù)據(jù)管理方案摘要 一種改進的x m l 數(shù)據(jù)管理方案 摘要 隨著互聯(lián)網(wǎng)技術的飛速發(fā)展 基于網(wǎng)絡的諸多服務如電子商務 電子圖書等在 生活中起著越來越重要的作用 如何利用i n t e m e t 上的大量信息成為函待解決的問 題 x m l 以其簡單 可擴展和跨平臺等諸多優(yōu)點 己經(jīng)成為數(shù)據(jù)表示 數(shù)據(jù)存儲和 數(shù)據(jù)交互的事實標準 如何有效地管理x m l 數(shù)據(jù) 如對x m l 數(shù)據(jù)進行存儲 查詢 更新 發(fā)布等已成為當今數(shù)據(jù)庫領域中一個重要的研究課題 本文在分析了相關研 究現(xiàn)狀的基礎上 開展了以下的研究 首先 根據(jù)當前存儲方案不能有效支持文檔更新的現(xiàn)狀 本文提出了一種具有 更新功能的x m l 存儲方案x s c 通過設計若干個關系表來存儲x m l 文檔樹中的結點 信息和結構信息 無論x m l 文檔是否具有d t d 都可以將x m l 文檔映射到存儲模式 中 當涉及插入 刪除結點操作時 只需要對其余的結點進行少量的重新編碼就可 以正確地實現(xiàn)x m l 文檔的發(fā)布 查詢 其次 針對目前小枝模式查詢效率不高的特點 本文提出了一種非歸并的小 枝模式匹配算法t w i g w m t w i g w m 算法利用索引將x m l 文檔中的結點組織成標 簽流 使用部分棧和鏈表的數(shù)據(jù)結構實現(xiàn)查詢 與許多小枝模式查詢算法不同 t w i g w m 算法的執(zhí)行是一個輸出整體結果的非歸并過程 最后 本文在o f f i c e 數(shù)據(jù)源上構建了一個x m l 數(shù)據(jù)管理應用的實例 實現(xiàn)了上述 提出的x m l 數(shù)據(jù)管理方案 本實例通過友好的用戶界面 可以實現(xiàn)任何以數(shù)據(jù)為中 心的x m l 文檔的存儲 更新和查詢 本文對x m l 數(shù)據(jù)管理技術的研究具有一定的現(xiàn)實意義 它不儀提出了對x m l 文 檔有效更新的存儲方案 還進一步研究了在x m l 查詢中小枝模式非歸并匹配的問 題 可以提高x m l 查詢的效率 另外 本文的實例驗證也對相關的實際應用具有一 定的參考價值 關鍵詞 x m l 存儲映射 動態(tài)更新 小枝模式 查詢算法 作者 趙圣猛 指導教師 錢培德 a n i m p r o v e ds c h e m af o rx m l d a t am a n a g e m e n t a b s t r a c t m a n yw e b b a s e ds e r v i c e ss u c ha se b u s i n e s sa r ep l a y i n ga ni n c r e a s i n g l yi m p o r t a n tr o l e i nl i f e h o wt ou s et h el a r g ea m o u n to fi n f o r m a t i o nh a sb e c o m et h ep r o b l e mw h i c hn e e dt o b es o l v e du r g e n t l y x m lh a sb e c o m ean e ws t a n d a r df o rd a t a r e p r e s e n t a t i o n d a t ae x c h a n g e o nt h ei n t e r n e t k n o w nf o ri t ss i m p l i c i t y e x t e n s i b i l i t ya n dn u m e r o u so t h e rb e n e f i t s h o wt o e f f e c t i v e l ym a n a g ex m ld a t ah a sb e c o m ea l li m p o r t a n tr e s e a r c ht o p i ci nd a t a b a s ef i e l d s u c h a sx m l s t o r a g e x m lq u e r ya n ds oo n i nt h i sp a p e r t h em a i nr e s e a r c hw o r ka sf o l l o w s f i r s t l y t h i sp a p e rp r o v i d e sas t o r a g es c h e m an a m e dx s c w h i c he f f e c t i v e l ys u p p o r t s x m l u p d a t e t h r o u g hd e s i g n i n gan u m b e ro ft a b l e s x s cs t o r e sn o d ei n f o r m a t i o na n d s t r u c t u r a li n f o r m a t i o n r e g a r d l e s so fw h e t h e rx m ld o c u m e n th a sd t d t h ex m l d o c u m e n tc a nb em a p p e di n t ox s c w h e nc o m i n gt oi n s e r tn o d e sa n dd e l e t en o d e s t h ex m l d o c u m e n tc a nb ec o r r e c t l yp u b l i s h e dw i t h o u tm u c h r e e n c o d i n go nt h er e m a i n i n gn o d e s s e c o n d l y i nt h ec a s eo fi n e f f i c i e n tt w i gp a t t e r nq u e r y t h ep a p e rp r o p o s e sa na l g o r i t h m o ft w i gp a t t e r nq u e r yn a m e dt w i g w m t w i g w m o r g a n i z e sn o d e si n t ol a b e ls t r e a mu s i n g i n d e x a n da c h i e v e sq u e r y i n gw i t ht h ed a t as t r u c t u r eo fs t a c ka n dl i n k e dl i s t c o m p a r e d w i t ho t h e rt w i gq u e r ya l g o r i t h m s t h ee x e c u t i o no ft w i g w ma l g o r i t h mi st h en o n m e r g i n g p r o c e s sw h i c hp r o v i d e st h eo v e r a l lr e s u l t s f i n a l l y b a s e do nt h ed a t ao fo f f i c ea p p l i c a t i o n t h i sp a p e rb u i l d sa ne x p e r i m e n t a ls y s t e m w h i c ha d o p mt h ea b o v ep r o p o s e dx m ld a t am a n a g e m e n ts c h e m a t h r o u g hf r i e n d l y u s e ri n t e r f a c e t h es y s t e mc a n m a n a g ea n yd a t a c e n t r i cx m l d o c u m e n t s t h ew o r ko nx m ld a t am a n a g e m e n th a sc e r t a i np r a c t i c a ls i g n i f i c a n c e o no n eh a n d w h e ns t o r i n gx m ld o c u m e n t s i ts o l v e st h ei s s u eo fu p d a t i n gx m ld o c u m e n t s o nt h e o t h e rh a n d t h i sp a p e rs t u d i e st h ea l g o r i t h mo ft w i gp a t t e r nq u e r yw i t h o u tm e r g i n g w h i c h i m p r o v e st h ee f f i c i e n c yo fx m lq u e r y b e s i d e s e x p e r i m e n t a ls y s t e mp r o v i d e ss o m er e f e r e n c ef o rr e l a t i v er e s e a r c h e s k e y w o r d s x m l s t o r a g em a p p i n g d y n a m i cu p d a t e t w i gp a t t e r n q u e r ya l g o r i t h m i i w r i t t e nb yz h a os h e n g m e n g s u p e r v i s e db yq i a np e i d e 第一章 1 1 1 2 1 3 1 4 1 5 第二章 2 1 2 2 2 3 2 4 2 5 2 6 目錄 緒論 課題背景 課題研究現(xiàn)狀 課題研究內容 課題研究意義 文章組織結構 x m l 數(shù)據(jù)管理概述 x m l 數(shù)據(jù)模型 x m l 查詢語言 x m l 文檔編碼方案 2 3 1基于區(qū)間的編碼 2 3 2 基于路徑的編碼 2 3 3其它編碼 x m l 數(shù)據(jù)索引技術 2 4 1結構概要類索引 2 4 2 結點記錄類索引 x m l 數(shù)據(jù)存儲映射 2 5 1 模型映射方案 2 5 2 結構映射方案 x m l 結構連接算法 2 6 1包含關系的結構連接 2 6 2 小枝模式的結構連接 第三章數(shù)據(jù)管理方案設計 3 1問題提出 3 2 設計目標 1 l 2 4 5 5 7 7 9 o 0 2 2 2 3 4 5 5 6 7 8 9 1 l 3 1 2 4 5 5 7 7 9 m m 屹 掄 掄 b m 埒 垮 m 掩 挎 扛 扒 乃 3 模型方案 2 4 4 小枝查詢方案 2 5 章可支持更新的x m l 存儲方案x s c 2 7 1引言 2 7 4 2x s c 映射實現(xiàn) 4 2 1x r e l 映射思想 4 2 2x s c 映射策略 4 2 3x s c 映射算法 4 3x m l 文檔重組 4 4x m l 查詢處理 4 5 動態(tài)更新x m l 文檔 4 6 實驗分析 4 6 1x m l 存儲性能分析 4 6 2x m l 查詢性能分析 2 8 2 8 2 8 3 0 3 2 3 4 3 5 3 6 3 6 3 7 第五章基于非歸并的小枝模式查詢方案t w i g w m 3 9 5 1 引言 3 9 5 2 相關概念及說明 4 0 5 2 1 結點編碼 4 0 5 2 2 相關定義 4 1 5 3 查詢匹配算法t w i g w m 4 3 5 3 1數(shù)據(jù)結構及說明 4 3 5 3 2 算法思想 4 4 5 3 3具體算法描述 4 6 5 4 算法分析 5 0 5 5 實驗分析 5 1 5 5 1實驗環(huán)境 5 1 5 5 2 實驗結果 5 2 第六章 6 1 6 2 第七章 7 1 7 2 參考文 攻讀碩 致謝 一種改進的x m l 數(shù)據(jù)管理方案第一章緒論 第一章緒論 1 1 課題背景 隨著互聯(lián)網(wǎng)技術的發(fā)展 特別是w e b 技術飛速發(fā)展 其豐富的資源給人們的生 活帶來了極大的便利 特別是應運而生的h t m l h y p e rt e x tm a r k u pl a n g u a g e 超 文本標記語言 以其簡單易學 靈活通用的特性 使人們發(fā)布 檢索 交流信息 變得非常簡單 從而使w e b 成了最大的環(huán)球信息資源庫 然而基于網(wǎng)絡的諸多服務 和應用如電子商務 電子圖書等使w e b 數(shù)據(jù)變得更加復雜和多樣化 從而使得作 為w e b 使用最廣的h t m l 語言的局限性越發(fā)明顯 由于i n t e r n e t 上的數(shù)據(jù)多以無結構的 形式出現(xiàn) x m l e x t e n s i b l em a r k u pl a n g u a g e 可擴展標記語言 1 1 以其簡單 可 擴展和跨平臺等諸多優(yōu)點 己經(jīng)成為數(shù)據(jù)表示 數(shù)據(jù)存儲和數(shù)據(jù)交互的事實上的標 準 x m l 與h t m l 相比具有許多優(yōu)點 1 x m l 簡單 自我描述且易于解析 x m l 對數(shù)據(jù)的語義描述和數(shù)據(jù)內容本身都 包含在x m l 文檔中 一個應用可以按照各種方式解析 過濾 重構x m l 文檔 2 h t m l 中的標記是固定的 不能擴展 而x m l 中的標記是由用戶定義的 可 以任意地擴展 x m l 的嵌套結構可以表示現(xiàn)實世界中各種復雜的對象 各種格式的 數(shù)據(jù)都可以比較容易地轉化為x m l 數(shù)據(jù) 3 咖 中的標記表示數(shù)據(jù)的顯示格式 沒有任何語義 而x m l 的標記則明確 指出了數(shù)據(jù)的含義 使得細粒度的x m l 數(shù)據(jù)處理成為可能 4 x m l 實現(xiàn)了內容和表現(xiàn)二者的分離 文檔類型定義d t d d o c u m e n tt y p e d e f i n i t i o n 描述了文檔中元素和子元素間的嵌套結構 不同的用戶可以通過x s l 按不 同的顯示方式顯示全部或部分的文檔內容 5 x m l 具有開放的國際化標準 x m l 支持文檔對象模型標準 可擴展類型語言 標準 可擴展鏈接語言標準和x m l 指針語言標準 使用x m l 數(shù)據(jù)可以在不同類型的 計算機系統(tǒng)問交換信息 由于x m l 同h t m l 兼容 且與平臺無關 同時又是一種真正的擴展語言 受 到了業(yè)界的廣泛關注 比如微軟 i b m o r a c l e 等參加了x m l 各項標準的制定 微 軟的w i n d o w s o f f i c e 都使用x m l 文件格式 i e 6 0 i e 7 0 已經(jīng)全面實現(xiàn)了對x m l 的 是兩個重要方面 受到了廣泛的關注 目前國內對x m l 數(shù)據(jù)管理的研究尚處于探索階段 特別是x m l 查詢方面 復 旦大學的v x m l r 系統(tǒng) 2 把文檔存儲到關系數(shù)據(jù)庫中 v x m l r 先把x m l 模式映射 為關系模式 然后把文檔數(shù)據(jù)存入關系數(shù)據(jù)庫中 查詢時 先把x m l 查詢語言重 寫為s q l 語句 最后把查詢結果重構為文檔 中國人民大學孟小峰教授等研究開發(fā) 的o r i e n t x 系統(tǒng) 3 是國內第一個純x m l 數(shù)據(jù)庫系統(tǒng) 它的記錄級別是文檔級的 按 2 一種改進的x m l 數(shù)據(jù)管理方案 第 章緒論 物理塊劃分 使記錄之問聯(lián)系的指針得以減少 提高了存儲效率 o r i e n t x 系統(tǒng) 4 將語義相近的記錄盡量按聚集存儲 這是一種按邏輯意義存儲策略 判斷語義相近 的方法是根據(jù)記錄類型是否相同進行的 在x m l 查詢處理方面 王靜等 5 提出了以 目標結點為導向對路徑表達式進行查詢處理 該方法利用擴展基本操作來減少連接 操作的數(shù)目 萬常選等 6 將編碼方案 逆序列表和路徑索引的思想相結合 提出了 一種改進的索引結構 最多只需對參與連接的兩個列表分別進行一次掃描 即可實 現(xiàn)查詢處理 國外有不少研究機構在數(shù)據(jù)管理方面做了大量工作 如x m l 數(shù)據(jù)的高效存 儲 索引機制 查詢處理和優(yōu)化等 德國s o f t w a r ea g 軟件公司的t a m i n o 7 是第一 個商用的純x m l 數(shù)據(jù)庫系統(tǒng) 它的主要創(chuàng)新在于索引結構和接口 密歇根大學 的t i m b e r 8 是一種采用面向對象數(shù)據(jù)庫s h o r e 來對x m l 進行存儲的x m l 數(shù)據(jù)庫 它 借用了s h o r e 系統(tǒng)中良好的存儲管理 并發(fā)機制等 由于其存儲粒度是結點級的 因 此 在x m l 文檔重組時可以避免冗余的轉換 在具體存儲方面 已提出的x r e l 映射 9 1 x p a r e n t 映射 l o 等屬于模型映射 模 型映射方法對某些應用來說提供了一定的靈活性 可以實現(xiàn)異構系統(tǒng)間數(shù)據(jù)的無 縫集成 而不需要考慮文檔的模式信息 即使源文檔的結構發(fā)生了一定的變化也 不會影響系統(tǒng)問數(shù)據(jù)的交換 然而 這種靈活性也是需要付出一定代價的 因為 在模型映射方法中 每個數(shù)據(jù)項都要重復其模式信息 因此增加了系統(tǒng)的磁盤開 銷 d t d 方法 1l s t o r e d 方法 1 2 和p s c h e m a 方法 1 3 屬于結構映射 它們需要 將x m l 模式 或d t d 映射為關系模式 關系模式用來表示目標x m l 文檔的邏輯結 構 因此它是x m l 模式 或d t d 相關的 從x m l 文檔的d t d 或s c h e m a 推斷x m l 元 素應該怎樣映射到關系中 這種方法能夠利用關系數(shù)據(jù)庫的特性 如查詢優(yōu)化和并 發(fā)性控制等 文獻 1 4 1 5 中提出的方法屬于約束映射方法 在存儲x m l 文檔時 考 慮x m l 模式中的語義約束 如 鍵 函數(shù)依賴等 在此基礎上推導出的關系模式可 以進一步保持語義信息 x m l 查詢處理方面 集中關注如何對路徑表達式進行匹配 已提出的方法主要 有兩種 第一種方法是把一個復雜的路徑表達式分解成幾個簡單路徑表達式 而簡 單路徑表達式的計算采用逐步結構連接法 這樣對x m l 文檔的結構查詢通常被轉 化為兩個結點列表之間的包含關系或文檔位置關系的結構連接操作 目前已提出的 結構連接算法有e e e a j o i n 1 6 m p m g j n 1 7 等 但是 這種計算方法會產(chǎn)生大 量的中間結果 從而影響了查詢的效率 第二種方法是把一個路徑表達式表示成一 3 第一章緒論一種改進的x m l 數(shù)據(jù)管理方案 個小枝模式t w i g 然后通過小枝模式匹配的方法來計算路徑表達式的值 在小枝模 式匹配方法方面 具有代表性的算法有t w i g s t a c k 1 8 t j f a s t 1 9 1 等 它們只需掃 描一遍輸入結點列表就可輸出匹配結果 此類算法對只包含祖先后代邊的小枝模式 查詢可以保證為最優(yōu)的 即所有的中間匹配結果都是可歸并連接的 但是在包含 父子邊的小枝模式查詢方面 這些算法并不是最優(yōu)的 因為它們會產(chǎn)生許多無用 的中間結果路徑 為了解決包含父子邊的小枝模式查詢的效率問題 目前已提出 t t w i 9 2 s t a c k 2 0 1 t w i g l i s t 2 1 算法 其分別采用層次棧和隊列的結構而不需要歸 并 因此性能優(yōu)于前述算法 但是他們需要遍歷文檔樹中的每個結點 并且算法也 較復雜 文獻 2 2 2 3 也針對t w i g 查詢進行了相關地研究 1 3 課題研究內容 x m l 作為數(shù)據(jù)交換的國際標準 已經(jīng)貫穿在i n t e m e t 應用的各個領域之中 從而 帶來了大量的x m l 格式的數(shù)據(jù) 如何存儲和查詢x m l 數(shù)據(jù)是一個重要的研究課題 本課題以x m l 數(shù)據(jù)管理為研究的切入點 在提出一種編碼方案的基礎上研 究x m l 數(shù)據(jù)存儲 此存儲方案考慮文檔更新情況 當在x m l 文檔中插入 刪除結點 時能及時地反映給用戶 在x m l 查詢方面 主要研究小枝模式匹配算法 利用索引 確定哪些文檔結點不滿足輸出要求 事先將其舍棄 用非歸并的思想輸出最終結果 具體研究步驟如下 1 提出一種x m l 編碼方案 正確的編碼方案是x m l 數(shù)據(jù)管理的基礎 已存在的x m l 編碼主要有區(qū)間編碼和 路徑串編碼 但在支持x m l 文檔更新的情況下并不理想 本課題將先序編號與路徑 串相結合對文檔樹中的結點進行編碼 并且在后期查詢方面將編碼中的路徑串轉換 成數(shù)字串以利于模式匹配 2 具有更新功能的x m l 存儲方案 x r e l 映射屬于結點模型映射 它通過設計若干個關系來存儲x m l 文檔樹中的結 點信息和結構信息 與x p a t h 標準緊密結合 能夠對基于x p a t h 的查詢給予相當好的 性能支持 但是它的p a t h 信息具有很大的冗余 修改一個結點的名稱都需要相當復 雜的操作 本課題借鑒t x r e l 方法的部分思想并提出了一種基于不同結構的x m l 文 檔存儲映射 無論x m l 文檔是否具有d t d 都可以將x m l 文檔映射到存儲模式中 當涉及插入 刪除結點操作時 只需要對其余的結點進行少量的重新編碼 就可以 4 一種改進的x m l 數(shù)據(jù)管理方案第一章緒論 正確的實現(xiàn)x m l 文檔的發(fā)布 查詢 3 非歸并的小枝模式查詢方案 小枝模式查詢是x m l 查詢中重要的方面 已有的算法女l l t w i g s t a c k 和t j f a s t 算法 等被提出 但是他們都是基于歸并的 不能避免大量的不必要的路徑歸并 本文提 出了一種新的算法 利用索引將x m l 文檔中的結點組織成標簽流 使用部分棧和鏈 表的數(shù)據(jù)結構實現(xiàn)查詢 在將元素結點進入鏈表之前先判斷其是否對整個路徑解有 貢獻 若有貢獻則進入鏈表 否則丟棄 整個過程是不斷輸出結果的非歸并過程 本文將上述的管理方案合成一個整體的流程 構建了一個x m l 數(shù)據(jù)管理 在o f f i c e 數(shù)據(jù)源上的應用實例 1 4 課題研究意義 x m l 為w e b 提供了一致的數(shù)據(jù)模型和描述語言 使得從語法上規(guī)范化地表 示w e b 數(shù)據(jù)成為可能 通過研究x m l 數(shù)據(jù)的管理技術 可以為基于w e b 的數(shù)據(jù)管理 提供新的途徑和方法 本課題主要研究了x m l 數(shù)據(jù)管理的相關技術 并改進了其中的部分算法 盡管 這些算法并不一定是最優(yōu)算法 還有待于進一步的研究與完善 但是本課題所做的 工作還是具有一定的現(xiàn)實意義 體現(xiàn)在如下方面 1 本文在對x m l 存儲方案做了深入研究的基礎上分析了其優(yōu)缺點 針對目前存 儲映射中更新的難題 設計了一種編碼方案并實現(xiàn)了x m l 模式的映射 經(jīng)實驗驗證 該方案具有跨平臺性 給x m l 數(shù)據(jù)管理中映射方面的研究提供了借鑒價值 2 本文在小枝模式查詢方面提出了一種新的匹配算法 實驗結果比較表明 此 算法在時間和空間方面有較好的效率 對部分x m l 查詢算法的改進具有參考價值 3 本課題將x m l 數(shù)據(jù)管理的理論運用于實際 在o f f i c e 應用方面進行了有益的 嘗試 并取得了較為滿意的結果 促進了x m l 數(shù)據(jù)管理的研究 綜上所述 課題研究的內容對于x m l 數(shù)據(jù)管理具有一定的現(xiàn)實意義和參考價值 對x m l 的進一步應用有一定的推動作用 1 5 文章組織結構 全文的組織如下 5 第一章緒論 一種改進的x m l 數(shù)據(jù)管理方案 第一章簡要介紹了課題提出的背景 課題的研究內容 課題的研究現(xiàn)狀和課題 的研究意義 第二章介紹了x m l 數(shù)據(jù)管理的相關知識 重點介紹了x m l 數(shù)據(jù)模型 查詢語 言 x m l 的常用編碼 x m l 索引 存儲映射方案 查詢中的結構連接算法 第三章介紹了數(shù)據(jù)管理方案的設計 其中對方案設計的由來和目標進行了闡述 同時還對存儲方案和查詢方案進行了介紹 第四章針對目前x m l 存儲方案不能有效地支持更新 提出了一種映射方案x s c 并介紹了如何用x s c 方案來更新和發(fā)布x m l 最后將x s c 方案與別的方案進行了性 能上的對比 第五章介紹了小枝模式查詢的處理過程 分析了當前小枝模式匹配算法的不足 在此基礎上提出了一種非歸并的小枝模式查詢算法t w i g w m 并將t w i g w m 算法與幾 種常用算法進行了比較 第六章介紹了此文提出的x m l 數(shù)據(jù)管理方案在o f f i c e 數(shù)據(jù)源上的應用實例 第七章對所做的工作進行總結 并對未來工作進行展望 6 一種改進的x m l 數(shù)據(jù)管理方案 第二章x m l 數(shù)據(jù)管理概述 第二章x m l 數(shù)據(jù)管理概述 本章將介紹x m l 數(shù)據(jù)管理的相關知識 x m l 數(shù)據(jù)模型 x m l 查詢語言 x m l 編 碼技術 x m l 索引技術 x m l 存儲映射技術和x m l 查詢技術 x m l 數(shù)據(jù)模型 和x m l 查詢語言是x m l 數(shù)據(jù)管理知識中的基礎 不同的編碼方案對x m l 存儲 查詢有很大的影響 由于索引的設計主要是為了提高查詢效率 因此 設計索引 時的主要考慮岡素應該是查詢 底層的存儲表示形式對上層的查詢和優(yōu)化有著重 要的影響 如何有效地存儲x m l 文檔已經(jīng)是一個重要的問題 關于查詢方面 目 前的x m l 查詢執(zhí)行策略主要有兩種 基于導航的x m l 查詢執(zhí)行策略和基于連接 的x m l 查詢執(zhí)行策略 由于基于導航的查詢策略重點在于結構概要類索引的設計 因此 本文重點介紹基于連接的查詢策略 下面進行詳細介紹 2 1x m l 數(shù)據(jù)模型 對x m l 數(shù)據(jù)進行有效地建模 正確 完全地反映x m l 數(shù)據(jù)的固有特征是 對x m l 數(shù)據(jù)進行有效管理的基礎 當前的研究工作大都建立于圖模型或者樹模 型之上 圖模型將x m l 數(shù)據(jù)看作一個復雜的圖狀結構 x m l 數(shù)據(jù)中元素之間 元素 和屬性之間的聯(lián)系在圖模型中被抽象成有向邊 樹模型將x m l 數(shù)據(jù)看作一棵有向的 標簽樹 x m l 數(shù)據(jù)上元素之間 元素和屬性之間的聯(lián)系被抽象成樹上的有向邊 這 兩種模型都可以形象地表示數(shù)據(jù) 其中 樹模型是描述x m l 數(shù)據(jù)最常使用的 因此 本文的研究也是基于該模型 圖2 1 表示一個x m l 文檔實例及其對應的樹模型 在樹 模型中 結點表示文檔元素 屬性和文本數(shù)據(jù)等 邊表示兩個結點之間的父子關系 一個結點的路徑是從文檔根結點開始到該結點所經(jīng)歷的標簽序列 標簽之間用 分隔 例如在圖2 1 中 h e i g h t 結點的路徑是 l i s t s l i s t g o o d s h e i g h t 結點是樹模型中最基本的概念 在樹模型中共有七種類型的結點 分別是文檔 結點 元素結點 屬性結點 文本結點 名字空間結點 處理指令結點和注釋結點 一個x m l 文檔有一個唯一的文檔結點 稱為根結點 元素結點依次指向其它的元素 結點 屬性結點 文本結點等 為了得到有效的x m l 文檔 還要確保文件中信息遵守的結構 即需要一種用 來描述x m l 文檔中信息結構的機制 這種機制定義了x m l 文檔中元素的順序 元 7 第二章x m l 數(shù)據(jù)管理概述 一種改進的x m l 數(shù)據(jù)管理方案 f a x m l 文檔 0 1b o o k9 90 2p d a1 0 02 2 9 9 b 文檔樹 圖2 1x m l 文檔及其對應的樹模型 素的嵌套關系和內容模型 并建立了文檔數(shù)據(jù)的數(shù)據(jù)類型 d t d d o c u m e n tb p e d e f i n i t i o n 文檔類型定義 可以滿足上述要求 它定義了x m l 文檔的邏輯結構 可 以用直接寫入或以外部鏈接的方式與x m l 文檔相結合 利用外部鏈接的方式 可以 讓多個x m l 文檔共同使用一個d t d d t d y u 出了可用在文檔中的元素 屬性 實體 和符號表示法 以及這些內容之間可能的相互關系 例如 d t d 可以確切的規(guī)定每 個g o o d s 元素只有一個n a n l e 子元素 只有一個p r i c e 子元素 這些規(guī)則都是在d t d 中定 義的 圖2 2 表示圖2 1 a 中x m l 文檔對應的d t d d o c t y p el i s t s e l e 刪ti i s t s 1 i s t 胗 e l e m e n th e i g h t p c d a t a p 圖2 2x m l d t d 示例 8 一種改進的x m l 數(shù)據(jù)管理方案 第二章x m l 數(shù)據(jù)管理概述 2 2x m l 查詢語言 現(xiàn)己提出的x m l 查詢語言有很多種 比如x p a t h 2 4 x q u e r y 2 5 和x m l q l 2 6 等 這些查詢語言有一個共同點就是通過路徑表達式來實現(xiàn)對文檔的查詢 本文 主要介紹x p m h 語言 2 4 x p a t h 是f l q w 3 c 倉 j 建的 它使用類似于u r l 的路徑表示法 在一個x m l 文檔中 進行導航 x p a t h 的主要部件是表達式 其中最重要的表達式是定位路徑表達式 亦 稱為路徑表達式 每個路徑表達式都是由一個或多個路徑步組成 路徑表達式有絕 對路徑表達式和相對路徑表達式兩種 絕對路徑表達式以正斜杠 開始 它是 從文檔樹的根結點開始定位路徑 相對路徑表達式則直接從某個定位步開始定位路 徑 以絕對路徑表達式為例 x p a t h 的語法為 阮砌 s t e p l s t e p 2 s t e p n 式2 1 中路徑步s t e p 被定義為 2 1 st e p a x i s n o d e t e s t p r e d i c a t e 2 2 式2 2 中 a x i s 軸指定了向前或向后的方向 每個軸都有一個基本結點類型 對于屬性軸 基本結點類型是屬性 對于命名空間軸 基本結點類型是命名空間 對于其它軸 基本結點類型是元素 在x p a t h 中最常用的軸有 c h i m d e s c e n d a n t p a r e n t a n c e s t o r n o d e t e s t 結點測試用來對軸中的結點進行測試 如果給定結點 的測試值為t r u e 則保留在結果結點集中 否則將它從結果結點集中刪除 可以使用 結點名稱或結點類型進行結點測試 p r e d i c a t e 謂詞對原結果結點集進行篩選并生 成新結果結點集 路徑表達式可以使用縮減句法 實際上縮減句法比完整句法更常用 因 為它們更簡潔 例如 地址路徑g o o d s n a m e 是c h i l d g o o d s c h i l d n a m e 的縮寫 地址路徑g o o d s i d 0 3 是c h i l d g o o d s a t t r i b u t e i d 0 3 的縮寫 地址路 徑l i s t s n a m e 是l i s t s d e s c e n d a n t o r s e l f n o d e c h i m n a m e 的縮寫 實際使用中的x p a t h 查詢只用至u x p a t h 語言的一個子集或稱之為片段 其中一個 較常用的x p a t h 片段包含 孩子軸 后裔軸 仂 謂詞和結點測試 下面舉幾個簡單 的例子說n j x p a t h 表達式的含義 9 第二章x i v l l 數(shù)據(jù)管理概述一種改進的x m l 數(shù)據(jù)管理方案 1 n a m e 選擇所有的n a m e 元素 不論n a m e 處在哪個層次 2 g o o d s i d 0 1 p r i c e 選擇所有父元素是g o o d s 的叫c e 元素 并n g o o d s 元 素的i d 屬性值為o l 2 3x m l 文檔編碼方案 根據(jù)編碼之間的關系可以將編碼方案主要分為兩類 基于區(qū)間的編碼和基于路 徑的編碼 基于區(qū)間的編碼方案利用x m l 文檔的有序特點 通過某種訪問順序給文 檔中的每個結點賦予一個編碼 基于路徑的編碼方案則利用x m l 文檔的嵌套特點 給從文檔根結點開始所能到達的每個路徑上的結點賦予一個編碼 常見的編碼方案設計在以下幾個方面是不同的 2 7 1 所支持的結構關系 例如包含關系 文檔位置關系 2 碼的最大長度或平均長度 3 編碼后的查詢執(zhí)行時間 4 插入操作導致的重新編碼代價 下面詳細介紹幾種編碼方案 2 3 1 基于區(qū)間的編碼 區(qū)間編碼方案的思想 樹丁中的每一個結點被賦予一個區(qū)間編碼 一個結點的區(qū)間編碼包含它的后裔結點的區(qū)間編碼 即若結點u 是結點v 的祖先 當 且僅當 s t a r t u s t a r t v ae n d v e n d u 2 3 兩個結點的區(qū)間編碼之間關系 要么完全包含 要么完全不相交 不可能出現(xiàn) 其它情況 第一種區(qū)間編碼方案是d i e t z 編碼 2 8 其編碼規(guī)則 樹r 中的每一個結點被賦 予一個由先序遍歷序號和后序遍歷序號組成的二元組 由于樹丁中的一 個祖先結點u 在先序遍歷中必然出現(xiàn)在它的后裔結點v 之前 因此若u 是v 的祖先 則 p r e u p r e v ap o s t v p o s t u 2 4 樹丁中的任意兩個結點之間的包含檢測能夠在常數(shù)時間內被計算 對于該編碼 方案 p r e 或p o s t 均可作為結點的唯一標識 一個d i e t z 編碼示例如圖2 3 所示 1 0 f 9 j 1 1 8 1 1 0 0 0 0 0 0 0 0 0 1 1 1 d i e t z 編碼 z h a n g 編碼 l i m o o n 編碼 位向量編碼 前綴編碼 素數(shù)編碼 圖2 3x m l 數(shù)據(jù)的編碼方案 第二種區(qū)間編碼方案是l i m o o n 編碼1 1 6 它的編碼規(guī)則 x m l 文檔樹丁中的 每一個結點被賦予一個二元組 其中 o r d e r 是結點的擴展先序遍歷序 號 它的取值是非連續(xù)的 為結點的插入預留序號空間 s i z e 為結點的后裔范圍 對 于該編碼方案 必須滿足如下兩點 1 結點v 和其父親結點u 有 o r d e r u o r d e r v ao r d e r v s i z e v o r d e r u s i z e u 2 5 2 兄弟結點u 和v 若在先序遍歷中結點v 是結點u 的右兄弟 則 o r d e r u s i z e u a 1 b e g i n 的第一個結點 稱為掃描點 然后在內表d l i s t 中 從掃描點開始順序掃描 對滿足b e g i n a 1 e n d 條件的所有結點d 再判斷是否滿足 條件 若滿足則產(chǎn)生連接結果結點對 以l d 繼續(xù)對外表a l i s t 中的第二個結點a 2 重 復上面的步驟 直到外表a l i s t 或內表d l i s t 中的結點連接完畢 圖2 7 是m p m g j n 算 法內表操作示意圖 圖2 7m p m g j n 算法內表操作示意圖 s t a c k t r e e 算法 s t a c k t r e e 算法分為s t a c k t r e e d e s c 按后裔結點有序 和s t a c k t r e e a n c 按祖 先結點有序 兩種 本文以s t a c k t r e e d e s c 算法為代表 s t a c k t r e e d e s c 算法的基本思想 歸并連接過程中 從a l i s t 中得到一個新結點a 如果它是目前棧項結點后裔 則日被壓入棧 若棧為空 以也被壓入棧 從d l i s t 中得 到的一個新結點d 如果它是目前棧頂結點的后裔 那么它也是目前棧中所有結點的 1 8 一種改進的x m l 數(shù)據(jù)管理方案第二章x m l 數(shù)據(jù)管理概述 后裔 因此 結點d 與棧中所有結點之問的連接結果可以被輸出了 如果結點d 不是 目前棧頂結點的后裔 則可以將棧頂結點出棧了 并且判斷d 是否是新棧項結點的后 裔 直到棧為空 圖2 8 是一個s t a c k t r e e d e s c 算法的執(zhí)行過程 左邊是一個x m l 文 檔實例 右邊是算法執(zhí)行過程 圖巾的查詢語句是 a d l j幽u幽u l 且i 一址1 一l h 0 一 阻阻 皿l s ls 2s 3s 4s 5s 6s 7s 8s 9 s i a 1 進棧s 2 輸出 a 1 d 1 s 3 a 2 進棧 s 4 輸出 a 1 d 2 a 2 d 2 s 5 輸出 a 1 d 3 a 2 d 3 s 6 a 2 出棧 s 7 a 3 進棧s s 輸出 a 1 d 4 a 3 d 4 9 a 3 a l 出棧 圖2 8s t a c k t r e e d e s c 算法執(zhí)行步驟 2 6 2 小枝模式的結構連接 目前的研究將小枝模式看成一個整體進行模式匹配 使得算法的效率有大 幅度的提高 根據(jù)是否需要歸并操作 小枝模式匹配分為兩種 第一種是基于歸 并的小枝模式匹配算法 有t w i g s t a c k 算法 1 8 t s g e n e t i c 算法 4 9 1 i t w i g j o i n 算 法 5 0 t w i g s t a c k l i s t 算法 5 1 和研a s t 算法 1 9 等 第二種是非歸并小枝模式匹配 算法 有t w i 9 2 s t a c k 算法 2 0 t w i g l i s t 算法 2 1 t w i g n m 算法 5 2 等 下面重點介 紹t w i 9 2 s t a c k 算法思想 t w i 9 2 s t a c k 算法 t w i 9 2 s t a c k 算法的基本思想 后序遍歷文檔 對于元素e 當且僅當它滿足以查 詢結點e 為根的小枝時 將其壓入層次棧h s e e 是與e 對應的查詢結點 由于是 后序遍歷 因此在訪問e 之前 已經(jīng)訪問過了p 的后裔 在檢查e 是否匹配e 的子小枝 時 只需要檢查一個查詢步 即e m 其中m 是e 的子結點 在檢查查詢結點或者 壓入元素時 要注意維護層次棧的結構 圖2 9 是一個層次棧構造示例 每個層次棧h s j 都由一個棧樹序列組成 1 9 五 舢i l 赴 外八一 x m l 數(shù)據(jù)管理概述 一種改進的x m l 數(shù)據(jù)管理方案 h s i d l x s l c j 圖2 9 層次棧編碼結構示例 一個棧樹s 丁是一個有序樹 其每一個結點是一個棧s 如h s a 邑含一個棧樹 而h s d 包含3 個棧樹 每個棧s 包含0 個或多個文檔元素 棧中每個元素是其之下元 素的父親 3 1 問題提出 x m l 數(shù)據(jù)可能以兩種形態(tài)存在 1 存在于一顆內存樹中 x m l 文檔被讀入內存并建立一棵形 t h d o m 樹 然后就 可以周游這棵樹來處理查詢 2 存在于磁盤上的若干表或者文件中 x m l 文檔在解析時已被分解到若干表或 文件中 查詢x m l 時需要將數(shù)據(jù)文件和索引文件的某些數(shù)據(jù)塊讀入內存進行處理 第一種方式雖然查詢簡單 但是嚴重依賴于內存大小 只能處理比較小 的x m l 文檔 對于一般的x m l 文檔需要使用第二種 將x m l 文檔分解到磁盤存儲 x m l 數(shù)據(jù)的存儲技術可以分為原生x m l 數(shù)據(jù)存儲和基于關系的x m l 數(shù)據(jù)存儲 原生x m l 數(shù)據(jù)存儲試圖在物理存儲格式上保持x m l 文檔中獨特的結構特征 x m l 數(shù) 據(jù)無需經(jīng)過映射 物理結構與邏輯結構一致 不會導致信息丟失 但在技術上還是 非常不成熟的 研究的比較少 而基于關系的x m l 數(shù)據(jù)存儲將x m l 數(shù)據(jù)分解到若干 關系表中 在這種存儲方式下 可以充分利用關系數(shù)據(jù)庫的成熟技術來管理x m l 數(shù) 據(jù) x m l 查詢操作轉化為一系列關系查詢操作 在技術上成熟可行 但由于x m l 數(shù) 據(jù)大都是半結構化數(shù)據(jù) 而關系數(shù)據(jù)都是結構化數(shù)據(jù) 因此需要映射 映射需要有編碼方案作為基礎 但映射之后 x m l 數(shù)據(jù)也會面臨插入 刪除等 更新問題 數(shù)據(jù)一旦更新 編碼也要作相應的調整 才能保證基于這個編碼的各種 索引和查詢算法的正確性 在編碼的更新方面 針對性的研究還不多 主要是在研 究編碼方案的同時順便考慮更新問題 5 3 5 7 可以支持更新的幾種編碼有 l i m o o n 編碼作為全局編碼 可以在一定程度上實現(xiàn)x m l 文檔的更新 中o r d e r 的取值是非連續(xù)的 目的是為結點的插入預留序號空間 但 是預留空間很大則造成存儲浪費 相反容易導致過多的重新編碼 2 l 第三章 數(shù)據(jù)管理方案設計一種改進的x m l 數(shù)據(jù)管理方案 對結點的編碼除了使用全局標識 還可以使用局部標識 使用局部標識 比如 使用兄弟結點序號對x m l 文檔樹中的結點進行編碼 其優(yōu)缺點正好與全局編碼相反 文獻 5 8 對其優(yōu)缺點進行了詳細了分析 文中給出了將實數(shù)作為序號的指標集的思 路 利用實數(shù)可表示無窮精度的特點滿足插入數(shù)據(jù)帶來的結點序號的擴張 但是 由實數(shù)計算帶來的結構關系計算的代價是提高查詢處理性能所不容忽視的 圖3 1 表 示當插入一個新結點時所引起結點編碼的變化 虛線結點表示新插入的結點 虛線 區(qū)域表示要重新編碼的結點范圍 a 全局編碼 b 局部編碼 圖3 1 全局編碼 局部編碼更新文檔示意圖 本課題提出的編碼方案優(yōu)勢在于可支持文檔的動態(tài)更新 且具有局部編碼更新 的特點 在經(jīng)過映射之后 當涉及文檔的動態(tài)更新時 不需要對已存在的結點進行 過多的編碼就可以及時的反映給用戶 這樣節(jié)省了二次編碼的時間 提高了映射方 案中文檔更新的效率 x m l 查詢處理中的連接是指以兩個或多個元素列表為輸入 輸出滿足一定結構 關系的符合查詢語義的結點對或者結點向量列表 與關系查詢中的連接條件一般是 關于值的約束不同 這里的連接條件一般是關于結構的約束 因而 此種連接常稱 為結構連接 目前關于結構連接的研究主要關注在多元的結構連接 即小枝模式的 結構連接 小枝模式的結構連接將一個小枝模式視為整體 無需分解和逐步連接 省去了中間的許多開銷 但目前的小枝連接算法還主要集中在歸并的結構連接 當參與連接的結點數(shù)目 不多時 歸并連接算法運行效率較好 但當參與連接的結點數(shù)目非常多時 歸并 連接要耗費很多的時間用于分支解的合并 以保證輸出的整體解正確 例