Representing and querying XML with incomplete information

ABSTRACT

We study the representation and querying of XML with incomplete information. We consider a simple model for XML data and their DTDs, a very simple query language, and a representation system for incomplete information in the spirit of the representations systems developed by Imielinski and Lipski [1984] for relational databases. In the scenario we consider, the incomplete information about an XML document is continuously enriched by successive queries to the document. We show that our representation system can represent partial information about the source document acquired by successive queries, and that it can be used to intelligently answer new queries. We also consider the impact on complexity of enriching our representation system or query language with additional features. The results suggest that our approach achieves a practically appealing balance between expressiveness and tractability.

REFERENCES

• 1: Serge Abiteboul , Omar Benjelloun , Bogdan Cautis , Ioana Manolescu , Tova Milo , Nicoleta Preda, Lazy query evaluation for Active XML, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007596]
• 2: Serge Abiteboul , Oliver M. Duschka, Complexity of answering queries using materialized views, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.254-263, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275516]
• 3: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 4: Serge Abiteboul , Paris Kanellakis , Gösta Grahne, On the representation and querying of sets of possible worlds, Theoretical Computer Science, v.78 n.1, p.159-187, Jan. 21, 1991
• 5: Serge Abiteboul , Luc Segoufin , Victor Vianu, Representing and querying XML with incomplete information, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.150-161, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375571]
• 6: Sihem Amer-Yahia , SungRan Cho , Laks V. S. Lakshmanan , Divesh Srivastava, Minimization of tree pattern queries, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.497-508, May 21-24, 2001, Santa Barbara, California, United States
• 7: Balmin, A., Ozcan, F., Beyer, K., Cochrane, R., and Pirahesh, H. 2004. A framework for using materialized XPath views in XML query processing. In Proceedings of the International Conference on Very Large Data Bases (VLDB).
• 8: Catriel Beeri , Tova Milo, Schemas for Integration and Translation of Structured and Semi-structured Data, Proceeding of the 7th International Conference on Database Theory, p.296-313, January 10-12, 1999
• 9: Bose, S. and Fegaras, L. 2005. XFrag: A query processing framework for fragmented XML data. In Proceedings of the WebDB.
• 10: Bruggemann-Klein, M.Murata, A., and Wood, D. 1998. Regular tree languages over non-ranked alphabets. Unpublished manuscript.
• 11: Calvanese, D., De Giacomo, G., and Lenzerini, M. 1998. Semi-structured data with constraints and incomplete information. In Proceedings of the Description Logic Workshop (DL'98). 11--20.
• 12: Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini , Moshe Y. Vardi, Rewriting of regular expressions and regular path queries, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.194-204, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303996]
• 13: Answering Regular Path Queries Using Views, Proceedings of the 16th International Conference on Data Engineering, p.389, February 28-March 03, 2000
• 14: Diego Calvanese , Moshe Y. Vardi , Giuseppe de Giacomo , Maurizio Lenzerini, View-based query processing for regular path queries with inverse, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.58-66, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335207]
• 15: Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini , Moshe Y. Vardi, Lossless regular views, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543646]
• 16: Surajit Chaudhuri , Ravi Krishnamurthy , Spyros Potamianos , Kyuseok Shim, Optimizing Queries with Materialized Views, Proceedings of the Eleventh International Conference on Data Engineering, p.190-200, March 06-10, 1995
• 17: Sophie Cluet , Claude Delobel , Jérǒme Siméon , Katarzyna Smaga, Your mediators need data conversion!, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.177-188, June 01-04, 1998, Seattle, Washington, United States
• 18: Codd, T. 1975. Understanding relations (installment #7). FDT Bull. of ACM Sigmod 7. 23--28.
• 19: Stavros S. Cosmadakis, The complexity of evaluating relational queries, Information and Control, v.58 n.1-3, p.101-112, July/Aug./Sept. 1983 [doi>10.1016/S0019-9958(83)80059-X]
• 20: Flesca, S., Furfaro1, F., Greco, S., and Zumpano, E. 2003. Repairs and consistent answers for xml data with functional dependencies. In Proceedings of the International XML Database Symposium. 238--253.
• 21: Hector Garcia-Molina , Wilburt Labio , Jun Yang, Expiring Data in a Warehouse, Proceedings of the 24rd International Conference on Very Large Data Bases, p.500-511, August 24-27, 1998
• 22: G. Grahne, Problem of Incomplete Information in Relational Databases, Springer-Verlag New York, Inc., Secaucus, NJ, 1991
• 23: Alon Y. Halevy, Theory of answering queries using views, ACM SIGMOD Record, v.29 n.4, p.40-47, Dec. 2000 [doi>10.1145/369275.369284]
• 24: Honeyman, P., Ladner, R., and Yannakakis, M. 1980. Testing the universal instance assumption. Information Processing Letters 10, 1, 14--19.
• 25: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 26: Tomasz Imieliński , Witold Lipski, Jr., Incomplete Information in Relational Databases, Journal of the ACM (JACM), v.31 n.4, p.761-791, Oct. 1984 [doi>10.1145/1634.1886]
• 27: Yaron Kanza , Werner Nutt , Yehoshua Sagiv, Queries with incomplete answers over semistructured data, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.227-236, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303999]
• 28: Wilburt J. Labio , Yue Zhuge , Janet L. Wiener , Himanshu Gupta , Héctor García-Molina , Jennifer Widom, The WHIPS prototype for data warehouse creation and maintenance, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.557-559, May 11-15, 1997, Tucson, Arizona, United States
• 29: Alon Y. Levy , Alberto O. Mendelzon , Yehoshua Sagiv, Answering queries using views (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.95-104, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.220198]
• 30: David Maier , Yehoshua Sagiv , Mihalis Yannakakis, On the Complexity of Testing Implications of Functional and Join Dependencies, Journal of the ACM (JACM), v.28 n.4, p.680-695, Oct. 1981 [doi>10.1145/322276.322280]
• 31: Bhushan Mandhani , Dan Suciu, Query caching and view selection for XML databases, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 32: Gerome Miklau , Dan Suciu, Containment and equivalence for a fragment of XPath, Journal of the ACM (JACM), v.51 n.1, p.2-45, January 2004 [doi>10.1145/962446.962448]
• 33: Tova Milo , Serge Abiteboul , Bernd Amann , Omar Benjelloun , Fred Dang Ngoc, Exchanging intensional XML data, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872793]
• 34: Tova Milo , Dan Suciu , Victor Vianu, Typechecking for XML transformers, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.11-22, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335171]
• 35: Tova Milo , Dan Suciu , Victor Vianu, Typechecking for XML transformers, Journal of Computer and System Sciences, v.66 n.1, p.66-97, 01 February 2003 [doi>10.1016/S0022-0000(02)00030-2]
• 36: Yannis Papakonstantinou , Victor Vianu, DTD inference for views of XML data, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.35-46, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335173]
• 37: Anand Rajaraman , Yehoshua Sagiv , Jeffrey D. Ullman, Answering queries using templates with binding patterns (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.105-112, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.220199]
• 38: Raymond Reiter, A sound and sometimes complete query evaluation algorithm for relational databases with null values, Journal of the ACM (JACM), v.33 n.2, p.349-370, April 1986 [doi>10.1145/5383.5388]
• 39: Schwentick, T. 2000. Personal communication.
• 40: Stockmeier, L. 1974. The complexity of decision problems in automata theory and logic. Ph.D. thesis. Report MAC TR-133, Project MAC. Massachusetts Institute of Technology.
• 41: Moshe Y. Vardi, The complexity of relational query languages (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.137-146, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802186]
• 42: Moshe Vardi, On the integrity of databases with incomplete information, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.252-266, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15419]
• 43: Zaniolo, C. 1984. Database relations with null values. J. Comput. Syst. Sci. 28, 1, 142--166.

INDEX TERMS

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

General Terms:
Design, Theory

Keywords:
Incomplete information, XML