On XML Integrity Constraints in the Presence of DTDs

Summary: Shows that DTDs interact with XML integrity constraints in intricate ways: general consistency (existence of a document satisfying both) is undecidable, while for unary keys and foreign keys consistency is NP-complete via encoding to linear integer constraints. Analyzes variants to identify tractable fragments and additional NP-complete cases, and proves that implication with constraint negation is coNP-complete for unary keys/foreign keys. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1228
Venue: PODS
Year: 2001
Pagerank: 8.4811795e-05
Overall Rank: 2,515 | 82.75%
DOI: 10.1145/375551.375568

Incoming Non-self Citations Over Time

Authors

1. Wenfei Fan (AT&T; Temple University)
2. Leonid Libkin (AT&T; University of Toronto)

BibTeX Citation

@inproceedings{fan_pods01,
        address = {New York, NY, USA},
        series = {{PODS} '01},
        title = {{On XML Integrity Constraints in the Presence of DTDs}},
        url = {https://dl.acm.org/doi/10.1145/375551.375568},
        doi = {10.1145/375551.375568},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Fan, Wenfei and Libkin, Leonid},
        year = {2001}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
494	Dependencies Revisited for Improving Data Quality	2008	PODS	0.00017526549
2,324	Dependencies for Graphs	2017	PODS	8.7506505e-05
3,433	On the Decidability and Finite Controllability of Query Processing in Databases with Incomplete Information	2006	PODS	7.4181806e-05
4,178	A Web Odyssey: from Codd to XML	2001	PODS	6.849218e-05
4,369	Semantic Query Optimization in the Presence of Types	2010	PODS	6.7390374e-05
4,619	DTD-Directed Publishing with Attribute Translation Grammars	2002	VLDB	6.6033756e-05
5,346	Running Tree Automata on Probabilistic XML	2009	PODS	6.257995e-05
5,616	Capturing Missing Tuples and Missing Values	2010	PODS	6.1493013e-05
6,252	Putting Context into Schema Matching	2006	VLDB	5.941182e-05
6,771	Efficient Discovery of XML Data Redundancies	2006	VLDB	5.7783105e-05
7,361	Static Analysis of Active XML Systems	2008	PODS	5.6340455e-05
8,417	XML Schema Mappings	2009	PODS	5.4288691e-05
8,480	Discovering XSD Keys from XML Data	2013	SIGMOD	5.4167813e-05
8,761	Incorporating Constraints in Probabilistic XML	2008	PODS	5.3766157e-05
10,665	Entity/Relationship Graphs: Principled Design, Modeling, and Data Integrity Management of Graph Databases	2025	SIGMOD	5.093636e-05
12,628	Reasoning about XML Update Constraints	2007	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
348	Regular Path Queries with Constraints	1997	PODS	0.00020518814
2,261	Type Inference for Queries on Semistructured Data (Extended Abstract)	1999	PODS	8.846133e-05
2,859	XML-Based Information Mediation with MIX	1999	SIGMOD	8.0283136e-05
3,308	Path Constraints on Semistructured and Structured Data	1998	PODS	7.5381026e-05
4,167	Integrity Constraints for XML	2000	PODS	6.8578387e-05
4,487	Reasoning about Nested Functional Dependencies	1999	PODS	6.6686357e-05
9,877	Interaction between Path and Type Constraints	1999	PODS	5.2041072e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,877	Interaction between Path and Type Constraints	1999	PODS
2	1,290	DTD Inference for Views of XML Data	2000	PODS
3	2,864	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS
4	5,939	Capturing both Types and Constraints in Data Integration	2003	SIGMOD
5	3,679	XML with Data Values: Typechecking Revisited	2001	PODS
6	2,049	XML Data Exchange: Consistency and Query Answering	2005	PODS
7	1,916	XPath Satisfiability in the Presence of DTDs	2005	PODS
8	12,628	Reasoning about XML Update Constraints	2007	PODS
9	4,167	Integrity Constraints for XML	2000	PODS
10	6,287	On Verifying Consistency of XML Specifications	2002	PODS