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: h809ea84d2bdae977
Venue: PODS
Year: 2005
Pagerank: 9.050183e-05
Overall Rank: 2,100 | 85.89%
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
517	Schema Mappings, Data Exchange, and Metadata Management	2005	PODS	0.00016948466
2,849	Nested Mappings: Schema Mapping Reloaded	2006	VLDB	7.942171e-05
2,989	Data Exchange and Incomplete Information	2006	PODS	7.7755739e-05
3,561	The Complexity of Data Exchange	2006	PODS	7.2055481e-05
3,614	On Reconciling Data Exchange, Data Integration, and Peer Data Management	2007	PODS	7.1605909e-05
4,189	Processing Queries on Tree-Structured Data Efficiently	2006	PODS	6.7459542e-05
4,704	Towards a Theory of Schema-Mapping Optimization	2008	PODS	6.4604802e-05
4,896	CWA-Solutions for Data Exchange Settings with Target Dependencies	2007	PODS	6.3660709e-05
5,750	Answering Aggregate Queries in Data Exchange	2008	PODS	6.0073031e-05
7,002	FICSR: Feedback-based InConSistency Resolution and Query Processing on Misaligned Data Sources	2007	SIGMOD	5.624639e-05
12,914	Expressiveness and Complexity of XML Publishing Transducers	2007	PODS	4.9793485e-05
12,915	The Complexity of Reasoning about Pattern-based XML Schemas	2007	PODS	4.9793485e-05
12,918	Reasoning about XML Update Constraints	2007	PODS	4.9793485e-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
24	Data Integration: A Theoretical Perspective	2002	PODS	0.00055043581
238	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00023591683
392	Data Exchange: Getting to the Core	2003	PODS	0.0001922472
426	Translating Web Data	2002	VLDB	0.00018483901
703	Composing Schema Mappings: Second-Order Dependencies to the Rescue	2004	PODS	0.00014660132
905	Constraint-Based XML Query Rewriting for Data Integration	2004	SIGMOD	0.00013170652
1,599	Conjunctive Queries over Trees	2004	PODS	0.00010117703
4,266	A Web Odyssey: from Codd to XML	2001	PODS	6.6972871e-05
4,367	Locally Consistent Transformations and Query Answering in Data Exchange	2004	PODS	6.633173e-05
4,636	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB	6.4931113e-05
6,626	Representing and Querying XML with Incomplete Information	2001	PODS	5.7291244e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,989	Data Exchange and Incomplete Information	2006	PODS
2	2,934	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS
3	1,976	XPath Satisfiability in the Presence of DTDs	2005	PODS
4	2,565	On XML Integrity Constraints in the Presence of DTDs	2001	PODS
5	905	Constraint-Based XML Query Rewriting for Data Integration	2004	SIGMOD
6	8,591	XML Schema Mappings	2009	PODS
7	3,756	XML with Data Values: Typechecking Revisited	2001	PODS
8	3,561	The Complexity of Data Exchange	2006	PODS
9	12,701	Certain Answers for XML Queries	2010	PODS
10	14,157	Regular Rewriting of Active XML and Unambiguity	2005	PODS