Database Reference
In-Depth Information
However, in order to unify this presentation with tgd's transformation in the pre-
vious section, we will have in mind the following considerations:
Each egd is logically equivalent to the sentence
¬
(φ
A
(
x
)
∧¬
(
y
.
∀
x
=
z
))
which
(
y
.
is satisfied if
φ
A
(
x
)
∧¬
=
z
)
is a
falsity
(i.e., false for every assignment of the
values to variables in
x
).
Consequently, we will represent this egd by the formula
x
φ
A
(
x
)
∧
(
y
z
)
⇒
r
(
0
,
1
)
,
∀
=
(
y
.
where
y
=
z
is equivalent to
¬
=
z
)
, i.e., an abbreviation for the formula
(y
1
=
z
1
)
∨···∨
(y
k
=
z
k
)
, as follows:
(
y
.
Σ
egd
Lemma 3
Any egd
∀
x
(φ
A
(
x
)
⇒
=
z
))
∈
A
⊆
Σ
A
of a given schema database
A
=
(S
A
,Σ
A
)
,
where
y
=
x
j
1
,...,x
j
k
⊆
x
and
z
=
x
l
1
,...,x
l
k
⊆
x
such that
j
i
=
l
i
for
1
≤
i
≤
k
,
is logically equivalent to the FOL formula
:
x
φ
A
(
x
)
z
)
⇒
r
(
0
,
1
)
,
∀
∧
(
y
=
=
z
is an abbreviation for the formula (x
j
1
=
∨···∨
(x
j
k
=
where
y
x
l
1
)
x
l
k
)
.
Proof
For any assignment
g
, the atom
r
(
0
,
1
)
cannot be satisfied because
g(
0
),g(
1
)
=
0
,
1
∈
/
R
=
=
I
T
(r
),
z
)
is logically equivalent to the f
o
r
m
ula
φ
A
(
x
)
⇒
((
y
.
so t
h
a
t
φ
A
(
x
)
⇒
(
y
=
=
z
)
∨
(
y
.
r
(
0
,
1
))
, i.e., to the formula
¬
φ
A
(
x
)
∨
=
z
)
∨
r
(
0
,
1
)
, or equivalently, to the
formula
¬
(φ
A
(
x
)
∧
(
y
=
z
))
∨
r
(
0
,
1
)
, and hence to the formula
(φ
A
(
x
)
∧
(
y
=
z
))
⇒
r
(
0
,
1
)
.
This formula does not transfer any information, differently from tgds, as it is
expected because on the right side of the implication we have the ground atom
without variables.
Based on these considerations, we can define the algorithm for transformation of
a given set of egds into a single SOtgd:
Transformation algorithm
EgdsToSOtgd(Σ
egd
A
)
Input.
A set of egds of a given schema
A
,
A
=
∀
x
1
φ
A,
1
(
x
1
)
z
1
)
,...,
x
n
φ
A,n
(
x
n
)
z
n
)
.
.
=
.
=
Σ
egd
⇒
(
y
1
∀
⇒
(
y
n
Output.
ASOtgd
1. (
Create the set of implications from egds
)
Initialize
S
AB
to be the empty set.
Put each of the
n
implications of tgds in
Σ
egd
A
.
=
,
φ
A,i
(
x
i
)
⇒
(
y
i
z
i
)
,in
S
AB
.
2. (
Convert the egds
)
Remove each implication
χ
in
S
AB
of the form
φ
A,i
(
x
i
)
.
=
⇒
(
y
i
z
i
)
from
S
AB
and add the implication
(φ
A,i
(
x
i
)
∧
(
y
i
=
z
i
))
⇒
r
(
0
,
1
)
in
S
AB
.
