Introduction to
Logic Programming
What
versus
How
 

Chapter 4 - Updates


4.1 Introduction

In the preceding chapter, we saw to how to write queries to extract information from a dataset. In this chapter, we look at how to update the information in a dataset, i.e. how to transform one dataset into another, ideally without rewriting all of the factoids and instead concentrating on only those factoids that have changed their truth values.

4.2 Update Syntax

As with our query language, our update language includes the language of datasets but provides some additional features. Again, we have variables, but in this case we have update rules in place of query rules.

An update rule is an expression consisting of a non-empty collection of literals (called conditions) and a second non-empty collection of literals (called conclusions). The conditions and conclusions may be ground or they may contain variables. There is only one restriction: all variables in conclusions must also appear in the positive conditions.

In what follows, we write update rules as in the example shown below. Here, p(a,b) and ~q(b) are conditions, and ~p(a,b) and p(b,a) are conclusions.

p(a,b) & ~q(b) ==> ~p(a,b) & p(b,a)

As we shall see in the next section, an update rule is something like a condition-action rule. It is a statement that whenever the conditions are true, then the negative conclusions should be deleted from the dataset, and the positive conclusions should be added. For example, the rule above states that, if p(a,b) is true and q(b) is not true, then p(a,b) should be removed from the dataset and p(b,a) should be added.

As with query rules, the power of update rules is greatly enhanced through the use of variables. Consider, for example, the rule shown below. This is a more general version of the rule shown above. Instead of applying to just the specific objects a and b it applies to all objects.

p(X,Y) & ~q(Y) ==> ~p(X,Y) & p(Y,X)

An update is a finite collection of update rules. Typically, an update consists of just one rule. However, updates with multiple rules are sometimes useful and do not add any major complexity, so in what follows we allow for the possibility of updates with multiple rules.

4.3 Update Semantics

An instance of an update rule is one in which all variables have been consistently replaced by ground terms (i.e. terms without variables). For example, if we have a language with symbols a and b, then the instances of p(X,Y) & ~q(Y) ==> ~p(X,Y) & p(Y,X) are shown below.

p(a,a) & ~q(a) ==> ~p(a,a) & p(a,a)
p(a,b) & ~q(b) ==> ~p(a,b) & p(b,a)
p(b,a) & ~q(a) ==> ~p(b,a) & p(a,b)
p(b,b) & ~q(b) ==> ~p(b,b) & p(b,b)

Suppose we are given a dataset Δ and an update rule r. We say that an instance of r is active on Δ if and only if the conditions are all true on Δ. We define the positive update set A(r,Δ) to be the set of all positive conclusions in some active instance of r, and we define the negative update set D(r,Δ) to be the set of all negative conclusions in some active instance of r.

The positive update set A(Ω,Δ) for a set of rules Ω on a dataset Δ is the union of the positive updates of the rules on Δ; and the negative update set D(Ω,Δ) for Ω is the union of the negative updates of the rules on Δ.

Finally, we obtain the result of applying a set of update rules R to a dataset Δ by removing the negative updates and adding in the positive updates, i.e. the result is Δ - D(Ω,Δ) ∪ A(Ω,Δ).

Let's look at some examples to illustrate this semantics. Consider the dataset shown below. In this case, there are four symbols and one binary predicate p.

p(a,a)
p(a,b)
p(b,c)
p(c,c)
p(c,d)

Now, suppose we wanted to drop all of the p factoids in our dataset in which the first and second arguments are the same. To do this, we would specify the update shown below.

p(X,X) ==> ~p(X,X)

In this case, there would be two instances in which the conditions are true. See below.

p(a,a) ==> ~p(a,a)
p(c,c) ==> ~p(c,c)

Consequently, after execution of this update, we would have the dataset shown below.

p(a,b)
p(b,c)
p(c,d)

Now suppose that we wanted to reverse the arguments of the remaining p factoids in our dataset. To do this, we would specify an update with p(X,Y) as a condition; we would include p(X,Y) as a negative conclusion; and we would specify p(Y,X) as a positive conclusion. In this case, we would have one variable assignment for every factoid in our dataset; the negative conclusions would be {p(a,b), p(b,c), p(c,d)}, i.e. every factoid in our dataset; and the positive conclusions would be {p(b,a), p(c,b), p(d,c)}.

