Database Reference
In-Depth Information
such that it is exactly a subrelation of
R
1
with all tuples that have at positions defined
by ordered list
I
the values
a
i
in
t
I
, that is,
π
I
(R
I
)
=
π
I
(
{
t
I
}
)
(equal to
{
t
}
, with
the tuple
t
=
a
1
a
2
a
3
a
4
a
5
a
6
in the example above).
Consequently,
2.
R
1
=
I
∈
S
R
I
,fora
finite
set
S
.
We recall that
S
is finite because the set J
A
is a finite set of values, so that
R
1
is
a finite union, thus a
finite-length
term of
Σ
R
(SRRJU) algebra (Definition
31
in
Sect.
5.1
), and, in order to show that
R
1
∈
T(
¬
∪¬¬
A
A)
, it is enough to show that
T(
¬
∪¬¬
R
I
∈
A
A)
for all
I
∈
S
. In fact, the projection
3.
R
(
1
I
π
J
(R
I
)
∈¬
A
is a (also infinite) relation with only values in J
¬
A
=
J
Υ
\
J
A
, while
4.
R
(
2
)
I
∈¬¬
A
,
is the relation with a single tuple composed of all values in the finite set J
A
. Thus,
let us show that from these two relations,
R
(
1
)
I
{
t
}=
π
I
(R
I
)
,R
(
2
I
∈¬
∪¬¬
A
A
we obtain that
T(
¬
∪¬¬
R
I
∈
A
A)
. First of all, we define the relation:
5.
R
(
3
)
I
(R
(
2
)
I
TIMES
R
(
1
)
I
T(
¬
∪¬¬
)
∈
A
A)
, and hence
6.
R
I
=
π
M
I
(R
(
2
)
TIMES
R
(
1
)
I
)
∈
T(
¬
A
∪¬¬
A)
,
=
0
≤
j
≤
m
k
j
and
g(m)
+
0
≤
j
≤
m
l
j
,for0
I
where, for
h(m)
=
h(n)
≤
m
≤
n
,we
have the following list of indexes:
l
1
k
1
M
I
=
1
+
g(
0
),...,g(
1
),
1
+
h(
0
),...,h(
1
),...,
l
m
+
1
k
m
+
1
1
+
g(m),...,g(m
+
1
),
1
+
h(m),...,h(m
+
1
),,...,
l
n
+
1
l
n
k
n
1
)
,
1
+
g(n
−
1
),...,g(n),
1
+
h(n
−
1
),...,h(n),
1
+
g(n),...,g(n
+
where, if
l
1
=
0, we eliminate the first sublist
l
1
, and, if
l
n
+
1
=
0, we eliminate the
last sublist
l
n
+
1
from the list of indexes above.
In fact,
ar(R
(
3
)
I
ar(R)
, and
M
I
is only the permutation of columns of
R
(
3
)
)
=
I
corresponding to
R
I
.
Consequently, from facts 1-4, for all
R
(
1
)
I
,R
2
∈¬
A
,
R
(
2
)
}∈¬¬
A
,
I
∈
S
{
t
I
∈
(where
S
is
finite
), for any
R
Υ
,
R
2
I
π
M
I
R
(
2
)
TIMES
R
(
1
I
∈
T(
¬
∪¬¬
R
=
A
A).
I
∈
S
Thus,
T(
¬
A
∪¬¬
A)
=¬
A
⊕¬¬
A
=
Υ
.
If J
¬¬
A
=
J
A
is infinite (it happens only when we have the cyclic tgds with
existential quantifiers on the right-hand side of implication, so that
all
infinite
Skolem constants in
SK
are inserted into a subset of relations of a database
A
),
then J
¬
A
=
J
Υ
\
J
A
is finite (in this case
¬
A
contains only a finite number of values
