ASP-05 | Rules Part II
Complex rule structures in ASP, focusing on conjunctions in rule bodies and their application to model real-world relationships.Photo Credit: Rob Grzywinski
Conjunctions in the Body of Rules
All of the rules that we have seen so far have a single atom in their body but atoms can be combined conjunctively (using a comma ",") to form rich expressions:a ; b .
p ← a, b .
The comma is read as "and": "If a and b are both in the answer set then q is in the answer set". Due to the disjunctive fact a ; b . and the minimality of answer sets, there are two possible answer sets: . Since p requires both a and b to be true (due to the conjunction in its body), and we don't have both a and b in the same answer set (due to minimality), p will never be derived.p(X) ← X = 1..3, X < 2 .
While one would never write this rule (rather than simply reduce the upper-bound on the interval) it does show how intervals, arithmetic operators and conjunctions can be combined into a single rule (whose result is ).Truth Tables
Recall that the conjunction of two truth values is true if and only if both values are true.truth(f,f) ← ⊥, ⊥ .
truth(f,t) ← ⊥, ⊤ .
truth(t,f) ← ⊤, ⊥ .
truth(t,t) ← ⊤, ⊤ .
Grounding
Looking at (2) and expanding the interval:p(X) ← X = 1, X < 2 .
p(X) ← X = 2, X < 2 .
p(X) ← X = 3, X < 2 .
Substituting the variable with its value:p(1) ← 1 = 1, 1 < 2 .
p(2) ← 2 = 2, 2 < 2 .
p(3) ← 3 = 3, 3 < 2 .
Finally replacing the arithmetic expressions with their truth value and striking out any bodies that evaluate to false:p(1) ← ⊤, ⊤ .
p(2) ← ⊤, ⊥ .
p(3) ← ⊤, ⊥ .
We are left with the expected result .
Example: Genealogy
Recall the earlier genealogy example in which we defined parent/2 from mother/2 and father/2:mother((janie ; pete ; tommy ; zuzu), mary) .
father((janie ; pete ; tommy ; zuzu), george) .
parent(C, M) ← mother(C, M) .
parent(C, F) ← father(C, F) .
With conjunctions and comparisons, we can add a relation for siblings:sibling(X, Y) ← parent(X, P), parent(Y, P), X != Y .
{| sibling/2 |
|---|
| janie | pete |
| janie | tommy |
| janie | zuzu |
| pete | janie |
| pete | tommy |
| pete | zuzu |
| tommy | janie |
| tommy | pete |
| tommy | zuzu |
| zuzu | janie |
| zuzu | pete |
| zuzu | tommy |
} - First,
parent(X, P) finds all child-parent pairs, binding variables X and P - Then
parent(Y, P) finds another child with the same parent (notice P is reused) - Finally,
X != Y ensures we don't match a child with themselves
For example, with pete and mary:parent(X, P) matches X = pete, P = maryparent(Y, P) then looks for all Y where P = mary- This finds
Y = janie, Y = tommy, and Y = zuzu X != Y ensures pete isn't matched with himself
The process repeats for each possible X and P combination. Think of it like nested loops:for each X,P in parent relationships:
for each Y where parent(Y,P):
if X != Y:
add sibling(X,Y) to answer set
This "joining" on shared variables is one of the most powerful features of Logic Programming, allowing us to express complex relationships concisely. The solver handles all the details of finding valid combinations that satisfy our rules.
We can "ask questions" of this program to find out who pete's siblings are:answer(X) ← sibling(pete, X) .
Exciting!Alternate Encoding
Notice that both sibling(pete, zuzu) and sibling(zuzu, pete) (as well as all of the other pairs) are found in the answer set. Based on how these results will be used, this may either help or hinder. In our case, it helped since it made (10) easy to rationalize and write.It's possible to use ASP's total ordering to eliminate these "duplicate" (symmetric) cases:sibling(X, Y) ← parent(X, P), parent(Y, P), X < Y .
{| sibling/2 |
|---|
| janie | pete |
| janie | tommy |
| janie | zuzu |
| pete | tommy |
| pete | zuzu |
| tommy | zuzu |
} =" and "!=" on non-integer terms, now you know!)This answer set does require rethinking the question in (10) as that now only returns which is missing janie. To get the complete set, an additional rule is required.answer(X) ← sibling(X, pete) .
Neither of these approaches is wrong — it simply depends on how the relations will be used.
On Relations and Relational Databases
If you thought about relational databases and SQL when relations were first mentioned in "Just The Facts...|Predicates", you would be quite justified. There is much similarity between Logic Programming and relational databases and in fact many techniques from relational databases are used in ASP. The same is true for graph databases and SPARQL.If you're familiar with SQL, you can think (8) in terms of a cross join: SELECT parent1.child AS sibling1
, parent2.child AS sibling2
FROM parent AS parent1
, parent AS parent2
WHERE parent1.parent = parent2.parent
AND parent1.child != parent2.child
The same technique used in (11) can be used here as well to eliminate duplicates (i.e. the "!=" can be replaced with "<").
