Page 174 - DCAP402_DCAO204_DATABASE MANAGEMENT SYSTEM_MANAGING DATABASE

Unit 10: Datalog and Recursion

These are rules in Datalog, a relational query language inspired by Prolog, the wellknown logic Notes
programming language; indeed, the notation follows Prolog. The first rule should be read as
follows:
For all values of Part, Subpart, and Qty,
if there is a tuple <Part, Subpart, Qty> in Assembly,
then there must be a tuple <Part, Subpart> in Components.

The second rule should be read as follows:
For all values of Part, Part2, Subpart, and Qty,
if there is a tuple <Part, Part2, Qty> in Assembly and
a tuple <Part2, Subpart> in Components,

then there must be a tuple <Part, Subpart> in Components.
The part to the right of the:- symbol is called the body of the rule, and the part to the left is called
the head of the rule. The symbol:- denotes logical implication; if the tuples mentioned in the
body exist in the database, it is implied that the tuple mentioned in the head of the rule must also
be in the database.

Notes The body could be empty; in this case, the tuple mentioned in the head of the rule
must be included in the database.
Therefore, if we are given a set of Assembly and Components tuples, each rule can be used to
infer, or deduce, some new tuples that belong in Components. This is why database systems that
support Datalog rules are often called deductive database systems.
Each rule is really a template for making inferences: by assigning constants to the variables that
appear in a rule, we can infer specific Components tuples. For example, by setting Part=trike,
Subpart=wheel, and Qty=3, we can infer that <trike, wheel> is in Components. By considering
each tuple in Assembly in turn, the first rule allows us to infer that the set of tuples obtained by
taking the projection of Assembly onto its first two fields is in Components.

Figure 10.1: Components Tuples Obtained by Applying the Second Rule Once

The second rule then allows us to combine previously discovered Components tuples with
Assembly tuples to infer new Components tuples. We can apply the second rule by considering
the cross-product of Assembly and (the current instance of) Components and assigning values to
the variables in the rule for each row of the cross-product, one row at a time. Observe how the

LOVELY PROFESSIONAL UNIVERSITY 167