Please use this identifier to cite or link to this item:
標題: 一個適用於XML串流的多查詢處理機制
A Mechanism for XML Twig Queries Streaming Processing
作者: 鄭焜旭
Cheng, Kun-Hsu
關鍵字: Filtering;Filtering機制;Streaming Processing;Multiple Twig Queries;XML;XPath;Encoding;串流查詢;多分支查詢;XML;XPath;編碼
出版社: 資訊科學與工程學系所
引用: [1]S. Al-Khalifa, H. V. Jagadish, N. Koudas, J. M. Patel, D. Srivastava and Y. Wu, “Structural Joins: A Primitive for Efficient XML Query Pattern Matching,” Proceedings of the 18th International Conference on Data Engineering, 2002, pages 141 - 152. [2]M. Altinel and M. J. Franklin, “Efficient Filtering of XML Documents for Selective Dissemination of Information,” Proceedings of the 26th International Conference on Very Large Data Bases, 2000, pages 53-64. [3]T. Bray, J. Paoli, C. M. Sperberg-McQueen and E. Maler, “Extensible Markup Language (XML) 1.0 (Fourth Edition),” W3C Recommendation, Available at, 2006. [4]N. Bruno, L. Gravano and N. Koudas, ”Navigation- vs. Index-Based XML Multi-Query Processing,” Proceedings of the 19th International Conference on Data Engineering, 2003, pages 139- 150. [5]N. Bruno, N. Koudas and D. Srivastava,“Holistic Twig Joins: Optimal XML Pattern Matching,” Proceedings of the ACM SIGMOD Conference, 2002, pages 310-321. [6]K. S. Candan, W.-P. Hsiung, S. Chen, J. Tatemura and D. Agrawal,“AFilter: Adaptable XML Filtering with PrefixCaching and SuffixClustering,” Proceedings of the 32nd International Conference on Very Large Data Bases, 2006, pages 12-15. [7]C. Chan, P. Felber, M. Garofalakis and R. Rastogi, ”Efficient Filtering of XML Documents with XPath Expressions,” The VLDB Journal, Vol. 11, Issue 4, 2002, pages 354 - 379. [8]Y. Chen, S. B. Davidson and Y. Zheng,“ViteX: A Streaming XPath Processing System,” Proceedings of the 21st International Conference on Data Engineering, 2005, pages 1118-1119. [9]Y. Chen, G. A. Mihaila, S. B. Davidson and S. Padmanabhan, “Efficient Path Query Processing on Encoded XML,” Proceedings of International Workshop on High Performance XML Processing, 2004. [10]Y. Chen, G. A. Mihaila, S. B. Davidson and S. Padmanabhan, “EXPedite: A System for Encoded XML Processing,” Proceedings of the 13th ACM International Conference on Information and Knowledge Management, 2004, pages 108-117. [11]J. Clark and S. DeRose, “XML Path Language (XPath),”, 1999. [12]Y. Diao and M. J. Franklin, “High-Performance XML Filtering: An Overview of YFilter,” Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, 2003, pages 41-48. [13]T. J. Green, G. Miklau, M. Onizuka and D. Suciu, “Processing XML Streams with Deterministic Automata,” Proceedings of the 9th International Conference on Database Theory, 2003, pages 173-189. [14]T Härder, M Haustein, C Mathis and M Wagner, “Node Labeling Schemes for Dynamic XML Documents Reconsidered”, Data & Knowledge Engineering, Vol. 60, No. 1, 2007, pages 126-149. [15]S. Krco, D. Cleary and D. Parker, “P2P Mobile Sensor Networks,” Proceedings of the 38th Annual Hawaii International Conference on System Sciences, 2005, pages 324c-324c. [16]Q. Li and B. Moon, “Indexing and Querying XML Data for Regular Path Expressions,” Proceedings of the 27th International Conference on Very Large Data Bases, 2001, pages 361-370. [17]T. Lopez and D. Kim, “A Context Middleware Based on Sensor and RFID Information,” Proceedings of the 5th IEEE International Conference on Pervasive Computing and Communications Workshops, 2007, pages 331- 336. [18]P. O'Neil, E. O'Neil, S. Pal, I. Cseri, G. Schaller and N. Westbury, “ORDPATHs: Insert-Friendly XML Node Labels”, Proceedings of the ACM SIGMOD International Conference on Management of Data, 2004, pages 903-908. [19]F. Peng and S. S. Chawathe, “XPath Queries on Streaming Data,” Proceedings of the ACM SIGMOD Conference, 2003, pages 431-442. [20]RosettaNetStandards, Default.aspx, 2008. [21]University of California at Berkeley, ”YFilter 1.0 Release,”, 2004. [22]XMLSpy online manual,, 2008. [23]XMPP Standards Foundation,, 2008.
無線網際網路環境中,資訊系統的資料交換標準與資訊傳輸協定的發展基礎已逐漸採用全球資訊網標準製定組織(W3C)所制定的XML 規格。資訊系統透過Filtering機制來決定當前的XML訊息是否符合使用者的要求。XML Filtering機制的效率可藉由有效的結果列舉方法來提昇。目前XML Filtering機制的結果列舉方法主要有兩類:一、以堆疊為基礎(stack-based)的方法,將每個查詢轉換為數個堆疊,並運用編碼在XML串流資料上,最後的查詢結果則藉由維護暫存結果來產生,其缺點是仍未支援多分支查詢(multiple twig queries)。二、以自動機為基礎(automata-based)的方法,將每個查詢轉換成相等的自動機,並以XML串流資料為自動機的輸入來驅動狀態轉移,最後查詢結果則藉由維護暫存狀態及暫存結果來產生,其缺點是需要保存許多的暫存狀態及暫存結果,查詢效率差。
本論文的主要貢獻在於提供一個適用於XML訊息串流的XML Filtering機制(MFilter)來支援多分支查詢。MFilter機制與現有機制不同在於,改用後序順序來瀏覽XML文件,並且使用查詢索引、搭配區間編碼、結合階層式堆疊群及變更結果列舉時機來完成查詢。實驗結果顯示MFilter機制的確能有效支援多分支查詢,提升系統執行效能約18%至43%,並且發現多分支查詢的最大深度越小、查詢步驟軸線為”//”的機率越高及巢狀查詢路徑出現的個數越多,會使得系統執行效率越好。
其他識別: U0005-1908200808243700
Appears in Collections:資訊科學與工程學系所

Show full item record

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.