Efficient XQuery join processing in publish/subscribe systems
Pages 95 - 104
Abstract
Efficient XML filtering has been a fundamental technique in recent Web service and XML publish/subscribe applications. In this paper, we consider the problem of filtering a continuous stream of XML data against a large number of XQuery queries that contain multiple inter-document value-based join operations in their where clauses. To perform efficient join operations, the path expressions from these queries are extracted and organized in a way that multiple path expressions can be joined simultaneously. The join operations are then pipelined to minimize the number of join operations and to share any intermediate join results as much as possible. Our system operates on top of many currently available XPath filtering engines as an add-on module to extend their features to support queries with join operations. Experiments show that our proposal is efficient and scalable.
References
[1]
}}Barta, A., Consens, M. P. & Mendelzon, A. O. (2005), Benefits of path summaries in an xml query optimizer supporting multiple access methods., in 'Proceedings of the 31st International Conference on Very Large Data Bases', ACM, Trondheim, Norway, pp. 133--144.
[2]
}}Barton, C., Charles, P., Goyal, D., Raghavachari, M., Fontoura, M. & Josifovski, V. (2003), Streaming xpath processing with forward and backward axes, in 'Proceedings of the 19th International Conference on Data Engineering', IEEE Computer Society, Bangalore, India, pp. 455--466.
[3]
}}Boncz, P. A., Grust, T., van Keulen, M., Manegold, S., Rittinger, J. & Teubner, J. (2006), Monetdb/xquery: a fast xquery processor powered by a relational engine., in 'Proceedings of the ACM SIGMOD International Conference on Management of Data', ACM, Chicago, IL, pp. 479--490.
[4]
}}Bruno, N., Koudas, N. & Srivastava, D. (2002), Holistic twig joins: optimal xml pattern matching, in 'Proceedings of the ACM SIGMOD International Conference on Management of Data', ACM, Madison, WI, pp. 310--321.
[5]
}}Chan, C.-Y., Felber, P., Garofalakis, M. & Rastogi, R. (2002), 'Efficient filtering of xml documents with xpath expressions', The VLDB Journal 11(4), 354--379.
[6]
}}Chen, Y., Davidson, S. & Zheng, Y. (2006), An efficient xpath query processor for xml streams, in 'Proceedings of the 22nd International Conference on Data Engineering', IEEE Computer Society, Atlanta, GA, p. 79.
[7]
}}Choi, R. H. & Wong, R. K. (2009), 'Efficient filtering of branch queries for high-performance xml data services', To appear: Journal of Database Management.
[8]
}}Clark, J. & DeRose, S. (1999), 'Xml path language (xpath)'. http://www.w3.org/TR/xpath.
[9]
}}Diao, Y., Altinel, M., Franklin, M. J., Zhang, H. & Fischer, P. (2003), 'Path sharing and predicate evaluation for high-performance xml filtering', ACM Trans. Database Syst. 28(4), 467--516.
[10]
}}Diao, Y. & Franklin, M. J. (2003), Query processing for high-volume xml message brokering., in 'Proceedings of 29th International Conference on Very Large Data Bases', Morgan Kaufmann, Berlin, Germany, pp. 261--272.
[11]
}}Diao, Y., Rizvi, S. & Franklin, M. J. (2004), Towards an internet-scale xml dissemination service., in 'Proceedings of the 30th International Conference on Very Large Data Bases', Morgan Kaufmann, Toronto, Canada, pp. 612--623.
[12]
}}Goldman, R. & Widom, J. (1997), Dataguides: Enabling query formulation and optimization in semistructured databases., in 'Proceedings of 23rd International Conference on Very Large Data Bases', Morgan Kaufmann, Athens, Greece, pp. 436--445.
[13]
}}Gottlob, G., Koch, C. & Pichler, R. (2005), 'Efficient algorithms for processing xpath queries', ACM Trans. Database Syst. 30(2), 444--491.
[14]
}}Gou, G. & Chirkova, R. (2007), Efficient algorithms for evaluating xpath over streams., in 'Proceedings of the ACM SIGMOD International Conference on Management of Data', ACM, Beijing, China, pp. 269--280.
[15]
}}Grust, T., Rittinger, J. & Teubner, J. (2007), Why off-the-shelf rdbmss are better at xpath than you might expect., in 'Proceedings of the ACM SIGMOD International Conference on Management of Data', ACM, Beijing, China, pp. 949--958.
[16]
}}Gupta, A. K. & Suciu, D. (2003), Stream processing of xpath queries with predicates, in 'Proceedings of the ACM SIGMOD International Conference on Management of Data', ACM, San Diego, CA, pp. 419--430.
[17]
}}Hong, M., Demers, A. J., Gehrke, J., Koch, C., Riedewald, M. & White, W. M. (2007), Massively multi-query join processing in publish/subscribe systems., in 'Proceedings of the ACM SIGMOD International Conference on Management of Data', ACM, Beijing, China, pp. 761--772.
[18]
}}Huo, H., Wang, G., Hui, X., Zhou, R., Ning, B. & Xiao, C. (2006), Efficient query processing for streamed xml fragments, in 'Proceedings of the 11th International Conference on Database Systems for Advanced Applications', Springer, Singapore, pp. 468--482.
[19]
}}Koch, C., Scherzinger, S., Schweikardt, N. & Stegmaier, B. (2004), Schema-based scheduling of event processors and buffer minimization for queries on structured data streams, in 'Proceedings of the Thirtieth International Conference on Very Large Data Bases', Morgan Kaufmann, Toronto, Canada, pp. 228--239.
[20]
}}Kwon, J., Rao, P., Moon, B. & Lee, S. (2005), Fist: Scalable xml document filtering by sequencing twig patterns., in 'Proceedings of the 31st International Conference on Very Large Data Bases', ACM, Trondheim, Norway, pp. 217--228.
[21]
}}Li, X. & Agrawal, G. (2005), Efficient evaluation of xquery over streaming data., in 'Proceedings of the 31st International Conference on Very Large Data Bases', ACM, Trondheim, Norway, pp. 265--276.
[22]
}}Olteanu, D., Furche, T. & Bry, F. (2004), An efficient single-pass query evaluator for xml data streams, in 'Proceedings of the 2004 ACM symposium on Applied computing', ACM, New York, NY, pp. 627--631.
[23]
}}Onizuka, M. (2003), Light-weight xpath processing of xml stream with deterministic automata, in 'Proceedings of the 12th International Conference on Information and Knowledge Management', ACM, New Orleans, LA, pp. 342--349.
[24]
}}Peng, F. & Chawathe, S. S. (2005), 'Xsq: A streaming xpath engine', ACM Trans. Database Syst. 30(2), 577--623.
[25]
}}Rao, P. & Moon, B. (2004), Prix: Indexing and querying xml using prüüfer sequences., in 'Proceedings of the 20th International Conference on Data Engineering', IEEE Computer Society, Boston, MA, pp. 288--300.
[26]
}}The Apache XML Project (2007), 'Xerces2 java parser'. http://xerces.apache.org/xerces2-j/.
[27]
}}Uchiyama, H., Onizuka, M. & Honishi, T. (2005), Distributed xml stream filtering system with high scalability, in 'Proceedings of the 21st International Conference on Data Engineering', IEEE Computer Society, Tokyo, Japan, pp. 968--977.
[28]
}}UW Database Group (2002), 'Xml data repository'. http://www.cs.washington.edu/research/xmldatasets/.
[29]
}}Wang, H., Park, S., Fan, W. & Yu, P. S. (2003), Vist: A dynamic index method for querying xml data by tree structures., in 'Proceedings of the ACM SIGMOD International Conference on Management of Data', ACM, San Diego, CA, pp. 110--121.
Index Terms
- Efficient XQuery join processing in publish/subscribe systems
Recommendations
Massively multi-query join processing in publish/subscribe systems
SIGMOD '07: Proceedings of the 2007 ACM SIGMOD international conference on Management of dataThere has been much recent interest in XML publish/subscribe systems. Some systems scale to thousands of concurrent queries, but support a limited query language (usually a fragment of XPath 1.0). Other systems support more expressive languages, but do ...
Processing and Evaluating Partial Tree Pattern Queries on XML Data
XML query languages typically allow the specification of structural patterns using XPath. Usually, these structural patterns are in the form of trees (Tree-Pattern Queries—TPQs). Finding the occurrences of such patterns in an XML tree is a key operation ...
Structural join and staircase join algorithms of sibling relationship
The processing of XML queries can result in evaluation of various structural relationships. Efficient algorithms for evaluating ancestor-descendant and parent-child relationships have been proposed. Whereas the problems of evaluating preceding-sibling-...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
- Helium, New Zealand
- Australian Comp Soc: Australian Computer Society
- CityLink, New Zealand
- Security Assessment, New Zealand
- New Zealand Computer Society
- CSIRO
- CORE - Computing Research and Education
- Victoria University of Wellington
- The University of New South Wales
- ARC research network in enterprise information infrastructure
- Xero
- Catalyst, New Zealand
Publisher
Australian Computer Society, Inc.
Australia
Publication History
Published: 01 January 2009
Author Tags
Qualifiers
- Research-article
Conference
ADC '09
Sponsor:
- Australian Comp Soc
Acceptance Rates
ADC '09 Paper Acceptance Rate 17 of 43 submissions, 40%;
Overall Acceptance Rate 98 of 224 submissions, 44%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 90Total Downloads
- Downloads (Last 12 months)34
- Downloads (Last 6 weeks)7
Reflects downloads up to 18 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in