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.4660607e-05
Overall Rank: 2,598 | 81.95%
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.0002012328
2,517	Dependencies for Graphs	2017	PODS	8.6058545e-05
2,732	Semantic Query Optimization in the Presence of Types	2010	PODS	8.2137395e-05
3,325	On the Decidability and Finite Controllability of Query Processing in Databases with Incomplete Information	2006	PODS	7.2149375e-05
3,444	DTD-Directed Publishing with Attribute Translation Grammars	2002	VLDB	7.086431e-05
4,014	A Web Odyssey: from Codd to XML	2001	PODS	6.5300582e-05
5,301	Running Tree Automata on Probabilistic XML	2009	PODS	5.5749031e-05
5,466	Capturing Missing Tuples and Missing Values	2010	PODS	5.4904942e-05
6,289	Putting Context into Schema Matching	2006	VLDB	5.1226008e-05
7,052	Efficient Discovery of XML Data Redundancies	2006	VLDB	4.8445913e-05
7,288	Static Analysis of Active XML Systems	2008	PODS	4.7695781e-05
8,190	XML Schema Mappings	2009	PODS	4.5598146e-05
8,251	Discovering XSD Keys from XML Data	2013	SIGMOD	4.5447747e-05
8,555	Incorporating Constraints in Probabilistic XML	2008	PODS	4.4893996e-05
10,388	Entity/Relationship Graphs: Principled Design, Modeling, and Data Integrity Management of Graph Databases	2025	SIGMOD	4.1905499e-05
12,443	Reasoning about XML Update Constraints	2007	PODS	4.1905499e-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
276	Regular Path Queries with Constraints	1997	PODS	0.00029365217
1,900	Type Inference for Queries on Semistructured Data (Extended Abstract)	1999	PODS	0.00010168127
2,700	XML-Based Information Mediation with MIX	1999	SIGMOD	8.2753626e-05
3,262	Path Constraints on Semistructured and Structured Data	1998	PODS	7.3081091e-05
3,962	Integrity Constraints for XML	2000	PODS	6.581926e-05
4,166	Reasoning about Nested Functional Dependencies	1999	PODS	6.3843679e-05
9,668	Interaction between Path and Type Constraints	1999	PODS	4.3033855e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,668	Interaction between Path and Type Constraints	1999	PODS	4.3033855e-05
880	DTD Inference for Views of XML Data	2000	PODS	0.00015642282
1,854	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS	0.00010320817
5,770	Capturing both Types and Constraints in Data Integration	2003	SIGMOD	5.3325833e-05
3,434	XML with Data Values: Typechecking Revisited	2001	PODS	7.0965116e-05
2,217	XML Data Exchange: Consistency and Query Answering	2005	PODS	9.2682054e-05
1,933	XPath Satisfiability in the Presence of DTDs	2005	PODS	0.00010049404
12,443	Reasoning about XML Update Constraints	2007	PODS	4.1905499e-05
3,962	Integrity Constraints for XML	2000	PODS	6.581926e-05
6,105	On Verifying Consistency of XML Specifications	2002	PODS	5.2040915e-05