On XML integrity constraints in the presence of DTDs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On XML integrity constraints in the presence of DTDs

Full text

Pdf (399 KB)

Source

Journal of the ACM (JACM) archive
Volume 49 , Issue 3 (May 2002) table of contents

Pages: 368 - 406

Year of Publication: 2002

ISSN:0004-5411

Authors

Wenfei Fan	Bell Laboratories, Murray Hill, New Jersey
Leonid Libkin	University of Toronto, Toronto, Ontario, Canada

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 15, Downloads (12 Months): 84, Citation Count: 33

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/567112.567117 What is a DOI?

ABSTRACT

The article investigates XML document specifications with DTDs and integrity constraints, such as keys and foreign keys. We study the consistency problem of checking whether a given specification is meaningful: that is, whether there exists an XML document that both conforms to the DTD and satisfies the constraints. We show that DTDs interact with constraints in a highly intricate way and as a result, the consistency problem in general is undecidable. When it comes to unary keys and foreign keys, the consistency problem is shown to be NP-complete. This is done by coding DTDs and integrity constraints with linear constraints on the integers. We consider the variations of the problem (by both restricting and enlarging the class of constraints), and identify a number of tractable cases, as well as a number of additional NP-complete ones. By incorporating negations of constraints, we establish complexity bounds on the implication problem, which is shown to be coNP-complete for unary keys and foreign keys.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked 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	Apparao, V., et al.1998. Document Object Model (DOM) Level 1 Specification. W3C Recommendation, Oct. http://www.w3.org/TR/REC-DOM-Level-1/.
	4	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
	5	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
	6	Bray, T., Paoli, J., and Sperberg-McQueen, C. M.1998. Extensible Markup Language (XML) 1.0. W3C Recommendation, Feb. http://www.w3.org/TR/REC-xml/.
	7	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]
	8	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
	9	Peter Buneman , Wenfie Fan , Scott Weinstein, Interaction between path and type constraints, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.56-67, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303982]
	10	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]
	11	Calvanese, D., De Giacomo, G., and Lenzerini, M.1999. Representing and reasoning on XML documents: A description logic approach. J. Logic Comput. 9, 3, 295--318.
	12	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]
	13	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
	14	Chamberlin, D., et al. 2001. XQuery 1.0: An XML query language. W3C Working Draft, June. http://www.w3.org/TR/xquery.
	15	Clark, J.1999. XSL Transformations (XSLT). W3C Recommendation, Nov. http://www.w3.org/TR/xslt.
	16	Clark. J., and DeRose, S.1999. XML Path Language (XPath). W3C Recommendation, Nov. http://www.w3.org/TR/xpath.
	17	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]
	18	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]
	19	Wenfei Fan , Jérôme Siméon, Integrity constraints for XML, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.23-34, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335172]
	20	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
	21	Florescu, D., Raschid, L., and Valduriez, P.1996. A methodology for query reformulation in CIS using semantic knowledge. Int'l J. Cooperative Information Systems (IJCIS) 5, 4, 431--468.
	22	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
	23	Carmem S. Hara , Susan B. Davidson, Reasoning about nested functional dependencies, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.91-100, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303985]
	24	John E. Hopcroft , Rajeev Motwani , Rotwani , Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computability, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
	25	Minoru Ito , Grant E. Weddell, Implication problems for functional constraints on databases supporting complex objects, Journal of Computer and System Sciences, v.50 n.1, p.165-187, Feb. 1995 [doi>10.1006/jcss.1995.1015]
	26	Kanellakis, P. C.1980. On the computational complexity of cardinality constraints in relational databases. Inf. Proc. Lett. 11, 2, 98--101.
	27	Layman, A., et al.1998. XML-Data. W3C Note, Jan. http://www.w3.org/TR/1998/ NOTE-XML-data.
	28	Lee, D., and Chu, W. W. 2000. Constraint-preserving transformation from XML document type to relational schema. In ER'00. pp. 323--338.
	29	Lenstra, H. W.1983. Integer programming in a fixed number of variables. Math. Oper. Res. 8, 538--548.
	30	Jim Melton , Alan R. Simon, Understanding the new SQL: a complete guide, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
	31	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
	32	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]
	33	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]
	34	Lucian Popa , Val Tannen, Object/relational query optimization with chase and backchase, 2000
	35	Robie, J., Lapp, J., and Schach, D. 1998. XML query language (XQL). Workshop on XML Query Languages, Dec.
	36	Thompson, H. S., et al.2000. XML Schema. W3C Working Draft, May. http://www.w3.org/XML/Schema.
	37	Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
	38	Widom, J.1999. Data management for XML: Research directions. In IEEE Data Eng. Bull. 22, 3, 44--52.

