臺灣博碩士論文加值系統

在本論文中，我們探討針對多份XML文件之查詢處理的問題。由於XML本身為樹狀結構，所以查詢句的基礎為路徑表示法。但是在一份XML文件中，元素可以重複出現，相同的路徑表示法因此有可能對應到許多不同的內容，但並非皆符合使用者的要求。所以本論文研究的重點，是根據使用者的查詢條件，從多份XML文件中，找出正確的答案，在本論文中我們假設這些文件皆符合相同的DTD。
本論文設計了三個特殊的資料結構。首先，由於DTD規範了XML文件中元素可以出現的結構，所以我們由DTD中找出XML文件內所有可能出現的路徑表示法，將這些路徑表示法編碼並記錄在元素編碼樹中。利用元素編碼樹，我們設計了元素值編碼表，將一份XML文件內的資料簡化並記錄下來，同時保留文件內元素間的階層父子關係，如此可以減少在查詢處理過程中解析XML文件的時間。最後，文件索引則協助我們從多份元素值編碼表檔中快速找到包含符合使用者需求答案的檔案。基於這三個資料結構，我們設計了一組查詢演算法，有效率地找出正確的答案，以加快利用路徑表示法尋找XML資料的速度。
為了測試我們設計的特殊索引結構及查詢演算法的效率，我們使用ACM SIGMOD Record的XML文件為測試資料，分別與Microsoft SQL Server 2000關聯式資料庫及史丹佛大學提出的Lore系統做比較。實驗結果證實我們所提出的演算法對於任意長度的路徑表示法有較佳的執行效率。

In this thesis, we discuss the query processing issue for multiple XML documents. Due to the tree-structured characteristic of XML documents, the path expression is the basic construct of XQuery. However, since the same element can occur multiple times in a single XML document, the same path expression might correspond to several contents, which are not all correct. Therefore, the focus of this thesis is to retrieve the correct answers according to users’ request, from multiple XML documents with the same DTD.
We proposed three special data structures in this thesis. First, because DTD defines the structures of elements that can appear in XML documents, all possible path expressions in these XML documents can be found in DTD. We encoded these path expressions and recorded them in the EN-Tree. Based on the EN-Tree, we designed a set of EV-Tables. Each table corresponds to a single XML document, which includes the document contents and keeps the parent-child relationship between elements. This structure could reduce the time for parsing XML document during query processing. Finally, Document Index can assist us to find those EV-Tables, which might consist of satisfied data. Base on these data structures; we designed a set of efficient algorithms to retrieve the accurate answers satisfying the input path expressions.
To show the efficiency of the proposed data structures and algorithms, we applied the XML documents for ACM SIGMOD Record as the test data, to compare with Microsoft SQL Server 2000 and the Lore system from Stanford University, respectively. The result of the experiments demonstrated that our approach has better performance.

目錄
摘要 i
英文摘要 iii
誌謝 v
目錄 vi
附表目錄 vii
附圖目錄 viii
第一章、緒論
1.1背景與研究動機
1.2相關研究
1.3研究目標
1.4論文架構
第二章、相關定義
2.1 XML的相關定義
2.2 XQuery的相關定義
第三章、資料結構
3.1 元素編碼樹
3.2 元素值編碼表
3.3 文件索引
第四章、查詢演算法
4.1 查詢處理的架構
4.2 查詢演算法的說明
4.3 查詢演算法範例
第五章、效率評估
5.1查詢句範本
5.2與傳統關聯式資料庫的效能比較
5.3與Lore的效能比較
第六章、結論與未來方向
參考文獻
附表目錄
表3.1 元素值編碼表
表4.1 路徑表示法與元素路徑編碼、元素值路徑編碼對照表
表4.2 元素路徑編碼與元素值路徑編碼對照表
表5.1 各查詢句與其相關資料對照表
表5.2 資料結構所需儲存空間對照表
表5.3 查詢句與路徑表示法長度對照表
附圖目錄
圖2.1 XML文件範例
圖2.2 DTD範例
圖2.3 XQuery範例：找出文章名稱 ( title ) 是Editor's Notes.的書籍資料
圖2.4 對應於圖2.3之XQuery的查詢結果
圖3.1 元素編碼樹結構
圖3.2 以XML表示之元素編碼樹範例
圖3.3 Construct_EN-Tree演算法
圖3.4 EncodeId函式
圖3.5 元素值編碼樹
圖3.6 Construct_EV-Table演算法
圖3.7 文件索引結構
圖3.8 文件索引節點檔案之DTD
圖3.9 文件索引節點之範例檔案
圖4.1 查詢處理架構
圖4.2 QueryProcessing演算法
圖4.3 TraverseBTree函式
圖4.4 元素路徑編碼與路徑樹對照圖
圖4.5 正確路徑集合圖例
圖4.6 Select_Path函式
圖4.7 reSelect函式
圖4.8 Compare_Ancestors函式
圖4.9 Find_TA函式
圖5.1 查詢句一( OpenXML函式)
圖5.2 我們的方法與Microsoft SQL Server 2000的執行效率比較圖
圖5.3 查詢句四( Lorel )
圖5.4 我們的方法與Lore的執行效率比較圖(單一XML文件)
圖5.5 我們的方法與Lore的執行效率比較圖
圖5.6 我們的方法與Lore的執行效率比較圖(依我們方法中開啟的檔案個數)
圖5.7 我們的方法與Lore的執行效率比較圖(依查詢結果個數)
圖5.8 查詢時間與欲查詢的XML文件個數對照圖
圖5.9 查詢時間與路徑表示法長度對照圖

