Answering XML queries by means of data summaries

ABSTRACT

XML is a rather verbose representation of semistructured data, which may require huge amounts of storage space. We propose a summarized representation of XML data, based on the concept of instance pattern, which can both provide succinct information and be directly queried. The physical representation of instance patterns exploits itemsets or association rules to summarize the content of XML datasets. Instance patterns may be used for (possibly partially) answering queries, either when fast and approximate answers are required, or when the actual dataset is not available, for example, it is currently unreachable. Experiments on large XML documents show that instance patterns allow a significant reduction in storage space, while preserving almost entirely the completeness of the query result. Furthermore, they provide fast query answers and show good scalability on the size of the dataset, thus overcoming the document size limitation of most current XQuery engines.

REFERENCES

• 1: Swarup Acharya , Phillip B. Gibbons , Viswanath Poosala, Aqua: A Fast Decision Support Systems Using Approximate Query Answers, Proceedings of the 25th International Conference on Very Large Data Bases, p.754-757, September 07-10, 1999
• 2: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 3: Enrico Augurusa , Daniele Braga , Alessandro Campi , Stefano Ceri, Design and implementation of a graphical interface to XQuery, Proceedings of the 2003 ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida [doi>10.1145/952532.952759]
• 4: Baralis, E., Garza, P., Quintarelli, E., and Tanca, L. 2004. Summarizing XML data by means of association rules. In Current Trends in Database Technology - EDBT 2004 Workshops, W. Lindner, M. Mesiti, C. Türker, Y. Tzitzikas, and A. Vakali, Eds. Lecture Notes in Computer Science, vol. 3268. Springer-Verlag, Berlin, Heidelberg, Germany, 260--269.
• 5: Baralis, E., Garza, P., Quintarelli, E., and Tanca, L. 2006. Answering XML queries by means of data summaries. Tech. Rep. 2006.43, Politecnico di Milano, Milano, Italy. March.
• 6: Boncz, P., Flokstra, J., Grust, T., van Keulen, M., Manegold, S., Mullender, S., Nes, N., Rittinger, J., Teubner, J., and Zhang, Y. 2006. MonetDB/XQuery. http://monetdb.cwi.nl/XQuery/.
• 7: Boncz, P. A., Grust, T., Manegold, S., Rittinger, J., and Teubner, J. 2005. Pathfinder: Relational XQuery Over Multi-Gigabyte XML Inputs In Interactive Time. Tech. Rep. INS-E0503, CWI, Amsterdam, The Netherlands. March
• 8: Daniele Braga , Alessandro Campi , Stefano Ceri, XQBE (XQuery By Example): A visual interface to the standard XML query language, ACM Transactions on Database Systems (TODS), v.30 n.2, p.398-443, June 2005 [doi>10.1145/1071610.1071613]
• 9: Daniele Braga , Alessandro Campi , Mika Klemettinen , Pier Luca Lanzi, Mining Association Rules from XML Data, Proceedings of the 4th International Conference on Data Warehousing and Knowledge Discovery, p.21-30, September 04-06, 2002
• 10: Peter Buneman , Susan Davidson , Gerd Hillebrand , Dan Suciu, A query language and optimization techniques for unstructured data, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.505-516, June 04-06, 1996, Montreal, Quebec, Canada
• 11: 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
• 12: Qun Chen , Andrew Lim , Kian Win Ong, D(k)-index: an adaptive structural summary for graph-structured data, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872776]
• 13: Chin-Wan Chung , Jun-Ki Min , Kyuseok Shim, APEX: an adaptive path index for XML data, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564706]
• 14: Mariano P. Consens , Alberto O. Mendelzon, GraphLog: a visual formalism for real life recursion, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.404-416, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298591]
• 15: Damiani, E., Oliboni, B., Quintarelli, E., and Tanca, L. 2003. Modeling Semistructured Data by using graph-based constraints. Tech. Rep. 27/03, Politecnico di Milano. Dipartimento di Elettronica e Informazione. July.
• 16: Min Fang , Narayanan Shivakumar , Hector Garcia-Molina , Rajeev Motwani , Jeffrey D. Ullman, Computing Iceberg Queries Efficiently, Proceedings of the 24rd International Conference on Very Large Data Bases, p.299-310, August 24-27, 1998
• 17: Feinberg, G. 2005. Anatomy of a Native XML Database. Tech. rep., Sleepycat Software.
• 18: Feinberg, G. 2006. Berkeley DB XML. http://www.sleepycat.com/products/bdbxml.html/.
• 19: Feng, L. and Dillon, T. 2004. Mining XML-Enabled Association Rules with Templates. In Proceedings of the 3rd International Workshop on Knowledge Discovery in Inductive Databases, B. Goethals and A. Siebes, Eds. Lecture Notes in Computer Science, vol. 3377. Springer-Verlag, Berlin, Heidelberg, Germany, 66--88.
• 20: Fomichev, A., Grinev, M., and Kuznetsov, S. 2006. Sedna: A native XML DBMS. In 32nd Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2006, J. Wiedermann, G. Tel, J. Pokorný, M. Bieliková, and J. Stuller, Eds. Lecture Notes in Computer Science, vol. 3831. Springer-Verlag, Berlin, Heidelberg, Germany, 272--281.
• 21: Bart Goethals , Mohammed J. Zaki, Advances in frequent itemset mining implementations: report on FIMI'03, ACM SIGKDD Explorations Newsletter, v.6 n.1, June 2004 [doi>10.1145/1007730.1007744]
• 22: Jiawei Han , Jian Pei , Guozhu Dong , Ke Wang, Efficient computation of Iceberg cubes with complex measures, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.1-12, May 21-24, 2001, Santa Barbara, California, United States
• 23: Venky Harinarayan , Anand Rajaraman , Jeffrey D. Ullman, Implementing data cubes efficiently, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.205-216, June 04-06, 1996, Montreal, Quebec, Canada
• 24: Hao He , Jun Yang, Multiresolution Indexing of XML for Frequent Queries, Proceedings of the 20th International Conference on Data Engineering, p.683, March 30-April 02, 2004
• 25: Jones, K. S. and Willett, P. 1997. Readings in information retrieval. Morgan-Kaufmann, San Francisco, CA.
• 26: Kay, M. 2006. Saxon---The XSLT and XQuery processor. http://saxon.sourceforge.net/.
• 27: Ley, M. 2005. DBLP bibliography server. http://dblp.uni-trier.de/xml.
• 28: Quanzhong Li , Bongki Moon, Indexing and Querying XML Data for Regular Path Expressions, Proceedings of the 27th International Conference on Very Large Data Bases, p.361-370, September 11-14, 2001
• 29: Wolfgang Meier, eXist: An Open Source Native XML Database, Revised Papers from the NODe 2002 Web and Database-Related Workshops on Web, Web-Services, and Database Systems, p.169-183, October 07-10, 2002
• 30: Merialdo, P. 2003. SIGMOD RECORD in XML. http://www.acm.org/sigmod/record/xml.
• 31: R. Milner, A Calculus of Communicating Systems, Springer-Verlag New York, Inc., Secaucus, NJ, 1982
• 32: A. Motro, Using integrity constraints to provide intensional answers to relational queries, Proceedings of the 15th international conference on Very large data bases, p.237-246, July 1989, Amsterdam, The Netherlands
• 33: Yannis Papakonstantinou , Hector Garcia-Molina , Jennifer Widom, Object Exchange Across Heterogeneous Information Sources, Proceedings of the Eleventh International Conference on Data Engineering, p.251-260, March 06-10, 1995
• 34: Jan Paredaens , Peter Peelman , Letizia Tanca, G-Log: A Graph-Based Query Language, IEEE Transactions on Knowledge and Data Engineering, v.7 n.3, p.436-453, June 1995 [doi>10.1109/69.390249]
• 35: David Park, Concurrency and Automata on Infinite Sequences, Proceedings of the 5th GI-Conference on Theoretical Computer Science, p.167-183, March 23-25, 1981
• 36: Porter, M. F. 1980. An algorithm for suffix stripping. Program 14, 3, 130--137.
• 37: Runapongsa, K., Patel, J. M., Bordawekar, R., and Padmanabhan, S. 2004. XIST: An XML index selection tool. In Database and XML Technologies: Second International XML Database Symposium, XSym 2004, Z. Bellahsène, T. Milo, M. Rys, D. Suciu, and R. Unland, Eds. Lecture Notes in Computer Science, vol. 3186. Springer-Verlag, Berlin, Heidelberg, Germany, 219--234.
• 38: John Staples , Peter J. Robinson, Unification of quantified terms, Proc. of a workshop on Graph reduction, p.426-450, September 1987, Santa Fe, New Mexico, United States
• 39: TPC-H. 2005. The TPC benchmark H. Transaction Processing Performance Council. http://www.tpc.org/tpch/default.asp.
• 40: W3C98b 1998. World Wide Web Consortium. Extensible Markup Language (XML) 1.0. http://www.w3C.org/TR/REC-xml/.
• 41: X-Hive Corporation 2006. X-Hive/DB. http://www.x-hive.com/.
• 42: Xin, D., Han, J., Li, X., and Wah, B. W. 2003. Star-cubing: Computing iceberg cubes by top-down and bottom-up integration. In VLDB '03: Proceedings of 29th International Conference on Very Large Data Bases. Morgan-Kaufmann, San Francisco, CA, 476--487.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models

General Terms:
Languages, Theory

Keywords:
Association rules, data mining, data summarization, intensional answers, itemsets, semistructured data