On Verifying Consistency of XML Specifications

Summary: Analyzes decidability/complexity of consistency checking for XML specs (DTDs plus integrity constraints), concluding that presence of foreign keys usually makes compile-time verification infeasible. Extends decidability to multi-attribute keys with unary FKs and to constraints with regular expressions (providing upper/lower bounds), proves undecidability for relative constraints even when unary, and isolates several restricted decidable fragments. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1269
Venue: PODS
Year: 2002
Pagerank: 5.9269709e-05
Overall Rank: 6,287 | 56.87%
DOI: 10.1145/543613.543647

Incoming Non-self Citations Over Time

Authors

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

BibTeX Citation

@inproceedings{arenas_pods02,
        address = {New York, NY, USA},
        series = {{PODS} '02},
        title = {{On Verifying Consistency of XML Specifications}},
        url = {https://dl.acm.org/doi/10.1145/543613.543647},
        doi = {10.1145/543613.543647},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Arenas, Marcelo and Fan, Wenfei and Libkin, Leonid},
        year = {2002}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,939	Capturing both Types and Constraints in Data Integration	2003	SIGMOD	6.0339259e-05
7,361	Static Analysis of Active XML Systems	2008	PODS	5.6340455e-05
12,353	Type-Based Detection of XML Query-Update Independence	2012	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,864	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS
2	8,417	XML Schema Mappings	2009	PODS
3	3,274	Frontiers of Tractability for Typechecking Simple XML Transformations	2004	PODS
4	9,877	Interaction between Path and Type Constraints	1999	PODS
5	1,916	XPath Satisfiability in the Presence of DTDs	2005	PODS
6	12,628	Reasoning about XML Update Constraints	2007	PODS
7	2,049	XML Data Exchange: Consistency and Query Answering	2005	PODS
8	3,679	XML with Data Values: Typechecking Revisited	2001	PODS
9	4,167	Integrity Constraints for XML	2000	PODS
10	2,515	On XML Integrity Constraints in the Presence of DTDs	2001	PODS