Databases Reference
In-Depth Information
This DB allows to consider as true either {R (a), Q (a)} or {R (a), P (a)}. R (a)
is always true because it belongs to the EDB, while P (a)orQ (a) is true
depending on the truth value of the other. Therefore, it is not possible to
agree on unique semantics for this DB.
To avoid that problem, deductive DBs usually are restricted to being
stratified. A deductive DB is stratified if derived predicates can be assigned to
different strata in such a way that a derived predicate that appears negatively
on the body of some rule can be computed by the use of only predicates in
lower strata. Stratification allows the definition of recursive predicates, but it
restricts the way negation appears in those predicates. Roughly, semantics of
stratified DBs are provided by the application of CWA strata by strata [14].
Given a stratified deductive DB D, the evaluation strata by strata always pro-
duces a minimal Herbrand model of D [20].
For instance, the preceding example is not stratifiable, while the DB of
Example 4.1 is stratifiable, with this possible stratification: S
1
=
{Father,
Mother, Parent, GrandMother, Ancestor} and S
2
=
{Nondirect-anc}.
Determining whether a deductive DB is stratifiable is a decidable prob-
lem and can be performed in polynomial time [6]. In general, several stratifi-
cations may exist. However, all possible stratifications of a deductive DB are
equivalent because they yield the same semantics [5].
A deeper discussion of the implications of possible semantics of deduc-
tive DBs can be found in almost all topics explaining deductive DBs (see, for
instance, [5, 6, 8, 9, 11, 14]). Semantics for negation (stratified or not) is dis-
cussed in depth in [5, 21]. Several procedures for computing the least Her-
brand model of a deductive DB are also described in those references. We
will describe the main features of these procedures when dealing with query
evaluation in Section 4.3.
4.2.3
Advantages Provided by Views and Integrity Constraints
The concept of view is used in DBs to delimit the DB content relevant to
each group of users. A view is a virtual data structure, derived from base facts
or other views by means of a definition function. Therefore, the extension
of a view does not have an independent existence because it is completely
defined by the application of the definition function to the extension of
the DB. In deductive DBs, views correspond to derived predicates and are
defined by means of deductive rules. Views provide the following advantages.
Views simplify the user interface, because users can ignore the
data
ยท
that
are
not
relevant
to
them.
For
instance,
the
view
