Database Reference
In-Depth Information
5.
For each relation R with the tuple of attributes in
x
,
and a term t
i
(
x
i
) with the
functions and variables
x
i
=
x
(
determined by the projection on a sublist
of the attributes S of R
),
the surjective function f
R,t
i
:
π
S
(
x
)
⊆
R
R
1
such that for any
tuple
d
∈
R
,
f
R,t
i
π
S
(
d
)
=
t
i
x
i
,π
S
(
d
)
∈
U
d
&
b,
where b
=
,
=
+
so that ar(R
1
)
ar(R)
1
and R
1
is the image of this function
.
Proof
Let us consider the following mapping implication
φ
Ai
(
x
)
⇒
r
B
(
t
)
, where
t
t
is
the (possibly empty) sublist of terms with at least one functional symbol in
f
. Hence,
we obtain as output of the algorithm
VarTransfom
the implication:
∼
i
r
i
x
i
|
=
(t
1
,...,t
n
)
is a tuple of terms with variables in
x
and
t
1
=
(t
i
1
,...,t
i
m
)
⊆
C(
x
)
S
J
S
F
k
∧
1
≤
i
≤
⇒
r
B
(
t
2
),
where
S
F
is a set of equations
z
i
j
=
t
i
j
,1
≤
j
≤
m
,
N
=
ar(r
1
)
+···+
ar(r
k
)
, and
x
=
x
k
. We divide this implication into a number of “atomic” logical equiv-
alences, by introducing a set of new auxiliary intermediate relations, as follows:
x
1
;
...
;
Implication/Equivalence
Σ
RE
algebra term
R-algebra operation
{∼
i
r
i
(
x
i
)
|
1
≤
i
≤
k
}
f
(k)
r
C
t
k
(Cartesian product)
=
t
1
⊗···⊗
R
C
(Cartesian
k
-ary function)
⊗
:
R
1
×···×
R
k
→
r
C
(
x
1
&
&
x
k
)
⇔
···
r
C
(
x
)
∧
C(
x
)
S
J
⇔
r
S
0
=
r
C
WHERE
C
S
J
(Select by
C(
x
)
in
−
1
:
R
C
R
S
0
(Inverse-inclusion function)
r
S
0
(
x
)
+
Join by
S
J
)
r
S
0
(
x
)
⇔
r
S
1
(
x
&
t
i
1
)
r
S
1
=
EXTEND
r
S
0
ADD
a
N
+
1
, name
N
+
1
,t
i
1
...
r
S
j
=
f
R
S
0
,t
i
1
:
R
S
0
→
R
S
1
,
with
π
[
1
,...,N
]
(R
S
1
)
=
R
S
0
...
f
R
S
j
−
1
,t
i
j
:
R
S
j
−
1
→
R
S
j
...
for
m
≥
j
≥
2
...
r
S
j
−
1
(
x
&
t
i
1
,...,t
i
j
−
1
)
⇔
r
S
j
(
x
&
EXTEND
r
S
j
−
1
ADD
a
N
+
j
, name
N
+
j
,t
i
j
...
r
S
m
=
t
i
1
,...,t
i
j
)
...
r
S
m
−
1
(
x
&
...
f
R
S
m
−
1
,t
i
m
:
R
S
m
−
1
→
R
S
m
t
i
1
,...,t
i
m
−
1
)
⇔
r
S
m
(
x
&
EXTEND
r
S
m
−
1
ADD
a
N
+
m
, name
N
+
m
,t
i
m
t
i
1
,...,t
i
m
)
r
S
m
(
x
&
t
i
1
,...,t
i
m
)
r
q
=[
S
]
r
S
m
(Project on
S
)
π
S
:
R
S
m
→
R
q
(Projection
function)
⇔
r
q
(
t
2
)
r
q
(
t
2
)
⇒
r
B
(
t
2
)
(R
B
UNION
R
q
)
→
R
B
in
R
B
(Injective function)
:
R
q
→
(Union)
where in the Cartesian product of relations
t
1
⊗···⊗
t
k
, for each 1
≤
i
≤
k
,
ar(r
i
)
r
∞
⊗···⊗
r
∞
)
MINUS
r
i
)
, if the symbol
t
i
=
((
∼
i
is a negation operator
¬
;
r
i
otherwise. So that
R
i
=
t
i
#
,1
≤
i
≤
k
.
