Database Reference
In-Depth Information
We have the following interesting cases:
1. If S A = A then S AB =∅
(empty set), and hence A B ;
2. If S B =
B then S AB =∅
, and hence A
B ;
3. If S A =
A and S B =
B then S AB =∅
, and hence A
B ;
4. If S A =
then S AB is the disjoint union of all possible mergings of the
simple objects (i.e., databases) in A and B , with A B and B A .
We have the following important properties for this generalization of the “merging
with A ” operator '
S B =∅
':
Lemma 17 The following properties for any two objects A and B in DB are valid :
1. ( Commutativity ) A
B
A , thus , A
B
A ;
2. ( Generalized merging ) If A is a simple object , then A
B
B
B
A
B . Thus ,
A
B
A
B ;
3. A
A and A
B
B
B ;
B then A
4. If A
B
B .
= (S A
Proof Claim 1. From A
B
S B
S AB ) we obtain the isomorphism (from
), A
B
A and hence A
B
the commutativity of
A (from Corol-
lary 14 any two isomorphic objects are behaviorally equivalent), which represents
the commutativity property of the generalized merging operator.
Claim 2. It is a generalization of the “merging with A ” operator in Theorem
13 , from the fact that when m
B
B
=
1(i.e., A is a simple object), we obtain S A =
and hence A B = S AB = { A 1 B i |
i k } 1 i k A 1 B i =
S B =∅
1
B . Thus, A
(from Theorem 13 )
=
A
B
A
B .
Claim 3. For each 1
j
m , the simple object A j is in S A or in S AB in form
TA j and hence A
A j
k ,thesimple
object B i is in S B or in S AB in form A j B i TB i , so that A B B .
Claim 4. From the fact that A
B i
B
A . Analogously, for each 1
i
B
B , let us show that if A
B (with a mapping
TB σ(j) ) then A
σ
:{
1 ,...,m
}→{
1 ,...,k
}
such that
1 j m .T A j
B
B as
B then S B =
B and S AB =∅
well. In fact, if A
. Thus, the elements in the disjoint
union of A B are all B i , with TB i TB i , 1
i k ,orsome A j , so that TA j
TB σ(j) and hence A
B
B .
We are now ready to introduce the following database lattice L DB :
Proposition 51 The set Ob DB of all database instances ( objects ) of DB , both with
the generalized merging and matching tensor products
and
( read “join” and
“meet” , respectively ) is a lattice with partial ordering '
' ( introduced by Defini-
tion 19 ).
This lattice L DB =
,
(Ob DB ,
,
) is a complete lattice with the top and bot-
0 , respectively .
tom objects Υ and
Proof First of all, if A
B with a mapping σ
:{
1 ,...,m
}→{
1 ,...,k
}
such that
1 j m .T A j
TB σ(j) , we obtain, from points 3 and 4 of Lemma 17 , that the
generalized merging '
' is equal to the join operator of this lattice w.r.t. the or-
dering '
'. Let us show that the matching operator
is the meet operator of
Search WWH ::




Custom Search