Database Reference
In-Depth Information
6. (
Construct
SOtgd)
If
S
AB
={
χ
1
,...,χ
m
}
is the set where
χ
1
,...,χ
m
are all the implications from
the previous step then SOtgd is the formula
∃
∀
x
1
χ
1
∧···∧∀
x
m
χ
m
)
, where
f
is the tuple of all function symbols that appear in any of the implications in
S
AB
, and the variables in
x
i
are all the variables found in the implication
χ
i
,for
1
f
(
≤
i
≤
m
.
Return
the SOtgd
x
m
χ
m
)
.
Let us consider the well known foreign-key integrity constraints:
∃
f
(
∀
x
1
χ
1
∧···∧∀
Example 3
Let us consider Example
2
with relation
Student
(x
n
,y)
where
x
n
is the primary-key of this relation (student's id) in the schema
B
and the relation
Takes1
(x
n
,x
c
)
where
x
n
is the foreign-key of this relation.
Thus, the foreign-key integrity constraint can be given by a single tgd in
Σ
tgd
B
=
{∀
x
n
,x
c
(
Takes1
(x
n
,x
c
)
⇒∃
y
Student
(x
n
,y))
}
. Consequently, with this input
Σ
tg
B
, we have the following steps of the algorithm:
1. We obtain
S
AB
={
Takes1
(x
n
,x
c
)
⇒∃
y
Student
(x
n
,y)
}
.
2. We obtain
(
Takes1
(x
n
,x
c
)
y
f
1
(x
n
,x
c
)
⇒
Student
(x
n
,y)
.
S
AB
=
∧
=
3. We obtain
S
AB
={
Takes1
(x
n
,x
c
)
⇒
Student
(x
n
,f
1
(x
n
,x
c
))
}
.
4. Non applicable.
5. We obtain
S
AB
=
Takes1
(x
n
,x
c
)
∧¬
Student
x
n
,f
1
(x
n
,x
c
)
⇒
r
(
0
,
1
)
.
6.
Return
f
1
∀
x
n
,x
c
Takes1
(x
n
,x
c
)
∧¬
Student
x
n
,f
1
(x
n
,x
c
)
⇒
(
0
,
1
)
.
∃
r
Consequently, the output of this algorithm is the SOtgd
TgdsToConSOtgd
∀
x
n
,x
c
Takes1
(x
n
,x
c
)
y
Student
(x
n
,y)
=
⇒∃
f
1
∀
x
n
,x
c
Takes1
(x
n
,x
c
)
∧¬
Student
x
n
,f
1
(x
n
,x
c
)
⇒
(
0
,
1
)
.
∃
r
2.2.2 Transformation of Equality-Generating Constraints into
SOtgds
.
=
∀
⇒
∈
An integrity constraint (egd)
x
(φ
A
(
x
)
(
y
z
))
Σ
A
of a given schema
database
(S
A
,Σ
A
)
(in Definition
2
) has no relation from the target database
on the right-hand side of the implication. It can be directly represented by SOtgds if
we consider the equality '
.
A
=
' as a built-in binary predicate with relational symbol
r
such that for any two given tuples
y
=
=
y
1
,...,y
k
and
z
=
z
1
,...,z
k
the formula
y
.
=
z
is an abbreviation for the formula
r
(y
1
,z
1
)
∧···∧
r
(y
k
,z
k
)
.
