## 5.1 IntroductionIn our discussion thus far, we have been talking about the use of datasets and logic programs and deductive databases to describe individual states of the world. In many application areas, it is necessary to describe not just individual states but also transitions between states. Dynamic logic programs provide a means for us to describe such changes. In what follows, we first introduce the notion of a transition rule. We then show how transition rules can be used to describe the dynamics of closed systems (where the system changes state on its own); and then we describe how transition rules can be used in describing the dynamics of open systems (where the system's behavior changes in response to external stimuli). We then discuss the trade-offs between differential update and whole-state update. And we conclude by comparing transition rules to situation calculus, a popular alternative to formalizing the behavior of dynamic systems. ## 5.2 Transition RulesThe language of dynamic logic programming is a superset of the language of ordinary logic programing. Every ordinary logic program is also a dynamic logic program. As in ordinary logic programming, we can write ground atoms and view definitions. However, in dynamic logic programming, we can also write "transition rules", which encode information about how the state of the world changes (over time or in response to external stimuli). A transition rule is an expression of the form shown below. Each rule consists of (1) a literal (an atom or a negation of an atom) or a conjunction of literals, (2) a double shafted forward arrow, and (3) a literal or a conjunction of literals. The literals on the left are called
Intuitively, the meaning of a transition rule is simple. If the conditions of a rule are true in any state, then the effects must be true in the For example, the following rule expresses the fact that, when p(a) is true and q(a) is false, then p(a) becomes false and q(a) becomes true in the next state.
As with view definitions, the conditions and effects of rules may contain variables to express dynamic information in a compact form. For example, we can write the following rule to express the fact that the preceding transition rule holds for all objects.
As with view definitions, transition rules are required to be The transition rule rules shown above are all safe. However, the rules shown below are not. The effect of the first rule contains a variable that does not appear in any condition. In the second rule, there is a variable that appears in a negative condition that does not appear in any positive condition.
If we were to allow the first of these rules, the resulting dataset might contain infinitely many effects (all the instances of the rule's effect). If we were to allow the second rule, we might have to check infinitely many conditions (all of the instances of the negated condition). A dynamic logic program (DLP) is simply a collection of view definitions and transition rules. As with ordinary logic programs, we are interested primarily in dynamic logic programs that are finite. However, in analyzing dynamic logic programs, we occasionally talk about infinite DLPs, e.g. the set of all ground instances of the rules. ## 5.3 Closed SystemsA deterministic closed dynamic system is one that operates without external input, changing from one state to the next in a deterministic fashion. These are sometimes called closed systems or Markov systems. Note that, in addition to deterministic closed dynamic systems, there are also Transition rules are an effective way of describing the behavior of closed systems. As an example, consider a simple dynamic system like the one shown below There are three conditions that can hold in a state - p, q, and r - meaning that the system has a total of eight possible states. The The following transition rules express the behavior of this system. Given any state in which p is true, p becomes false in the next state; and vice versa. If p is true in a state, then q becomes true in the next state. If p and q are true in a state, then r becomes true in the next state; otherwise it becomes false.
This, of course, is a very simple closed system. There are many examples of closed systems in the real world. In fact, the universe as a whole can be viewed as a closed system (though there are some who would argue that it is really a non-deterministic closed system). The following section describes an class of more complex closed systems that exhibit interesting behavior. ## 5.4 Example - The Game of LifeThe Game of Life is a cellular automaton devised by the British mathematician John Conway in 1970. The universe of the game is a two-dimensional orthogonal grid of square cells, each of which is in one of two possible states - alive (shown in black) or dead (shown in white). Every cell interacts with its eight neighbors, which are the cells that are horizontally, vertically, or diagonally adjacent. On each step, the next state is determined by applying the following rules. - Any live cell with fewer than two live neighbors dies, as if caused by underpopulation.
- Any live cell with two or three live neighbors lives on to the next generation.
- Any live cell with more than three live neighbors dies, as if by overpopulation.
- Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
Press Play to allow the system to operate on its own. Press Pause to pause operation. Press Step to advance one step.
Changing the initial state of the system can change the way the system evolves. In some cases, the system reaches quiescence, i.e. nothing changes from step to step. In some cases, the system oscillates. With an infinite universe, it is possible for a system to run forever without repeating any state. With the game paused, create a new state by clicking cells to toggle their statuses between live and dead. Once you are done, click Play to see what happens with your new state. Reload the page to return to the initial state. Now, let's see how we can describe this system using transition rules. Of course, we must also define the concepts used in these transition rules. Finally, we need some base data. ## 5.5 Open SystemsAn open dynamic system is one in which state changes depend not only on the current state of the system but also on inputs from the system's external environment. The most common example of such inputs are actions performed by one or more agents operating on the system. As an example, consider a variation on the closed system describe in Section 2. Again, the state of the system is based on three conditions p, q, and r. However, in this variation, the behavior of the system is determined not just by the current state but also by the actions on an external agent. In the version shown here, the agent has three possible actions - a, b, and c. Doing action a toggles p; doing action b interchanges p and q; and doing action r interchanges q and r. We can described the behavior of this simple system with the transition rules shown below.
Note that, if the system started in a state in which all three conditions were false, it could achieve a state in which they are true by executing the action sequence a, b, c, a, b, a. Can you think of a different sequence of actions that would do the trick? How many sequences are there that produce the desired state? ## 5.6 Example - Blocks WorldAs a more complex example of an open system, once again consider the Blocks World introduced in Chapter 3. 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.
## 5.7 Example - DatabasesIn updating a database, a user specifies a sentence to add to a database or a sentences to delete. In some cases, the user can group several changes of this sort in a single, so-called, Unfortunately, if a user forgets to include an addition or deletion required by the constraints, this can lead to errors. In order to simplify the update process for the user, some database systems provide the administrator the ability to write update rules, i.e. rules that are executed by the system to augment a specified transaction with the additions and deletions necessary to avoid errors. In what follows, we show one way that this can be done with transition rules. Our update language includes two new operators - pluss and minus. pluss takes an atom as argument and is true in a state if and only if the
As an example of this mechanism in action, consider the rules shown below. The first directs the system to remove a sentence of the form
Similarly, we can enforce the inclusion dependency on
Another use of this update mechanism is to maintain materialized views. (A Suppose, for example, we were to materialize the
Note that not all constraints can be enforced using update rules. For example, if a user suggests adding the sentence ## ExercisesExercise 5.1: The transition rules for the Buttons and Lights World in Section 5.3 assume that just one action is performed at a time. Find a situation in which the rules will give an incorrect update if multiple actions are performed at the same time. Write transition rules that correctly update the database for any combination of actions. Exercise 5.2: Consider the game of life presented in Section 5.4. The state in which all cells are dead is stable in that it does not change from one step to the next. Find another state in which the world is stable. Exercise 5.3: Consider the game of life presented in Section 5.4. The initial state shown in that section eventually reaches a point at which the world oscillates between two different states. Find a different state in which the world oscillates between two different states. Exercise 5.4: Consider the Blocks World described in Section 5.6, and imagine an action |