Database Reference
In-Depth Information
Hence
,
we obtain the following complete distributive lattice of relations
(e1)
L
v
=
(
Υ
,
≤
v
,
∧
v
,
∨
v
,
0
,
1
)
,
where
0
equal to empty relation
⊥
,
and
1
is equal
to top relation
Υ
={
|
∈
U
}
,
and for any two relations R
1
,R
2
∈
a
a
Υ
,
the
meet and join operators are defined by
(e2)
R
1
∧
v
R
2
R
1
∩
R
2
,
R
1
∨
v
R
2
R
1
∪
R
2
.
The vectorization operation _
.
Υ
is the l.u.b
.(
'
'
)
operation of the
:
P
(
Υ
)
→
lattice L
v
.
Proof
Any vector relation is a unary relation and, by definition,
⊥=⊥={}
where
is the empty tuple (Definition
10
in Sect.
2.4.1
). Consequently, for any
R
,
⊥=⊥={}⊆
R
, so that
is the bottom element of this
lattice. By definition,
Υ
=
R
∈
Υ
R
=
R
∈
Υ
{
a
|
a
is a value in
R
}={
a
|
a
∈
U
}
⊥≤
v
R
, that is,
⊥
(where
Υ
is generated by all values in
U
=
dom
∪
SK
, where
dom
is a finite
domain of values and
SK
is the infinite number of indexed Skolem
constants, i.e., marked null values). Analogously, for any
R
={
ω
0
,ω
1
,...
}
Υ
,
R
∈
⊆{
a
|
a
∈
U
}=
Υ
≤
v
Υ
so that
Υ
is the top element of this lattice. It is easy to
verify, form (e2) that this lattice is distributive. We have that for any (also infinite)
subset
S
∈
Υ
, thus
R
=
R
∈
S
R
=
R
∈
S
R
and
lub(S)
=
R
∈
S
R
=
R
∈
S
R
=
S
, thus well defined, and
lub
operation is equal to the vectorization operation _
.
;
hence, this is a complete lattice.
⊆
Υ
,
glb(S)
It is easy to see that the “vectorization” operation _
.
is a homomorphism
{
R
_
.
,
0
,
1
)
between the complete distributive lattices,
where the right-hand side lattice is the quotient of the left-hand side lattice w.r.t. the
equivalence
:
L
v
→
(
|
R
∈
Υ
}
,
⊆
,
∩
,
∪
v
, that is, equal to
L
v
/
v
. If we denote by
[
R
]
the equivalence class
v
, then
R
of relations w.r.t. the equivalence
is the representing element of
this equivalence class, and the kernel of the homomorphism _
.
∈[
R
]
corresponds to the
v
. Notice that from the fact that
L
v
is a complete
distributive lattice (satisfying the infinite distributivity (equation 10 in Sect.
1.2
), it
holds that it is also a complete Heyting algebra with relative pseudo-complements.
Sadly, we have the desired property
TA
=↓
v
A
={
R
∈
Υ
|
R
≤
v
A
}
congruence relation defined by
only
when the unary relation
A is finite
. However, generally it holds that
TA
⊆↓
v
A
(in fact, if
R
∈
TA
then
R
=
1
≤
i
≤
ar(R)
π
i
(R)
⊆
A
=
−−→
(A)
, thus
R
≤
v
A
, i.e.,
∈↓
v
A
). Let us show that inverse does not hold, i.e.,
TA
↓
v
A
:
R
↓
v
A
, we can see by con-
Example 44
That inverse does not hold, that is,
TA
=
I
sidering Example
27
in Sect.
4.2.4
, when
A
can(
,D)
has two infinite binary
relations
R
1
and
R
2
:
