XML Data Exchange: Consistency and Query Answering

Summary: Formalizes XML data exchange with DTDs and hierarchical s-t dependencies and pins down complexity of consistency. Shows a dichotomy for query answering—tractable vs coNP-complete—driven by DTD regex classes, and gives PTIME algorithms to build representative target XMLs. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1336
Venue: PODS
Year: 2005
Pagerank: 9.255274e-05
Overall Rank: 2,049 | 85.95%
DOI: 10.1145/1065167.1065171

Incoming Non-self Citations Over Time

Authors

1. Marcelo Arenas (University of Toronto)
2. Leonid Libkin (University of Toronto)

BibTeX Citation

@inproceedings{arenas_pods05,
        address = {New York, NY, USA},
        series = {{PODS} '05},
        title = {{XML Data Exchange: Consistency and Query Answering}},
        url = {https://dl.acm.org/doi/10.1145/1065167.1065171},
        doi = {10.1145/1065167.1065171},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Arenas, Marcelo and Libkin, Leonid},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
506	Schema Mappings, Data Exchange, and Metadata Management	2005	PODS	0.0001728171
2,785	Nested Mappings: Schema Mapping Reloaded	2006	VLDB	8.1236628e-05
2,934	Data Exchange and Incomplete Information	2006	PODS	7.9451055e-05
3,485	The Complexity of Data Exchange	2006	PODS	7.3703451e-05
3,546	On Reconciling Data Exchange, Data Integration, and Peer Data Management	2007	PODS	7.3244507e-05
4,107	Processing Queries on Tree-Structured Data Efficiently	2006	PODS	6.8973582e-05
4,608	Towards a Theory of Schema-Mapping Optimization	2008	PODS	6.6082619e-05
4,794	CWA-Solutions for Data Exchange Settings with Target Dependencies	2007	PODS	6.5038715e-05
5,624	Answering Aggregate Queries in Data Exchange	2008	PODS	6.145135e-05
6,856	FICSR: Feedback-based InConSistency Resolution and Query Processing on Misaligned Data Sources	2007	SIGMOD	5.7530103e-05
12,624	Expressiveness and Complexity of XML Publishing Transducers	2007	PODS	5.093636e-05
12,625	The Complexity of Reasoning about Pattern-based XML Schemas	2007	PODS	5.093636e-05
12,628	Reasoning about XML Update Constraints	2007	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
22	Data Integration: A Theoretical Perspective	2002	PODS	0.00056204792
225	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00024101949
377	Data Exchange: Getting to the Core	2003	PODS	0.00019643793
416	Translating Web Data	2002	VLDB	0.00018877803
685	Composing Schema Mappings: Second-Order Dependencies to the Rescue	2004	PODS	0.00014979915
879	Constraint-Based XML Query Rewriting for Data Integration	2004	SIGMOD	0.00013456577
1,564	Conjunctive Queries over Trees	2004	PODS	0.00010349456
4,178	A Web Odyssey: from Codd to XML	2001	PODS	6.849218e-05
4,281	Locally Consistent Transformations and Query Answering in Data Exchange	2004	PODS	6.7848108e-05
4,537	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB	6.6417534e-05
6,501	Representing and Querying XML with Incomplete Information	2001	PODS	5.8604724e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,934	Data Exchange and Incomplete Information	2006	PODS
2	2,864	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS
3	1,916	XPath Satisfiability in the Presence of DTDs	2005	PODS
4	2,515	On XML Integrity Constraints in the Presence of DTDs	2001	PODS
5	879	Constraint-Based XML Query Rewriting for Data Integration	2004	SIGMOD
6	8,417	XML Schema Mappings	2009	PODS
7	3,679	XML with Data Values: Typechecking Revisited	2001	PODS
8	3,485	The Complexity of Data Exchange	2006	PODS
9	12,410	Certain Answers for XML Queries	2010	PODS
10	13,846	Regular Rewriting of Active XML and Unambiguity	2005	PODS