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: h997e71ca45c1f091
Venue: PODS
Year: 2001
Pagerank: 8.2596816e-05
Overall Rank: 2,571 | 82.77%
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
502	Dependencies Revisited for Improving Data Quality	2008	PODS	0.00017239652
2,269	Dependencies for Graphs	2017	PODS	8.711418e-05
3,515	On the Decidability and Finite Controllability of Query Processing in Databases with Incomplete Information	2006	PODS	7.2247195e-05
4,281	A Web Odyssey: from Codd to XML	2001	PODS	6.6721591e-05
4,482	Semantic Query Optimization in the Presence of Types	2010	PODS	6.5653184e-05
4,732	DTD-Directed Publishing with Attribute Translation Grammars	2002	VLDB	6.4311491e-05
5,495	Running Tree Automata on Probabilistic XML	2009	PODS	6.0944915e-05
5,753	Capturing Missing Tuples and Missing Values	2010	PODS	5.9887721e-05
6,324	Putting Context into Schema Matching	2006	VLDB	5.7958172e-05
6,929	Efficient Discovery of XML Data Redundancies	2006	VLDB	5.6273176e-05
7,526	Static Analysis of Active XML Systems	2008	PODS	5.4868482e-05
8,619	XML Schema Mappings	2009	PODS	5.2870085e-05
8,674	Discovering XSD Keys from XML Data	2013	SIGMOD	5.2752387e-05
8,951	Incorporating Constraints in Probabilistic XML	2008	PODS	5.2361195e-05
11,176	Entity/Relationship Graphs: Principled Design, Modeling, and Data Integrity Management of Graph Databases	2025	SIGMOD	4.9605343e-05
12,966	Reasoning about XML Update Constraints	2007	PODS	4.9605343e-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
358	Regular Path Queries with Constraints	1997	PODS	0.00020030407
2,331	Type Inference for Queries on Semistructured Data (Extended Abstract)	1999	PODS	8.6151201e-05
2,932	XML-Based Information Mediation with MIX	1999	SIGMOD	7.8282753e-05
3,377	Path Constraints on Semistructured and Structured Data	1998	PODS	7.3455463e-05
4,267	Integrity Constraints for XML	2000	PODS	6.6786936e-05
4,602	Reasoning about Nested Functional Dependencies	1999	PODS	6.4944895e-05
10,106	Interaction between Path and Type Constraints	1999	PODS	5.0681497e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,106	Interaction between Path and Type Constraints	1999	PODS
2	1,326	DTD Inference for Views of XML Data	2000	PODS
3	2,948	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS
4	6,077	Capturing both Types and Constraints in Data Integration	2003	SIGMOD
5	3,764	XML with Data Values: Typechecking Revisited	2001	PODS
6	2,113	XML Data Exchange: Consistency and Query Answering	2005	PODS
7	1,983	XPath Satisfiability in the Presence of DTDs	2005	PODS
8	12,966	Reasoning about XML Update Constraints	2007	PODS
9	4,267	Integrity Constraints for XML	2000	PODS
10	6,423	On Verifying Consistency of XML Specifications	2002	PODS