Efficient Core Computation in Data Exchange Export

@techreport{GotNas2006, abstract = {Data exchange deals with inserting data from one database into another database having a differentschema. Fagin, Kolaitis, and Popa have shown that among the universal solutions of a solvabledata exchange problem, there exists – up to isomorphism – a unique most compact one, ” thecore”, and have convincingly argued that this core should be the database to be materialized.They stated as an important open problem whether the core can be computed in polynomialtime in the general setting where the mapping between the source and target schemas is given bysource-to-target constraints which are arbitrary tuple generating dependencies (tgds) and targetconstraints consisting of equality generating dependencies (egds) and a weakly-acyclic set of tgds.In this paper we solve this problem by developing new methods for efficiently computing the coreof a universal solution. This positive result shows that data exchange based on cores is feasible andapplicable in a very general setting. In addition to our main result, we use the method of hypertreedecompositions to derive new algorithms and upper bounds for query containment checking andcomputing cores of arbitrary database instances. We also show that computing the core of a dataexchange problem is fixed-parameter intractable with respect to a number of relevant parameters,and that computing cores is NP-complete if the rule bodies of target tgds are augmented by aspecial predicate that distinguishes a null value from a constant data value.}, author = {Gottlob, Georg and Nash, Alan}, citeulike-article-id = {2364051}, keywords = {caesar\_paper, cores, data\_exchange}, posted-at = {2008-02-11 22:40:19}, priority = {5}, title = {Efficient Core Computation in Data Exchange}, year = {2006} }

TY - RPRT ID - GotNas2006 L3 - citeulike-article-id:2364051 N2 - Data exchange deals with inserting data from one database into another database having a differentschema. Fagin, Kolaitis, and Popa have shown that among the universal solutions of a solvabledata exchange problem, there exists – up to isomorphism – a unique most compact one, “thecore”, and have convincingly argued that this core should be the database to be materialized.They stated as an important open problem whether the core can be computed in polynomialtime in the general setting where the mapping between the source and target schemas is given bysource-to-target constraints which are arbitrary tuple generating dependencies (tgds) and targetconstraints consisting of equality generating dependencies (egds) and a weakly-acyclic set of tgds.In this paper we solve this problem by developing new methods for efficiently computing the coreof a universal solution. This positive result shows that data exchange based on cores is feasible andapplicable in a very general setting. In addition to our main result, we use the method of hypertreedecompositions to derive new algorithms and upper bounds for query containment checking andcomputing cores of arbitrary database instances. We also show that computing the core of a dataexchange problem is fixed-parameter intractable with respect to a number of relevant parameters,and that computing cores is NP-complete if the rule bodies of target tgds are augmented by aspecial predicate that distinguishes a null value from a constant data value. TI - Efficient Core Computation in Data Exchange KW - caesar_paper KW - cores KW - data_exchange AU - Gottlob, Georg AU - Nash, Alan PY - 2006/// ER -