Database Reference
In-Depth Information
The following property for the closed object (instance-database) in each (deter-
mined by dom ) DB category is valid:
Lemma 23
The set J A of join-irreducible elements in any closed object ( instance
database ) A
=
TA
Ob DB sk
is equal to the set of its atoms ,
J A = R
=
d i |
val(A) = R
=
d i |
d i A ,
d i
so that J A
A , and A
J A iff J A is a finite nonempty set .
Proof The 'atomic database' J A was introduced in Sect. 1.4 . Let us consider the
sublattice (T A, ) = ( ( (A)), ) ( Υ , ) with the bottom relation
and the
top relation
(A) . Then for each R
J A ,
⊥≤
R , so that R is an atom in this
lattice (T A,
) . Each relation R 1
(
(A),
)
=
(T A,
) different from atoms
is composed of at least two distinct values in S
U
and hence it is a join of a subset
, i.e., R 1 {
of atoms
{
R
={
d
}|
d
S
}
R
={
d
}|
d
S
}
, and consequently,
the set of join irreducible elements in (T A,
) is equal to the set of its atoms.
If J A is finite, then A = TA is finite as well with all finite relations, so that
A
=
T J A , i.e., A
J A .IfJ A is infinite , for a database A
=
TA with at least one
relation R
A with infinite number of tuples, then T J A is a set of all finite relations
(because each query is a finite-length SPJRU term, thus it can generate from J A
only a finite relation) with T J A
TA (thus, J A
A ).
Thus, if J A is finite then it is a set of generators of the relational algebra (A,Σ R )
(hence, this algebra (A,Σ R ) is finitely generated by a finite set J A because any
element (relation) in A can be expressed as a finite-length term in J A ), that is, of the
database A . Also the lattice (T A,
) is then finitely generated by J A .
Notice that in the case when A = Υ (for a given universe
U =
dom
SK ), we
obtain that J Υ ={
is an infinite set, but it is only a strict subsetset
of generators of Υ (the relational algebra ( Υ R ) cannot be generated by J Υ only).
A special case of a database with a relation with an infinite number of tuples
may appear in Data Integration with cyclic tgds with the existentially quantified
right-hand side of material implication, as explained in Sect. 4.2.4 .
R
={
d
}|
d
U }
9.2.3 Embedding of WMTL (Weak Monoidal Topos Logic) into
Intuitionistic Bimodal Logics
Intuitionistic propositional logic IL and its extensions, known as intermediate or
superintuitionistic logics, in many respects can be regarded just as fragments of
classical modal logics containing S4. At the syntactical level, the Gödel translation
embeds every intermediate logic into modal logics. Semantically, this is reflected by
the fact that Heyting algebras are precisely the algebras of open elements of topo-
logical Boolean algebras. This embedding is a powerful tool for transferring various
kinds of results from intermediate logics to modal ones and back via preservation
theorems.
Search WWH ::




Custom Search