XML with incomplete information: models, properties, and query answering

ABSTRACT

We study models of incomplete information for XML, their computational properties, and query answering. While our approach is motivated by the study of relational incompleteness, incomplete information in XML documents may appear not only as null values but also as missing structural information. Our goal is to provide a classification of incomplete descriptions of XML documents, and separate features - or groups of features - that lead to hard computational problems from those that admit efficient algorithms. Our classification of incomplete information is based on the combination of null values with partial structural descriptions of documents. The key computational problems we consider are consistency of partial descriptions, representability of complete documents by incomplete ones, and query answering. We show how factors such as schema information, the presence of node ids, and missing structural information affect the complexity of these main computational problems, and find robust classes of incomplete XML descriptions that permit tractable query evaluation.

REFERENCES

• 1: 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]
• 2: 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
• 3: Serge Abiteboul , Luc Segoufin , Victor Vianu, Representing and querying XML with incomplete information, ACM Transactions on Database Systems (TODS), v.31 n.1, p.208-254, March 2006 [doi>10.1145/1132863.1132869]
• 4: S. Abiteboul, R. Hull and V. Vianu. Foundations of Databases, Addison Wesley, 1995.
• 5: Marcelo Arenas , Wenfei Fan , Leonid Libkin, On the Complexity of Verifying Consistency of XML Specifications, SIAM Journal on Computing, v.38 n.3, p.841-880, June 2008 [doi>10.1137/050646895]
• 6: Marcelo Arenas , Leonid Libkin, XML data exchange: Consistency and query answering, Journal of the ACM (JACM), v.55 n.2, p.1-72, May 2008 [doi>10.1145/1346330.1346332]
• 7: Michael Benedikt , Wenfei Fan , Floris Geerts, XPath satisfiability in the presence of DTDs, Journal of the ACM (JACM), v.55 n.2, p.1-79, May 2008 [doi>10.1145/1346330.1346333]
• 8: H. Bjorklund, W. Martens, T. Schwentick. Conjunctive query containment over trees. DBPL'07, pages 66--80.
• 9: Henrik Björklund , Wim Martens , Thomas Schwentick, Optimizing Conjunctive Queries over Trees Using Schema Information, Proceedings of the 33rd international symposium on Mathematical Foundations of Computer Science, August 25-29, 2008, Toruń, Poland [doi>10.1007/978-3-540-85238-4_10]
• 10: Andrea Calì , Domenico Lembo , Riccardo Rosati, On the decidability and complexity of query answering over inconsistent and incomplete databases, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.260-271, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773179]
• 11: D. Calvanese, G. De Giacomo, M. Lenzerini. Semi-structured data with constraints and incomplete information. Description Logics, 1998.
• 12: D. Calvanese, G. De Giacomo, M. Lenzerini. Representing and reasoning on XML documents: a description logic approach. J. Log. Comput. 9 (1999), 295--318.
• 13: Sara Cohen , Benny Kimelfeld , Yehoshua Sagiv, Incorporating constraints in probabilistic XML, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376916.1376933]
• 14: Claire David, Complexity of Data Tree Patterns over XML Documents, Proceedings of the 33rd international symposium on Mathematical Foundations of Computer Science, August 25-29, 2008, Toruń, Poland [doi>10.1007/978-3-540-85238-4_22]
• 15: Alin Deutsch , Val Tannen, Reformulation of XML Queries and Constraints, Proceedings of the 9th International Conference on Database Theory, p.225-241, January 08-10, 2003
• 16: Document Object Model (DOM). W3C Recommendation, April 2004. http://www.w3.org/TR/DOM--Level--3--Core.
• 17: Ronald Fagin , Phokion G. Kolaitis , Renée J. Miller , Lucian Popa, Data exchange: semantics and query answering, Theoretical Computer Science, v.336 n.1, p.89-124, 25 May 2005 [doi>10.1O16/j.tcs.2004.10.033]
• 18: Philippa A. Gardner , Gareth D. Smith , Mark J. Wheelhouse , Uri D. Zarfaty, Local Hoare reasoning about DOM, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376916.1376953]
• 19: Georg Gottlob , Christoph Koch , Klaus U. Schulz, Conjunctive queries over trees, Journal of the ACM (JACM), v.53 n.2, p.238-272, March 2006 [doi>10.1145/1131342.1131345]
• 20: 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]
• 21: Y. Kanza, W. Nutt, Y. Sagiv. Querying incomplete information in semistructured data. JCSS 64 (2002), 655--693.
• 22: Ph. Kolaitis and M. Vardi. A logical approach to constraint satisfaction. In Finite Model Theory and its Applications, Springer 2007, pages 339--370.
• 23: Maurizio Lenzerini, Data integration: a theoretical perspective, 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.543644]
• 24: Dan Olteanu , Christoph Koch , Lyublena Antova, World-set decompositions: Expressiveness and efficient algorithms, Theoretical Computer Science, v.403 n.2-3, p.265-284, August, 2008 [doi>10.1016/j.tcs.2008.05.004]
• 25: T. Schwentick. A little bit infinite? On adding data to finitely labelled structures. In STACS'08, pages 17--18.
• 26: L. Segoufin. Automata and logics for words and trees over an infinite alphabet. In CSL'06, pages 41--57.
• 27: Pierre Senellart , Serge Abiteboul, On the complexity of managing probabilistic XML data, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China [doi>10.1145/1265530.1265570]
• 28: Moshe Y Vardi, Querying logical databases, Journal of Computer and System Sciences, v.33 n.2, p.142-160, Oct. 1986 [doi>10.1016/0022-0000(86)90016-4]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

General Terms:
Algorithms, Languages, Theory

Keywords:
certain answers, consistency, incomplete information, membership, query answering, xml