Database Reference
In-Depth Information
(
u
) computed in line
8
of this algorithm is a source rewriting of target query
P
(
u
). We leave to the reader the
proof of this fact, and also the proof that procedure M
AXIMUM
R
ECOVERY
F
ULL
is correct
(see
Exercise 22.3
).
M
AXIMUM
R
ECOVERY
for the case of full st-tgds, as the formula
α
Example 20.36 Let R
1
be a schema consisting of a unary relation
A
and a binary relation
B
, R
2
be a schema consisting of binary relations
D
and
E
,and
M
=(R
1
,
R
2
,
Σ
),where
Σ
is a set of dependencies consisting of the following st-tgds:
A
(
x
)
→
D
(
x
,
x
)
(20.11)
B
(
x
,
y
)
→
D
(
y
,
y
)
(20.12)
B
(
x
,
x
)
→
E
(
x
)
.
(20.13)
M
=(R
2
,
R
1
,
In order
, algorithm
M
AXIMUM
R
ECOVERY
F
ULL
first considers the predicate symbol
D
fromR
1
. For this sym-
bol, it generates a fresh tuple (
u
1
,
u
2
) of variables. Let
to compute a maximum recovery
Γ
) of
M
Δ
be the empty set. Then it considers
the two dependencies in
mentioning the predicate symbol
D
in its right-hand side. In the
case of st-tgd
(20.11)
, it adds
Σ
∃
x
(
A
(
x
)
∧
x
=
u
1
∧
x
=
u
2
) to
Δ
. In the case of st-tgd
(20.12)
,
it first notices that this dependency has to be read as
∃
xB
(
x
,
y
)
→
D
(
y
,
y
), and then it adds
∃
. Thus, once the dependencies with predicate symbol
D
in its right-hand side have been processed, it holds that:
y
∃
x
(
B
(
x
,
y
)
∧
y
=
u
1
∧
y
=
u
2
) to
Δ
Δ
=
{∃
x
(
A
(
x
)
∧
x
=
u
1
∧
x
=
u
2
)
,
∃
y
∃
x
(
B
(
x
,
y
)
∧
y
=
u
1
∧
y
=
u
2
)
}
.
Therefore, the following dependency is added to
Γ
:
P
(
u
1
,
u
2
)
→
x
A
(
x
)
x
=
u
2
x
B
(
x
,
y
)
y
=
u
2
.
(20.14)
∃
∧
x
=
u
1
∧
∨∃
y
∃
∧
y
=
u
1
∧
In the same way, algorithm M
AXIMUM
R
ECOVERY
F
ULL
considers all the dependencies in
Σ
mentioning predicate
E
in its right-hand side, and computes the following dependency:
E
(
u
3
)
→∃
x
(
B
(
x
,
x
)
∧
x
=
u
3
)
.
(20.15)
Given that R
1
consists only of predicate symbols
D
and
E
, we conclude that the mapping
specified by dependencies
(20.14)
and
(20.15)
is a maximum recovery of
M
.
As for the case of algorithmM
AXIMUM
R
ECOVERY
, from
Theorem20.32
and
Propositions
20.27
and
20.28
, we conclude that algorithmM
AXIMUM
R
ECOVERY
F
ULL
can also be used
to compute inverses and quasi-inverses.
Corollary 20.37
is a finite set of full st-tgds with each
dependency in it having a single atom in its right-hand side. If
Let
M
=(R
1
,
R
2
,
Σ
)
,where
Σ
M
is invertible (quasi-
invertible), then on input
M
, algorithm
M
AXIMUM
R
ECOVERY
F
ULL
computes an inverse
(quasi-inverse) of
M
.