p(X,Y) ==> ~p(X,Y) & p(Y,X)

After executing this update on the preceding dataset, we would have the dataset shown below.

p(b,a)
p(c,d)
p(d,c)

4.4 Simultaneous Updates

Note that it sometimes happens that a factoid appears as both a positive and a negative update. As an example of this, consider an update with p(X,a) as condition, with p(X,a) as a negative conclusion and with p(a,X) as a positive conclusion.

p(X,a) ==> ~p(X,a) & p(a,X)

In the case of the first dataset shown in the preceding section, p(a,a) would appear as both a positive and a negative update.

In such cases, our semantics dictates that the factoid be removed and then added right back in again, with the result that there is no change. This is a relatively arbitrary resolution to the conflict in such cases, but it appears to be the one favored most often by programmers.

4.5 Example - Kinship

Once again consider the Kinship application; and assume, as before, that we start with a single binary predicate parent (which is true of two people if and only if the person specified as the first argument is the parent of the person specified as the second argument).

The factoids shown below constitute a dataset using this vocabulary. The person named art is a parent of the person named bob and the person named bea; bob is the parent of cal and cam; and bea is the parent of coe and cory.

parent(art,bob)
parent(art,bea)
parent(bob,cal)
parent(bob,cam)
parent(bea,cat)
parent(bea,coe)

In Chapter 3, we saw how to write queries to characterize other kinship relations in terms of parent. In some cases, we might want to store the resulting factoids so that they can be accessed without recomputing.

Suppose, for example, we wanted to store information about grandparents and their grandchildren. We could do this by writing an update like the one shown below.

parent(X,Y) & parent(Y,Z) ==> grandparent(X,Z)

Starting with the dataset shown above, applying this update would result in the addition of the following factoids to our dataset.

grandparent(art,cal)
grandparent(art,cam)
grandparent(art,cat)
grandparent(art,coe)

If we subsequently wanted to remove these factoids, we could execute the update shown below, and we would end up back where we started.

grandparent(X,Y) ==> ~grandparent(X,Z)

Now, suppose we wanted to reverse the arguments to the parent predicate, relating children and parents rather than relating parents and children. To do this, we could write the following update.

parent(X,Y) ==> ~parent(X,Y) & parent(Y,X)

Executing this update would result in the following dataset.

parent(bob,art)
parent(bea,art)
parent(cal,bob)
parent(cam,bob)
parent(cat,bea)
parent(coe,bea)

In understanding updates like this one, it is important to keep in mind that updates happen atomically - we first compute all factoids to be changed and we then make those changes all at once - before considering any other updates.

4.6 Example - Colors

Ruby Red, Willa White, and Betty Blue meet for lunch. One is wearing a red skirt; one is wearing a white skirt; and one is wearing a blue skirt. No one is wearing more than one color, and no two are wearing the same color. Betty Blue tells one of her companions, "Did you notice we are all wearing skirts with different colors from our names?"; and the other woman, who is wearing a white skirt, says, "Wow, that's right!" Our job is to figure out which woman is wearing which skirt.

One way to solve problems like this is to enumerate possibilities and check, for each, whether it satisfies the constraints in the statement of the problem. This approach works, but it often requires a good deal of search. To make the process of finding solutions more efficient, we can sometimes use values we already know to infer additional values and thereby cut down on the number of possibilities we need to consider. In this section, we see how we can use updates to implement this technique. In this very special case, as we shall see, this technique eliminates search altogether.

To solve the problem, we adopt a vocabulary with six symbols r, w, b, v, x, and e. The first three denote people / colors and the latter three denote "truth values" - true, false, and unknown. To express the state of our problem, we use a ternary relation constant c. For example, we would write c(r,b,v) to mean that Ruby Red is wearing a white skirt; we would write c(r,b,x) to mean that Ruby Red is not wearing a white skirt; and we would write c(r,b,e) to mean that we do not know whether or not Ruby Red wearing a white skirt.

In solving this problem we start with the dataset shown below. Initially, we know nothing about who is wearing what.

