Database Reference
In-Depth Information
5
Extensions of Relational Codd's Algebra and
DB Category
5.1
Introduction to Codd's Relational Algebra and Its
Extensions
The standard terminology for a Relational Data Base (RDB) is slightly different
from the terminology used for basic database concepts presented in Sect.
1.4
of the
introduction, for instance, in RDB we use the term “table” as a special case of the
more general concept “relation”, and attributes instead of predicate variables, etc.
In this section, we will shortly introduce some additional RDB concepts that are
used in E.F. Codd's relational algebra for RDBs [
1
].
A base table in a relational system consists of a row of column headings, to-
gether with zero or more rows of data values. The column heading row specifies
one or more columns (giving, among other things, a data type for each). Each data
row contains exactly one scalar value for each of the columns specified in the col-
umn heading row. Five primitive operators of Codd's algebra are: the selection, the
projection, the Cartesian product (also called the cross-product or cross-join), the
set union, and the set difference. Another operator, rename, was not noted by Codd,
but the need for it is shown by the inventors of Information Systems Base Language
(ISBL) for one of the earliest database management systems which implemented
Codd's relational model of data. These six operators are fundamental in the sense
that if we omit any one of them, we will lose expressive power. Many other opera-
tors have been defined in terms of these six. Among the most important are the set
intersection, division, and the natural join. In fact, ISBL made a compelling case for
replacing the Cartesian product with the natural join, of which the Cartesian product
is a degenerate case.
Recall that two relations
r
1
and
r
2
are union-compatible iff
{
atr(r
1
)
}={
atr(r
2
)
}
,
where for a given list (or tuple) of the attributes
a
=
atr(r)
=
a
1
,...,a
k
=
atr
r
(
1
),...,atr
r
(k)
, we denote the
set
{
a
1
,...,a
k
}
by
{
atr(r)
}
,
k
=
ar(r)
, with
the injective function
nr
r
:{
1
,...,k
}→
SN
which assigns distinct names to each
column of this relation. If a relation
r
2
is obtained from a given relation
r
1
by per-
mutating its columns, then we say that they are not equal (in the set-theoretic sense)
but that they are equivalent. Notice that in the RDB theory the two equivalent re-
