在本論文中，我們探討如何在XQuery查詢處理演算法中，加入資訊檢索之技術，進而從大量的XML文件中找出符合使用者查詢句結構化和關鍵字限制之資料。
本論文查詢處理的範圍包含對XML元素結構限制的處理，以及對關鍵字距離和順序限制的處理。本論文提出兩種作法，並評估其效益。第一種TJ_IR方法是將使用者輸入之查詢句結構建立成查詢樹，根據該查詢樹抓取符合節點的元素，接著處理關鍵字限制，再將符合的結果利用TJFast [LLCC05] 合併，最後回傳符合結構的樹。第二種SCU_Twig方法則是先透過[ACD06]的作法，根據查詢樹抓取符合關鍵字限制的元素資料，接著計算這些元素的LCA，並且加入路徑的判斷，最後再套用TJFast的方式合併。
實驗結果顯示，當查詢句中的關鍵字在檔案中出現的次數不高時，SCU_Twig會較有效率。

In this thesis, we discuss how to combine the technology of Information Retrieval with the XQuery query processing algorithm, so that we could retrieve the data satisfying the structural constraints and the keyword constraints imposed by users.
We propose two methods. One is TJ_IR and the other is SCU_Twig. The first one will convert a user to a query tree. According to the structure of the query tree, the system retrieves the corresponding elements and processes the keyword constraints. Then, the system uses the technique of TJFast to merge and feedback the final results. The second one will retrieve the elements which match the keyword constraints from the query tree, calculate the LCAs, and determine if they match the path constraints. Finally, the system will merge and feedback the results through the technique of TJFast.
The experimental results show that the SCU_Twig system will perform better when the keywords have lower selectivity in the XML data.

第一章 緒論………………………………………..……………………1
1.1 背景與研究動機……………………………...……………………………1
1.2 相關研究……………………………………...………...………………….1
1.3 論文架購……………………………………………………………….…..4
第二章 相關定義……………………………..…………………………5
2.1 XML基本架構……………………………………………………..………5
2.2 XQuery之結構表示式…………………………………………………6
2.3 XQuery之資訊檢索表示式……………………………………………8
2.4 問題描述…………………………………………………………………10
第三章 資料表示……………………………………………………13
3.1 延伸杜威編碼……………………………………………….………..13
3.2 TJ_IR的元素編碼表……………………………………………….…15
3.3 SCU_Twig的關鍵字編碼表……...…………………………….……..19
第四章 TJ_IR系統…………………………………...……………….22
4.1 查詢樹建立模組…………………………………………………….22
4.2 資料擷取和資訊檢索模組…………………………………………....26
4.3 整合模組……………………………………………………………….33
第五章 SCU_Twig系統………….…………………...…………….38
5.1 SCU Table……………………………………………………….38
5.2 整體演算法…………………………………….…………..…….39
第六章 實驗………………………………….……………………..….45
6.1 dataset大小之實驗………………………………………….……………46
6.2 不同資訊檢索限制之實驗………………………………………….……51
6.3 關鍵字頻率影響之實驗………………………………………………….53
6.4 不同節點限制之實驗……………………………………………….57
6.5 相同節點不同限制之實驗……………………………………………….59
6.6 不同查詢句節構之實驗………………………………………………….61
6.7 標籤頻率影響之實驗………………………………………………….62
第七章 結論與未來研究方向…………………………………………65
參考文獻………………………………………………………….…….66

[ACD06] Sihem Amer-Yahia, Emiran Curtmola, Alin Deutsch, "Flexible and Efficient XML Search with Complex Full-Text Predicates", In Proceeding of the SIGMOD Conference, Chicago, Illinois, USA, 2006.
[AKMD+05] Sihem Amer-Yahia, Nick Koudas, Amelie Marian, Divesh Srivastava, David Toman, "Structure and Content Scoring for XML", In Proceedings of the VLDB Conference, Pages: 361–372, Trondheim, Norway, 2005.
[AYJ03] Shurug Al-Khalifa, Cong Yu, H. V. Jagadish, "Querying Structured Text in an XML Database", In Proceedings of the SIGMOD Conference, Jun. 2003.
[BKH02] Nicolas B, Nick K, Divesh S. Holistic Twig joins, "Optimal XML pattern matching", In Proceedings of the SIGMOD Conference, 2002.
[CDZ04] Yi Chen, Susan B. Davidson, Yifeng Zheng, "BLAS : An Efficient XPath Processing System", In Proceedings of the SIGMOD Conference, Pages 47-58, Paris, France, 2004.
[CLTH+07] Songting Chen, Hua-Gang Li, Junichi Tatemura, Wang-Pin Hsiung,
Divyakant Agrawal, K. Selcuk Candan, "Twig2Stack: Bottom-up
Processing of Generalized-Tree-Pattern Queries over XML
Documents", In Proceedings of the VLDB Conference, Pages:
283–294, September 12–15, 2007.
[CKS06] SungRan Cho, Nick Koudas, Divesh Srivastava, "Meta-data Indexing
for XPath Location Steps", In Proceedings of the SIGMOD Conference, June 27–29, Chicago, Illinois, USA, 2006.
[GSBS03] Lin Guo, Feng Shao, Chavdar Botev, Jayavel Shanmugasundaram,
"XRANK: Ranked Keyword Search over XML Documents", In
Proceedings of the SIGMOD Conference, San Diego, CA, June 9-12,
2003.
[G87] G. H. Gonnet: The PAT text searching sytem. Technical report,
University of Waterloo, 1987
[KKNR04] Raghav Kaushik, Rajasekar Krishnamurthy, Jeffrey F. Naughton
, "Raghu Ramakrishnan: On the Integration of Structure Indexes and
Inverted Lists", In Proceedings of the ICDE Conference, 2004.
[LLCC05] Jiaheng Lu,Tok Wang,Ling Chee-Yong Chan,Ting Chen, "From Region
Encoding To Extended Dewey: On Efficient Processing of XML Twig
Pattern Matching", In Proceedings of VLDB Conference, Pages:
193–204, Norway, 2005.
[P85] R. Y. Pinter: Efficient string matching with don't care patterns. In Combinatorial ALgorithms on Words, NATO ASI Series, volume 12, pages11-29, 1985.
[TSW05] Martin Theobald, Ralf Schenkel, Gerhard Weikum, "An Efficient and
Versatile Query Engine for TopX Search", In Proceedings of the VLDB
Conference, 2005.
[XP05] Yu Xu, Yannis Papakonstantinou, "Efficient Keyword Search for
Smallest LCAs in XML Databases", In Proceedings of the SIGMOD
Conference, 2005.
[YLP04] Sihem AmerYahia, Laks V.S. Lakshmanan, Shashank Pandit,
"FleXPath: Flexible Structure and FullText Querying for XML", In Proceedings of the SIGMOD Conference, Pages: 13-18, Paris, France, 2004.