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