Databases Reference
In-Depth Information
The deductive DB in this example contains three facts stating exten-
sional data about fathers and mothers, six deductive rules defining the inten-
sional notions of parent, grandmother, and ancestor, with their meaning being
hopefully self-explanatory, and nondirect-anc, which defines nondirect ances-
tors as those ancestors that do not report a direct parent relationship. Two
integrity constraints state that nobody can be the parent of himself or herself
and that nobody can be father and mother at the same time.
Note that inconsistency predicates may also contain variables that
allow the identification of the individuals that violate a certain integrity con-
straint. For instance, the evaluation of IC2(x) would give as a result the dif-
ferent values of x that violate that constraint.
4.2.2
Semantics of Deductive Databases
A semantic is required to define the information that holds true in a particu-
lar deductive DB. This is needed, for instance, to be able to answer queries
requested on that DB. In the absence of negative literals in the body of deduc-
tive rules, the semantics of a deductive DB can be defined as follows [18].
An interpretation, in the context of deductive DBs, consists of an
assignment of a concrete meaning to constant and predicate symbols. A cer-
tain clause can be interpreted in several different ways, and it may be true
under a given interpretation and false under another. If a clause C is true
under an interpretation, we say that the interpretation satisfies C. A fact F
follows from a set S of clauses; each interpretation satisfying every clause of S
also satisfies F.
The Herbrand base (HB) is the set of all facts that can be expressed in
the language of a deductive DB, that is, all facts of the form P (c
1
,
, c
n
) such
that all c
i
are constants. A Herbrand interpretation is a subset
J
of HB that
contains all ground facts that are true under this interpretation. A ground
fact P (c
1
,
¼
¼
, c
n
) is true under the interpretation
J
if P (c
1
,
¼
, c
n
)
Î
J
. A rule
of the form A
0
¬
L
n
is true under
J
if for each substitution
q
that
replaces variables by constants, whenever L
1
L
1
Ù¼Ù
Î
Ù¼Ù
L
n
Î
J
, then it
q
J
q
also holds that A
0
q
J
.
A Herbrand interpretation that satisfies a set S of clauses is called a Her-
brand model of S. The least Herbrand model of S is the intersection of all
possible Herbrand models of S. Intuitively, it contains the smaller set of facts
required to satisfy S. The least Herbrand model of a deductive DB D defines
exactly the facts that are satisfied by D.
For instance, it is not difficult to see that the Herbrand interpretation
{Father( John,Tony), Father(Peter,Mary), Mother(Mary,Bob), Parent( John,
Î
