Database Reference

In-Depth Information

Proposition 20.28
(1) There exists a mapping specified by a finite set of st-tgds that is

not quasi-invertible but has a maximum recovery.

(2) For every mapping

that is total, closed-down on the left and quasi-invertible, there

exists a mapping that is a maximum recovery of

M

M
is a maximum

M

and, moreover,

M
is a quasi-inverse and recovery of

recovery of

M

if and only if

M

.

Note that part (1) of this proposition has already been proved in
Proposition 20.27
.

Given that inverses and quasi-inverses are not guaranteed to exist for the class of map-

pings specified by st-tgds, we study in
Sections 20.1
and
20.1
the decidability of invert-

ibility and quasi-invertibility for this class of mappings. On the other hand, the problem of

verifying whether a mapping

has a maximum recovery becomes trivial in this context,

as every mapping specified by this class of dependencies admits a maximum recovery.

Thus, we only consider here the fundamental problem of verifying, given mappings

M

M

M
specified by st-tgds, whether

M
is a maximum recovery of

and

. Somewhat sur-

prisingly, not only is this problem undecidable, but also the problem of verifying whether

a mapping

M

M
is a recovery of a mapping

M

.

M
=

Theorem 20.29
The problem of verifying, given mappings

M

=(R
1
,
R
2
,

Σ

12
)
and

M
is a recovery (maximum

(R
2
,
R
1
,

Σ

21
)
with

Σ

12
and

Σ

21
finite sets of st-tgds, whether

recovery) of
M
is undecidable.

As we have mentioned in the previous sections, we are still missing the algorithms for com-

puting the inverse operators introduced in this chapter. In the next section, we present a uni-

fied algorithm for computing these operators, which uses some query rewriting techniques,

and takes advantage of the tight connections between the notions of inverse, quasi-inverse

and maximum recovery shown in
Propositions 20.14
,
20.27
and
20.28
.

20.3 Computing the inverse operator

Up to this point, we have introduced and compared three notions of inverse proposed in the

literature, focusing mainly on the fundamental problem of the existence of such inverses.

Arguably, the most important problem about these operators is the issue of how to compute

them for the class of mappings specified by st-tgds. This problem has been studied for the

case of the notions of inverse, quasi-inverse and maximum recovery. In this section, we

present an algorithm for computing maximum recoveries of mappings specified by st-tgds,

which by the results of the previous sections can also be used to compute inverses and

quasi-inverses for this type of mapping. Interestingly, this algorithm is based on
query

rewriting
, which greatly simplifies the process of computing such inverses.

We start by introducing the notion of query rewritability over the source, which is similar

to the notion of rewritability introduced in
Section 7.5
.Let

be a mapping from a schema

R
1
to a schema R
2
and
Q
a query over schema R
2
. Then a query
Q
is said to be a
rewriting

of Q over the source
if
Q
is a query over R
1
such that for every
S

M

∈

I
NST
(R
1
), it holds