Database Reference
In-Depth Information
Example 33
Consider the term
t
R
given in Example
32
, represented here in the first
step of the tree-term transformations.
The next steps of the transformations in these diagrams are denoted by
↓
(n)
,
where
n
is the index of the next transformation-step to be executed.
In fact, in Step 1, we have indicated by
↓
↓
(
2
)
and
(
3
)
the unfolding of binary
nodes _ TIMES _ (or _
_), as specified by Definition
33
. Notice that any two
consecutive operations _ WHERE
C
k
and_WHERE
C
m
, can be shortened by the
equivalent operation _ WHERE
C
k
∧
C
m
.
After the execution of the Steps 2 and 3, we obtained the tree represented by the
diagram Step 3. The next step of transformation
⊗
↓
(
4
)
corresponds to the unfolding
of the unary operation
_ along the path composed of unary operations
in
Σ
RA
\
Σ
RA
, equal to (_ REDUCE
S
4
TO
S
3
)
a,name,e
◦
(
_
[
S
3
&
S
4
]
)
◦
(
_ WHERE
C
4
)
,
as it is specified by Definition
34
. The unfolding of
_ over (_ REDUCE
S
4
TO
S
3
) is presented in Step 4, and corresponds to the transformation defined in
point 4.1 of Definition
34
(note that the attribute
a(
1
)
is a copy of the attribute
a
,
while
nome
1
is a new fresh name different from the original
name
).
By
a,name,e
↓
(
5
)
we indicated the next steps for unfolding of
(
_
a(
1
), name
1
,e
nr
)
◦
(
_
a,name,e
)
along the operations _
[
S
3
&
S
4
]
, and its result is presented in the
diagram Step 5.
By
↓
(
6
)
we indicated the next steps for unfolding of
(
_
a(
1
), name
1
,e
nr
)
◦
(
_
a,name,e
)
along the operations _ WHERE
C
4
, with resulting diagram in
Step 6.
In the last Step 7, we executed the unfolding of _ TIMES _ binary operators to
leafs, as specified by tensorial (“Cartesian”) product of the two paths in Proposi-
tion
22
, and hence we obtained the final normalized one path-term with the unique
leaf which is a term in
T
RA
X
(a Cartesian product of relational tables with all up-
dates).
Based on this example, we can generalize this process in the following proposi-
tion:
Proposition 23
(T
HE COMPLETENESS OF
RA
)
There is a normalization mapping
→
Mor
RA
such that a term t
R
∈
T
RE
X of the Σ
RE
-algebra in Definition
31
is repre-
sented by an arrow f
:
T
RA
X
→
Mor
RA
with composed mapping Rd
RE
=
◦
:
T
RE
X
Nrm
Nrm
Trw
f(t
RA
)
,
with
:
1.
The source object is a term t
RA
∈
T
RA
X composed as a Cartesian products of
relational tables
(
that appear in the original term t
R
)
updated eventually by the
'
EXTEND. . .
' operations _
t
RA
→
:
.
2.
The target object is a term f(t
RA
)
∈
T
RA
X
,
where f is a path composed of the
unary operations
(
arrows
)
in Σ
RA
\
Σ
RA
,
such that f(t
RA
) is equivalent to t
R
.
a,name,e
Proof
The first step is to reduce a given term
t
R
∈
T
RE
X
of the
Σ
RE
-algebra to the
equivalent term
t
RA
, by using the term-rewriting algorithm
Trw
→
T
RA
X
in Proposition
20
. This binary tree-term
t
RA
with a given root operation can have
as binary nodes only the Cartesian product operations _
TIMES
_(or_
:
T
RE
X
⊗
_). The
