Database Reference
In-Depth Information
or in other words, the operation of composition
◦
for the new algorithm
Compose
is
associative.
Let us show that we are able to define the identity mappings for any schema
A
,
such that composition with another arrow is equal to this arrow:
Lemma 5
For a schema
A
=
(S
A
,Σ
A
) we define its identity mapping as
∀
S
A
x
i
r
i
(
x
i
)
r
i
(
x
i
)
|
M
AA
=
Id
A
=
⇒
r
i
∈
:
A
→
A
.
Consequently
,
for any two mappings
M
BA
:
B
→
A
and
M
AB
:
A
→
B
,
M
AB
◦
Id
A
=
Compose(
M
AB
, Id
A
)
=
M
AB
and Id
A
◦
M
BA
=
Compose(Id
A
◦
M
BA
)
=
M
BA
.
Proof
Let us verify that
Compose(
M
AB
, Id
A
)
=
M
AB
. In step 2, each
r
i
(
y
i
)
on the left-hand side of the implication in
S
BD
is replaced by the conjunction
r
i
(
x
i
)
.
=
x
i
)
. Consequently, in step 3, we replace all
y
's on the right-hand side
of implications with
x
's and eliminate the equations
y
i
∧
(
y
i
.
=
x
i
from the left-hand side
of these implications, so that we obtain exactly the SOtgd of the mapping
M
AB
.
=
M
BA
. In step 2, each
r
i
(
y
i
)
on the
left-hand side of the implication in
S
BD
such that there is an implication
φ
i
(
y
i
)
Let us verify that
Compose(Id
A
◦
M
BA
)
⇒
.
=
r
i
(
t
i
)
in
S
AB
is replaced by the conjunction
φ
i
(
y
i
)
∧
(
y
i
t
i
)
. Consequently, in
step 3, we replace all
y
's on the right-hand side of implications with terms in
t
i
and
we eliminate the equations
y
i
.
=
t
i
from the left-hand side of these implications, so
that we obtain exactly the SOtgd of the mapping
M
BA
.
Based on these two lemmas, we have the following important corollary:
Corollary 2
The database schemas and the composition of their schema mappings
can be represented by a sketch category
.
Proof
It is a direct result of Lemma
4
which demonstrates the associativity for com-
position of the mappings (i.e., morphisms of a sketch category) and Lemma
5
that
demonstrates that for each schema (i.e., object of a sketch category) there is an
identity mapping.
Note that the identity SOtgds are not tuple-generating, that is, they do not insert
new tuples in the target database. From the fact that each implication is of the form
r
i
(
x
i
)
r
i
(
x
i
)
and hence if for a tuple of values
c
,
r
i
(
c
)
is true, then
c
is already a
tuple in the relation
r
i
. Thus, this implication is true without inserting a new tuple
in the relation
r
i
.
From the logical point of view, the SOtgd of an identity mapping is a tautol-
ogy and, consequently, its conjunction with another SOtgd is equivalent logically
to this SOtgd. Consequently, based on this general algorithm, we can represent the
⇒
