Database Reference
In-Depth Information
We can use the atomic mappings in order to compose another composed map-
pings. The algorithm for composition of SOtgds
f
∀
ψ
B,
1
)
∧···∧
∀
ψ
B,n
)
∈
M
AB
:
A
→
B
∃
x
1
(φ
A,
1
⇒
x
n
(φ
A,n
⇒
and
g
∀
ψ
D,
1
)
∧···∧
∀
ψ
D,m
)
∈
M
BD
:
B
→
D
∃
y
1
(φ
B,
1
⇒
y
m
(φ
B,m
⇒
,
presented in [
5
] for the data-exchange settings, assumes that all relational symbols
in
as well, so that a composition
of these two SOtgds does not introduce new functional symbols. Differently from
this setting in [
5
], it often happens that in our general framework, where a target
database
{
φ
B,
1
,...,φ
B,m
}
are contained in
{
ψ
B,
1
,...,ψ
B,n
}
B
is not completely determined by the mappings from the source database
A
, the target database
B
can have some relational symbols that are not used in the
mappings
.
Consequently, if these 'independent' (w.r.t. mapping
M
AB
:
A
→
B
M
AB
) relational symbols
B
M
BD
:
B
→
D
in
then we will need to introduce new
characteristic-functional symbols for them (by considering that they are the predi-
cates in FOL) during the composition of the mappings
are used in a mapping
M
AB
and
M
BD
into a com-
posed mapping
M
AD
=
M
BD
◦
M
AB
:
A
→
D
because they are not the relational
symbols in the source schema
.
Hence, in our more general setting, we need a more general algorithm than that
presented in [
5
]. Note that, differently from the data-exchange setting, the mapping
M
AB
has SOtgds where each relational symbol in
ψ
B,i
is in
A
B
, and the mapping
M
BD
has SOtgds where each relational symbol in
ψ
D,i
is in
.
Notice that this is, from a logical point of view, a conservative extension of the
algorithm in [
5
] because we only substitute some atoms with logically equivalent
equations composed by characteristic functions of the relational symbols of these
substituted atoms. This point is important as we will see in the next subsection
in order to demonstrate the associativity property of the composition of schema
mappings.
In fact, the algorithm in [
5
] is extended by the new step 4, while steps 1 and 3 are
identical (and step 2 is slightly modified) to those presented in [
5
], as follows:
D
New algorithm
Compose
(
M
AB
,
M
BD
)
M
AB
:
A
→
B
M
BD
:
B
→
D
Input.
Two schema mappings
given by a set of
SOtgds. We assumed by Definition
1
of FOL that a “sufficiently l
a
rge”
u
niverse
and
U
contains the set
2
of classic truth values for the constants 0 and 1.
Output.
A schema mapping
={
0
,
1
}
M
AD
=
M
BD
◦
M
AB
:
A
→
B
, which is the compo-
sition of
M
BD
, represented by an SOtgd.
1. (
Normalize the SOtgds in
M
AB
and
M
BD
)
Rename the functional symbols so that the functional symbols which appear in
M
AB
are all distinct from the functional symbols which appear in
M
AB
and
M
BD
.For
notational convenience, we shall refer to variables in
M
AB
as
x
's, possibly with
