Database Reference
In-Depth Information
which is represented by the tree above, with the four different paths that end with
leafs which are equal to relational tables.
In what follows, we will show that it is possible to transform each such a term-
tree into the
single path
(composed of only unary operations) which ends with a
single relation, obtained as a Cartesian product of the original relational tables up-
dated (eventually) by the operations “EXTEND _ AD ...”.
This term can be represented (in the figure) as the term-tree where the leafs are
the relational symbols (the variables in
X
⊆R
),
r
1
,r
2
,r
3
,r
4
∈
X
.
In Sect.
5.2
, we will show how such a complex tree-terms can be reduced to the
simple path-term with only one leaf, obtained as a Cartesian product of (eventu-
ally updated) relational tables. In order to show that each assignment
:
→
Υ
which assigns a relation to each relational symbol (a variable) can be
uniquely
ex-
tended to all terms, by a function
_
X
Υ
, we need to introduce the theory
of initial algebras and initial semantics in the next section.
_
#
:
T
P
X
→
5.1.1 Initial Algebras and Syntax Monads: Power-View Operator
The
syntax
of a programming language, given by a signature
Σ
P
(as, for example,
Σ
RE
or its subset
Σ
R
in Definition
31
), can be identified with a monad, the
syntac-
tical monad
T
P
freely generated by the program constructors (operations)
o
i
∈
Σ
P
(with arity
ar(o
i
)
≥
0 where the nullary operations are the constants, as
⊥
,forex-
ample).
We illustrate the link between a single-sorted
Σ
P
algebra signature and the
T
P
-
algebras of the endofunctor
T
P
. The assumption that the signature
Σ
P
is finite is
not essential for the correspondence between models of
Σ
P
and algebras of
T
P
.If
Σ
P
is infinite one can define
T
P
via an infinite coproduct (in
Set
which corresponds
to the disjoint union
), commonly written for a set of program variables in
X
(in
Set
the '
×
' denotes the Cartesian product)
