A sampling approach for XML query selectivity estimation

ABSTRACT

As the Extensible Markup Language (XML) rapidly establishes itself as the de facto standard for presenting, storing, and exchanging data on the Internet, large volume of XML data and their supporting facilities start to surface. A fast and accurate selectivity estimation mechanism is of practical importance because selectivity estimation plays a fundamental role in XML query optimization. Recently proposed techniques are all based on some forms of structure synopses that could be time-consuming to build and not effective for summarizing complex structure relationships. In this research, we propose an innovative sampling method that can capture the tree structures and intricate relationships among nodes in a simple and effective way. The derived sample tree is stored as a synopsis for selectivity estimation. Extensive experimental results show that, in comparison with the state-of-the-art structure synopses, specifically the TreeSketch and Xseed synopses, our sample tree synopsis applies to a broader range of query types, requires several orders of magnitude less construction time, and generates estimates with considerably better precision for complex datasets.

REFERENCES

• 1: Dblp data set. http://www.informatik.unitrier.de/ley/db/index.html.
• 2: Nicolas Bruno , Nick Koudas , Divesh Srivastava, Holistic twig joins: optimal XML pattern matching, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564727]
• 3: Surajit Chaudhuri , Rajeev Motwani , Vivek Narasayya, On random sampling over joins, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.263-274, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 4: Ting Chen , Jiaheng Lu , Tok Wang Ling, On boosting holism in XML twig pattern matching using structural indexing techniques, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066209]
• 5: 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
• 6: W. G. Cochran. Sampling Techniques. Wiley, 1977.
• 7: 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]
• 8: Sumit Ganguly , Phillip B. Gibbons , Yossi Matias , Avi Silberschatz, Bifocal sampling for skew-resistant join size estimation, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.271-281, June 04-06, 1996, Montreal, Quebec, Canada
• 9: Peter J. Haas , Jeffrey F. Naughton , S. Seshadri , Lynne Stokes, Sampling-Based Estimation of the Number of Distinct Values of an Attribute, Proceedings of the 21th International Conference on Very Large Data Bases, p.311-322, September 11-15, 1995
• 10: Peter J. Haas , Jeffrey F. Naughton , S. Seshadri , Arun N. Swami, Fixed-precision estimation of join selectivity, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.190-201, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153875]
• 11: Wen-Chi Hou , Gultekin Ozsoyoglu , Baldeo K. Taneja, Statistical estimators for relational algebra expressions, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.276-287, March 1988, Austin, Texas, United States [doi>10.1145/308386.308455]
• 12: Wen-Chi Hou , Gultekin Ozsoyoglu , Baldeo K. Taneja, Processing aggregate relational queries with hard time constraints, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.68-77, June 1989, Portland, Oregon, United States
• 13: Haifeng Jiang , Hongjun Lu , Wei Wang, Efficient processing of XML twig queries with OR-predicates, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007578]
• 14: Richard J. Lipton , Jeffrey F. Naughton , Donovan A. Schneider, Practical selectivity estimation through adaptive sampling, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.1-11, May 23-26, 1990, Atlantic City, New Jersey, United States
• 15: Jiaheng Lu , Tok Wang Ling , Chee-Yong Chan , Ting Chen, From region encoding to extended dewey: on efficient processing of XML twig pattern matching, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 16: Cheng Luo , Zhewei Jiang , Wen-Chi Hou , Feng Yan , Chih-Fang Wang, Estimating XML Structural Join Size Quickly and Economically, Proceedings of the 22nd International Conference on Data Engineering, p.62, April 03-07, 2006 [doi>10.1109/ICDE.2006.63]
• 17: Mirella M. Moro , Zografoula Vagena , Vassilis J. Tsotras, Tree-pattern queries on a lightweight XML processor, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 18: Neoklis Polyzotis , Minos Garofalakis, Structure and value synopses for XML data graphs, Proceedings of the 28th international conference on Very Large Data Bases, p.466-477, August 20-23, 2002, Hong Kong, China
• 19: 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]
• 20: Neoklis Polyzotis , Minos Garofalakis , Yannis Ioannidis, Approximate XML query answers, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007599]
• 21: 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
• 22: Sheldon M. Ross, Introduction to Probability Models, Ninth Edition, Academic Press, Inc., Orlando, FL, 2006
• 23: A. R. Schmidt , Florian Waas , Martin L. Kersten , D. Florescu , I. Manolescu , M. J. Carey , R. Busse, The XML benchmark project, CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 2001
• 24: 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]
• 25: Ning Zhang , M. Tamer Ozsu , Ashraf Aboulnaga , Ihab F. Ilyas, XSEED: Accurate and Fast Cardinality Estimation for XPath Queries, Proceedings of the 22nd International Conference on Data Engineering, p.61, April 03-07, 2006 [doi>10.1109/ICDE.2006.178]