Quasi-inverses of schema mappings

Authors: 
Fagin, R.; Kolaitis, P. G.; Popa, L.; Tan, W. C.
Author: 
Fagin, R
Kolaitis, P
Popa, L
Tan, W
Year: 
2007
Venue: 
PODS 2007
URL: 
http://www.almaden.ibm.com/cs/people/fagin/quasi.pdf
DOI: 
http://doi.acm.org/10.1145/1265530.1265548
Citations: 
65
Citations range: 
50 - 99
AttachmentSize
Fagin2007Quasiinversesofschema.pdf167.08 KB

Schema mappings are high-level specifications that describe the relationship
between two database schemas. Two operators on schema
mappings, namely the composition operator and the inverse operator,
are regarded as especially important. Progress on the study of
the inverse operator was not made until very recently, as even finding
the exact semantics of this operator turned out to be a fairly delicate
task. Furthermore, this notion is rather restrictive, since it is rare that
a schema mapping possesses an inverse.
In this paper, we introduce and study the notion of a quasi-inverse
of a schema mapping. This notion is a principled relaxation of the
notion of an inverse of a schema mapping; intuitively, it is obtained
from the notion of an inverse by not differentiating between instances
that are equivalent for data-exchange purposes. For schema mappings
specified by source-to-target tuple-generating dependencies (s-t tgds),
we give a necessary and sufficient combinatorial condition for the existence
of a quasi-inverse, and then use this condition to obtain both
positive and negative results about the existence of quasi-inverses. In
particular, we show that every LAV (local-as-view) schema mapping
has a quasi-inverse, but that there are schema mappings specified by
full s-t tgds that have no quasi-inverse. After this, we study the language
needed to express quasi-inverses of schema mappings specified
by s-t tgds, and we obtain a complete characterization. We also characterize
the language needed to express inverses of schema mappings,
and thereby solve a problem left open in the earlier study of the inverse
operator. Finally, we show that quasi-inverses can be used in many
cases to recover the data that was exported by the original schema
mapping when performing data exchange.