c(r,r,e)
c(r,w,e)
c(r,b,e)
c(w,r,e)
c(w,w,e)
c(w,b,e)
c(b,r,e)
c(b,w,e)
c(b,b,e)

We can picture this situation as shown below, with the idea that the value in each cell is an indication of our belief about whether the person listed as the first argument in one of our c factoids is wearing a skirt with the color specified as the second argument. For the sake of clarity, we leave cells empty when they have value e.

  r w b
r      
w      
b      

First we apply the constraint that none of the women is wearing a skirt with the same color as her name.

c(C,C,e) ==> ~c(C,C,e) & c(C,C,x)

After this update, we are left with the state of affairs shown below. We now have x values along the diagonal, but we still have empty cells everywhere else.

  r w b
r    
w    
b    

Next we take into account Betty Blue's comment to someone who is wearing a white skirt, which means that Betty Blue is not wearing a white skirt.

color(b,w,e) ==> ~color(b,w,e) & color(b,w,x)

This leaves us with the situation shown below.

  r w b
r    
w    
b  

Now we get to the interesting part. First, we have updates that tell us that, if there are two occurrences of x in a row or a column and the remaining cell is an e, then the final possibility in that row or column must be a v.

c(P,C1,x) & c(P,C2,x) & c(P,C3,b) ==> ~c(P,C3,b) & c(P,C3,v)
c(P1,C,x) & c(P2,C,x) & c(P3,C,b) ==> ~c(P3,C,b) & c(P3,C,v)

Applying these updates once to the situation above leads to the situation depicted below. Here we use a green check to represent the value v. Since neither Willa White nor Betty Blue is wearing a white skirt, Ruby Red must be wearing white.

  r w b
r  
w    
b  

Similarly, we have updates that tell us that, if there is an occurrence of an v in a row or a column and there is a cell containing an e, then that e should be changed to an x.

c(P,C1,v) & c(P,C2,e) ==> ~c(P,C2,e) & c(P,C2,x)
c(P1,C,v) & c(P2,C,e) ==> ~c(P2,C,e) & c(P2,C,x)

Applying these updates gives us more information. Since Ruby Red is wearing a red skirt, she must not be wearing a blue skirt.

  r w b
r
w    
b  

Applying these updates three more times leads to an overall solution to the problem. Since neither Ruby Red nor Betty Blue is wearing blue, Willa White must be wearing blue. Therefore, Willa White cannot be wearing red. And, therefore, Betty Blue must be wearing red.

  r w b
r
w
b

This problem is special in that we can solve it solely by inferring values from other values. In constraint satisfaction problems like this one, some search is often necessary. That said, constraint propagation techniques, like the one used here, can often cut down on this search even when they cannot be used to solve the problem altogether.

This case is also special in that it is easy to express all of the update rules necessary to solve the problem. For some problems, such as solving Sudoku puzzles, it is impractical to write update rules using our limited update language. Luckily, as we shall see in future chapters, we can easily express more complicated rules once we have the ability to write view definitions and action definitions.

Exercises

Exercise 4.1: For each of the following strings, say whether it is a syntactically legal update.

  (a) p(a,f(f(X))) ==> p(X,Y)
  (b) P(a,Y) ==> P(Y,a)
  (c) p(X,Y) & p(Y,Z) ==> ~p(X,Y) & ~p(Y,Z) & p(X,Z)
  (d) p(X,b) ==> f(X,f(b,c))

Exercise 4.2: What is the result of applying the update rule p(X,Y) ==> ~p(X,Y) & p(Y,X) to the dataset shown below?

p(a,a)
p(a,b)
p(b,a)

Exercise 4.3: Suppose we have a kinship dataset with a binary predicate parent and a unary predicate male. Write update rules to replace all factoids using the parent predicate with equivalent factoids using the binary predicates father and mother.

Exercise 4.4: Amy, Bob, Coe, and Dan are traveling to different places. One goes by train, one by car, one by plane, and one by ship. Amy hates flying. Bob rented his vehicle. Coe tends to get seasick. And Dan loves trains. Write update rules to solve this problem by constraint propagation.