Approximate XML query answers

ABSTRACT

The rapid adoption of XML as the standard for data representation and exchange foreshadows a massive increase in the amounts of XML data collected, maintained, and queried over the Internet or in large corporate data-stores. Inevitably, this will result in the development of on-line decision support systems, where users and analysts interactively explore large XML data sets through a declarative query interface (e.g., XQuery or XSLT). Given the importance of remaining interactive, such on-line systems can employ approximate query answers as an effective mechanism for reducing response time and providing users with early feedback. This approach has been successfully used in relational systems and it becomes even more compelling in the XML world, where the evaluation of complex queries over massive tree-structured data is inherently more expensive.In this paper, we initiate a study of approximate query answering techniques for large XML databases. Our approach is based on a novel, conceptually simple, yet very effective XML-summarization mechanism: TREESKETCH synopses. We demonstrate that, unlike earlier techniques focusing solely on selectivity estimation, our TREESKETCH synopses are much more effective in capturing the complete tree structure of the underlying XML database. We propose novel construction algorithms for building TREESKETCH summaries of limited size, and describe schemes for processing general XML twig queries over a concise TREESKETCH in order to produce very fast, approximate tree-structured query answers. To quantify the quality of such approximate answers, we propose a novel, intuitive error metric that captures the quality of the approximation in terms of both the overall structure of the XML tree and the distribution of document edges. Experimental results on real-life and synthetic data sets verify the effectiveness of our TREESKETCH synopses in producing fast, accurate approximate answers and demonstrate their benefits over previously proposed techniques that focus solely on selectivity estimation. In particular, TREESKETCHes yield faster, more accurate approximate answers and selectivity estimates, and are more efficient to construct. To the best of our knowledge, ours is the first work to address the timely problem of producing fast, approximate tree-structured answers for complex XML queries.

REFERENCES

• 1: Ashraf Aboulnaga , Alaa R. Alameldeen , Jeffrey F. Naughton, Estimating the Selectivity of XML Path Expressions for Internet Scale Applications, Proceedings of the 27th International Conference on Very Large Data Bases, p.591-600, September 11-14, 2001
• 2: P. Buneman, M. Grohe, and C. Koch. "Path Queries on Compressed XML". In Proceedings of the 29th Intl. Conf. on Very Large Data Bases, 2003.
• 3: Kaushik Chakrabarti , Minos N. Garofalakis , Rajeev Rastogi , Kyuseok Shim, Approximate Query Processing Using Wavelets, Proceedings of the 26th International Conference on Very Large Data Bases, p.111-122, September 10-14, 2000
• 4: Don Chamberlin, James Clark, Daniela Florescu, Jonathan Robie, Jérôme Siméon, and Mugur Stefanescu. "XQuery 1.0: An XML Query Language". W3C Working Draft, 2001.
• 5: Zhimin Chen, H. V. Jagadish, Laks V. S. Laksmanan, and Stelios Paparizos. "From Tree Patterns to Generalized Tree Patterns: On Efficient Eavluation of XQuery". In Proceedings of the 29th Intl. Conf. on Very Large Data Bases, 2003.
• 6: Zhiyuan Chen , H. V. Jagadish , Flip Korn , Nick Koudas , S. Muthukrishnan , Raymond T. Ng , Divesh Srivastava, Counting Twig Matches in a Tree, Proceedings of the 17th International Conference on Data Engineering, p.595-604, April 02-06, 2001
• 7: James Clark. "XSL Transformations (XSLT), Version 1.0". W3C Recommendation, November 1999.
• 8: James Clark and Steve DeRose. "XML Path Language (XPath), Version 1.0". W3C Recommendation, November 1999.
• 9: Juliana Freire , Jayant R. Haritsa , Maya Ramanath , Prasan Roy , Jérôme Siméon, StatiX: making XML count, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564713]
• 10: Yannis E. Ioannidis , Viswanath Poosala, Histogram-Based Approximation of Set-Valued Query-Answers, Proceedings of the 25th International Conference on Very Large Data Bases, p.174-185, September 07-10, 1999
• 11: Exploiting Local Similarity for Indexing Paths in Graph-Structured Data, Proceedings of the 18th International Conference on Data Engineering, p.129, February 26-March 01, 2002
• 12: L. Lim, M. Wang, S. Padmanabhan, J. S. Vitter, and R. Parr. XPathLearner: An On-Line Self-Tuning Markov Histogram for XML Path Selectivity Estimation. In Proceedings of the 28th Intl. Conf. on Very Large Data Bases, 2002.
• 13: Jason McHugh , Jennifer Widom, Query Optimization for XML, Proceedings of the 25th International Conference on Very Large Data Bases, p.315-326, September 07-10, 1999
• 14: Tova Milo , Dan Suciu, Index Structures for Path Expressions, Proceeding of the 7th International Conference on Database Theory, p.277-295, January 10-12, 1999
• 15: Neoklis Polyzotis , Minos Garofalakis, Statistical synopses for graph-structured XML databases, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564733]
• 16: N. Polyzotis and M. Garofalakis. "Structure and Value Synopses for XML Data Graphs". In Proceedings of the 28th Intl. Conf. on Very Large Data Bases, 2002.
• 17: Neoklis Polyzotis, Minos Garofalakis, and Yannis Ioannidis. Approximate XML Query Answers. 2004.
• 18: Neoklis Polyzotis , Minos Garofalakis , Yannis Ioannidis, Selectivity Estimation for XML Twigs, Proceedings of the 20th International Conference on Data Engineering, p.264, March 30-April 02, 2004
• 19: Cecilia Magdalena Procopiuc , Pankaj K. Agarwal, Geometric techniques for clustering: theory and practice, 2001
• 20: Dennis Shasha , Kaizhong Zhang, Fast algorithms for the unit cost editing distance between trees, Journal of Algorithms, v.11 n.4, p.581-621, Dec. 1990 [doi>10.1016/0196-6774(90)90011-3]
• 21: Wei Wang , Haifeng Jiang , Hongjun Lu , Jeffrey Xu Yu, Containment join size estimation: models and methods, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872777]
• 22: Yuqing Wu , Jignesh M. Patel , H. V. Jagadish, Estimating Answer Sizes for XML Queries, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.590-608, March 25-27, 2002
• 23: Tian Zhang , Raghu Ramakrishnan , Miron Livny, BIRCH: an efficient data clustering method for very large databases, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.103-114, June 04-06, 1996, Montreal, Quebec, Canada