Database Reference
In-Depth Information
M
is a quasi-inverse of
(R
2
,
R
1
,
Σ
21
)
with
Σ
12
and
Σ
21
finite sets of st-tgds, whether
M
is undecidable.
20.2 Bringing exchanged data back: the recovery of a schema mapping
As we mentioned before, a drawback of the notions of inverse and quasi-inverse is that not
every mapping specified by a set of st-tgds is guaranteed to have an inverse under these
notions. In this section, we present the concepts of recovery and maximum recovery, that
were introduced to overcome this limitation.
The notion of recovery is defined by following a different approach to that of inverses
and quasi-inverses. In fact, the main goal behind this notion is not to define an inverse
operator, but instead to give a formal definition for what it means for a mapping
M
to
M
is called a
recover
sound information
with respect to a mapping
M
. Such a mapping
recovery of
. But given that, in general, there may exist many possible recoveries for a
given mapping, it is also necessary to introduce a way to compare alternative recoveries.
This naturally gives rise to the notion of maximum recovery, which is a mapping that brings
back the maximum amount of sound information.
Let
M
M
be a mapping from a schema R
1
to a schema R
2
,andId
R
1
the identity schema
mapping over R
1
,thatis,Id
R
1
=
{
(
S
,
S
)
|
S
∈
I
NST
(R
1
)
}
.Whentryingtoinvert
M
,the
M
from R
2
to R
1
such that
M ◦M
= Id
R
1
;ifsucha
ideal would be to find a mapping
M
gives as a result exactly the initial source instance. Unfortunately, in most cases this ideal is
impossible to reach (for example, for the case of mappings specified by st-tgds). But then
at least one would like to find a schema mapping
mapping exists, then we know that if we use
M
to exchange data, the application of
M
2
that does not forbid the possibility of
recovering the initial source data. This gives rise to the notion of recovery.
Definition 20.18 (Recovery) Let
M
be a mapping from a schema R
1
to a schema R
2
,
M
a mapping from R
2
to R
1
.Then
M
is a
recovery
of
and
M
if for every instance
∈M ◦M
.
S
∈
D
OM
(
M
), it holds that (
S
,
S
)
Being a recovery is a sound but mild requirement. Indeed, a schema mapping
M
from
a schema R
1
to a schema R
2
always has as recoveries, for example, mappings
M
1
=
M
−
1
=
I
NST
(R
2
)
×
I
NST
(R
1
) and
M
2
=
{
(
T
,
S
)
|
(
S
,
T
)
∈ M}
. If one has to choose
between
M
1
and
M
2
as a recovery of
M
, then one would probably choose
M
2
since the
space of possible solutions for an instance
S
under
M◦M
2
is smaller than under
M◦M
1
.
M
is a recovery of
In general, if
M
, then the smaller the space of solutions generated
M
is about the initial source instances. This naturally
gives rise to the notion of maximum recovery.
M ◦M
, the more informative
by
Definition 20.19 (Maximum recovery) Let
M
be a mapping from a schema R
1
to a
M
a mapping from R
2
to R
1
.Then
M
is a
maximum recovery
of
schema R
2
,and
M
if:
M
is a recovery of
1.
M
,and
M
of
M ◦M
⊆M ◦M
.
2. for every recovery
M
, it holds that
