Data Exchange: Getting to the Core

Summary: Core of any universal solution is unique (up to isomorphism), is the minimal universal solution, and optimally answers unions of conjunctive queries with inequalities. Complexity: core computation NP-hard in general and core-recognition DP-complete; provide broad data-exchange conditions yielding polynomial-time construction. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1281
Venue: PODS
Year: 2003
Pagerank: 0.00019643793
Overall Rank: 377 | 97.42%
DOI: 10.1145/773153.773163

Incoming Non-self Citations Over Time

Authors

1. Ronald Fagin (IBM)
2. Phokion G. Kolaitis (University of California Santa Cruz)
3. Lucian Popa (IBM)

BibTeX Citation

@inproceedings{fagin_pods03,
        address = {New York, NY, USA},
        series = {{PODS} '03},
        title = {{Data Exchange: Getting to the Core}},
        url = {https://dl.acm.org/doi/10.1145/773153.773163},
        doi = {10.1145/773153.773163},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Fagin, Ronald and Kolaitis, Phokion G. and Popa, Lucian},
        year = {2003}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 55 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,577	Nested Dependencies: Structure and Reasoning	2014	PODS	5.2528121e-05
12,279	Getting Unique Solution in Data Exchange	2013	VLDB	5.093636e-05
12,410	Certain Answers for XML Queries	2010	PODS	5.093636e-05
12,624	Expressiveness and Complexity of XML Publishing Transducers	2007	PODS	5.093636e-05
12,725	Determining Source Contribution in Integration Systems	2005	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
22	Data Integration: A Theoretical Perspective	2002	PODS	0.00056204792
40	Testing Implications Of Data Dependencies	1979	SIGMOD	0.00046918506
180	Schema Mapping as Query Discovery	2000	VLDB	0.00026772368
225	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00024101949
416	Translating Web Data	2002	VLDB	0.00018877803
1,467	The Complexity of Evaluating Relational Queries	1983	PODS	0.00010687075
2,047	Functional and Inclusion Dependencies: A Graph Theoretic Approach	1984	PODS	9.2564254e-05
2,189	Physical Data Independence, Constraints, and Optimization with Universal Plans	1999	VLDB	8.9856333e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,934	Data Exchange and Incomplete Information	2006	PODS
2	4,794	CWA-Solutions for Data Exchange Settings with Target Dependencies	2007	PODS
3	5,624	Answering Aggregate Queries in Data Exchange	2008	PODS
4	6,933	Laconic Schema Mappings: Computing the Core with SQL Queries	2009	VLDB
5	4,281	Locally Consistent Transformations and Query Answering in Data Exchange	2004	PODS
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	2,550	Computing Cores for Data Exchange: New Algorithms and Practical Solutions	2005	PODS
10	3,302	Data Exchange: Computing Cores in Polynomial Time	2006	PODS