Computing Cores for Data Exchange: New Algorithms and Practical Solutions

Summary: Hypertree-decomposition-based algorithms for computing cores of relational instances with labeled nulls, plus a fixed-parameter intractability result when parameterized by instance block size. Prove tractability for two broad target-constraint classes—FDs with weakly-acyclic IDs and full TGDs with arbitrary EGDs—and NP-hardness if a NULL(x) system predicate is present. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1348
Venue: PODS
Year: 2005
Pagerank: 8.4290753e-05
Overall Rank: 2,550 | 82.51%
DOI: 10.1145/1065167.1065187

Incoming Non-self Citations Over Time

Authors

1. Georg Gottlob (Vienna University of Technology)

BibTeX Citation

@inproceedings{gottlob_pods05,
        address = {New York, NY, USA},
        series = {{PODS} '05},
        title = {{Computing Cores for Data Exchange: New Algorithms and Practical Solutions}},
        url = {https://dl.acm.org/doi/10.1145/1065167.1065187},
        doi = {10.1145/1065167.1065187},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Gottlob, Georg},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
506	Schema Mappings, Data Exchange, and Metadata Management	2005	PODS	0.0001728171
1,541	Generalized Schema-Mappings: From Termination To Tractability	2009	PODS	0.00010427058
2,934	Data Exchange and Incomplete Information	2006	PODS	7.9451055e-05
3,302	Data Exchange: Computing Cores in Polynomial Time	2006	PODS	7.5406585e-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
5,624	Answering Aggregate Queries in Data Exchange	2008	PODS	6.145135e-05
7,930	Optimizing the Chase: Scalable Data Integration under Constraints	2014	VLDB	5.5181056e-05
8,348	Reflections on Schema Mappings, Data Exchange, and Metadata Management	2018	PODS	5.4469775e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 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
69	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00038090878
97	Efficient Optimization of a Class of Relational Expressions	1978	SIGMOD	0.00034574497
162	Inclusion dependencies and their interaction with functional dependencies (Extended abstract)	1982	PODS	0.00027886326
180	Schema Mapping as Query Discovery	2000	VLDB	0.00026772368
377	Data Exchange: Getting to the Core	2003	PODS	0.00019643793
382	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00019546431
414	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00018893507
416	Translating Web Data	2002	VLDB	0.00018877803
506	Schema Mappings, Data Exchange, and Metadata Management	2005	PODS	0.0001728171
1,673	Robbers, Marshals, and Guards: Game Theoretic and Logical Characterizations of Hypertree Width	2001	PODS	0.00010040854
2,678	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS	8.2680182e-05
4,139	Foundations of Semantic Web Databases	2004	PODS	6.8776612e-05
4,281	Locally Consistent Transformations and Query Answering in Data Exchange	2004	PODS	6.7848108e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,933	Laconic Schema Mappings: Computing the Core with SQL Queries	2009	VLDB
2	2,934	Data Exchange and Incomplete Information	2006	PODS
3	2,049	XML Data Exchange: Consistency and Query Answering	2005	PODS
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	4,193	Core Schema Mappings	2009	SIGMOD
7	3,485	The Complexity of Data Exchange	2006	PODS
8	2,510	Peer Data Exchange	2005	PODS
9	377	Data Exchange: Getting to the Core	2003	PODS
10	3,302	Data Exchange: Computing Cores in Polynomial Time	2006	PODS