11.1 Introduction

In the preceding unit (Chapters 7-10), we saw how to write rules to define view relations in terms of base relations. Once defined, we can use those views in queries and in the definitions of other views. In this unit (Chapters 11-14), we look at how to write rules that define operations in terms of changes to base relations. Once defined, we can use those operations in updates and in the definitions of other operations. It is important to keep in mind the differences between views and operations - views are used in talking about facts that are true in states whereas operations are used in talking about changes to states.

In this chapter, we define the syntax and semantics of operation definitions. In the next chapter, we see how operation definitions can be used to specify the handling of events in dynamic systems (where the system's behavior changes in response to internal or external stimuli). In Chapter 13, we look at how to use operation definitions in database management. And, in Chapter 14, we look at how to use operation definitions in building interactive worksheets.

11.2 Syntax

The syntax of operation definitions is analogous to the syntax for view definitions. The various types of constants are the same, and the notions of term and atom and literal are also the same. However, to these, we add a few new items.

To denote operations, we designate some constants as operation constants. As with constructors and relation constants, each operation constant has a fixed arity - unary, binary, and so forth.

An action is an application of an operation to specific objects. In what follows, we denote actions using a syntax similar to that of atomic sentences, viz. an n-ary operation constant followed by n terms enclosed in parentheses and separated by commas. For example, if f is a binary operation constant and a and b are symbols, then f(a,b) denotes the action of applying the operation f to a and b.

An operation definition rule (or, more simply, an operation rule) is an expression of the form shown below. Each rule consists of (1) an action expression, (2) a double colon, (3) a literal or a conjunction of literals, (4) a double shafted forward arrow, and (5) a literal or an action expression or a conjunction of literals and action expressions. The action expression to the left of the double colon is called the head; the literals to the left of the arrow are called conditions; and the literals to its right are called effects.

Intuitively, the meaning of an operation rule is simple. If the conditions of a rule are true in any state, then executing the action in the head requites that we execute the effects of the rule.

For example, the following rule states that in any state in which p(a,b) is true and q(a) is false, the executing click(a) requires that we remove p(a,b) from our dataset, add q(b), perform action click(b).

As with rules defining views, operation rules may contain variables to express information in a compact form. For example, we can write the following rule to generalize the preceding rule to all objects.

As with view rules, safety is a consideration. Safety in this case means that every variable among the effects of a rule or in negative conditions also appears in the head of the rule or in the positive conditions.

The operation rules shown above are both safe. However, the rules shown below are not. The second effect of the first rule contains a variable that does not appear in the head or in any positive condition. In the second rule, there is a variable that appears in a negative condition that does not appear in the head or in any positive condition.

In some operation rules there is no condition, i.e. the effects of the transition rule take place on all datasets. We can, of course, write such rules by using the condition true, as in the following example.

For the sake of simplicity in writing our examples, we sometimes abbreviate such rules by dropping the conditions and the transition operator and instead write just the effects of the transition as the body of the operation rule. For example, we can abbreviate the rule above as shown below.

An operation definition is a collection of operation rules in which the same operation appears in the head of every rule. As with view definitions, we are interested primarily in rulesets that are finite. However, in analyzing operation definitions, we occasionally talk about the set of all ground instances of the rules, and in some cases these sets are infinite.

11.3 Semantics

The semantics of operation definitions is more complicated than the semantics of updates due to the possible occurrence of views in the conditions of the rule and the possible occurrence of operations in its effects. In what follows, we first define the expansion of an action in the context of a given dataset, and we then define the result of performing that action on that dataset.

Suppose we are given a set Ω of rules, a set Γ of actions (factoids, negated factoids, and actions), and a dataset Δ. We say that an instance of a rule in Ω is active with respect to Γ and Δ if and only if the head of the rule is in Γ and the conditions of the rule are all true in Δ.

Given this notion, we define the expansion of action γ with respect to rule set Ω and dataset Δ as follows. Let Γ₀ be {γ} and let Γ_i+1 be the set of all effects in any instance of any rule in Ω with respect to Γ_i and Δ. We define our expansion U(γ,Ω,Δ) as the fixpoint of this series. Equivalently, it is the union of the sets Γ_i, for all non-negative integers i.

Next, we define the positive updates A(γ,Ω,Δ) to be the positive base factoids in U(γ,Ω,Δ). We define the negative updates D(γ,Ω,Δ) to be the set of all negative factoids in U(γ,Ω,Δ).

Finally, we define the result of applying an action γ to a dataset Δ as the result of removing the negative updates from Δ and adding the positive updates, i.e. the result is (Δ - D(γ,Ω,Δ)) ∪ A(γ,Ω,Δ).

11.4 Example - Graphs

To illustrate these definitions, consider an application with a dataset representing a directed acyclic graph. In the sentences below, we use symbols to designate the nodes of the graph, and we use the edge relation to designate the arcs of the graph.

The following operation definition defines a ternary operation copy that copies the outgoing arcs in the graph from its first argument to its second argument.

Given this operation definition and the dataset shown above, the expansion of copy(b,c) consists of the changes shown below. In this case, the factoids representing the two arcs emanating from b are all copied to c.

After executing this event, we end up with the following dataset.

The following rule defines a unary operation invert that reverses the incoming arcs of the node specified as it argument.

The expansion of invert(c) is shown below. In this case, the arguments in the factoid with c as second argument have all been reversed.

After executing this event, we end up with the following dataset.

Finally, the following operation rules define a binary operation that inserts a new node into the graph (the first argument) with an arc to the second argument and arcs to all of the nodes that are reachable from the second argument.

The expansion of insert(w,b) is shown below. The first rule adds edge(w,b) to the expansion. The second rule adds insert(w,d) and insert(w,e). Given these events, on the next round of expansion, the first rule adds edge(w,d) and edge(w,e) and the second rules adds insert(w,c). On the third round of expansion, we get edge(w,c). At this point, neither rule adds any additional items to our expansion, and the process terminates.

Applying this event to the preceding dataset produces the result shown below.

Note that it is possible to define insert in other ways. We could, for example, define a view of edge that relates each node to every node that can be reached from the node; and we could then use this view in a non-recursive definition of insert. However, this would require us to introduce a new view into our vocabulary; and, for many people, this is less clear than the definition shown above.

11.5 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.

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.

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

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.

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.

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.

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 11.1: For each of the following strings, say whether it is a syntactically legal operation definition.