Page 175 - DCAP402_DCAO204_DATABASE MANAGEMENT SYSTEM_MANAGING DATABASE

Database Management Systems/Managing Database

Notes repeated use of the variable Part2 prevents certain rows of the cross product from contributing
any new tuples; in effect, it specifies an equality join condition on Assembly and Components.
The tuples obtained by one application of this rule are shown in Figure 10.1. (In addition,
Components contains the tuples obtained by applying the first rule; these are not shown.)
The tuples obtained by a second application of this rule are shown in Figure 10.2. Note that each
tuple shown in Figure 10.1 is reinferred. Only the last two tuples are new.
Figure 10.2: Components Tuples Obtained by Applying the Second Rule Twice

Applying the second rule a third time does not generate any additional tuples. The set of
Components tuples shown in Figure 10.2 includes all the tuples that can be inferred using the
two Datalog rules defining Components and the given instance of Assembly. The components
of a trike can now be obtained by selecting all Components tuples with the value trike in the
first field.
Each application of a Datalog rule can be understood in terms of relational algebra. The first rule
in our example program simply applies projection to the Assembly relation and adds the resulting
tuples to the Components relation, which is initially empty. The second rule joins Assembly
with Components and then does a projection. The result of each rule application is combined
with the existing set of Components tuples using union.
The only Datalog operation that goes beyond relational algebra is the repeated application of
the rules defining Components until no new tuples are generated. This repeated application of
a set of rules is called the fixpoint operation.
We conclude this section by rewriting the Datalog de_nition of Components in terms of extended
SQL, using the syntax proposed in the SQL:1999 draft and currently supported in IBM’s DB2
Version 2 DBMS:

WITH RECURSIVE Components(Part, Subpart) AS
(SELECTA1.Part, A1.Subpart FROM Assembly A1)
UNION
(SELECTA2.Part, C1.Subpart
FROM Assembly A2, Components C1
WHERE A2.Subpart = C1.Part)
SELECT * FROM Components C2

The WITH clause introduces a relation that is part of a query definition; this relation is similar
to a view, but the scope of a relation introduced using WITH is local to the query definition. The

168 LOVELY PROFESSIONAL UNIVERSITY