Database Reference
In-Depth Information
It is important to notice that, as for the case of procedure M
AXIMUM
R
ECOVERY
, algo-
rithm M
AXIMUM
R
ECOVERY
F
ULL
returns mappings that are specified by dependencies
that extend st-tgds with disjunctions in their right-hand sides. As we have mentioned be-
fore, these types of mappings are difficult to use in the data exchange context and, thus,
it is natural to ask whether the use of disjunction in the output languages of algorithms
M
AXIMUM
R
ECOVERY
and M
AXIMUM
R
ECOVERY
F
ULL
can be avoided, and, in particu-
lar, whether the maximum recovery of a mapping specified by st-tgds can be specified in
the same mapping language. We conclude this section by given a negative answer to this
question not only for the notion of maximum recovery, but also for the notions of inverse
and quasi-inverse.
Proposition 20.38
There exists a mapping
M
=(R
1
,
R
2
,
Σ
)
specified by a finite set
Σ
of
full st-tgds that is invertible, but has no inverse specified by a finite set of tgds.
Proof
We only present the mapping, and leave the proof as an exercise. Let R
1
be a
schema consisting of a unary predicate
A
and a binary predicate
B
, R
2
a schema consisting
of unary predicates
D
,
E
and a binary predicate
F
,and
Σ
be a set consisting of the following
full st-tgds:
A
(
x
)
→
D
(
x
)
,
A
(
x
)
→
F
(
x
,
x
)
,
B
(
x
,
y
)
→
F
(
x
,
y
)
,
B
(
x
,
x
)
→
E
(
x
)
.
M
=(R
2
,
R
1
,
Σ
),where
Σ
The mapping
M
is invertible; in fact its inverse is a mapping
consists of the following dependencies
D
(
x
)
→
A
(
x
)
,
F
(
x
,
y
)
∧
x
=
y
→
B
(
x
,
y
)
,
E
(
x
)
→
B
(
x
,
x
)
.
M
is indeed an inverse, and that it cannot be specified
The reader is invited to verify that
by a finite set of tgds.
Proposition 20.38
shows that the language of tgds is not closed under the notion of inverse.
By combining this result with
Propositions 20.27
and
20.28
, we conclude that the same
holds for the notions of quasi-inverse and maximum recovery.
Corollary 20.39
of
full st-tgds that is quasi-invertible, but has neither a quasi-inverse nor a maximum recovery
specified by a finite set of tgds.
There exists a mapping
M
=(R
1
,
R
2
,
Σ
)
specified by a finite set
Σ
