Database Reference
In-Depth Information
Proof
We have to show that the binary operators 'UNION' and 'MINUS' can be
equivalently expressed by operators in this new
Σ
RA
algebra. In fact, for any two
terms
t
R
,t
R
of the
Σ
RE
-algebra with the union-compatible relations
r
1
with
r
1
=
t
R
#
, with
n
t
R
#
, and
r
2
with
r
2
=
=
ar(r
1
)
=
ar(r
2
)
,wehavethat
'
t
R
UNION
t
R
' is equivalent to
t
R
if
t
R
#
is empty, to
t
R
if
t
R
#
is empty, and
t
R
)
REDUCE
S
2
TO
S
1
' otherwise;
'
t
R
MINUS
t
R
' is equivalent to
t
R
if
to '
(t
R
⊗
t
R
#
is empty or
t
R
#
is empty, and to
t
R
)
DISJOINT
S
2
FROM
S
1
' otherwise,
where
S
1
=
'
(t
R
⊗
nr
r
(
1
),...nr
r
(n)
,
S
2
=
nr
r
(n
+
1
),...nr
r
(
2
n)
, for the relation
r
r
2
.
By application of these transformations to each term
t
R
∈
T
RE
X
of the
Σ
RE
-
algebra as far as possible, we obtain an equivalent to it term
t
RA
∈
T
RA
X
, and we
define a mapping
Trw
by
Trw(t
R
)
equal to the Cartesian product
r
1
⊗
=
#
=
t
R
#
.
t
RA
, with
Trw(t
R
)
Example 32
Let us consider the term
t
R
given in Example
28
equal to the algebraic
expression
r
1
[
S
1
]
WHERE
C
1
UNION
(r
2
WHERE
C
2
)
S
2
]
WHERE
C
5
[
S
5
]
[
MINUS
EXTEND
r
3
[
S
3
]
UNION
(r
4
WHERE
C
4
)
S
4
]
[
ADD
a,name
AS
e
[
S
6
]
,
which is represented by the tree in Example
28
, with the four different paths that
end with leafs which are equal to relational tables.
We will use both 'TIMES' and
symbols for the Cartesian products.
By reduction of 'MINUS' and 'UNION' operations into the composition of op-
erations in
Σ
RA
, we obtain the equivalent term
t
RA
∈
T
RA
,
⊗
