Database Reference
In-Depth Information
x
and
y
i
⊆{
of
χ
by replacing each atom
r
i
(
x
i
,
y
i
)
in
φ
2
(where
x
i
⊆
y
1
,..y
k
}
)
with the equation
(f
r
i
(
x
i
,
y
i
)
.
1
)
by introducing its characteristic function
f
r
i
(i.e., for a given Tarski's interpretation
I
T
in Definition
1
,
I
T
(f
r
i
)(
c
)
=
=
1if
c
is a
tuple of the interpreted relation
I
T
(r
i
)
; 0 otherwise).
5. (
Construct
M
AD
)
If
S
BD
={
χ
1
,...,χ
j
}
is the set, where
χ
1
,...,χ
j
are all the implications from
the previous step, then
M
AD
is a singleton set composed of an SOtgd element
∃
∀
z
1
χ
1
∧···∧∀
g
(
z
j
χ
j
),
where
g
is the tuple of all function symbols that appear in any of the implications
in
S
BD
, and where the variables in
z
i
are all the variables found in the implication
χ
i
,for1
≤
i
≤
j
.
Return
M
AD
={∃
g
(
∀
z
1
χ
1
∧···∧∀
z
j
χ
j
)
}:
A
→
D
.
is another generalization of the previous algorithm
in [
5
]; it is necessary for the introduction of characteristic functions in the step 4 of
this new algorithm.
Note that we also do not obtain the empty composition if there is no direct map-
ping from the relations in
The assumption that
2
⊂
U
A
into
D
. For example, let us consider the database
)
with
S
A
=
Takes
(x
n
,x
c
)
,
A
=
(S
A
,
∅
)
with
S
B
=
Takes1
(x
n
,x
c
),
Professor
(x
p
)
,
B
=
(S
B
,
∅
)
with
S
D
=
Professor1
(x
p
)
D
=
(S
D
,
∅
and with mappings
M
AB
=
∀
x
n
∀
x
c
Takes
(x
n
,x
c
)
⇒
Takes1
(x
n
,x
c
)
:
A
→
B
and
M
BD
=
∀
x
p
Professor
(x
p
)
⇒
Professor1
(x
p
)
:
B
→
D
.
Then,
M
AD
=
M
BD
◦
M
AB
=
∃
f
Professor
∀
x
p
f
Professor
(x
p
)
=
1
⇒
Professor1
(x
p
)
:
A
→
D
.
Example 5
Let us consider Example 2.3 in [
5
] (also discussed in our Example
2
)
for the composition of SOtgds
M
AD
=
M
BD
◦
M
AB
, where
M
AB
=
∀
x
c
Takes
(x
n
,x
c
)
⇒
Takes1
(x
n
,x
c
)
,
x
n
∀
x
c
Takes
(x
n
,x
c
)
⇒
Student
(x
n
,y)
,
∀
x
n
∃
y
∀
