6.1 Introduction

In the preceding chapters, we saw to how to write queries to extract information from a dataset. In this chapter, we look at how to write transitions that specify how to transform one dataset into another, ideally without specifying all of the factoids and instead concentrating on only those factoids that change their truth values.

6.2 Transition Syntax

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

A transition 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 conclusions must also appear in the positive conditions.

In what follows, we write transition 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.

As we shall see in the next section, a transition 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 transition 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.

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

6.3 Transition Rule Semantics

An instance of a transition 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.

Suppose we are given a dataset Δ and a transition 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 transition 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.

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.

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

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

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)}.

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

6.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 a transition rule with p(X,a) as condition, with p(X,a) as a negative conclusion and with p(a,X) as a positive conclusion.

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.

6.5 Example - Kinship

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.

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 a transition rule like the one shown below.

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

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

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 transition rule.

Executing this transition rule would result in the following dataset.

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.

Exercises