Database Reference
In-Depth Information
By the definition of algorithm M
AXIMUM
R
ECOVERY
, we know that there exists a de-
pendency
ψ
(
x
,
y
)
∧
C(
x
)
→
α
(
x
) in
Γ
such that
α
(
x
) is a rewriting of
∃
y
ψ
(
x
,
y
) over
R
1
.Thensince
T
(
a
,
y
),
a
is a tuple of constant values, and (
T
,
S
2
)
|
=
∃
y
ψ
|
=
Γ
,we
(
a
). Now consider the queries
Q
(
x
) and
Q
(
x
) defined by formulae
know that
S
2
|
=
α
Q
(
S
2
).Furthermore,
∃
y
ψ
(
x
,
y
) and
α
(
x
), respectively. Since
S
2
|
=
α
(
a
), we know that
a
∈
we know that
Q
(
S
2
)=
certain
M
(
Q
,
S
2
),andthen
a
∈
certain
M
(
Q
,
S
2
). In particular, since
T
(
a
,
y
).We
have shown that for every σ
∈
Σ of the form ϕ(
x
)
→∃
y
ψ(
x
,
y
),if
S
1
|
= ϕ(
a
) for some tu-
ple
a
,then
T
|
∈
S
OL
M
(
S
2
), we know that
a
∈
Q
(
T
), from which we conclude that
T
|
=
∃
y
ψ
=
∃
y
ψ
(
a
,
y
). Thus, we have that (
S
1
,
T
)
|
=
Σ
and, therefore,
T
∈
S
OL
M
(
S
1
).
This concludes the proof of the theorem.
Example 20.33 Let R
1
be a schema consisting of a unary relation
P
and a binary relation
R
, R
2
be a schema consisting of a binary relation
T
and
M
=(R
1
,
R
2
,
Σ
),where
Σ
is a set
of dependencies consisting of the following st-tgds:
P
(
x
)
→
T
(
x
,
x
)
,
R
(
x
,
y
)
→
T
(
x
,
y
)
.
M
=(R
2
,
R
1
,
In order
, algorithm
M
AXIMUM
R
ECOVERY
first computes a source rewriting of target query
T
(
x
,
x
):
to compute a maximum recovery
Γ
) of
M
P
(
x
)
∨
R
(
x
,
x
)
,
and it adds dependency
T
(
x
,
x
)
∧
C(
x
)
→
P
(
x
)
∨
R
(
x
,
x
)
(20.9)
to
Γ
. Then it computes a rewriting of target query
T
(
x
,
y
) (see
Example 20.31
):
(
P
(
x
)
∧
x
=
y
)
∨
R
(
x
,
y
)
,
and it finishes by adding dependency
T
(
x
,
y
)
∧
C(
x
)
∧
C(
y
)
→
(
P
(
x
)
∧
x
=
y
)
∨
R
(
x
,
y
)
(20.10)
to
. Given that
(20.10)
logically implies
(20.9)
, we conclude that the mapping specified
by dependency
(20.10)
is a maximum recovery of
Γ
M
.
From
Theorem 20.32
and
Propositions 20.27
and
20.28
, we conclude that algorithm
M
AXIMUM
R
ECOVERY
can also be used to compute inverses and quasi-inverses.
Corollary 20.34
Let
M
=(R
1
,
R
2
,
Σ
)
,where
Σ
is a finite set of st-tgds. If
M
is invert-
ible (quasi-invertible), then on input
M
, algorithm
M
AXIMUM
R
ECOVERY
computes an
inverse (quasi-inverse) of
M
.
One of the interesting features of algorithm M
AXIMUM
R
ECOVERY
is the use of query
rewriting, as it allows us to reuse in the computation of the inverse operator the large
number of techniques developed to deal with the problem of query rewriting. However,
one can identify two drawbacks in this procedure. First, algorithm M
AXIMUM
R
ECOVERY
