Database Reference
In-Depth Information
Consequently, we define
R
A
(R
11
TIMES
R
21
)
UNION
R
∈
TA,
so that
−
R
A
=
−
SK
, with
−
SK
∈
T(
{
R
A
}
)
, that is,
T(
{
−
SK
}
)
⊆
T(
{
R
A
}
)
(in fact,
−
SK
=
(π
1
(R
A
))
UNION
π
4
(R
A
)
). But
R
A
cannot be obtained by a finite-length term
over the unary relation
−
SK
and hence
R
A
∈
T(
{
−
SK
}
)
.
Thus,
A
\
−
R
A
=
A
\
−
SK
={
a
,
b
}∈
TA
is a finite unary relation with only
two tuples, so that
=
TIMES
R
A
(A)
a
,
b
is a finitary relation with
ar(
(A))
=
5 and with an infinite set of tuples.
In order to show that
T(
{
(A)
}
)
=
TA
=
T(T(can(
I
,D)))
=
T(can(
I
,D))
=
A
, it is enough to show that
{
R
1
,R
2
}⊆
T(
{
(A)
}
)
:
1.
R
31
={
a,b
}=
((π
1
(
(A))
WHERE
(name
=
a))
TIMES
(π
1
(
(A))
WHERE
(name
=
a)))
∈
T(
{
(A)
}
)
;
2.
R
32
={
b,ω
1
}=
((π
1
(
(A))
WHERE
(name
=
b))
TIMES
(π
2
(
(A))
WHERE
(name
=
ω
1
)))
∈
T(
{
(A)
}
)
;
3.
R
33
={
b,ω
0
}=
((π
1
(
(A))
WHERE
(name
=
b))
TIMES
(π
2
(
(A))
WHERE
(name
=
ω
0
)))
∈
T(
{
(A)
}
)
.
Thus,
R
1
=
π
2
,
3
(A)
UNION
(R
31
UNION
R
31
)
∈
T
(A)
,
R
2
=
π
4
,
5
(A)
UNION
R
33
∈
T
(A)
.
From the fact that for each
R
A
=
(A)
∈
Υ
,
T(
{
R
A
}
)
=
TA
⊆
Υ
=
T(
{
R
Υ
}
)
,we
are able to introduce a partial ordering between the relations in
Υ
.
In order to introduce this partial ordering between the relations, and a complete
lattice of them, that is, in order to obtain the possible worlds with the partial ordering
(as it was developed by Kripke for intuitionistic logic), we do as follows:
Lemma 22
We define the PO set (
Υ
,
≤
) such that for any two relations
,
R
1
,
R
2
∈
Υ
,
T
{
R
1
}
⊆
T
{
R
1
}
,
R
1
≤
R
2
iff
so that
⊥
is the bottom element in (
Υ
,
≤
)
.
We denote R
1
R
2
iff R
1
≤
R
2
and R
2
≤
R
2
.
Consequently
,
we obtain the fol-
lowing complete lattice of relations
:
(i)
L
Υ
=
(
Υ
,
≤
,
∧
,
∨
,
0
,
1
)
,
where
0
equal to empty relation
⊥
,
and
1
is equal to
top relation R
Υ
=
(
Υ
)
,
and for any two relations R
1
,R
2
∈
Υ
we define the
meet and join operators by
:
(ii)
R
1
∧
R
2
(T
{
R
1
}∩
T
{
R
2
}
)
,
R
1
∨
R
2
(T
{
R
1
}∪
T
{
R
2
}
)
,
where
:
Ob
DB
→
Υ
is a function introduced in Proposition
69
.
Consequently
,
the com-
posed operation '
' in this lattice corresponds to the lattice l
.
u
.
b
.(
supremum
)
operator '
' of this lattice
,
and for any instance-database A
∈
Ob
DB
,
