Database Reference
In-Depth Information
As we can see, each monadic T-coalgebra is an
equivalent inverted
arrow in
DB
of some monadic T-algebra and vice versa: the fundamental duality property
of
DB
introduces the equivalence of monadic T-algebras and monadic T-coalgebras
and hence the equivalence of the dichotomy “
construction
versus
observation
”or
duality between induction and coinduction principles [
9
].
We have seen (from the Universal algebra considerations in Sect.
8.1.4
) that
there exists the unique universal functor
U
:
K
such that for any simple
instance-database
A
in
DB
sk
it returns the free
Σ
R
-algebra
U(A)
.
Its adjoint is the forgetful functor
F
:
DB
sk
−→
DB
sk
such that for any free algebra
U(A)
in
K
the object
F
◦
U(A)
in
DB
sk
is equal to its carrier-set
A
(for each
n
-ary
operation
o
i
∈
Σ
R
,theterm
o
i
(R
1
,...,R
n
)
∈
U(A)
with
R
i
∈
A
,
i
=
K
−→
1
,...,n
,is
evaluated into some view (
computed
relation) of this closed object
A
in
DB
sk
).
Finitariness
. In a locally finitely presentable (lfp) category, every object can be
given as the directed (or filtered) colimit of the finitely presentable (fp) objects.
Hence, if the action of a monad preserves this particular kind of colimits, its action
on any object will be determined by its action on the fp objects; such a monad is
called finitary.
Let us verify that the power-view closure 2-endofunctor
T
:
DB
−→
DB
is a
finitary
monad.
Proposition 58
DB
is immedi-
ate from the universal property of composed adjunction (UT
sk
, In
sk
F,In
sk
η
U
T
sk
·
η
sk
,ε
U
·
The power-view closure
2
-endofunctor T
:
DB
−→
Id
DB
.
It is finitary
.
The category
DB
is equivalent to the
(
Eilenberg-Moore
)
category T
alg
of all
monadic T-algebras and is equivalent to the category T
coalg
of all monadic T-
coalgebras
.
Its equivalent skeletal category
DB
sk
is
,
instead
,
isomorphic to T
alg
and T
coalg
.
Uε
sk
F)
:
DB
−→
K
,
i
.
e
.,
T
=
In
sk
FUT
sk
Proof
For any object
A
in
DB
,
In
sk
FUT
sk
(A)
=
In
sk
T
sk
(A)
=
TA
, and for any
morphism
f
:
A
−→
B
in
DB
,
In
sk
FUT
sk
(f )
=
In
sk
K
sk
(f )
=
In
sk
(f
T
)
=
Tf
(where, from Theorem
14
,
f
T
=
T
sk
(f )
and
f
T
=
Tf
=
f
).
The adjunction-equivalence
(T
sk
, In
sk
,η
sk
,ε
sk
)
between
DB
and
DB
sk
and the
adjunction-isomorphism
(U,F,η
U
,ε
U
)
of
DB
sk
K
produce a composed adjunc-
tion
(UT
sk
, In
sk
F,In
sk
η
U
T
sk
·
η
sk
,ε
U
·
Uε
sk
F)
:
DB
−→
K
, which is an equiva-
lence.
Hence,
K
DB
sk
and, from universal algebra (Back's theorem) theory,
K
T
alg
. Thus,
DB
sk
T
alg
. From this fact and the fact that
DB
is equivalent to
DB
sk
,
we obtain that
DB
is equivalent to
T
alg
. Similarly, by duality, we obtain that
DB
is
equivalent to
T
coalg
.
In order to show the finitarity condition, let us consider the term algebra
U(A)
over a simple database
A
with
infinite
set of relations. Since every operation
ρ
∈
Σ
R
can only take finitely many arguments, every term
t
U(A)
can only contain finitely
many variables from
A
. Hence, instead of building the term algebra over the
infinite
database
A
, we can also build the term algebras over
all finite subsets
(of relations)
A
0
of
A
and take union of these:
U(A)
∈
=
{
U(A
0
)
|
A
0
⊆
ω
A
}
. This result comes