Database Reference
In-Depth Information
The
ω
-cocompleteness amounts to chain-completeness, i.e., to the existence of
least upper bound of
ω
-chains. Consequently,
Σ
A
is
ω
-cocontinuous endofunctor,
i.e., a monotone function which preserves l.u.bs of
ω
-chains.
In what follows, we will pass from lattice-based concepts, as l.u.bs of directed
subsets, compact subsets, and algebraic lattices, to the categorially generalized con-
cepts as directed colimits, finitely presentable (fp) objects, and locally finitely pre-
sentable (lfp) categories, respectively:
•
A
directed colimit
in
DB
is a colimit of the functor
F
:
(J,
)
−→
DB
, where
(J,
)
is a directed partially ordered set, such that for any two objects
j,k
∈
J
there is an object
l
∈
J
such that
j
l,k
l
, considered as a category. For ex-
ample, when
J
Ob
DB
we obtain the algebraic (complete and compact) lattice
which is an directed PO-set such that for any two objects
A,B
=
∈
J
there is an
object
C
∈
J
with
A
C
and
B
C
(when
C
=
sup
(A,B)
∈
J
).
•
An object
A
is said to be
finitely presentable
(fp), or finitary, if the functor
DB
(A,
_
)
:
Set
preserves directed colimits (or, equivalently, if it pre-
serves filtered colimits). We write
DB
fp
for the full subcategory of
DB
on the
finitely presentable objects: it is essentially small. Intuitively, fp objects are “fi-
nite objects”, and a category is lfp if it can be generated from its finite ob-
jects: a
strong generator
M
of a category is its small full subcategory such that
f
DB
→
B
is an isomorphism
iff
for all objects
C
of this subcategory, given
a hom-functor
M
(C,
_
)
:
A
−→
:
M
−→
Set
, the following isomorphism of hom-setts
M
(C,B)
in
Set
is valid.
From Theorem 1.11 [
2
], a category is
locally finitely presentable
(lfp) iff it is co-
complete and has a strong generator.
M
(C,f )
:
M
(C,A)
−→
Corollary 29 DB
and
DB
sk
are concrete
,
locally small
,
and locally finitely pre-
sentable categories
(
lfp
).
Proof
Given any two objects
A
and
B
in
DB
, the hom-set
DB
(A,B)
of all arrows
f
={
f
0
:
A
−→
B
corresponds to the directed subset (see Proposition
6
)
K
|⊥
f
A
⊗
B
}⊆
Ob
DB
sk
, which is bounded algebraic (complete and compact) sub-
latice of
C
. Thus, the set of all arrows
f
:
Υ
−→
Υ
corresponds to the directed set
={
f
f
0
|⊥
⊗
=
}
K
)
(which
is a sublattice of the algebraic lattice
L
DB
in Proposition
51
, composed of only
closed objects in
DB
). Thus,
DB
is
locally small
(has small hom-sets), and, since
DB
Υ
Υ
Υ
, which is equal to the lattice
(Ob
DB
sk
,
DB
sk
,also
DB
sk
is locally small.
Let us show that the full subcategory
DB
fin
, composed of closed objects ob-
tained from
finite
database objects, is a strong generator of
DB
: in fact, if
A
⊇
B
,
=
1
≤
j
≤
m
A
j
,m
=
1
≤
i
≤
k
B
i
,k
where
A
1aretwo
finite
databases
(so that from Lemma
15
and Corollary
26
in Sect.
8.1
,
k
≥
1 and
B
≥
=
m
with a bijection
σ
:{
1
,...,m
}→{
1
,...,k
}
of simple databases
A
j
B
σ(j)
,
1
≤
j
≤
m
)thenforall
=
1
≤
l
≤
n
C
l
,m
C
≥
1in
DB
fin
,
|
DB
fin
(C,A)
|
is the rank of the complete sublattice
0
⊥
⊗
|
|
of
Ob
DB
sk
,
bounded by
D
C
A
, while
DB
fin
(C,B)
is the rank of the
0
complete sublattice of
Ob
DB
sk
,
bounded by
⊥
D
1
C
⊗
B
.From
A
B
we
