Database Reference
In-Depth Information
•
The complete lattice (
C
,
⊆
) obtained by this closure operator T is an algebraic
⊗
⊕
C
⊆
lattice with meet
and join
operators
.
The compact elements of (
,
) are
⊆
ω
Υ
.
closed objects of the
DB
category generated by
finite
simple objects A
•
The lattice (Ob
DB
,
) is an algebraic lattice such that the algebraic clo-
sure operator T is a surjective homomorphism from this lattice into the 'skeletal'
algebraic lattice of closed databases (
C
,
⊆
)
.
,
⊗
,
⊕
Proof
From Theorem
6
in Sect.
3.2.5
,
T
Ob
DB
is a closure operator
over the subset
Ob
DB
and hence the set of closed (and simple) objects
:
Ob
DB
−→
is closed
under intersection. From Definition
26
in Sect.
3.2.5
, the total object
Υ
is the top
object such that for any
A
C
∈
C
(thus,
A
=
TA
),
A
⊆
Υ
. In fact, each object
A
∈
Ob
DB
is a subset of
Υ
and vice versa, each subset of
Υ
(that contains
⊥
)isa
database instance and hence an object in
DB
category.
From the Universal algebra theory it holds that each closure operator and its
equivalent closure-set system
(
Υ
,
C
C
⊆
)
generate a complete lattice
(
,
)
such that for
any subset
K
⊆
C
of
simple
closed objects
K
={
A
i
=
TA
i
|
i
∈
I,A
i
is closed set of
DB
}
we obtain:
The greatest lower bound
K
=
i
∈
I
A
i
=
i
∈
I
A
i
=
K
=
i
∈
I
A
i
(from
Theorem
12
for the simple databases and from
A
i
=
TA
i
), that is, meet lattice
•
operator
corresponds to the matching operation
⊗
.
The least upper bound
K
=
i
∈
I
A
i
=
T(
i
∈
I
A
i
)
T(
i
∈
I
TA
i
)
•
=
=
i
∈
I
A
i
(from Theorem
13
for the simple databases), that is, the join lattice
operator
corresponds to the merging operation
⊕
, and hence for
K
=
C
we
obtain
C
=
T(
A
i
∈
Ob
DB
A
i
)
=
(by Definition
26
)
=
T
Υ
=
Υ
.
=
{
T(A
)
A
⊆
ω
A
Let us demonstrate that
T
is algebraic, that is,
T(A)
|
}
also
for the infinite simple objects
A
K
be the unique uni-
versal functor (which is a restriction of the functor
U
to the subcategory
DB
of only simple objects, described previously in Sect.
8.1.4
). Then, for this infi-
nite simple database
A
,
U(A)
⊆
Υ
.Let
U
:
DB
−→
={[
t
i
]|
t
i
∈
T
P
A
}
is an infinite set of the equiva-
lence classes
of SPJRU algebra terms with an infinite carrier set
A
of rela-
tional tables. From the fact that for all
Σ
R
-algebra operators
o
i
∈
[
t
i
]
Σ
R
with finite
=
≤
2 and
R
1
,...,R
n
∈
A
,
t
i
=
∈
T
P
A
, we can define
n
ar(o
i
)
o
i
(R
1
,...,R
n
)
a finite database
A
={
∈
T
P
A
,
R
1
,...,R
n
}⊆
ω
A
such that
t
i
=
o
i
(R
1
,...,R
n
)
U(A)
={[
t
i
]|
t
i
∈
T
P
A
}=
{[
t
i
]|
t
i
∈
T
P
A
,A
⊆
ω
A
}
. Thus, from Definition
31
in Sect.
5.1
,
TA
={
R
=[
t
i
]
#
|
t
i
∈
T
P
A
}=
{
R
=[
t
i
]
#
|
t
i
∈
T
P
A
,A
⊆
ω
A
}=
{{
R
=[
t
i
]
#
|
t
i
∈
T
P
A
}|
A
⊆
ω
A
}=
{
TA
|
A
⊆
ω
A
}
. Hence,
T
is an
algebraic closure operator and, consequently, the lattice
(
C
,
⊆
)
obtained from this
closure operator and the closed-set system
(
Υ
,
C
)
is algebraic. It is well known that
the compact elements of such a lattice
(
)
, obtained from the algebraic closure
operator
T
, are precisely the closed sets
T(A)
, where
A
is a finite subset of
Υ
.
The ordering in the lattice
(Ob
DB
,
C
,
⊆
,
⊗
,
⊕
)
is defined for any two simple
databases
A,B
∈
Ob
DB
by
A
B
iff
TA
⊆
TB
. Thus,
A
≈
B
iff
TA
=
TB
,so
that
A
TB)
.
From the fact that each non-closed element
A
in this lattice is equivalent to the
closed element obtained from it (
A
≈
TA
with
A
⊗
B
=
TA
∩
TB
and
A
⊕
B
=
T(A
∪
B)
=
T(TA
∪
≈
TA
), this lattice has the same structure of the
