Database Reference
In-Depth Information
T
P
X
of its terms with variables is equal to the lfp of the endofunctor
The set
Σ
R
:
X
Set
→
Set
and hence, when
X
=∅
is the empty set, the least fixpoint (lfp)
T
P
(
∅
)
is obtained by the chain (note that in
Set
, the empty set
∅
is the initial object,
so that
∅
Y
=
Y
):
Σ
R
∅
)
=
Σ
R
Σ
R
(
)
=
Σ
R
⊥
0
Σ
R
(
0
Σ
R
(
∅⊆∅
∅
)
=⊥
⊆∅
∅
∅
Σ
R
∅
Σ
R
∅
)
=
Σ
R
Σ
R
⊥
0
⊆···
Σ
R
(
⊆∅
∅
,
∅
Σ
R
by iterating the functor
.
If this chain is infinite then we can generate the finitary relations with an in-
finite number of tuples, but not the relations with an infinite number of attributes
(by an infinite number of applications of the operations of type 'EXTEND...'
we do not produce the infinitary relations because this operation increments the
number of attributes of only finitary relations, so that we always obtain a fini-
tary relation). Hence, based on Definition
31
in Sect.
5.1
, in this case we obtain
that
Υ
on the empty set
∅
t
R
∈
T
P
(
, because all relations in
Υ
(from Definition
26
in
Sect.
8.1.5
,
Υ
is the union of all
simple
objects (databases) in
DB
category) are
finitary (i.e., have a finite arity).
Note that here we do not use the parameters in
A
as the set of nullary operations
in
Σ
R
(because the signature
Σ
R
has only unary and binary operators), differently
from the analog case of the set of flattened guarded system of equations used in
operational semantics (Proposition
37
) in Sect.
7.3.2
.
Thus, the system of guarded equations above, which defines a mapping from
a simple database
A
to a simple database
B
, my be expressed by the function
f
e
:
⊇{
t
R
#
|
∅
)
}
T
P
(X)
, such that for the left-hand side (a variable
r
X
→
A
∈
X
)ofaflat-
Σ
R
) it returns its
right-hand side, i.e.,
f
e
(r)
=
o
i
(r
1
,...,r
k
)
∈
T
P
(X)
, while for an equation with a
parameter
R
,
r
≈
R
,
f
e
(r)
=
R
∈
A
. Consequently, this function
f
e
is just a coal-
gebra
(X,f
e
)
of the polynomial
Set
endofunctor
A
tened guarded equation
r
≈
o
i
(r
1
,...,r
k
)
(with operation
o
i
∈
T
P
(
_
)
:
→
Set
Set
with the
signature
Σ
R
.
It is well known [
1
] that such polynomial endofunctors of
Set
have a
final coal-
gebra
which is the algebra of all finite and infinite
Σ
-labeled trees with leafs in
A
(which are the ground terms). Hence,
T
T
P
(T
(A)
A
(A))
, i.e.,
T
(A)
is the
∞
∞
∞
T
P
(
_
)
obtained by union of the chain
∅⊆
A
T
P
(
∅
)
⊆
A
T
P
A
T
P
(
∅
)
⊆···
,
greatest fixpoint (gfp) of the endofunctor
A
T
P
i.e., obtained by iterating the functor
A
on the empty set, so that each param-
∈
⊆
eter
R
A
T
∞
(A)
is a single node tree (tree composed of only the leaf
R
)in
T
∞
(A)
.
So, the flattened guarded system of equations defined by a mapping
f
e
has the
unique
solution
f
s
:
T
P
(
_
)
-coalgebra homomor-
phism from the coalgebra
(X,f
e
)
into the final coalgebra
(T
X
→
T
∞
(A)
, which is the
A
(A),
)
, as repre-
∞
sented by the following commutative diagram in
Set
category:
