Efficiently Supporting Changes to Declarative Schema Mappings
                       TJ Green, UC Davis

A major challenge faced by today's information systems is that of
evolution as data usage changes or new data resources become
available. Modern databases sometimes exchange data with one another
via declarative schema mappings, as in data exchange and collaborative
data sharing systems. Such mappings are frequently revised and refined
as new data becomes available, new cross-reference tables are created,
and corrections are made. A fundamental question is how to handle
changes to these mapping definitions: in settings where the mappings
are compositional, a single mapping change may have a cascading effect
on the contents of all "downstream" database instances.

We consider how to incrementally recompute database instances in this
setting, reusing (if possible) previously computed instances to speed
up computation. We develop a principled solution that performs
cost-based exploration of recomputation versus reuse, and
simultaneously handles updates to source data and mapping definitions
through a single, unified mechanism. Our solution also takes advantage
of provenance information, when present, to speed up computation even
further. We present an implementation that takes advantage of an
off-the-shelf DBMS's query processing system, and we show
experimentally that our approach provides orders of magnitude
performance benefits on typical workloads.