Database Reference
In-Depth Information
Algorithm 20.1 M
AXIMUM
R
ECOVERY
Require:
M
12
=(R
1
,
R
2
,
Σ
) with
Σ
a finite set of st-tgds
Ensure:
M
21
=(R
2
,
R
1
,
Γ
) is a maximum recovery of
M
:= 0
2:
for all ϕ
Γ
1:
(
x
)
→∃
y
ψ
(
x
,
y
) in
Σ do
Q
(
x
) :=
∃
y
ψ
(
x
,
y
)
3:
let
α
(
x
) be the output of algorithm Q
UERY
R
EWRITING
with input
M
12
and
Q
4:
Γ
:=
Γ
∪{
ψ
(
x
,
y
)
∧
C(
x
)
→
α
(
x
)
}
5:
6:
end for
Proof
From
Proposition 20.30
, it is straightforward to conclude that algorithm
M
AXIMUM
R
ECOVERY
runs in exponential time. Assume that
M
=(R
1
,
R
2
,
Γ
) is the
M
output of the algorithm M
AXIMUM
R
ECOVERY
with input
M
. In order to prove that
M
is a recovery of
M
M
is a maximum recovery of
, we first show that
, that is, we prove
∈M ◦M
.
Let
S
be an instance of R
1
and let
T
be the canonical universal solution for
S
under
M
that for every instance
S
of R
1
, it holds that (
S
,
S
)
∈M
, from which we conclude that (
S
,
S
)
∈M ◦M
since
. Next we show that (
T
,
S
)
(
S
,
T
)
∈M
.Let
σ
∈
Γ
. We need to show that (
T
,
S
)
|
=
σ
. Assume that
σ
is of the form
ψ
(
x
,
y
)
∧
C(
x
)
→
α
(
x
),andthat
a
is a tuple of values from
T
such that
T
|
=
∃
y
(
ψ
(
a
,
y
)
∧
C(
a
)). We need to show that
S
|
=
α
(
a
). Consider the conjunctive query
Q
(
x
) defined by
the formula
Q
(
T
).
Thus, from the results about query answering proved in
Chapter 7
and the fact that
T
is the canonical universal solution for
S
under
∃
y
ψ
(
x
,
y
).SinceC(
a
) holds and
T
|
=
∃
y
ψ
(
a
,
y
), we obtain that
a
∈
M
∈
certain
M
(
Q
,
S
).
, we obtain that
a
Consider now the query
Q
(
x
) defined by formula
(
x
). By the definition of algorithm
M
AXIMUM
R
ECOVERY
,wehavethat
Q
is a rewriting of
Q
over schema R
1
,andthen
certain
M
(
Q
,
S
)=
Q
(
S
). Thus, we have that
a
α
Q
(
S
),andthen
S
∈
|
=
α
(
a
),whichwasto
be shown.
Given that
M
is a recovery of
M
and D
OM
(
M
)=I
NST
(R
1
), we know from
Propo-
M
is a maximum recovery of
M ◦M
◦M ⊆ M
sition 20.21
that
M
if
.Nextwe
∈ M ◦M
,thenS
OL
M
(
S
2
)
show that if (
S
1
,
S
2
)
⊆
S
OL
M
(
S
1
), from which we con-
M ◦M
◦M ⊆ M
∈ M ◦M
◦M
clude that
. To see why this is the case, let (
S
,
T
)
.
Then there exist instances
T
1
,
R
1
of R
2
and R
1
, respectively, such that (
S
,
T
1
)
∈ M
,
∈M
and (
S
1
,
T
)
∈M ◦M
, we have by hypothe-
(
T
1
,
S
1
)
∈M
. Then given that (
S
,
S
1
)
sis that S
OL
M
(
S
1
)
⊆
S
OL
M
(
S
). Thus, from the fact that (
S
1
,
T
)
∈M
, we conclude that
(
S
,
T
)
∈M
, which was to be shown.
Let (
S
1
,
S
2
)
∈ M ◦M
,and
T
an instance of R
2
such that (
S
1
,
T
)
∈ M
and
(
T
,
S
2
)
∈M
. We need to prove that S
OL
M
(
S
2
)
⊆
S
OL
M
(
S
1
). To this end, assume that
T
∈
S
OL
M
(
S
2
). Next we show that
T
∈
S
OL
M
(
S
1
).Let
σ
∈
Σ
be a dependency of the
form
ϕ
(
x
)
→∃
y
ψ
(
x
,
y
), and assume that
S
1
|
=
ϕ
(
a
) for some tuple
a
of constant val-
ues. We show next that
T
|
=
∃
y
ψ
(
a
,
y
). Given that
S
1
|
=
ϕ
(
a
), we have that for every
T
∈
S
OL
M
(
S
1
), it holds that
T
|
(
a
,
y
). In particular, it holds that
T
=
∃
y
ψ
|
=
∃
y
ψ
(
a
,
y
).
