Database Reference
In-Depth Information
this lattice. In fact, from Theorem
12
,
A
⊗
B
A
and
A
⊗
B
B
(for each dis-
joint component
A
j
⊗
B
i
in
A
⊗
B
,
A
j
⊗
B
i
=
TA
j
∩
TB
i
⊆
TA
j
and
A
j
⊗
B
i
=
TA
j
∩
TB
i
⊆
TB
i
). If
A
B
with a mapping
σ
:{
1
,...,m
}→{
1
,...,k
}
such that
∀
1
≤
j
≤
m
.T A
j
⊆
TB
σ(j)
, then
A
A
⊗
B
as well (we define a map-
ping
σ
:{
such that
σ
(j)
=
1
,...,m
}→{
(
1
,
1
),...,(
1
,k),...,(m,
1
),...(m,k)
}
(j,σ(j)),
1
≤
j
≤
m
, with
TA
j
⊆
TA
j
⊗
TB
σ(j)
=
TA
j
∩
TB
σ(j)
=
TA
j
). Thus,
if
A
B
then
A
⊗
B
≈
A
.
A
⊕
B
.
Consequently, the equivalence in this lattice is equal to the strong behavioral
equivalence of the
DB
category (from Corollary
14
in Sect.
3.4.1
). We have to show
that the following laws hold:
1.
A
⊕
A
≈
A, A
⊗
A
≈
A
; (idempotency)
2.
A
⊕
Hence, inf
(A,B)
=
A
⊗
B
and sup
(A,B)
=
≈
⊕
⊗
≈
⊗
B
B
A, A
B
B
A
; (commutativity)
3.
A
⊕
(B
⊕
(A
⊕
B)
⊕
C)
≈
A, A
⊗
(B
⊗
C)
≈
(A
⊗
B)
⊗
C
; (associativity)
0
4.
A
⊕⊥
≈
A, A
⊗
Υ
≈
A
; (bottom-top laws, see Proposition
10
)
A
⊕
(A
⊕
5.
A
B)
. (absorption)
The commutative and idempotency laws hold directly from the definitions of
⊕
(with Lemma
17
) and
≈
(A
⊗
B), A
≈
A
⊗
⊗
, and from the results obtained previously. The second
associative law for '
⊕
'
used in definitions for the sets of simple objects
S
A
,S
B
in Definition
57
. The iso-
morphism (a)
A
' holds from the transitive property of the PO relation '
C
comes from definition of matching in
Theorems
12
, and the fact that disjoint union is commutative up to an isomorphism.
Hence, from the fact that isomorphic objects are behaviorally equivalent, we obtain
the associativity
A
⊗
(B
⊗
C)
≈
(A
⊗
B)
⊗
C
for the matching operator. Let us
show absorbtion: We have
(A
⊗
(B
⊗
C)
≈
(A
⊗
B)
⊗
⊗
B)
A
and hence, from point 4 of Lemma
17
,
A
⊕
(A
⊕
(A
⊗
B)
≈
A
. Analogously, from point 3 of Lemma
17
,
A
B)
and from
(A
⊕
above,
A
⊗
B)
≈
A
.
=
A
i
∈
K
A
i
∈
0
For any subset
K
⊆
Ob
DB
,
⊥
inf
(K)
Ob
DB
and
Υ
=
A
i
∈
K
A
i
∈
=
sup
(K)
Ob
DB
(it holds also for the limit case when
K
Ob
DB
, with
=
A
i
∈
Ob
DB
A
i
=
A
i
⊆
Υ
, i.e.,
A
i
Υ
, so that sup
(Ob
DB
)
Υ
∈
Ob
DB
). Conse-
quently, the lattice
(Ob
DB
,
)
for every subset
K
has the greatest-lower-bound and
the least-upper-bound, and hence it is a complete lattice.
C
∈
C
⊆
C
An element
B
in a lattice
,
B
,is
compact
iff, for every
X
such that
sup
(X)
, then there exists a
finite X
⊆
ω
X
such that
B
sup
(X)
exists and
B
sup
(X
)
: the set of compact elements in
. For example, the
lattice of subsets of a set is an algebraic lattice where the compact elements are finite
sets.
A lattice is
algebraic
if it is
complete
and
compactly generated
: a lattice
(
C
,
)
is compactly generated if every element of
C
is denoted by
Comp
C
C
is a sup of compact elements less then
or equal to it, i.e., for every
A
∈
C
,
A
≈
sup
{
B
∈
Comp
C
|
B
A
}
. The closed ele-
ments, obtained by a closure operator
from finite subsets, are compact elements.
Clearly, finite lattices are algebraic. But in our case, the complete database lattice
L
DB
in Proposition
51
is infinite, thus we need to investigate if it is algebraic or not.
J
