The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

An Isaac Newton Institute Workshop

Logic and Databases

Computational Problems of Data Exchange

Author: Georg Gottlob (Oxford University)

Abstract

Data Exchange is the problem of inserting data structured under a source schema into a target schema of different structure (possibly with integrity constraints), while reflecting the source data as accurately as possible. We study computational issues related to data exchange in the setting of Fagin, Kolaitis, and Popa (PODS´03). In particular, we are interested in computing a particular universal solution to a data exchange problem, called "the core". We present polynomial algorithms for computing the core of large classes of data exchange problems, solving relevant open problems by Fagin et al. Our results show that data exchange with cores is feasible in a very general framework. Furthermore, we use the technique of hypertree decompositions to derive improved algorithms for computing the core of a relational instance with labeled nulls, a problem we show to be fixed-parameter intractable with respect to the block size of the input instances. Finally, we show that computing cores is NP-hard in presence of a system-predicate NULL(x), which is true if x is a null value.

Part of this work is joint work with Alan Nash, UCSD.