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.2682054e-05
Overall Rank: 2,217 | 84.60%
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
620	Schema Mappings, Data Exchange, and Metadata Management	2005	PODS	0.00018983367
2,909	Nested Mappings: Schema Mapping Reloaded	2006	VLDB	7.9282234e-05
3,115	Processing Queries on Tree-Structured Data Efficiently	2006	PODS	7.5414053e-05
3,507	Data Exchange and Incomplete Information	2006	PODS	7.0299158e-05
3,647	The Complexity of Data Exchange	2006	PODS	6.8796285e-05
3,940	On Reconciling Data Exchange, Data Integration, and Peer Data Management	2007	PODS	6.6096825e-05
4,980	Towards a Theory of Schema-Mapping Optimization	2008	PODS	5.7825422e-05
4,997	CWA-Solutions for Data Exchange Settings with Target Dependencies	2007	PODS	5.7690207e-05
5,901	Answering Aggregate Queries in Data Exchange	2008	PODS	5.2791434e-05
6,787	FICSR: Feedback-based InConSistency Resolution and Query Processing on Misaligned Data Sources	2007	SIGMOD	4.9207828e-05
12,439	Expressiveness and Complexity of XML Publishing Transducers	2007	PODS	4.1905499e-05
12,440	The Complexity of Reasoning about Pattern-based XML Schemas	2007	PODS	4.1905499e-05
12,443	Reasoning about XML Update Constraints	2007	PODS	4.1905499e-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
47	Data Integration: A Theoretical Perspective	2002	PODS	0.00069691761
297	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00028572729
480	Translating Web Data	2002	VLDB	0.00022166928
493	Data Exchange: Getting to the Core	2003	PODS	0.00021782199
818	Composing Schema Mappings: Second-Order Dependencies to the Rescue	2004	PODS	0.00016240185
868	Constraint-Based XML Query Rewriting for Data Integration	2004	SIGMOD	0.00015737664
1,662	Conjunctive Queries over Trees	2004	PODS	0.00010966423
4,014	A Web Odyssey: from Codd to XML	2001	PODS	6.5300582e-05
4,624	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB	6.034764e-05
4,707	Locally Consistent Transformations and Query Answering in Data Exchange	2004	PODS	5.9773898e-05
6,505	Representing and Querying XML with Incomplete Information	2001	PODS	5.0282726e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,507	Data Exchange and Incomplete Information	2006	PODS	7.0299158e-05
1,854	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS	0.00010320817
1,933	XPath Satisfiability in the Presence of DTDs	2005	PODS	0.00010049404
2,598	On XML Integrity Constraints in the Presence of DTDs	2001	PODS	8.4660607e-05
868	Constraint-Based XML Query Rewriting for Data Integration	2004	SIGMOD	0.00015737664
8,190	XML Schema Mappings	2009	PODS	4.5598146e-05
3,647	The Complexity of Data Exchange	2006	PODS	6.8796285e-05
3,434	XML with Data Values: Typechecking Revisited	2001	PODS	7.0965116e-05
12,223	Certain Answers for XML Queries	2010	PODS	4.1905499e-05
13,659	Regular Rewriting of Active XML and Unambiguity	2005	PODS	-