Title:   Composition of mappings given by embedded dependencies
Speaker: Alan Nash (joint work with Phil Bernstein and Sergey Melnik from Microsoft Research)

Abstract:

Composition is a fundamental operation on mappings. It is needed to
support schema evolution, data exchange, data integration, and other
data management tasks.  In many applications, mappings are given by
full dependencies or by embedded dependencies. In addition to these,
we consider mappings given by a restricted class of second-order
constraints which arise from Skolemizing embedded dependencies. In
this paper, we study the issues involved in composing such mappings.

Fagin et al. [FKPT04] recently showed that the composition of mappings
given by embedded dependencies can not always be given by embedded
dependencies. We show that this is also the case for mappings given by
full dependencies. Furthermore, we show that determining whether the
composition can be so given is undecidable.

For each of the three classes of mappings that we study, we provide 
(a) an algorithm which attempts to compute the composition and 
(b) polynomial-time checkable conditions on the input mappings
    which guarantee that the algorithm will succeed (and which hold for
    a wide class of mappings).
Our algorithms and results extend those of Fagin et al. [FKPT04] who
examined mainly ``source-to-target'' constraints (which exclude
recursion and view definitions) and did not address the issue of 
de-Skolemizing second-order constraints to obtain embedded dependencies.

We implemented our algorithms in a model-management prototype, in which 
composition of mappings is the key basic operator involved in manipulating
schemas and mappings. We show that several other basic operators can be
reduced to composition (e.g., domain and range) or are easy to compute
(e.g., intersection).