[1] S. Abiteboul, D. Quass, J. McHugh, J. Widom, J. Wiener, The Lorel Query Language for Semistructured Data, International Journal on Digital Libraries, volume 1, number 1, pages: 68 — 88, 1997.
[2] Ashraf Aboulnaga, Alaa R. Alameldeen, Jeffrey F. Naughton, Estimating the Selectivity of XML Path Expressions for Internet Scale Applications, Twenty-Seventh International Conference on Very Large Databases, 2001.
[3] Vincent Aguilera, Sophie Cluet, Pierangelo Veltri, Dan Vodislav, Fanny Wattez, Querying XML Documents in Xyleme, ACM SIGIR 2000 Workshop On XML and Information Retrieval, 2000.
[4] K. Bohm, On extending the XML engine with query-processing capabilities, In Proceedings of IEEE Advances in Digital Libraries, pages: 127 —138, 2000.
[5] Ya-Hui Chang, Ben-Hsu Chen, Chun-Chieh Wu, The Design and Implementation of an Efficient Library Management System by XML, Journal of Internet Technology, volume 2, number 4, 2001.
[6] Chung-Min Chen, N. Stoffel; M. Post, C. Basu, D. Bassu, C. Behrens, Telcordia LSI Engine: implementation and scalability issues, Eleventh International Workshop on Proceedings of Research Issues in Data Engineering, pages: 51 —58, 2001.
[7] V. Christophides, S. Cluet and J. Simeon, On Wrapping Query Languages and Efficient XML Integration, In Proceedings of ACM SIGMOD Conference on Management of Data, pages: 141 — 152, 2000.
[8] Sophie Cluet, Pierangelo Veltri, Dan Vodislav, Views in a Large Scale XML Repository, Twenty-Seventh International Conference on Very Large Databases, 2001.
[9] Brian F. Cooper, Neal Sample, Michael J. Franklin, Gísli R. Hjaltason, Moshe Shadmon, A fast index for semistructured data, Twenty-Seventh International Conference on Very Large Databases, 2001.
[10] D. Florescu, D. Kossmann, A Performance Evaluation of Alternative Mapping Schemes for Storing XML Data in a Relational Database, Rapport de Recherche No. 3680, INRIA, Rocquencourt, France, May, 1999.
[11] T. Grabs, K. Bohm, H.-J. Schek, Scalable distributed query and update service implementations for XML document elements, Eleventh International Workshop on Proceedings of Research Issues in Data Engineering, pages : 35 — 42, 2001.
[12] H. Kato, K. Oyama, M. Yoshikawa, S. Uemura, A query optimization for XML document views constructed by aggregations, Proceedings of 1999 International Symposium on Database Applications in Non-Traditional Environments, pages: 189 —196, 1999.
[13] E. Kotsakis, K. Bohm, XML Schema Directory: A data structure for XML data processing, Proceedings of the First International Conference on Web Information Systems Engineering, volume 1, pages: 62 —69, 2000.
[14] Quanzhong Li, Bongki Moon, Indexing and Querying XML Data for Regular Path Expressions, Twenty-Seventh International Conference on Very Large Databases, 2001.
[15] J. McHugh, J. Widom, Query optimization for semistructured data. Technical report, Stanford University Database Group, February, 1999.
[16] J. McHugh, J. Widom, Query Optimization for XML. Twenty-Fifth International Conference on Very Large Databases, 1999.
[17] Torsten Schlieder, Felix Naumann, Freie Universitat Berlin, Humboldt Universitat zu Berlin, Approximate Tree Embedding for Querying XML Data, ACM SIGIR 2000 Workshop On XML and Information Retrieval, 2000.
[18] J. Widom, Data Management for XML : Research Directions, IEEE Data Engineering Bulletin, volume 22, number 3, 1999.
[19] 張雅惠，吳俊頡，謝璨隆，查詢多份XML文件的資料結構設計，廿一世紀數位生活與網際網路科技研討會論文集，2001。
[20] 張雅惠，吳俊頡，謝璨隆，支援XML文件查詢的索引結構，中華民國九十年全國計算機會議論文集，2001。