Database Reference
In-Depth Information
framework, but we still permit that the relations can contain also an infinite num-
ber of tuples. Is it possible to have only a finite number of the relational algebra
operators?
4. Why is the initiallity property for the syntax algebra semantics important? How
are we using the inductive principle in such an initial semantics? In which way
is the semantics of another algebra with the same set of algebraic operators in
Σ
P
but a different carrier set defined by the initial algebra semantics? (Consider
Example
29
by providing a concrete carrier set
Z
.)
5. Why in the
Σ
RE
relational algebra is it enough to have only one nullary operator
(a constant) equal to the empty relation
? Does it mean that we are able to
construct any relation by using only the empty relation
⊥
⊥
and the (infinite) set
of unary operators in
Σ
RE
and its three binary operators? Can you show the
inductive process of constructions of the relations from the relation
?
6. Describe and explain the inductive process of the construction of the power-
object
TA
, for a given database schema
⊥
A
and a given interpretation
α
with
α
∗
(
)
, based on the initial algebra semantics.
7. Why is it important to be able to transform any tree-term of a relational algebra
(where the leafs are the simple relations) into a single path-term with only one
complex leaf? Define the subclass of the single path-terms for the
Σ
P
equal to
the Codd's SPJRU algebra.
8. In this chapter, we presented an example of transformation of the term-tree
r
1
[
S
1
]
WHERE
C
1
UNION
(r
2
WHERE
C
2
)
[
S
2
]
WHERE
C
5
[
S
5
]
MINUS
EXTEND
r
3
[
S
3
]
UNION
(r
4
WHERE
C
4
)
[
S
4
]
ADD
a,name
AS
e
[
S
6
]
the database instance
A
=
A
into the single-path term in
T
RA
which is a morphism of the
RA
action-category.
Choose other examples of the terms of
Σ
RE
algebra and show their transforma-
tion into a single path-term in
T
RA
.
:
→
9. The evaluation functor
Eval
DB
formally expresses the semantics of the
terms (i.e., their evaluation) of the most expressive relational algebra
Σ
RA
, and
hence the category
DB
is able to represent not only the query computations but
all kinds of the RDB updates. Conversely, Proposition
27
demonstrates that each
morphism in the
DB
category can be equivalently represented by a term of the
relational algebra
Σ
RE
, and hence the computational power of the
DB
category
is equivalent to the most powerful relational algebra with all kinds of update
operations. Based on a part of the table in the proof of Theorem
9
given below,
develop an algorithm for the inverse mapping from
DB
into
RA
(first, transform
the morphism of
DB
into an equivalent term of
Σ
RE
algebra, by using the table
above, and then transform this term into a single path-term and the corresponding
morphism in
RA
).
RA