On verifying consistency of XML specifications

ABSTRACT

XML specifications often consist of a type definition (typically, a DTD) and a set of integrity constraints. It has been shown previously that such specifications can be inconsistent, and thus it is often desirable to check consistency at compile-time. It is known that for general keys and foreign keys, and DTDs, the consistency problem is undecidable; however, it becomes NP-complete when all keys are one-attribute (unary), and tractable, if no foreign keys are used.In this paper, we consider a variety of constraints for XML data, and study the complexity of the consistency problem. Our main conclusion is that in the presence of foreign keys, compile-time verification of consistency is usually infeasible. We look at two types of constraints: absolute (that hold in the entire document), and relative (that only hold in a part of the document). For absolute constraints, we extend earlier decidability results to the case of multi-attribute keys and unary foreign keys, and to the case of constraints involving regular expressions, providing lower and upper bounds in both cases. For relative constraints, we show that even for unary constraints, the consistency problem is undecidable. We also establish a number of restricted decidable cases.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: Serge Abiteboul , Victor Vianu, Regular path queries with constraints, Journal of Computer and System Sciences, v.58 n.3, p.428-452, June 1999 [doi>10.1006/jcss.1999.1627]
• 3: Chaitan Baru , Amarnath Gupta , Bertram Ludäscher , Richard Marciano , Yannis Papakonstantinou , Pavel Velikhov , Vincent Chu, XML-based information mediation with MIX, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.597-599, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 4: 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
• 5: Peter Buneman , Susan Davidson , Wenfei Fan , Carmem Hara , Wang-Chiew Tan, Keys for XML, Proceedings of the 10th international conference on World Wide Web, p.201-210, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.371984]
• 6: Peter Buneman , Susan B. Davidson , Wenfei Fan , Carmem S. Hara , Wang Chiew Tan, Reasoning about Keys for XML, Revised Papers from the 8th International Workshop on Database Programming Languages, p.133-148, September 08-10, 2001
• 7: Peter Buneman , Wenfei Fan , Scott Weinstein, Path constraints in semistructured databases, Journal of Computer and System Sciences, v.61 n.2, p.146-193, Oct. 2000 [doi>10.1006/jcss.2000.1710]
• 8: D. Calvanese, G. De Giacomo, and M. Lenzerini. Representing and reasoning on XML documents: A description logic approach. JLC 9 (1999), 295-318.
• 9: Diego Calvanese , Maurizio Lenzerini, Making object-oriented schemas more expressive, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.243-254, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182620]
• 10: Diego Calvanese , Maurizio Lenzerini, On the Interaction Between ISA and Cardinality Constraints, Proceedings of the Tenth International Conference on Data Engineering, p.204-213, February 14-18, 1994
• 11: M. Carey et al. XPERANTO: Publishing object-relational data as XML. In WebDB 2000.
• 12: Stavros S. Cosmadakis , Paris C. Kanellakis , Moshe Y. Vardi, Polynomial-time implication problems for unary inclusion dependencies, Journal of the ACM (JACM), v.37 n.1, p.15-46, Jan. 1990 [doi>10.1145/78935.78937]
• 13: Anat Eyal , Tova Milo, Integrating and customizing heterogeneous e-commerce applications, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.1, p.16-38, August 2001
• 14: Wenfei Fan , Leonid Libkin, On XML integrity constraints in the presence of DTDs, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.114-125, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375568]
• 15: Mary F. Fernandez , Daniela Florescu , Alon Y. Levy , Dan Suciu, Verifying Integrity Constraints on Web Sites, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.614-619, July 31-August 06, 1999
• 16: M. Fernandez, A. Morishima, D. Suciu, and W. Tan. Publishing relational data in XML: the SilkRoute approach. IEEE Data Eng. Bull., 24(2):12-19, 2001.
• 17: D. Florescu and D. Kossmann. Storing and querying XML data using an RDMBS. IEEE Data Eng. Bull., 22(3):27-34, 1999.
• 18: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 19: P. C. Kanellakis. On the computational complexity of cardinality constraints in relational databases. Information Processing Letters, 11(2):98-101, 1980.
• 20: D. Lee and W. W. Chu. Constraints-preserving transformation from XML document type definition to relational schema. In ER'2000.
• 21: Yuri V. Matiyasevich, Hilbert's tenth problem, MIT Press, Cambridge, MA, 1993
• 22: David A. McAllester , Robert Givan , Carl Witty , Dexter Kozen, Tarskian Set Constraints, Proceedings of the 11th Annual IEEE Symposium on Logic in Computer Science, p.138, July 27-30, 1996
• 23: Frank Neven, Extensions of Attribute Grammars for Structured Document Queries, Revised Papers from the 7th International Workshop on Database Programming Languages: Research Issues in Structured and Semistructured Database Programming, p.99-116, September 01-03, 1999
• 24: Christos H. Papadimitriou, On the complexity of integer programming, Journal of the ACM (JACM), v.28 n.4, p.765-768, Oct. 1981 [doi>10.1145/322276.322287]
• 25: C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
• 26: Jayavel Shanmugasundaram , Eugene J. Shekita , Rimon Barr , Michael J. Carey , Bruce G. Lindsay , Hamid Pirahesh , Berthold Reinwald, Efficiently Publishing Relational Data as XML Documents, Proceedings of the 26th International Conference on Very Large Data Bases, p.65-76, September 10-14, 2000
• 27: Jayavel Shanmugasundaram , Kristin Tufte , Chun Zhang , Gang He , David J. DeWitt , Jeffrey F. Naughton, Relational Databases for Querying XML Documents: Limitations and Opportunities, Proceedings of the 25th International Conference on Very Large Data Bases, p.302-314, September 07-10, 1999
• 28: W3C. Document Object Model (DOM) Level 1 Specification. W3C Recommendation, Oct. 1998.
• 29: W3C. Extensible Markup Language (XML) 1.0. W3C Recommendation, Feb. 1998.
• 30: W3C. XML-Data. W3C Note, Jan. 1998.
• 31: W3C. XML Path Language (XPath). Nov. 1999.
• 32: W3C. XSL Transformations (XSLT). Nov. 1999.
• 33: W3C. XML Schema. W3C Working Draft, May 2001.
• 34: W3C. XQuery 1.0: An XML Query Language. W3C Working Draft, June 2001.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.2 Document Preparation
          Subjects: Markup languages

Additional Classification:
  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.2 Document Preparation

          Nouns: XML

General Terms:
Design, Languages, Performance, Theory