Inverting Schema Mappings

Fagin, R.
Fagin, R
Proc. PODS 2006
Citations range: 
50 - 99
Fagin2006InvertingSchema.pdf433.52 KB

A schema mapping is a specification that describes how data
structured under one schema (the source schema) is to be
transformed into data structured under a different schema
(the target schema). Although the notion of an inverse of
a schema mapping is important, the exact definition of an
inverse mapping is somewhat elusive. This is because a
schema mapping may associate many target instances with
each source instance, and many source instances with each
target instance. Based on the notion that the composition
of a mapping and its inverse is the identity, we give a formal
definition for what it means for a schema mapping M0 to be
an inverse of a schema mapping M for a class S of source instances.
We call such an inverse an S-inverse. A particular
case of interest arises when S is the class of all instances, in
which case an S-inverse is a global inverse. We focus on the
important and practical case of schema mappings defined by
source-to-target tuple-generating dependencies, and uncover
a rich theory. When S is defined by a set of dependencies
with a finite chase, we show how to construct an S-inverse
when one exists. In particular, we show how to construct
a global inverse when one exists. Given M and M0, we
show how to define the largest class S such that M0 is an
S-inverse of M.