Database Reference
In-Depth Information
(iii) TA
=↓
R A , where R A =
(A)
Υ .
Proof This PO is well defined since a singleton
{
R
}
is equivalent to a database,
and T(
) is the set of all views that can be obtained from it in SPRJU relational
algebra, with
{
R
}
0
⊥∈
T(
{
R
}
)
Ob DB . T
{⊥}={⊥}=⊥
A
TA for each database
A in DB , so that T
R .
From point 2 of Proposition 69 , for any simple database A , TA
{⊥}⊆
T
{
R
}
for any R
Υ , i.e.,
⊥≤
=
T(
{
(A)
}
) ,
which is valid when A is a singleton set of relations as well. Let R 1
R 2 , i.e.,
T
{
R 1 }⊆
T
{
R 1 }
. Then,
T
T
T
T
T(R 1
R 2 )
=
{
R 1 }∩
T
{
R 2 }
=
{
R 1 }
=
T
{
R 1 }
,
so that we obtain the lattice equality R 1
R 2
R 1 . While
T T
R 2 } =
T T
R 2 } =
T(R 1
R 2 )
=
{
R 1 }∪
T
{
{
T
{
R 2 }
,
so that we obtain the lattice equality R 1
R 2
R 2 . Consequently, the meet and
join operations of this lattice are well defined. The finitary relation
(A) is the
{
}⊆
=
l.u.b. of all elements in TA . In fact, for each view (relation) v
TA , T
v
TA
{
}
T(
(A)
) , so that v
(A) and, consequently,
(A)
TA is the l.u.b. of relations
= (T A) and TA
=
in TA . Thus, for each closed database TA
Ob DB sk ,
(T A)
(
(A)) .
Consequently, from the fact that Υ
=
T Υ is a closed object in DB , we obtain that
the top element of this complete lattice is 1
= (T Υ )
=
R Υ =
=
=
( Υ )
(T Υ )
( Υ ) .
From the fact that
( {
(R 1 ,R 2 )
T
{
R 1 }
,T
{
R 2 }}
) , we obtain for the supre-
mum
T
A
A
(A),
(from the set-equality T( { ( { T { R }| R A } ) } ) = T( { (A) } ) ) and hence the
supremum in this lattice corresponds to the relation R Υ = ( Υ ) = ( Υ ) .
{
R
}|
R
We recall that a Boolean algebra is a distributive lattice (which satisfies the equa-
tions of points 1-6 in Sect. 1.2 ) with additional negation operator
¬
, such that it
satisfies the following additional equations:
a
0
=
0 ,
a
1
=
1 ,
a
∧¬
a
=
0 ,
a
∨¬
a
=
1 .
The lattice of relations L Υ in Lemma 22 and the lattice L v in Example 44 above
have the following properties:
Proposition 70
The complete distributive lattice L v in Lemma 21 is a Boolean
, Υ ) with negation operation defined by :
algebra ( Υ ,
v ,
v ,
¬ v ,
= R ¬
R
¬ v R
a
|
a
U
,
a
/
Search WWH ::




Custom Search