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: 1229
Venue: PODS
Year: 2001
Pagerank: 8.474176e-05
Overall Rank: 2,594 | 81.96%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Wenfei Fan
2. Leonid Libkin

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
560	Dependencies Revisited for Improving Data Quality	2008	PODS	0.00020141923
2,527	Dependencies for Graphs	2017	PODS	8.5954406e-05
2,727	Semantic Query Optimization in the Presence of Types	2010	PODS	8.2216778e-05
3,324	On the Decidability and Finite Controllability of Query Processing in Databases with Incomplete Information	2006	PODS	7.2213002e-05
3,438	DTD-Directed Publishing with Attribute Translation Grammars	2002	VLDB	7.0932714e-05
4,010	A Web Odyssey: from Codd to XML	2001	PODS	6.5351699e-05
5,296	Running Tree Automata on Probabilistic XML	2009	PODS	5.5802694e-05
5,459	Capturing Missing Tuples and Missing Values	2010	PODS	5.4957751e-05
6,290	Putting Context into Schema Matching	2006	VLDB	5.1271647e-05
7,056	Efficient Discovery of XML Data Redundancies	2006	VLDB	4.8492432e-05
7,291	Static Analysis of Active XML Systems	2008	PODS	4.7741469e-05
8,190	XML Schema Mappings	2009	PODS	4.5641911e-05
8,255	Discovering XSD Keys from XML Data	2013	SIGMOD	4.5491362e-05
8,558	Incorporating Constraints in Probabilistic XML	2008	PODS	4.4937074e-05
10,376	Entity/Relationship Graphs: Principled Design, Modeling, and Data Integrity Management of Graph Databases	2025	SIGMOD	4.1945683e-05
12,434	Reasoning about XML Update Constraints	2007	PODS	4.1945683e-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
274	Regular Path Queries with Constraints	1997	PODS	0.00029390022
1,897	Type Inference for Queries on Semistructured Data (Extended Abstract)	1999	PODS	0.00010178006
2,694	XML-Based Information Mediation with MIX	1999	SIGMOD	8.2832701e-05
3,257	Path Constraints on Semistructured and Structured Data	1998	PODS	7.3151681e-05
3,960	Integrity Constraints for XML	2000	PODS	6.5882121e-05
4,169	Reasoning about Nested Functional Dependencies	1999	PODS	6.3905263e-05
9,668	Interaction between Path and Type Constraints	1999	PODS	4.3074872e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,668	Interaction between Path and Type Constraints	1999	PODS	4.3074872e-05
882	DTD Inference for Views of XML Data	2000	PODS	0.00015657456
1,848	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS	0.00010330772
5,761	Capturing both Types and Constraints in Data Integration	2003	SIGMOD	5.3377412e-05
3,427	XML with Data Values: Typechecking Revisited	2001	PODS	7.1033924e-05
2,211	XML Data Exchange: Consistency and Query Answering	2005	PODS	9.2771941e-05
1,929	XPath Satisfiability in the Presence of DTDs	2005	PODS	0.00010058897
12,434	Reasoning about XML Update Constraints	2007	PODS	4.1945683e-05
3,960	Integrity Constraints for XML	2000	PODS	6.5882121e-05
6,101	On Verifying Consistency of XML Specifications	2002	PODS	5.2090945e-05