Database Reference
In-Depth Information
objects and arrows in the
DB
category, it is justified to ask if each simple arrow
f
is
by itself composed in some way by the set of terms of some particular extension of
the Codd's relational algebra
Σ
R
, that is, if each R-operad
q
i
∈
O(r
i
1
,...,r
i
k
,r
B
)
is
computationally equivalent
to some relational-algebra term, and exactly to which
one.
If there is such a relational algebra, then it has to include the Codd's (SPRJU)
Σ
R
algebra and hence in this case all elements (the objects and the arrows) in the
DB
category can be equivalently represented by the subsets of terms of such a relational
algebra. Consequently, the category
DB
, also with different prime-objects (which
for
DB
are the instance-databases and not the simple relations as for the relational
algebras), would be equivalent (from the computational point of view) to such a
relational algebra.
In what follows, we will make this investigation and will shortly resume the pro-
cess of the “algebraization” of the schema database mappings presented in Chap.
2
.
In Sect.
2.4
, we discussed the process of the “algebraization” of the logic theory
based on SOtgds into an algebraic theory based on R-operads
q
O(r
1
,...,r
k
,r)
,
which are the abstract
k
-ary “operations” (functional symbols), but we did not con-
sider the problem of what is a minimal subset of the elementary R-operads that
composes the signature of this database-mapping algebra.
We mentioned that the left-hand sides of the SOtgds can be equivalently repre-
sented by SPRJU (Codd's) relational algebra (
Σ
R
in Definition
31
in Sect.
5.1
)but
augmented by the binary MINUS operator (for the predicates preceded by logical
negation
∈
¬
, so that a logic formula
¬
r(x
1
,...,x
n
)
is transformed into the relational-
ar(r)
algebra term
(
r
∞
⊗···⊗
r
∞
)
MINUS
r
), where for every R-algebra
α
, from point
ar(r)
a
r(r
)
U
×···×
U
=
U
ar(r)
for
1 of Definition
10
in Sect.
2.4.1
,
α(r
∞
)
⊗···⊗
α(r
∞
)
=
ar(r)
ar(r)
a given universe
U
, so that,
R
=
α
#
((
r
∞
⊗···⊗
r
)
MINUS
r)
=
U
\
α(r)
=
∞
ar(R)
U
R
(i.e., the complement of
R
). Notice that here we do not make the Codd's
constraints about the necessity to have only the relations with a finite extensions
(i.e., the finite number of tuples), so we permit the infinite universes as well (espe-
cially when
\
U
=
∪
SK
where
SK
is an infinite set of marked null values, i.e., the
Skolem constants) also for a finite domain
dom
. Hence, we do not make extensions
of the Codd's original SPRJU algebra of finite relations with a set of new algebraic
operations, but we permit to work in the full correspondence with the FOL for such
relational algebra where we can have the infinite extensions of the predicates (i.e.,
relations) for a given infinite universe
dom
.
Then in Definition
11
, Sect.
2.4.1
, we considered the valid subset of R-algebra
interpretations
α
for these R-operads (
mapping-interpretations
), such that
α(q)
U
:
×···×
→
α(r
1
)
α(r
k
)
α(r)
is an
n
-ary operation (a function) whose arguments are
the relations
α(r
i
)
Υ
. Thus, in order to define the algebra (its signature and the
semantics of its operators (R-operads) for the database mappings, we need to rec-
ognize a strict subfamily of functions
α(q)
, from which, by a composition, we can
obtain all other R-operads as composed terms: we can see that all of them are parts
∈
