Database Reference
In-Depth Information
lations are considered equal as well. In what follows, given any two lists (tuples),
d
d
1
,...,d
k
,b
1
,...,b
m
is denoted by
d
&
b
, where '&' is the symbol for concatenation of the lists. By
=
d
1
,...,d
k
and
b
=
b
1
,...,b
m
their concatenation
we denote the extension of a given relation (relational symbol)
r
; it is extended to
any term
t
R
of Codd's algebra, so that
r
is the relation obtained by computation
of this term. Let us briefly define these basic operators, and their correspondence
with the formulae of FOL:
1. Rename is a unary operation written as _ RENAME
name
1
AS
name
2
where the
result is identical to input argument (relation)
r
except that the column
i
with
name
nr
r
(i)
t
R
name
2
.
This operation is neutral w.r.t. the logic, where we are using the variables for
the columns of relational tables and not their names.
2. Cartesian product is a binary operation _ TIMES _, written also as _
=
name
1
in all tuples is renamed to
nr
r
(i)
=
_, such
that for the relations
r
1
and
r
2
, first we do the rename normalization of
r
2
(w.r.t.
r
1
), denoted by
r
2
, such that:
For each
k
th copy of the attribute
a
i
(or, equivalently,
a
i
(
0
)
)ofthe
m
th column
of
r
2
(with 1
⊗
atr(r
2
)
, such that the
maximum index of the same attribute
a
i
in
r
1
is
a
i
(n)
, we change
r
2
by:
(a)
a
i
(k)
≤
m
≤
ar(r
2
)
), denoted by
a
i
(k)
=
atr
r
2
(m)
∈
→
a
i
(k
+
n)
;
(b) If
name
1
=
nr
r
2
(m)
is a name that exists in the set of the column names
in
r
1
, then we change the naming function
nr
r
2
:{
1
,...,ar(r
2
)
}→
SN
,
by
nr
r
2
(m)
SN
is a new name distinct from all
other used names, and we define the renaming normalization
ρ
by mapping
name
1
→
=
name
2
, where
name
2
∈
name
2
.
The relation obtained from
r
2
, after this renaming normalization, will be denoted
by
r
2
. Then we define the new relation
r
(when both
r
1
={}
and
r
2
=
r
2
, with
{}
, i.e., when are not empty relations) by
r
1
⊗
r
{
d
1
&
d
2
|
d
1
∈
r
1
,
d
2
∈
r
2
}
, and with the naming function
nr
r
:{
1
,...,ar(r
1
)
+
ar(r
2
)
}→
SN
such that
nr
r
(i)
=
nr
r
1
(i)
for 1
≤
i
≤
ar(r
1
)
and
nr
r
(i)
=
nr
r
2
(i)
for
1
+
ar(r
1
)
≤
i
≤
ar(r
1
)
+
ar(r
2
)
, and the
atr
r
:{
1
,...,ar(r
1
)
+
ar(r
2
)
}→
att
function defined by
atr
r
(i)
=
atr
r
1
(i)
for 1
≤
i
≤
ar(r
1
)
and
atr
r
(i)
=
atr
r
2
(i)
for 1
ar(r
2
)
.
This Cartesian product is given by the following logical equivalence, by con-
sidering the relational symbols as predicates,
r(x
1
,...,x
ar(r
1
)
,y
1
,...,y
ar(r
2
)
)
⇔
r
1
(x
1
,...,x
ar(r
1
)
)
∧
r
2
(y
1
,...,y
ar(r
2
)
)
,
+
ar(r
1
)
≤
i
≤
ar(r
1
)
+
so that
r
=
r
1
(x
1
,...,x
ar(r
1
)
)
∧
r
2
(y
1
,...,y
ar(r
2
)
)
.
r
2
=
r
2
=
(if
r
1
is empty then
r
1
⊗
r
2
;if
r
2
is empty then
r
1
⊗
r
1
).
3. Projection is a unary operation written as _
[
S
]
, where
S
is a tuple of col-
umn names such that for a relation
r
1
and
S
=
nr
r
1
(i
1
),...,nr
r
1
(i
k
)
, with
k
≥
1 and 1
≤
i
m
≤
ar(r
1
)
for 1
≤
m
≤
k
, and
i
m
=
i
j
if
m
=
j
, we define
the relation
r
by:
r
1
[
S
]
, with
r
=
r
1
if
∃
name
∈
S.name /
∈
nr(r
1
)
; other-
wise
r
=
π
i
1
,...,i
k
(
r
1
)
, where
nr
r
(m)
=
nr
r
1
(i
m
)
,
atr
r
(m)
=
atr
r
1
(i
m
)
,for
1
≤
m
≤
k
.
