Database Reference
In-Depth Information
algebra must also satisfy the equations given in
E
in the sense that equal
terms
give rise to identical functions (with obvious adjustments where the equated terms
do not contain exactly the same variables). A
homomorphism
of algebras from an
algebra
X
to an algebra
Y
is given by a function
g
:
X
−→
Y
which commutes with
operations of the algebra
g(
o
i
(g(x
1
),...,g(x
k
))
.
This generates a variety category
K
of all relational algebras. Consequently, there
is a bifunctor
E
o
i
(x
1
,...,x
k
))
=
DB
OP
Set
such that for any
simple
database instance
A
in
DB
sk
there exists the functor
E(A,
_
)
:
sk
×
K
−→
Set
with an universal element
(U(A),)
, where
∈
E(A,U(A))
, i.e.,
:
A
−→
U(A)
is an inclusion function.
U(A)
is a free algebra over
A
(i.e., the quotient-term algebra generated by a carrier
database instance
A
) such that for any function
f
∈
E(A,Z)
,
f
:
A
→
Z
, there is
a unique homomorphism
k
(in
K
) from the free algebra
U(A)
into an algebra
Z
,
with
f
:
K
−→
=
◦
E(A,k)
, represented by the following initial algebra semantics dia-
gram in
Set
:
where
k
(Z,h)
is this unique
Σ
R
-algebra homomorphism cor-
responding to the unique homomorphism
k
from the initial
(A
:
(U(A), inr
A
)
→
Σ
R
)
-algebra
(U(A),
f
#
is a function
equal to
k
but without the structural properties of this homomorphism (to commute
with operations of the algebra).
Consequently,
U(A)
is a quotient-term algebra, where a carrier is a set of equiv-
alence classes of closed terms of a well defined formulae of a relational algebra,
“constructed” by
Σ
R
-constructors (relational operators in SPJRU algebra: select,
project, join and union) and elements (relations) of a database instance
A
.
From the so-called “parameter-theorem” we obtain that there exist:
[
inl
A
, inr
A
]
)
into the algebra
(Z,
[
f,k
]
)
, and
E(A,k)
=
•
A unique universal functor
U
:
K
such that for any simple database
instance
A
in
DB
sk
it returns the free
Σ
R
-algebra
U(A)
. It is a quotient-term al-
gebra where a carrier is a set
U(A)
of the equivalence classes
DB
sk
−→
of closed terms
t
i
∈
T
P
A
(in Definition
31
) of well defined formulae of a relational algebra, “con-
structed” by
Σ
R
-constructors (i.e., the relational operators
o
i
∈
[
t
i
]
Σ
R
in SPJRU
algebra: select, project, join and union) and relational symbols of a database in-
stance
A
. That is,
U(A)
. An alternative for
U(A)
is given by
considering
A
as a set of variables rather than a set of constants. In either case,
each
k
-ary operation
o
i
∈
={[
t
i
]|
t
i
∈
T
P
A
}
U(A)
k
Σ
R
, with the function
o
i
:
→
U(A)
(i.e., a com-
=
o
i
∈
Σ
R
U(A)
ar(o
i
)
,
ponent of
inr
A
:
Σ
R
(U(A))
→
U(A)
where
Σ
R
(U(A))
so that
inr
A
=
o
i
∈
Σ
R
o
i
is the interpretation of all operations in the signature
Σ
R
) and hence is interpreted syntactically
o
i
(
[
t
1
]
,...,
[
t
k
]
)
=[
o
i
(t
1
,...,t
k
)
]
,
