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: 1349
Venue: PODS
Year: 2005
Pagerank: 8.0546963e-05
Overall Rank: 2,829 | 80.33%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Georg Gottlob

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
621	Schema Mappings, Data Exchange, and Metadata Management	2005	PODS	0.00019005115
1,736	Generalized Schema-Mappings: From Termination To Tractability	2009	PODS	0.00010720323
3,424	Data Exchange: Computing Cores in Polynomial Time	2006	PODS	7.110765e-05
3,502	Data Exchange and Incomplete Information	2006	PODS	7.0366655e-05
3,937	On Reconciling Data Exchange, Data Integration, and Peer Data Management	2007	PODS	6.6159574e-05
4,907	DEMo: Data Exchange Modeling Tool	2009	VLDB	5.8359897e-05
4,978	Towards a Theory of Schema-Mapping Optimization	2008	PODS	5.7881299e-05
5,897	Answering Aggregate Queries in Data Exchange	2008	PODS	5.2842198e-05
7,509	Optimizing the Chase: Scalable Data Integration under Constraints	2014	VLDB	4.7180617e-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
38	Testing Implications Of Data Dependencies	1979	SIGMOD	0.00075110004
58	Efficient Optimization of a Class of Relational Expressions	1978	SIGMOD	0.00064826446
82	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00054402763
104	Inclusion dependencies and their interaction with functional dependencies (Extended abstract)	1982	PODS	0.00048766186
173	Schema Mapping as Query Discovery	2000	VLDB	0.00038627829
407	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00024004562
431	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023370207
480	Translating Web Data	2002	VLDB	0.00022191997
494	Data Exchange: Getting to the Core	2003	PODS	0.00021805832
621	Schema Mappings, Data Exchange, and Metadata Management	2005	PODS	0.00019005115
1,038	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS	0.00014492414
2,015	Robbers, Marshals, and Guards: Game Theoretic and Logical Characterizations of Hypertree Width	2001	PODS	9.7901938e-05
3,282	Foundations of Semantic Web Databases	2004	PODS	7.2808673e-05
4,705	Locally Consistent Transformations and Query Answering in Data Exchange	2004	PODS	5.9830709e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,078	Laconic Schema Mappings: Computing the Core with SQL Queries	2009	VLDB	4.8424931e-05
3,502	Data Exchange and Incomplete Information	2006	PODS	7.0366655e-05
2,211	XML Data Exchange: Consistency and Query Answering	2005	PODS	9.2771941e-05
5,000	CWA-Solutions for Data Exchange Settings with Target Dependencies	2007	PODS	5.774558e-05
5,295	Scalable Data Exchange with Functional Dependencies	2010	VLDB	5.580776e-05
4,513	Core Schema Mappings	2009	SIGMOD	6.1227596e-05
3,643	The Complexity of Data Exchange	2006	PODS	6.8862411e-05
2,715	Peer Data Exchange	2005	PODS	8.2433779e-05
494	Data Exchange: Getting to the Core	2003	PODS	0.00021805832
3,424	Data Exchange: Computing Cores in Polynomial Time	2006	PODS	7.110765e-05