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: h93995e647c2c0b7b
Venue: PODS
Year: 2005
Pagerank: 8.2426092e-05
Overall Rank: 2,594 | 82.57%
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
517	Schema Mappings, Data Exchange, and Metadata Management	2005	PODS	0.00016948466
1,575	Generalized Schema-Mappings: From Termination To Tractability	2009	PODS	0.00010194712
2,989	Data Exchange and Incomplete Information	2006	PODS	7.7755739e-05
3,366	Data Exchange: Computing Cores in Polynomial Time	2006	PODS	7.3722866e-05
3,614	On Reconciling Data Exchange, Data Integration, and Peer Data Management	2007	PODS	7.1605909e-05
4,704	Towards a Theory of Schema-Mapping Optimization	2008	PODS	6.4604802e-05
4,749	DEMo: Data Exchange Modeling Tool	2009	VLDB	6.4370799e-05
5,750	Answering Aggregate Queries in Data Exchange	2008	PODS	6.0073031e-05
8,098	Optimizing the Chase: Scalable Data Integration under Constraints	2014	VLDB	5.3942942e-05
8,503	Reflections on Schema Mappings, Data Exchange, and Metadata Management	2018	PODS	5.3294549e-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
41	Testing Implications Of Data Dependencies	1979	SIGMOD	0.00045899672
72	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00037549176
102	Efficient Optimization of a Class of Relational Expressions	1978	SIGMOD	0.00033914384
159	Inclusion dependencies and their interaction with functional dependencies (Extended abstract)	1982	PODS	0.00027958527
182	Schema Mapping as Query Discovery	2000	VLDB	0.00026277842
390	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00019248147
392	Data Exchange: Getting to the Core	2003	PODS	0.0001922472
421	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00018516535
426	Translating Web Data	2002	VLDB	0.00018483901
517	Schema Mappings, Data Exchange, and Metadata Management	2005	PODS	0.00016948466
1,690	Robbers, Marshals, and Guards: Game Theoretic and Logical Characterizations of Hypertree Width	2001	PODS	9.8609347e-05
2,728	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS	8.0895728e-05
4,222	Foundations of Semantic Web Databases	2004	PODS	6.7237398e-05
4,367	Locally Consistent Transformations and Query Answering in Data Exchange	2004	PODS	6.633173e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,071	Laconic Schema Mappings: Computing the Core with SQL Queries	2009	VLDB
2	2,989	Data Exchange and Incomplete Information	2006	PODS
3	2,100	XML Data Exchange: Consistency and Query Answering	2005	PODS
4	4,896	CWA-Solutions for Data Exchange Settings with Target Dependencies	2007	PODS
5	5,176	Scalable Data Exchange with Functional Dependencies	2010	VLDB
6	4,280	Core Schema Mappings	2009	SIGMOD
7	3,561	The Complexity of Data Exchange	2006	PODS
8	2,554	Peer Data Exchange	2005	PODS
9	392	Data Exchange: Getting to the Core	2003	PODS
10	3,366	Data Exchange: Computing Cores in Polynomial Time	2006	PODS