Query Processing on Compressed XML Data Using Staircase Join

XML是最近資訊科技的寵兒，許多人投入心力去研究XML。然而用XML格式來表示的資訊，往往需要更龐大的空間來儲存。所以我們需要能將XML文件壓縮的方法，才能使XML更加實用。 為了使XML、RDB可以相結合，文獻提出staircase join[14]的方法來融合兩者。但是壓縮的問題仍然沒有解決，所以我們再將壓縮的觀念引入staircase join之中，並且提出一套方法來壓縮XML文件。並且探討每個節點之間種種的關係，以及加速的方法，再加上討論這些關係和加速方法，在我們壓縮之後的結果上是如何改變和運作。 之後，我們做了一些觀察，比較壓縮之前和用我們的方法壓縮之後，兩者之間的差異，並且分析結果及可能原因。最後對這樣的方式給予一些結論，還有未來可以研究與改進的地方。誌謝....................................................01 目錄....................................................02 圖標題..................................................04 表標題..................................................05 摘要....................................................06 第一章 緒論............................................07 1.1 研究動機...........................................07 1.2 問題簡介...........................................08 1.3 文獻回顧...........................................08 1.4 論文架構...........................................11 第二章 理論基礎........................................13 2.1 介紹XML............................................13 2.1.1 XML語法淺介.................................14 2.1.2 XML的優越性.................................24 2.1.3 DTD.........................................28 2.2 壓縮格式...........................................34 2.2.1 最小的儲存空間需求..........................34 2.2.2 最小的傳輸頻寬要求..........................35 2.2.3 處理工作時所需最小主記憶體..................36 2.3 階梯式的連結方法...................................37 2.3.1 XML文件用樹的結構表示.......................37 2.3.2 XML路徑的加速方法...........................38 2.3.3 修剪、分割和跳過............................45 第三章 在壓縮的XML文件上使用階梯式的連結...............50 3.1 我們的壓縮方法.....................................50 3.2 結合壓縮和階梯式的連結.............................53 3.2.1 標示staircase join後，壓縮preorder的方法....54 3.2.2 preorder/postorder都壓縮....................59 3.3 檢查功能...........................................68 3.3.1 壓縮的結果..................................68 3.3.2 四種axis的調整..............................69 3.3.3 三個技巧的改變..............................73 3.3.4 query的效率.................................73 3.4 舉例...............................................75 3.4.1 實際使用我們的方法..........................75 3.4.2 分析結果....................................83 第四章 觀察結果與分析..................................85 4.1 觀察方法...........................................85 4.2 數據結果...........................................86 4.3 效率分析...........................................90 4.4 實際應用...........................................94 第五章 結論與未來展望..................................96 第六章 參考文獻........................................9