Database Reference
In-Depth Information
M
AD
,
h
Student
(x
1
,y
3
)
.
so that for any instance
D
that satisfies also the mapping
=
1
is equivalent to
y
3
.
=
f
1
(x
1
)
.
2.3.1 Categorial Properties for the Schema Mappings
Now we will show that this new algorithm for composition of schema mappings ex-
pressed by SOtgds can be used as the composition of morphisms in a category where
the objects are database schemas and morphisms (the arrows in such a category)
are the mappings. We recall that, as it was presented in [
5
], the space of instances
Inst(
M
AB
)
of a mapping
M
AB
:
A
→
B
is a binary relation between instance-
databases of
A
and target instance-databases of
B
. Consequently, the schema map-
ping
M
AC
is a composition of two schema mappings
M
AB
and
M
BC
, denoted by
M
BC
◦
M
AB
, if the space of instances of
M
AC
is the set-theoretic composition of
the spaces of instances of
M
BC
. The advantage of this approach is that
the set of formulae defining a composition
M
AB
and
M
AC
of
M
AB
and
M
BC
is unique
up
to logical equivalence. Consequently,
(Comp)
M
AC
=
M
BC
◦
M
AB
if
Inst(
M
AC
)
=
Inst(
M
AB
)
∗
Inst(
M
BC
),
where
∗
denotes the composition of binary relations.
Lemma 4
The composition of two schema mappings
M
AB
and
M
BC
,
presented
by the new algorithm as
M
BC
◦
M
AB
Compose(
M
AB
,
M
BC
)
,
is associative
.
Proof
From the fact that the new algorithm is a conservative extension of the algo-
rithm in [
5
] (see the proof of Proposition 4.1 in [
5
] for more details) such that in the
new step 4 we only replace the remaining atoms (that are removed in this step) by
their characteristic functions, the property (Comp) above is still valid. Consequently,
M
AD
=
M
CD
◦
(
M
BC
◦
M
AB
)
=
M
CD
◦
M
AC
if
M
AD
)
=
M
AC
)
∗
M
CD
)
Inst(
Inst(
Inst(
=
Inst(
M
BC
)
∗
M
AB
)
∗
M
CD
)
(by (Comp))
Inst(
Inst(
=
Inst(
M
AB
)
∗
Inst(
M
BC
)
∗
Inst(
M
CD
). (
by associativity of
∗
)
M
AD
=
Analogously,
(
M
CD
◦
M
BC
)
◦
M
AB
=
M
BD
◦
M
AB
if
Inst
M
AD
=
Inst(
M
AB
)
∗
Inst(
M
BD
)
Inst(
M
CD
)
(by (Comp))
=
Inst(
M
AB
)
∗
M
BC
)
∗
Inst(
=
Inst(
M
AB
)
∗
Inst(
M
BC
)
∗
Inst(
M
CD
). (
by associativity of
∗
)
M
AD
)
M
AD
=
M
AD
, i.e.,
Consequently,
Inst(
=
Inst(
M
AD
)
, that is,
M
CD
◦
M
BC
)
◦
M
AB
=
M
CD
◦
M
BC
◦
M
AB
),
(
(
