Database Reference
In-Depth Information
Lemma 12
For any two simple instance-databases A and B
,
A
‡
B
=
B
‡
A and
A
‡
B
A
B.
Proof
If
A
B
, the claim is clear because all relationships above are identities.
From Definition
27
,
(i)
A
‡
B
={
(
A
,φ
i
)
|
φ
i
∈
Σ
A
}∪{
(
B
,ψ
j
)
|
ψ
j
∈
Σ
B
}=
B
‡
A
.
Let us show that
id
A
=
B
are the
identity morphisms) is the identity morphism
id
A
‡
B
for
A
‡
B
. In fact, for
any morphisms
f
id
B
(where
id
A
:
A
→
A,id
B
:
B
→
g
:
A
‡
B
→
C
‡
D
(with
f
:
A
→
C,g
:
B
→
D
),
◦
(id
A
=
◦
◦
=
(f
g
, and for any morphism
h
k
:
C
‡
D
→
A
‡
B
(with
h
:
C
→
A,k
:
D
→
B
),
(id
A
g)
id
B
)
(f
id
A
)
(g
id
B
)
f
id
B
)
◦
(k
h)
=
(id
A
◦
k)
(id
B
◦
k)
=
h
k
. Thus,
id
=
(id
A
id
B
)
:
A
‡
B
→
A
‡
B
is equal
to the identity arrow of
A
‡
B
, i.e.,
(ii)
id
A
id
A
‡
B
.
In point 2 of Example
19
, it was demonstrated that
(id
A
id
B
=
:
→
id
B
)
A
B
A
B
is the identity arrow
id
A
B
of the object
A
B
as well. That is,
(iii)
id
A
id
A
B
.
Let us show now that the morphism
(id
A
id
B
=
id
B
)
:
A
‡
B
→
A
B
is an
isomorphism, with its inverse morphism
id
B
)
OP
id
O
A
id
O
B
=
(id
A
=
id
A
id
B
:
→
A
B
A
‡
B.
In fact,
id
B
)
OP
(id
A
id
B
)
◦
(id
A
=
(id
A
id
B
)
◦
(id
A
id
B
)
=
(id
A
◦
id
A
)
(id
B
◦
id
B
)
=
id
A
id
B
from
(
iii
)
id
A
B
:
=
A
B
→
A
B
the identity
),
and analogously,
id
B
)
OP
(id
A
◦
(id
A
id
B
)
=
id
B
from
(
ii
)
id
A
=
id
A
‡
B
:
A
‡
B
→
A
‡
B
the identity
).
Consequently,
(id
A
id
B
)
:
A
‡
B
→
A
B
is an isomorphism, i.e.,
B
.
Thus, we have from (iv) and (i) that
A
B
A
‡
B
=
B
‡
A
B
A
and hence
A
(iv)
A
‡
B
A
B
B
A
as it was demonstrated in Lemma
9
.
Notice that
T(A
‡
B)
={
(
A
,v
i
)
|
v
i
∈
TA
}∪{
(
B
,v
j
)
|
v
j
∈
TB
}=
TA
‡
TB
=
T(A
}=
id
A
id
B
=
={
|
v
i
∈
}∪{
|
v
j
∈
id
A
id
B
=
B)
(
1
,v
i
)
TA
(
2
,v
j
)
TB
id
A
B
. However, from (iv),
id
A
‡
B
=
=
id
A
B
, so that for the
T(A
‡
B)
T(A
B)
