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: hc58e769a518c2857
Venue: PODS
Year: 2002
Pagerank: 5.7939875e-05
Overall Rank: 6,410 | 56.91%
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
6,060	Capturing both Types and Constraints in Data Integration	2003	SIGMOD	5.8991462e-05
7,503	Static Analysis of Active XML Systems	2008	PODS	5.5076551e-05
12,644	Type-Based Detection of XML Query-Update Independence	2012	VLDB	4.9793485e-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,934	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS
2	8,591	XML Schema Mappings	2009	PODS
3	3,343	Frontiers of Tractability for Typechecking Simple XML Transformations	2004	PODS
4	10,067	Interaction between Path and Type Constraints	1999	PODS
5	1,976	XPath Satisfiability in the Presence of DTDs	2005	PODS
6	12,918	Reasoning about XML Update Constraints	2007	PODS
7	2,100	XML Data Exchange: Consistency and Query Answering	2005	PODS
8	3,756	XML with Data Values: Typechecking Revisited	2001	PODS
9	4,248	Integrity Constraints for XML	2000	PODS
10	2,565	On XML Integrity Constraints in the Presence of DTDs	2001	PODS