Database Reference
In-Depth Information
Natural join
r
2
)
, where
r
1
and
r
2
are rela-
tions. The result of the natural join is the set of all combinations of tuples in
r
1
and
r
2
that are equal on their common attribute names. In fact,
(r
1
is a binary operator, written as
(r
1
r
2
)
can be obtained
by creating the Cartesian product
r
1
⊗
r
2
and then by execution of the Selection
with the condition
C
defined as a conjunction of atomic formulae
nr
r
1
(i)
nr
r
2
(j)
(where
i
and
j
are the columns of the same attribute in
r
1
and
r
2
, respectively, i.e.,
satisfying
atr
r
1
(i)
=
=
atr
r
2
(j)
) that represents the equality of the common attribute
names of
r
1
and
r
2
. The natural join is arguably one of the most important operators
since it is the relational counterpart of logical AND. Note carefully that if the same
variable appears in each of two predicates that are linked by AND, then that variable
stands for the same thing and both appearances must always be substituted by the
same value. In particular, the natural join allows the combination of relations that
are associated by a foreign key. It can also be used to define a composition of binary
relations. In category theory, the join is precisely the fiber product. Altogether, the
operators of a relational algebra have identical expressive power to that of domain
relational calculus or tuple relational calculus. However, relational algebra is less
expressive than first-order predicate calculus without function symbols. Relational
algebra corresponds to
a subset
of FOL (denominated
relational calculus
), namely
Horn clauses without recursion and negation (or union of conjunctive queries intro-
duced in Sect.
1.4
). Consequently, relational algebra is essentially equivalent in ex-
pressive power to
relational calculus
(and thus FOL and queries defined in Sect.
1.4
in the introduction); this result is known as Codd's theorem. However, the negation,
applied to a formula of the calculus, constructs a formula that may be true on an infi-
nite set of possible tuples. To overcome this difficulty, Codd restricted the operands
of relational algebra to finite relations only and also proposed restricted support for
negation
(OR). Codd defined the term “relational com-
pleteness” to refer to a language that is complete with respect to first-order predicate
calculus apart from the restrictions he proposed. In practice, the restrictions have no
adverse effect on the applicability of his relational algebra for database purposes. In
our theoretical setting, we permit the relations with infinite number of tuples, so we
do not use such restrictions.
Several papers have proposed new operators of an algebraic nature as candi-
dates for addition to the original set. We choose the additional unary operator
'EXTEND_ ADD
a,name
AS
e
' denoted shortly as _
¬
(NOT) and disjunction
∨
, where
a
is a
new added attribute as the new column (at the end of relation) with a new fresh
name
name
and
e
is
a
n expression (in the most simple cases it can be the value
NULL or a constant
d
,orthe
i
th column name
nr(i)
of the argument (i.e., relation)
of this operation), for
update
relational algebra operators, in order to cover all of the
basic features of data manipulation (DML) aspects of a relation models of data, so
that
•
a,name,e
We define a unary operator _
att
, its name, and
expression
e
, as a function with a set of column names, such that for a relation
r
1
and expression
e
composed of the names of the columns of
r
1
with
n
a,name,e
, for an attribute
a
∈
=
ar(r
1
)
,
+
we obtain the
(ar(r
1
)
1
)
-ary relation
r
by
a,name,e
(r
1
)
, with the naming
function
nr
r
:{
+
}→
=
≤
ar(r
1
)
1
SN
such that
nr
r
(i)
nr
r
1
(i)
if
i
ar(r
1
)
and
