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.2870757e-05
Overall Rank: 2,565 | 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
501	Dependencies Revisited for Improving Data Quality	2008	PODS	0.00017273167
2,365	Dependencies for Graphs	2017	PODS	8.5625389e-05
3,503	On the Decidability and Finite Controllability of Query Processing in Databases with Incomplete Information	2006	PODS	7.2485903e-05
4,266	A Web Odyssey: from Codd to XML	2001	PODS	6.6941178e-05
4,461	Semantic Query Optimization in the Presence of Types	2010	PODS	6.5870588e-05
4,720	DTD-Directed Publishing with Attribute Translation Grammars	2002	VLDB	6.4521915e-05
5,478	Running Tree Automata on Probabilistic XML	2009	PODS	6.1147103e-05
5,740	Capturing Missing Tuples and Missing Values	2010	PODS	6.0085833e-05
6,315	Putting Context into Schema Matching	2006	VLDB	5.8144467e-05
6,912	Efficient Discovery of XML Data Redundancies	2006	VLDB	5.6459867e-05
7,508	Static Analysis of Active XML Systems	2008	PODS	5.505048e-05
8,598	XML Schema Mappings	2009	PODS	5.3045486e-05
8,655	Discovering XSD Keys from XML Data	2013	SIGMOD	5.2927398e-05
8,931	Incorporating Constraints in Probabilistic XML	2008	PODS	5.2534908e-05
11,115	Entity/Relationship Graphs: Principled Design, Modeling, and Data Integrity Management of Graph Databases	2025	SIGMOD	4.9769913e-05
12,924	Reasoning about XML Update Constraints	2007	PODS	4.9769913e-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
356	Regular Path Queries with Constraints	1997	PODS	0.0002009439
2,319	Type Inference for Queries on Semistructured Data (Extended Abstract)	1999	PODS	8.6436947e-05
2,919	XML-Based Information Mediation with MIX	1999	SIGMOD	7.8541889e-05
3,367	Path Constraints on Semistructured and Structured Data	1998	PODS	7.3693945e-05
4,249	Integrity Constraints for XML	2000	PODS	6.7008425e-05
4,584	Reasoning about Nested Functional Dependencies	1999	PODS	6.5160342e-05
10,072	Interaction between Path and Type Constraints	1999	PODS	5.0849609e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,072	Interaction between Path and Type Constraints	1999	PODS
2	1,315	DTD Inference for Views of XML Data	2000	PODS
3	2,935	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS
4	6,061	Capturing both Types and Constraints in Data Integration	2003	SIGMOD
5	3,759	XML with Data Values: Typechecking Revisited	2001	PODS
6	2,101	XML Data Exchange: Consistency and Query Answering	2005	PODS
7	1,978	XPath Satisfiability in the Presence of DTDs	2005	PODS
8	12,924	Reasoning about XML Update Constraints	2007	PODS
9	4,249	Integrity Constraints for XML	2000	PODS
10	6,413	On Verifying Consistency of XML Specifications	2002	PODS