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.0468415e-05
Overall Rank: 2,835 | 80.30%
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
620	Schema Mappings, Data Exchange, and Metadata Management	2005	PODS	0.00018983367
1,737	Generalized Schema-Mappings: From Termination To Tractability	2009	PODS	0.00010711961
3,426	Data Exchange: Computing Cores in Polynomial Time	2006	PODS	7.1040993e-05
3,507	Data Exchange and Incomplete Information	2006	PODS	7.0299158e-05
3,940	On Reconciling Data Exchange, Data Integration, and Peer Data Management	2007	PODS	6.6096825e-05
4,914	DEMo: Data Exchange Modeling Tool	2009	VLDB	5.8304201e-05
4,980	Towards a Theory of Schema-Mapping Optimization	2008	PODS	5.7825422e-05
5,901	Answering Aggregate Queries in Data Exchange	2008	PODS	5.2791434e-05
7,508	Optimizing the Chase: Scalable Data Integration under Constraints	2014	VLDB	4.7135369e-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.0007528369
58	Efficient Optimization of a Class of Relational Expressions	1978	SIGMOD	0.00064817807
82	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00054430106
105	Inclusion dependencies and their interaction with functional dependencies (Extended abstract)	1982	PODS	0.00049082041
174	Schema Mapping as Query Discovery	2000	VLDB	0.00038586435
401	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00024281448
432	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023349408
480	Translating Web Data	2002	VLDB	0.00022166928
493	Data Exchange: Getting to the Core	2003	PODS	0.00021782199
620	Schema Mappings, Data Exchange, and Metadata Management	2005	PODS	0.00018983367
1,039	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS	0.00014488271
2,007	Robbers, Marshals, and Guards: Game Theoretic and Logical Characterizations of Hypertree Width	2001	PODS	9.8123766e-05
3,285	Foundations of Semantic Web Databases	2004	PODS	7.2738104e-05
4,707	Locally Consistent Transformations and Query Answering in Data Exchange	2004	PODS	5.9773898e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,072	Laconic Schema Mappings: Computing the Core with SQL Queries	2009	VLDB	4.8378485e-05
3,507	Data Exchange and Incomplete Information	2006	PODS	7.0299158e-05
2,217	XML Data Exchange: Consistency and Query Answering	2005	PODS	9.2682054e-05
4,997	CWA-Solutions for Data Exchange Settings with Target Dependencies	2007	PODS	5.7690207e-05
5,299	Scalable Data Exchange with Functional Dependencies	2010	VLDB	5.5751426e-05
4,514	Core Schema Mappings	2009	SIGMOD	6.1168694e-05
3,647	The Complexity of Data Exchange	2006	PODS	6.8796285e-05
2,719	Peer Data Exchange	2005	PODS	8.2355137e-05
493	Data Exchange: Getting to the Core	2003	PODS	0.00021782199
3,426	Data Exchange: Computing Cores in Polynomial Time	2006	PODS	7.1040993e-05