The Complexity of Data Exchange

Summary: Shows weak acyclicity and a fixed mapping indispensable: slightest relaxation of weak acyclicity yields undecidability (via universal-algebra), and allowing the mapping as input makes the existence-of-solutions problem EXPTIME-complete. Classifies combined complexity for natural mapping restrictions as EXPTIME- or coNP-complete. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h497d2dfeae13e043
Venue: PODS
Year: 2006
Pagerank: 7.2021386e-05
Overall Rank: 3,564 | 76.05%
DOI: 10.1145/1142351.1142357

Incoming Non-self Citations Over Time

Authors

1. Phokion G. Kolaitis (IBM; University of California Santa Cruz)
2. Jonathan Panttaja (University of California Santa Cruz)
3. Wang-Chiew Tan (University of California Santa Cruz)

BibTeX Citation

@inproceedings{kolaitis_pods06,
        address = {New York, NY, USA},
        series = {{PODS} '06},
        title = {{The Complexity of Data Exchange}},
        url = {https://dl.acm.org/doi/10.1145/1142351.1142357},
        doi = {10.1145/1142351.1142357},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Kolaitis, Phokion G. and Panttaja, Jonathan and Tan, Wang-Chiew},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
539	The Chase Revisited	2008	PODS	0.0001672793
3,019	The Recovery of a Schema Mapping: Bringing Exchanged Data Back	2008	PODS	7.7434413e-05
3,614	On Reconciling Data Exchange, Data Integration, and Peer Data Management	2007	PODS	7.1572016e-05
4,897	CWA-Solutions for Data Exchange Settings with Target Dependencies	2007	PODS	6.363076e-05
8,508	Reflections on Schema Mappings, Data Exchange, and Metadata Management	2018	PODS	5.3269436e-05
8,598	XML Schema Mappings	2009	PODS	5.3045486e-05
8,951	Chase Termination: A Constraints Rewriting Approach	2010	VLDB	5.2517655e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 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.00055018384
191	Applying Model Management to Classical Meta Data Problems	2003	CIDR	0.00025757196
392	Data Exchange: Getting to the Core	2003	PODS	0.00019215652
427	Translating Web Data	2002	VLDB	0.00018475614
703	Composing Schema Mappings: Second-Order Dependencies to the Rescue	2004	PODS	0.00014653248
1,522	Composition of Mappings Given by Embedded Dependencies	2005	PODS	0.00010362522
2,099	Functional and Inclusion Dependencies: A Graph Theoretic Approach	1984	PODS	9.0478598e-05
2,101	XML Data Exchange: Consistency and Query Answering	2005	PODS	9.0459184e-05
4,303	The Inference Problem for Template Dependencies	1982	PODS	6.6750057e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,596	Computing Cores for Data Exchange: New Algorithms and Practical Solutions	2005	PODS
2	4,473	Data Exchange and Schema Mappings in Open and Closed Worlds	2008	PODS
3	4,533	Data Exchange beyond Complete Data	2011	PODS
4	2,990	Data Exchange and Incomplete Information	2006	PODS
5	2,101	XML Data Exchange: Consistency and Query Answering	2005	PODS
6	3,975	On the Complexity of Deriving Schema Mappings from Database Instances	2008	PODS
7	3,368	Data Exchange: Computing Cores in Polynomial Time	2006	PODS
8	2,554	Peer Data Exchange	2005	PODS
9	392	Data Exchange: Getting to the Core	2003	PODS
10	4,897	CWA-Solutions for Data Exchange Settings with Target Dependencies	2007	PODS