DeAL TutorialRules

Rules Defined

Definitions
  • A rule is an expression of the form:

          A B1, B2, ... , Bn.

    where A and B1 through Bn are predicates. A is called the head of the rule and the expression to the right of the '''' is called the body.

    part_cost1(X, Y) <- part_cost(top_tube, X, Y, Z).
  • A rule that contains no variables is a ground rule or an instantiated rule.

    run_for_your_life <- physician(`Dr. Frankenstein`).

  • A rule with no body is a unit clause.
    distance(City, City, 0).
  • A ground unit clause is fact.
    distance(`Austin`, `Waco`, 110).

    Facts are normally stored in the database (but facts occasionally occur in the program.)

Semantics of Rules

Union
The two rules,
A <- B.
A <- C.

are logically equivalent to (B A) & (C A) which is (B C) A.

We will refer to a predicate such as A, which is the result of the union of two (or more) rules, as a union predicate.

Interpretation

A rule,

      A B1, B2, ... , Bn.

is logically equivalent to: the conjunction of B1, B2, ... , Bn implies A .

When the truth value of each predicate in the body is TRUE, the head predicate is also TRUE.

Bottom-Up Evaluation

(a) h1(X,Y) <- p(X,Y).
(b) h2(X) <- h1(X,Y).
(c) p(X,Y) <- b(X,Y).
    b(1,2).
    b(2,4).

  1. Rule (c) is the only one whose body contains only a base predicate. Matching the body with the data produces {p(1,2),p(2,4)} as new facts.
    The partial result is the set {b(1,2),b(2,4),p(1,2),p(2,4)}
  2. Now rule (a) can be evaluated using the results of step (1).
    The result is {b(1,2),b(2,4),p(1,2),p(2,4),h1(1,2),h1(2,4)}.
  3. Rule (b) is evaluated using the result of step (2).
    The result is {b(1,2),b(2,4),p(1,2),p(2,4),h1(1,2),h1(2,4),h2(1),h2(2)}.
  4. No more results are produced.

Equality Predicate (.deal | .fac)

Say that t(X, Y, Z) is a base predicate; X,Y,Z are integers. Then, sums(X) <- t(X,Y,Z), X = Y + Z. returns all a,b,c such that the tuple t(a,b,c) appears in t and a = b + c. The equality serves as a test.

t(3,2,1).
t(5,2,3).
t(8,4,3).
t(7,4,3).
t(7,3,4).

export sums(X). 
query sums(X).

returns {sums(3), sums(5), sums(7)}

export sums($X).
query sums(5).

returns TRUE, and

query sums(8).

returns FALSE.

Equation Solving

t1(X, Z) is a base predicate; X, Z are integers.

sums1(Y) <- t1(X, Z), X = Y*Y + Z.

Fails at compile time! Although X, Z are known, the system cannot solve the equation for Y.

(DeAL will however solve simple linear equations.)

Equality Predicate Operating as Single Assignment

t1(X, Z) is a base predicate, X, Z are integers.

sums2(Y) <- t1(X, Z), Y = X + Z.
export sums2(X).

compiles correctly! In this form the equality is used as a single assignment.

t1(1,2).
t1(3,5).

query sums2(X).

returns {sums2(3), sums2(8)}.

export sums2($X). 
query sums2(3).

returns TRUE and

query sums2(4).

returns FALSE.

Safety

Safety is a program property that ensures that the values of program variables can be effectively computed.

Safety thus depend on the execution used (e.g., bottom-up, top-down, or a combination of the two).

  1. For the bottom-up execution, the safe predicates are those that are derivable from from database relations (possibly using arithmetic and equality assignments).
  2. For top-down execution, safety also depends from the binding pattern of the export.
  3. Assume that goals in the rules are evaluated from left to right. Then the re-ordering of the goals could make a safe rule unsafe or vice-versa
  4. The safe binding patterns for equality and inequality predicates are summarized in the following table:

Built-in Predicates for Terms

Predicate name
and Arguments
Safe Binding
Patterns
Comments
L = R $L, $R L, R arbitrary terms
L, $R L is a variable
$L, R R is a variable
L ~= R $L, $R $ L \neq R$
L > R $L, $R  
L < R $L, $R  
L <= R $L, $R $ L \geq R$
L >= R $L, $R $ L \geq R$

Example: Safety

good_salary(X) <- X > 80000.

But,

export good_salary(X).

does not compile! The query form is unsafe. However,

export good_salary($X).

is safe. query good_salary(100,000). is TRUE. query good_salary(50,000). is FALSE.

In DeAL the bound values in the exports are always propagated down to the defining predicates---if these are not recursive. For recursive predicates the situation is more complex and will be discussed later.

Example: Safety - A Modified Example

well_paid_employee(Name, Salary) <- employee(Name, Salary), Salary > 80000.

Now export well_paid_employee(Name, Salary). is safe.


Last Updated 2014