Database Reference
In-Depth Information
each original term-tree (with leafs equal to real relational tables, as in Example
28
)
has to be transformed into an equivalent
single-path-term
, where the source object
is a Cartesian product of (eventually updated) real relational tables that appear in
the original term.
The algorithm how to transform any term into such a single-path-term, by un-
folding the updates (by 'EXTEND...') and Cartesian products to the most nidified
level will be presented in what follows. Let us consider first the reduction of the
'_ UNION _' and '_ MINUS _' binary operators in
Σ
RE
, by introducing two new
unary operators '_ REDUCE
S
2
TO
S
1
' and '_ DISJOINT
S
2
FROM
S
1
'.
Definition 32
Let for a given
r
1
let
S
1
=
nr
r
1
(i),...,nr
r
1
(i
+
k)
and
S
2
=
nr
r
1
(j),...,nr
r
1
(j
+
k)
with
i
≥
1,
k
≥
0,
j>i
+
k
and
j
+
k
≤
ar(r
1
)
. Then
we define the following two unary operators:
1. Reduction is a unary operation written as _ REDUCE
S
2
TO
S
1
such that for a
relation
r
1
and
S
=
nr
r
1
(
1
),...,nr
r
1
(ar(r
1
))
we define the relation
r
by:
r
1
REDUCE
S
2
TO
S
1
,
d
|
the tuple
d
is obtained by
where
r
=
π
S
\
S
2
(
r
1
∪{
for each
d
∈
r
1
)
.
2. Disjoint is a unary operation written as _ DISJOINT
S
2
FROM
S
1
such that for
a relation
r
1
and
S
replacing
d
i
+
m
by
d
j
+
m
for
m
=
0
,...,k
in
d
}
=
nr
r
1
(
1
),...,nr
r
1
(ar(r
1
))
we define the relation
r
by:
r
1
DISJOINT
S
2
FROM
S
1
,
d
∈
r
1
such that
(d
i
=
d
j
)
∧···∧
where
r
=
π
S
\
S
2
(
{
d
|
d
∈
r
1
and
∃
d
j
+
k
)
)
.
In both cases,
π
S
\
S
2
is the projection for all columns different from that in
S
2
(or,
equivalently, the elimination of all columns in
S
2
), so that
ar(r)
(d
i
+
k
=
}
1
)
and
nr
r
,
atr
r
are the reductions of
nr
r
1
and
atr
r
1
, respectively, obtained by this
projection.
=
ar(r
1
)
−
(k
+
Proposition 20
Let us define the Σ
RA
algebra for the relations composed of the
unique binary operator _
TIMES
_
(
denoted by _
⊗
_aswell
),
the unary operators
Renaming
,
Projection
,
Selection and Extend
(
i
.
e
.,
_
a,name,e
)
in Sect
.
5.1
and
the unary operators Reduction and Disjoint in Definition
32
.
We denote the set of terms
(
with variables X
⊆R
)
of this Σ
RA
algebra by
T
RA
X
,
and the evaluation of terms by the function
_
#
:
T
RA
X
→
Υ
(
which is a unique
extension of a given assignment
Υ
as in Definition
31
and Sect
.
5.1.1
).
The strict subalgebra of Σ
RA
,
with only the Cartesian product binary operation
_
:R→
,
will be denoted by Σ
RA
,
and the set
_
⊗
_ and the unary operations _
a,name,e
T
RA
X
(
i
.
e
.,
T
RA
X
of its terms by
⊂
T
RA
X
).
There is a term-rewriting mapping Trw
→
T
RA
X such that a term t
R
∈
T
RE
X of the Σ
RE
algebra in Definition
31
can be transformed into an equivalent
term in Trw(t
R
)
∈
T
RA
X with the operators of this new Σ
RA
algebra
.
:
T
RE
X
