[Back]

G. Gottlob, A. Nash:
"Data Exchange: Computing Cores in Polynomial Time";
Talk: PODS 2006, Chicago, USA; 2006-06-26 - 2006-06-28; in: "Proceedings of the Twenty-Fifth ACM SIGMOND-SIGACT-SIGART Symposium on Principles of Database Systems", ACM Press, (2006), ISBN: 1-59593-318-2; 40 - 49.

Data exchange deals with inserting data from one database into another database having a different schema. We study and solve a central computational problem of data exchange, namely, computing the core of a universal solution to a data exchange problem. Fagin, Kolaitis, and Popa have shown that among the universal solutions of a solvable data exchange problem, there exists a most compact one (up to isomorphism), the "core" (of any universal solution), and have convincingly argued that this core should be the solution of choice. They stated as an important open problem whether the core of a universal solution can be computed in polynomial time in the general setting where the source-to-target constraints are arbitrary tuple generating dependencies (EGDs) and weakly-acyclic TGDs. In this paper we solve this problem by developing new efficient methods for computing the core of a universal solution. This positive result shows that the core approach of Fagin, Kolaitis, and Popa is feasible and applicable in a very general setting and thus provides a further momentum to the use of cores in data exchange.

http://aleph.ub.tuwien.ac.at/F?base=tuw01&func=find-c&ccl_term=AC06586789

Project Head Thomas Eiter:
REWERSE