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.

Skip to content



Computational problems of data exchange

Gottlob, G (Oxford)
Tuesday 28 February 2006, 10:15-11:00

Seminar Room 1, Newton Institute


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.


MP3MP3 Real AudioReal Audio

Back to top ∧