Database Reference
In-Depth Information
for any R
Υ
.
If
Υ
is finite
,
then the lattice L
Υ
in Lemma
22
is a Boolean algebra
(
Υ
,
∧
,
∨
,
¬
,
⊥
,
×
c
(
Υ
)) as well
,
with negation
∈
¬
equal to the pseudo-complement
.
∧
v
⊥=
R
∨
Υ
=
R
∪
Υ
=
Υ
, and
R
Proof
For any
R
∈
Υ
,
R
∩⊥=⊥
,
R
∧
v
=
R
∩
R
=
R
∪
R
¬
=
Υ
, thus the lattice
L
Υ
is a Boolean
¬
v
R
¬
=⊥
,
R
∨
v
¬
v
R
algebra.
Let us show that, when
Υ
is finite, the lattices
L
Υ
and
L
v
are
equal
, that is,
the binary relations (ordering)
≤
and
≤
v
are equal. Thus, we have to show that for
iff
R
1
⊆
R
2
. In fact, from the fact
any two relations
R
1
,R
2
∈
Υ
,
T
{
R
1
}⊆
T
{
R
2
}
that
Υ
is finite (thus
U
=
dom
, without Skolem constants), every relation
R
∈
Υ
is
TR
:
1. (From right to left) If
R
1
⊆
R
2
then
TR
1
⊆
TR
2
, thus from (a),
T
{
R
1
}⊆
T
finite, so that (a)
T
{
R
}=
.
2. (From left to right) If
T
{
R
2
}
then from (a),
TR
1
⊆
TR
2
. Thus for any
{
R
1
}⊆
{
R
2
}
T
TR
1
, thus,
∈
R
1
,wehave
R
TR
2
, so that
∈
R
1
R
={
a
}∈
a
={
a
}∈
a
and hence
R
1
⊆
R
2
.
Consequently, we obtain
R
1
≤
R
2
iff
R
1
≤
v
R
2
, that is, we obtain the equal ordering,
thus the same lattices, both with the bottom element
⊥
(empty relation), and with
(
Υ
)
=
Υ
. Let us show that the Boolean negation in the lattice
L
Υ
is the pseudo-complement. In fact, for any
R
the top element
∈
Υ
, for its pseudo-complement
in
L
Υ
,
we have (for
finite
Υ
):
T
≤⊥
¬
R
=
{
R
1
∈
Υ
|
R
1
∧
R
≤⊥}=
{
R
1
}|
R
1
∧
R
T
=⊥
=
{
R
1
}|
R
1
∧
R
(from (a) and equal meet operations
∧
and
∧
v
)
T
=⊥
T
=⊥
{
R
1
}|
{
R
1
}|
R
1
∩
R
=
R
1
∧
v
R
=
T
{
R
1
}|
R
1
⊆
R
¬
=
T
{
R
¬
}
=
{
R
¬
}
=
R
¬
=¬
v
R.
=
From these results we may conclude that the important properties of the lattice
of finitary relations have to be investigated when
is infinite (thus with an infinite
number of Skolem constants), that is, when the set of all finitary relations (but which
can have infinite number of tuples) in
Υ
is
infinite
.
We are ready now to establish the relationship between the Galois connection
of Birkhoff polarity (its special case when the incompatibility binary relation is a
PO-set) and the power-view operator
T
for databases:
U
