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: 1337
Venue: PODS
Year: 2005
Pagerank: 9.2771941e-05
Overall Rank: 2,211 | 84.63%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Marcelo Arenas
2. Leonid Libkin

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
621	Schema Mappings, Data Exchange, and Metadata Management	2005	PODS	0.00019005115
2,904	Nested Mappings: Schema Mapping Reloaded	2006	VLDB	7.9355829e-05
3,117	Processing Queries on Tree-Structured Data Efficiently	2006	PODS	7.5407318e-05
3,502	Data Exchange and Incomplete Information	2006	PODS	7.0366655e-05
3,643	The Complexity of Data Exchange	2006	PODS	6.8862411e-05
3,937	On Reconciling Data Exchange, Data Integration, and Peer Data Management	2007	PODS	6.6159574e-05
4,978	Towards a Theory of Schema-Mapping Optimization	2008	PODS	5.7881299e-05
5,000	CWA-Solutions for Data Exchange Settings with Target Dependencies	2007	PODS	5.774558e-05
5,897	Answering Aggregate Queries in Data Exchange	2008	PODS	5.2842198e-05
6,787	FICSR: Feedback-based InConSistency Resolution and Query Processing on Misaligned Data Sources	2007	SIGMOD	4.92548e-05
12,430	Expressiveness and Complexity of XML Publishing Transducers	2007	PODS	4.1945683e-05
12,431	The Complexity of Reasoning about Pattern-based XML Schemas	2007	PODS	4.1945683e-05
12,434	Reasoning about XML Update Constraints	2007	PODS	4.1945683e-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
48	Data Integration: A Theoretical Perspective	2002	PODS	0.00069720859
297	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00028596715
480	Translating Web Data	2002	VLDB	0.00022191997
494	Data Exchange: Getting to the Core	2003	PODS	0.00021805832
822	Composing Schema Mappings: Second-Order Dependencies to the Rescue	2004	PODS	0.00016255689
873	Constraint-Based XML Query Rewriting for Data Integration	2004	SIGMOD	0.00015752865
1,663	Conjunctive Queries over Trees	2004	PODS	0.00010977096
4,010	A Web Odyssey: from Codd to XML	2001	PODS	6.5351699e-05
4,625	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB	6.0406081e-05
4,705	Locally Consistent Transformations and Query Answering in Data Exchange	2004	PODS	5.9830709e-05
6,509	Representing and Querying XML with Incomplete Information	2001	PODS	5.0331402e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,502	Data Exchange and Incomplete Information	2006	PODS	7.0366655e-05
1,848	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS	0.00010330772
1,929	XPath Satisfiability in the Presence of DTDs	2005	PODS	0.00010058897
873	Constraint-Based XML Query Rewriting for Data Integration	2004	SIGMOD	0.00015752865
2,594	On XML Integrity Constraints in the Presence of DTDs	2001	PODS	8.474176e-05
8,190	XML Schema Mappings	2009	PODS	4.5641911e-05
3,427	XML with Data Values: Typechecking Revisited	2001	PODS	7.1033924e-05
3,643	The Complexity of Data Exchange	2006	PODS	6.8862411e-05
12,215	Certain Answers for XML Queries	2010	PODS	4.1945683e-05
13,645	Regular Rewriting of Active XML and Unambiguity	2005	PODS	-