CITED BY 33

	Victor Vianu, A Web odyssey: from codd to XML, ACM SIGMOD Record, v.32 n.2, June 2003
	Makoto Murata , Akihiko Tozawa , Michiharu Kudo , Satoshi Hada, XML access control using static analysis, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA
	Peter Buneman , Susan Davidson , Wenfei Fan , Carmem Hara , Wang-Chiew Tan, Reasoning about keys for XML, Information Systems, v.28 n.8, p.1037-1063, December 2003
	Christian Nentwich , Wolfgang Emmerich , Anthony Finkelstein, Consistency management with repair actions, Proceedings of the 25th International Conference on Software Engineering, May 03-10, 2003, Portland, Oregon
	Shiyong Lu , Yezhou Sun , Mustafa Atay , Farshad Fotouhi, On the consistency of XML DTDs, Data & Knowledge Engineering, v.52 n.2, p.231-247, February 2005
	David Toman , Grant Weddell, On reasoning about structural equality in XML: a description logic approach, Theoretical Computer Science, v.336 n.1, p.181-203, 25 May 2005
	Millist W. Vincent , Jixue Liu , Chengfei Liu, Strong functional dependencies and their application to normal forms in XML, ACM Transactions on Database Systems (TODS), v.29 n.3, p.445-462, September 2004
	Sven Hartmann , Sebastian Link , Klaus-Dieter Schewe, Axiomatisations of functional dependencies in the presence of records, lists, sets and multisets, Theoretical Computer Science, v.355 n.2, p.167-196, 11 April 2006
	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
	Chang Xu , S. C. Cheung , W. K. Chan, Incremental consistency checking for pervasive context, Proceeding of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China
	Makoto Murata , Akihiko Tozawa , Michiharu Kudo , Satoshi Hada, XML access control using static analysis, ACM Transactions on Information and System Security (TISSEC), v.9 n.3, p.292-324, August 2006
	Philip Bohannon , Eiman Elnahrawy , Wenfei Fan , Michael Flaster, Putting context into schema matching, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
	Cong Yu , H. V. Jagadish, Efficient discovery of XML data redundancies, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
	Riccardo Rosati, On the decidability and finite controllability of query processing in databases with incomplete information, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA
	Sven Hartmann , Sebastian Link, Deciding implication for functional dependencies in complex-value databases, Theoretical Computer Science, v.364 n.2, p.212-240, 6 November 2006
	Susan Davidson , Wenfei Fan , Carmem Hara, Propagating XML constraints to relations, Journal of Computer and System Sciences, v.73 n.3, p.316-361, May, 2007
	Luc Segoufin, Static analysis of XML processing with data values, ACM SIGMOD Record, v.36 n.1, March 2007
	Bogdan Cautis , Serge Abiteboul , Tova Milo, Reasoning about XML update constraints, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China
	Sven Hartmann , Sebastian Link , Klaus-Dieter Schewe, Functional and multivalued dependencies in nested databases generated by record and list constructor, Annals of Mathematics and Artificial Intelligence, v.46 n.1-2, p.114-164, February 2006
	Wenfei Fan, Dependencies revisited for improving data quality, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada
	Sebastian Link , Thu Trinh, Know your limits: enhanced XML modeling with cardinality constraints, Tutorials, posters, panels and industrial contributions at the 26th international conference on Conceptual modeling, November 01-01, 2007, Auckland, New Zealand
	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
	Yannis Smaragdakis , Christoph Csallner , Ranjith Subramanian, Scalable automatic test data generation from modeling diagrams, Proceedings of the twenty-second IEEE/ACM international conference on Automated software engineering, p.4-13, November 05-09, 2007, Atlanta, Georgia, USA
	Wenfei Fan , Philip Bohannon, Information preserving XML schema embedding, ACM Transactions on Database Systems (TODS), v.33 n.1, p.1-44, March 2008
	Georg Lausen , Michael Meier , Michael Schmidt, SPARQLing constraints for RDF, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France
	Wei Ni , Tok Wang Ling, Semantic validation for XML updates, Proceedings of the 2nd international conference on Ubiquitous information management and communication, January 31-February 01, 2008, Suwon, Korea
	Yannis Smaragdakis , Christoph Csallner , Ranjith Subramanian, Scalable satisfiability checking and test data generation from modeling diagrams, Automated Software Engineering, v.16 n.1, p.73-99, March 2009
	Sven Hartmann , Sebastian Link, Expressive, yet tractable XML keys, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, March 24-26, 2009, Saint Petersburg, Russia
	Sara Cohen , Benny Kimelfeld , Yehoshua Sagiv, Running tree automata on probabilistic XML, Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 29-July 01, 2009, Providence, Rhode Island, USA
	Bogdan Cautis , Serge Abiteboul , Tova Milo, Reasoning about XML update constraints, Journal of Computer and System Sciences, v.75 n.6, p.336-358, September, 2009
	Mikoaj Bojańczyk , Anca Muscholl , Thomas Schwentick , Luc Segoufin, Two-variable logic on data trees and XML reasoning, Journal of the ACM (JACM), v.56 n.3, p.1-48, May 2009
	Shun'ichi Amano , Leonid Libkin , Filip Murlak, XML schema mappings, Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 29-July 01, 2009, Providence, Rhode Island, USA
	Sven Hartmann , Sebastian Link, Efficient reasoning about a robust XML key fragment, ACM Transactions on Database Systems (TODS), v.34 n.2, p.1-33, June 2009