臺灣博碩士論文加值系統

近年來XML資料格式已成為全球網際網路環境資料交換的標準，有效率地查詢擷取XML資料成為一項重要的研究課題。從XML查詢的歷史記錄所形成的資料庫中，探勘出常見的XML查詢樣式樹，並將這些樣式作為索引或快取的依據，可以減少使用者查詢XML資料的等待時間。本論文針對XML查詢樹所形成的資料庫，以樹首遞迴投影概念為基礎，提出探勘常見XML查詢樣式樹的方法，稱為XP_Mine演算法。其探勘過程中，首先將查詢樹資料庫中以前序字串編碼的XML查詢樹轉換成前序字串-層級表示法表示，接著以樹首遞迴投影的方式進行探勘。此外，XML查詢路徑中允許有”*”及”//”特殊比對方式的查詢樣式，所以本論文方法在探勘過程中亦擴展查詢樹包含比對的方法。由實驗結果顯示，對固定大小的資料庫，在查詢樹節點個數較小的時候，XP_Mine 較FastXMiner演算法有更好的執行效率。

附表目錄 ii
附圖目錄 iv
第一章 緒論 1
1.1 背景與研究動機 1
1.2 相關文獻探討 2
1.3 論文方法 7
1.4 論文架構 8
第二章 相關名詞與問題定義 9
2.1 名詞定義 9
2.2 問題描述 16
第三章 查詢樹之樹首投影概念 17
3.1 前序字串－層級表示法 17
3.2 樹首投影 20
3.3 以前序字串－層級表示法做樹首遞迴投影 22
3.4 正規化 27
第四章 常見查詢樣式樹探勘方法 31
4.1 擴展正規化轉換處理 31
4.2 特殊查詢符號的處理 32
4.3 投影資料庫中之暫時項目節點 40
4.4 XP_Mine演算法探勘流程 41
第五章 演算法效率評估 52
5.1 交易資料產生方式 52
5.2 實驗評估 54
第六章 結論與未來研究方向 63
參考文獻 65

R. Agarwal, T.Imielinski, and A. Swami, “Mining association rules between sets of items in large databases,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, 1993.
R. Agarwal and R. Srikant, “Fast Algorithms for Mining Association Rules,” in Proceedings of the 20th International Conference on Very Large Database, 1994.
R. Agarwal and R. Srikant, “Mining Sequential Patterns,” in Proceedings of the 11th International Conference on Data Engineering（ICDE）, IEEE, 1995.
J. Han, J. Pei, and Y. Yin, ”Mining Frequent Patterns without Candidate Generation,” in Proceedings of the 2000 ACM-SIGMOD International Conference on Management of Data, 2000.
J. Pei, J. Han, B. Mortazavi-Asi and H. Pinto, ”PrefixSpan：Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth,” in Proceedings of the International Conference on Data Engineering（ICDE）, 2001.
M. J. Zaki, “Efficiently Mining Frequent Trees in a Forest,” in Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2002.
L.H. Yang, M.L. Lee, W. Hsu, and S. Acharya, “Mining Frequent Query Patterns from XML Queries,” in Proceedings of the Eighth International Conference on Database System for Advanced Applications (DASFAA), 2003.
L.H. Yang, M.L. Lee, and W. Hsu, “Efficient Mining of XML Query Patterns for Caching,“ in Proceedings of the 29th International Conference on Very Large Databases (VLDB), 2003.
林真伊, 柯佳伶, “以樹首遞迴投影探勘常見子樹之研究,” 碩士論文, 2004.
D. Chamberlin, D. Florescu, J. Robie, J. Simon, and M. Stefanescu, “XQuery: A Query Language for XML W3C working draft,” World Wide Web Consortium, 2001.