Page 177 - DCAP402_DCAO204_DATABASE MANAGEMENT SYSTEM_MANAGING DATABASE

Database Management Systems/Managing Database

Notes Observe that the instances for the input relations are given, and the definition of a model
essentially restricts the instances for the output relations.

Consider the rule

Components(Part, Subpart) :- Assembly(Part, Part2, Qty),
Components(Part2, Subpart).

Suppose that we replace the variable Part by the constant wheel, Part2 by tire, Qty by 1, and
Subpart by rim:
Components(wheel, rim) :- Assembly(wheel, tire, 1),

Components(tire, rim).
Let A be an instance of Assembly and C be an instance of Components. If A contains the tuple
<wheel, tire, 1> and C contains the tuple <tire, rim>, then C must also contain the tuple <wheel,
rim> in order for the pair of instances A and C to be a model. Of course, the instances A and C
must satisfy the inclusion requirement illustrated above for every assignment of constants to
the variables in the rule: If the tuples in the rule body are in A and C, the tuple in the head must
be in C.

Safe Datalog Programs

Consider the following program:

Complex Parts(Part) :- Assembly(Part, Subpart, Qty), Qty > 2.
According to this rule, complex part is defined to be any part that has more than two copies of
any one subpart. For each part mentioned in the Assembly relation, we can easily check if it is a
complex part. In contrast, consider the following program:
Price Parts(Part,Price) :- Assembly(Part, Subpart, Qty), Qty > 2.
This variation seeks to associate a price with each complex part. However, the variable Price
does not appear in the body of the rule. This means that an infinite number of tuples must be
included in any model of this program! To see this, suppose that we replace the variable Part by
the constant trike, SubPart by wheel, and Qty by 3. This gives us a version of the rule with the
only remaining variable being Price:

Price Parts(trike,Price) :- Assembly(trike, wheel, 3), 3 > 2.
Now, any assignment of a constant to Price gives us a tuple to be included in the output relation
Price Parts. For example, replacing Price by 100 gives us the tuple Price Parts(trike,100). If the
least model of a program is not finite, for even one instance of its input relations, then we say the
program is unsafe.

Database systems disallow unsafe programs by requiring that every variable in the head of a
rule must also appear in the body. Such programs are said to be range restricted, and every
range-restricted Datalog program has a finite least model if the input relation instances are
finite.

170 LOVELY PROFESSIONAL UNIVERSITY