Data Exchange: Computing Cores in Polynomial Time

Summary: Polynomial-time algorithms to compute the core of a universal solution for data-exchange instances with arbitrary source-to-target TGDs and target EGDs plus weakly-acyclic TGDs, resolving a longstanding open problem. Establishes feasibility of the core approach via new efficient techniques. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1374
Venue: PODS
Year: 2006
Pagerank: 7.5406585e-05
Overall Rank: 3,302 | 77.35%
DOI: 10.1145/1142351.1142358

Incoming Non-self Citations Over Time

Authors

1. Georg Gottlob (University of Oxford)
2. Alan Nash (University of California San Diego)

BibTeX Citation

@inproceedings{gottlob_pods06,
        address = {New York, NY, USA},
        series = {{PODS} '06},
        title = {{Data Exchange: Computing Cores in Polynomial Time}},
        url = {https://dl.acm.org/doi/10.1145/1142351.1142358},
        doi = {10.1145/1142351.1142358},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Gottlob, Georg and Nash, Alan},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
525	The Chase Revisited	2008	PODS	0.00017118255
1,541	Generalized Schema-Mappings: From Termination To Tractability	2009	PODS	0.00010427058
2,954	The Recovery of a Schema Mapping: Bringing Exchanged Data Back	2008	PODS	7.9234704e-05
3,546	On Reconciling Data Exchange, Data Integration, and Peer Data Management	2007	PODS	7.3244507e-05
4,608	Towards a Theory of Schema-Mapping Optimization	2008	PODS	6.6082619e-05
4,655	DEMo: Data Exchange Modeling Tool	2009	VLDB	6.5837448e-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
8,970	Understanding Queries by Conditional Instances	2022	SIGMOD	5.3422757e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
40	Testing Implications Of Data Dependencies	1979	SIGMOD	0.00046918506
377	Data Exchange: Getting to the Core	2003	PODS	0.00019643793
506	Schema Mappings, Data Exchange, and Metadata Management	2005	PODS	0.0001728171
2,550	Computing Cores for Data Exchange: New Algorithms and Practical Solutions	2005	PODS	8.4290753e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,049	XML Data Exchange: Consistency and Query Answering	2005	PODS
2	12,099	Recovering Exchanged Data	2015	PODS
3	6,933	Laconic Schema Mappings: Computing the Core with SQL Queries	2009	VLDB
4	4,794	CWA-Solutions for Data Exchange Settings with Target Dependencies	2007	PODS
5	5,060	Scalable Data Exchange with Functional Dependencies	2010	VLDB
6	2,510	Peer Data Exchange	2005	PODS
7	4,193	Core Schema Mappings	2009	SIGMOD
8	3,485	The Complexity of Data Exchange	2006	PODS
9	377	Data Exchange: Getting to the Core	2003	PODS
10	2,550	Computing Cores for Data Exchange: New Algorithms and Practical Solutions	2005	PODS