Schema Evolution publication categorizer

Composition of mappings between schemas is essential to support
schema evolution, data exchange, data integration, and other data
management tasks. In many applications, mappings are given by
embedded dependencies. In this paper, we study the issues involved
in composing such mappings.
Our algorithms and results extend those of Fagin et al. [8] who
studied composition of mappings given by several kinds of constraints.
In particular, they proved that full source-to-target tuplegenerating
dependencies (tgds) are closed under composition, but
embedded source-to-target tgds are not. They introduced a class of
second-order constraints, SO tgds, that is closed under composition
and has desirable properties for data exchange.
We study constraints that need not be source-to-target and we
concentrate on obtaining (first-order) embedded dependencies. As
part of this study, we also consider full dependencies and secondorder
constraints that arise from Skolemizing embedded dependencies.
For each of the three classes of mappings that we study, we
provide (a) an algorithm that attempts to compute the composition
and (b) sufficient conditions on the input mappings that guarantee
that the algorithm will succeed.
In addition, we give several negative results. In particular, we
show that full dependencies are not closed under composition, and
that second-order dependencies that are not limited to be sourceto-
target are not closed under restricted composition. Furthermore,
we show that determining whether the composition can be given by
these kinds of dependencies is undecidable.