臺灣博碩士論文加值系統

XML已經逐漸成為現今網際網路上熱門的一種資料交換的標準格式之一，使用者往往需要對XML文件進行查詢，但是在對原始XML文件的結構無法掌握的情況下很難使用一般的結構語言進行查詢，則通常會採用關鍵字查詢的方法進行搜尋，而為了使關鍵字查詢的方法能夠更有效率則需對XML資料進行索引的建立。
在本篇論文中，我們採用以杜威為基礎的兩個索引編碼法進行索引的建立，當XML文件進行更新時，不需重新對整份文件建置索引而僅需對異動的部份進行更新即可；在關鍵字查詢方面，我們加入了關係的條件限制以確保資料的正確性，並防止沒有意義的資料回傳，我們實作了一個系統讓使用者在對XML文件的結構不了解的情況下，也能夠搜尋出想要取得的資料。

XML is becoming the standard for data exchanges and data representation. Keyword search allows a user to easily query and access XML data and thus becomes an important research issue.
In this thesis, we used Dewey-base two indices to index XML data. It does not require re-computation of existing labels when an XML document is updated. When returning keyword search results, we use the relationships between nodes ensure the return data is correct and to avoid returning meaningless data. Users can query XML data without having to understand the XML structure. An example system was implemented as an illustration.

中文摘要 I
ABSTRACT II
致謝 III
目錄 IV
圖形目錄 VI
表格目錄 VII
1. 簡介 1
2.背景知識 5
2.1 杜威編碼法介紹 5
2.2 杜威為基礎兩個索引編碼法介紹 7
2.3 PATH SUMMARY介紹 10
2.4 關鍵字查詢介紹 11
3.系統設計 12
3.1系統架構 12
3.2 關鍵字節點關係 16
3.3 關係節點合併 18
4.系統實作 21
4.1 開發環境 21
4.2 資料儲存 22
4.2.1 索引的儲存 22
4.2.2 關係節點和樹狀結構節點的暫存 23
4.2.3 資料表設計 26
4.3 實作結果 29
5.相關研究比較 32
6.結論與未來展望 34
參考文獻 36
作者簡介 38




圖形目錄
圖一. XML 資料樹 T1........................................................................ 4
圖二.杜威編碼法................................................................................ 5
圖三. 杜威編碼法更新問題.............................................................. 6
圖四. 杜威為基礎兩個索引編碼法................................................... 7
圖五. 杜威為基礎兩個索引插入編碼法........................................... 9
圖六. Path Summary for T1 ............................................................... 10
圖七.XML 索引建立架構圖............................................................... 12
圖八.XML 關鍵字查詢架構圖........................................................... 13
圖九.採用杜威為基礎兩個索引編碼法的path summary graph ..... 15
圖十.父子節點合併(父節點存在)................................................... 19
圖十一.父子節點合併(父節點不存在) ........................................... 19
圖十二.父子節點集合合併.............................................................. 20
圖十三. 以節點名稱為主的反向索引表......................................... 22
圖十四. 採用串列及structure 的樹狀結構暫存............................. 25
圖十五. XML 資料樹 T2.................................................................. 31
圖十六. 實作畫面結果.................................................................... 31
圖十七. R_Search 問題..................................................................... 35
圖十八. 關鍵字(year course name department)之正確回傳子樹..... 35



表格目錄
表格一.父子關係節點對暫存表....................................................... 24
表格二.父子節點集合暫存表........................................................... 24
表格三.XML 檔案儲存表格............................................................. 26
表格四.以節點名稱為主的索引儲存表............................................ 27
表格五.以節點的值為主的索引儲存表............................................ 27
表格六.Path Summary 後的以節點名稱為主的索引儲存表............ 28
表格七.相關研究比較表................................................................... 33

[1] W3C, “Extensible Markup Language (XML) 1.0”, Article from: http://www.w3.org/XML, June 2007.
[2] “XML Path Language (XPath) 2.0”, http://www.w3.org/TR/xpath20, June 2007.
[3] “XQuery 1.0: An XML query language”, http://www.w3.org/TR/xquery/, June 2007.
[4] I. Tatarinov, S. Viglas, K. Beyer, J. Shanmugasundaram, E. Shekita, and C. Zhang, “Storing and Querying Ordered XML Using a Relational Database System”, In Proc. ACM SIGMOD 2002, June 2002, pp. 204-215.
[5] 李哲彰. “動態XML資料的索引方法之研究”, 中原大學資訊工程研究所碩士論文, 2008年6月.
[6] Y. Xu, and Y. Papakonstantinou “Efficient Keyword Search for Smallest LCAs in XML Databases”, In Proc. ACM SIGMOD 2005, June 2005, pp. 527-538.
[7] R. Goldman, and J. Widom, “Data Guides: Enabling Query Formulation and Optimization in Semistructured Databases”, In Proc. VLDB 1997, August 1997, pp. 436-445.
[8] Q. Zou, S. Liu, and W. W. Chu, “Ctree: A Compact Tree for Indexing XML Data”, In Proc. WIDM 2004, November 2004, pp. 39-46.
[9] C.W. Chung, J.K. Min, and K. Shim, “APEX: An Adaptive Path Index for XML data”, In Proc. ACM SIGMOD 2002, June 2002, pp. 121-132.
[10]G. Li, J. Feng, J. Wang, and L. Zhou “Effective Keyword Search for Valuable LCAs over XML Documents”, In Proc. CIKM 2007, November 2007, pp. 31-40.
[11] Z. Liu, J. Walker, and Y. Chen “XSeek: A Semantic XML Search Engine Using Keywords”, In Proc. VLDB 2007, September 2007, pp. 1330-1333.
[12] Z. Liu, and Y. Chen “Identifying Meaningful Return Information for XML Keyword Search”, In Proc. ACM SIGMOD 2007, June 2007, pp. 329-340.
[13] Y. Xu, and Y. Papakonstantinou “Efficient LCA based Keyword Search in XML Data”, In Proc. CIKM 2007, November 2007, pp. 1007-1010.
[14] Y. Li, C. Yu, and H. V. Jagadish “Schema-Free XQuery”, In Proc. VLDB 2004, August 2004, pp. 72-83.
[15] V. Hristidis, N. Koudas, Y. Papakonstantinou, and D. Srivastava “Keyword Proximity Search in XML Trees”, In Proc. TKDE 2006, February 2006, pp. 525-539.
[16] S. Son, H. Shin, and Z. Xu, “Structural Semi-Join: A light-weight structural join operator for efficient XML path query pattern matching”, In Proc. IDEAS 2007, September 2007, pp. 233-240.
[17] D. Srivastava, S. Al-Khalifa, H. V. Jagadish, N. Koudas, J. M. Patel, and Y. Wu, “Structural joins: A primitive for efficient XML query pattern matching”, In Proc. ICDE 2002, March 2002, pp. 141-152.
[18] C. Zhang, J. Naughton, Q. Luo, D. DeWitt, and G. Lohman “ On supporting containment queries in relational database management systems” In Proc. ACM SIGMOD 2001, May 2001, pp. 425-436.
[19] W. Yang, B. Shi, “Schema-aware Keyword Search over XML
Streams”, In Proc. CIT 2007, October 2007, pp. 29-34.