4.1 Introduction

In the preceding chapter, we saw how to write rules to define view relations in terms of base relations. Once defined, we can use these views in queries and in the definitions of other views. In this chapter, we look at how to write rules that define operations as 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.

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

4.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(γ,Ω,Δ).

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

4.5 Example - Blocks World

Recall the Blocks World introduced earlier. One state of the Blocks World is shown below. Here block C is on block A, block A is on block B, and block D is on block E.

Now, let's consider a dynamic variation of this world, one in which there is a robot that can modify the state of the world by performing various actions. For example, if a block is clear and on another block, the robot can unstack the block and place it on the table. If a block is clear and on the table and there is another block that is clear, the robot can pick up the first block and stack it on the second block.

As in our earlier formalization, we name our blocks with five symbols (a, b, c, d, e), with one symbol for each of the five blocks in the scene. And once again, we use various predicates to describe the state of our world. We use the binary predicate on to express the fact that one block in directly on another. We use the unary predicate clear to a block has no other blocks on top of it. We use the unary predicate table to state that a block is resting on the table.

In order to talk about events, we using the constant u to refer to the act of removing one block from another, and we use the constant s to refer to the act of stacking one block on another.

Using this vocabulary, we can describe the effects of these actions using the operation definitions shown below. If the robot attempts to unstack one block from another and the first block is clear and the first block is resting on the second block, then in the next state, the first block is no longer on the second, the first block is on the table, and the second block is clear. If, on the other hand, the robot attempts to stack one block on another and the first block is on the table and clear and the second block is clear, then afterward the first block is no longer on the table, the second block is no longer clear, and the first block is resting on the second block.

Note that, if any of the conditions is not true, these operation definitions by themselves do not say what happens. For example, if the user attempts to stack one block on another and one of the blocks is not clear, neither rule applies; and, in the absence of additional rules, the semantics of operation definitions implies that the state remains unchanged. In the real world, we might have a different result. For example, trying to perform a stacking action in this case might result in disaster, with all of the blocks scattered across the table. In order to deal with such contingencies, we would need to write additional rules.

4.6 Example - Tic Tac Toe

Tic Tac Toe (or Noughts and Crosses, Xs and Os) is a game for two players who take turns placing their marks in a 3x3 grid. The first player to place three of his marks in a horizontal, vertical, or diagonal row wins the game. The figure below shows one state of play in Tic Tac Toe.

In our definition of Tic Tac Toe, states are characterized by the contents of the cells on the Tic Tac Toe board and control (whose turn it is to play). (It is true that control can be defined in terms of the contents of cells; but making control explicit costs little and simplifies the description.) In what follows, we use the ternary relation constant cell together with a row m and a column n and a mark w to designate the fact that the cell in row m and column n contains w where w is either an x or an o or a b (for blank). We use the unary relation constant control to state that it is that role's turn to mark a cell. The dataset shown below uses this vocabulary to characterize the game state show above.

    cell(1,1,x)
    cell(1,2,o)
    cell(1,3,b)
    cell(2,1,b)
    cell(2,2,x)
    cell(2,3,o)
    cell(3,1,b)
    cell(3,2,b)
    cell(3,3,b)
    control(x)

Our first step is to define legality of moves. A player may mark a cell if that cell is blank. Otherwise, it has no legal actions.

    legal(M,N) :- cell(M,N,b)

    mark(M,N) :: control(Z) ==> ~cell(M,N,b) & cell(M,N,Z)
    mark(M,N) :: control(x) ==> ~control(x) & control(o)
    mark(M,N) :: control(o) ==> ~control(o) & control(x)

Finally, to complete our game description, we define some properties of game states - rows, columns, diagonals, lines - and we must say when the game terminates.

A row of marks mean that there are three marks all with the same first coordinate. The column and diagonal relations are defined analogously.

    row(M,Z) :- cell(M,1,Z) & cell(M,2,Z) & cell(M,3,Z)
    column(M,Z) :- cell(1,N,Z) & cell(2,N,Z) & cell(3,N,Z)
    diagonal(Z) :- cell(1,1,Z) & cell(2,2,Z) & cell(3,3,Z)
    diagonal(Z) :- cell(1,3,Z) & cell(2,2,Z) & cell(3,1,Z)

A line is a row of marks of the same type or a column or a diagonal.

    line(Z) :- row(M,Z)
    line(Z) :- column(M,Z)
    line(Z) :- diagonal(Z)

A game is over whenever either player has a line of marks of the appropriate type or if there are no cells containing blanks. We use the expression [M,N] here to specify that the countofall aggregate ranges over all pairs of rows and columns.

    terminal :- line(x)
    terminal :- line(o)
    terminal :- evaluate(countofall([M,N],cell(M,N,b)),0)

Our rules specify the states and physics of the game. They do not specify how to play the game effectively. In order to decide this, a player needs to consider the effects of his legal moves in order to decide a course of action that will lead to a line of his marks while considering the possible moves of the other player.

Exercises

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