Database Reference
In-Depth Information
Variable-normalization algorithm
VarTransform(φ
Ai
(
x
)
⇒
r
B
(
t
))
⇒
=
Input
. A mapping implication
φ
Ai
(
x
)
r
B
(
t
)
, where
t
(t
1
,...,t
n
)
is a tuple of
terms with variables in
x
and
t
1
=
(t
i
1
,...,t
i
m
)
⊆
t
is the (possibly empty) sublist
of terms with at least one functional symbol in
f
.
Output
. A logically equivalent implication with extended set of variables.
1. (
Replacing of the characteristic functions with its relations
)
If there are no equations in
φ
Ai
(
x
)
with the characteristic functions for relations,
go to Step 2. Otherwise, e
ac
h condition in
φ
Ai
(
x
)
with a characteristic function of
some relation,
(f
r
i
(
x
i
)
.
=
1
)
with
x
i
⊆
x
, is eliminated from
φ
Ai
(
x
)
and replaced
by
r
i
(
x
i
)
.
2. (
Introduction of the new variables for the join-conditions
)
Here we have the following implication (logically equivalent to the implication
in input), for
k
≥
1,
∼
i
r
i
(
x
i
)
|
≤
i
≤
k
∧
C(
x
)
1
⇒
r
B
(
t
),
where
∼
i
is the identity logical operator or the negation logical operator
¬
,the
tuples of variables
x
i
⊆
k
, and
C(
x
)
is a condition with variables in
x
without characteristic func
ti
on
s
of relations, or if there is no such a condition we
take that it is a tautology
(
1
.
x
,
1
≤
i
≤
=
1
)
.
Set
S
J
to be the empty set. For each variable
x
i
j
in a relation
r
i
, such that the same
variable is present in another relations on the left-hand side of this implication,
we introduce a fresh new variable
y
i
j
, then we substitute
x
i
j
in all other relations
r
j
,1
x
i
j
in
S
J
. Continue
this proce
ss a
s far as possible. At the end of this step (if
S
J
is empty then set
S
J
={
≤
j
≤
k
,
j
=
i
,by
y
i
j
and insert the equation
y
i
j
=
r
(
0
,
0
)
), we obtain the resulting implication,
∼
i
r
i
x
i
|
}
C(
x
)
S
J
k
∧
1
≤
i
≤
⇒
r
B
(
t
),
where the new tuples of variables
x
i
are obtained from
x
i
by the substitutions
of some variables by the new introduced variables above (by substitutions of old
variables with new variables), so that for 1
j
,
x
i
∩
x
j
=∅
.
3. (
Elimination of the terms with functional symbols from the right-hand side of
implication
)
If
t
1
is empty then set
S
F
={
r
(
1
,
1
)
}
≤
i,j
≤
k
,
i
=
and go to Step 4.
For each term
t
i
j
∈
t
1
we introduce a fresh new variable
z
i
j
and we insert the
t
i
j
in
S
F
.
4. (
Construction of the new implication
)
The new implication is a formula
∼
i
r
i
x
i
|
equation
z
i
j
=
C(
x
)
S
J
S
F
k
∧
1
≤
i
≤
⇒
r
B
(
t
2
),
where
t
2
is obtained from
t
by substituting each term
t
i
j
by the variable
z
i
j
,for
1
≤
j
≤
m
.
Return
the resulting implication.
