Declarative Logic Programming. Michael KiferЧитать онлайн книгу.
reactivity has been identified as an important paradigm in building large systems. Reactive rules, which usually come in the form of event-condition-action rules (or ECA rules), are a natural adaptation of this paradigm to declarative languages. In SQL, for example, this idea is realized through triggers. Prolog, on the other hand, does not have explicit support for this paradigm, but it can be simulated.
4. Reasoning about actions. If a robot picks up a block from the top of another block, will the top of that other block become clear in the next state? It seems like an obvious question, but can this statement be proven within the same logical language that is being used to specify the states of such a “blocks world” and the actions of a robot in it? Most of the approaches surveyed here do not support such reasoning.
We will now briefly survey the three aforementioned categories of approaches to updates and discuss them vis-à-vis the above desiderata.
1.4.8.1 Approaches Based on Explicit State Identifiers
The oldest and best-known approach in this category is the situation calculus [McCarthy and Hayes 1969], which is still widely used for reasoning about actions, albeit not in Datalog or other logic-programming languages.
The idea is to use one designated argument of each state-dependent predicate to hold a state identifier. For instance, if the initial state is denoted s0 then the state obtained by picking up block a in state s0 and then putting that block down on top of block b would be represented as do(putdown(a, b), do(pickup(a), s0)). Thus, the state identifier reflects the history of actions that brought about that state. The effects of the various actions are specified via logical formulas. For instance, in the following example, the designated state argument is the last one:
This formula says that if in state S block a is on some block X and it is possible to execute the action of picking up a, then in the new state, denoted do(pickup(a), S), block X would be clear and the robot would be holding block a.
One of the issues with situation calculus and the other approaches that rely on state identifiers is the frame problem. To understand the issue, consider the example above. The rule that specifies the effects of the pickup action deals with the direct effects of that action, but it says nothing about what did not change. Indeed, suppose that in state s0 we had on(d, e, s0). Intuitively, picking up block a should not affect the fact that block d is sitting on top of block e, so we would expect that on(d, e, do(pickup(a), s0)) is true. However, there is no way to derive this fact given the rules above. The missing piece of the puzzle can be provided using frame axioms, which state that the facts that are not directly affected by an action remain true in the state resulting from that action.
There are two problems with frame axioms. The first is that the number of such axioms can be large. The original solution [Green 1969] required a quadratic number of frame axioms (predicates × actions). A more feasible solution, which required only one frame axiom, was presented by Kowalski and Sergot [1986]. It was well received by database and logic programming communities, but not by some AI researchers because that solution relied on the closed-world assumption, which goes beyond first-order logic. A purely first-order logic solution, requiring a linear number of frame axioms, was later proposed by Reiter [1991]. The other problem with frame axioms is that, as the system evolves, inference can slow down significantly. For instance, after 10,000 actions, finding out what is true in the current state might require a 10,000-element chain of inferences via the frame axioms.
With respect to the desiderata stated earlier, situation calculus scores well on the first and the fourth criteria (declarativeness and reasoning), but it does not do well when it comes to the second and third criteria. Among the other approaches that rely on state identifiers [Chomicki 1990, Kowalski and Sergot 1986, Lausen and Ludäscher 1995, Zaniolo 1993], the event calculus [Kowalski and Sergot 1986] is the best-known one. Unlike the situation calculus, these approaches use time (continuous or discrete) as a state identifier and they rely on the closed-world assumption to specify the frame axioms, which greatly reduces the number of such axioms. Apart from that, they suffer from some of the same limitations as the situation calculus but score well on the first and the fourth desiderata. Here is an example expressed in the event calculus:
The first rule here says that an event of picking up a block initiates the states in which the robot holds that block. The second rule says that an event of putting down a block terminates such state sequences. The third rule does not depend on the domain of discourse. It says that a fact holds at a certain time if that fact was initiated at some prior time and was not terminated between the initiation time and the time under consideration.
1.4.8.2 Destructive Updates in Rule Heads
The most prominent representatives of this category of systems are SQL triggers [Zaniolo et al. 1997] and production-rule (or business-rule) systems [Agrawal et al. 1991, de Sainte Marie et al. 2013, Snyder and Schmolze 1996], which are based on the event-condition-action paradigm. An event-condition-action rule (ECA rule) is a statement of the form
which means that if an event E occurs (usually some kind of a database state change) and if precondition C of the rule is satisfied, then perform action A. This action corresponds to what one would call a “rule head” in logic. An action can be complex and affect many database objects, such as “increase the salary of all administrators by 5%.” Much more needs to be said in order to make this statement precise, however.
1. Several ECA rules may find their preconditions satisfied after the event E. Should only one of these rules fire (that is, has its action executed) or all?
(a) If one, then which one?
(b) If all, then sequentially (in which order, if so?) or all at once?
(c) If sequentially, should the condition C be retested after each rule firing? (Firing of a rule may mean the preconditions of some other rules may no longer be satisfied, while other, previously ineligible, rules might suddenly find that their preconditions are now satisfied.)
2. If a rule fires and the database gets updated as a result, can this update event trigger execution of other ECA rules?
3. If an event involves several updates to the database, should ECA rules attempt to fire right after each update or they must wait until all the updates associated with the event are committed?
4. Can rule firing continue indefinitely? How does one ensure termination?
In addition to database triggers and production rules, many other approaches were developed [Abiteboul and Vianu 1990, Alferes et al. 2002, Kowalski and Sadri 2012]. The differences among them essentially boils down to the answers to the questions above and to the details of the preconditions and actions, such as can an action change multiple database objects? For example, how does one ensure that the same employee has his salary changed at most once and not repeatedly?
With respect to our classification dimensions discussed at the beginning of this section, updates in rule heads are good for representing reactive systems (desideratum 3) but hardly anything else.16 Their semantics is usually described as a series of applications of various state-changing operators, which often gets quite involved (depending on the choices made in deciding which ECA rules fire, when, and so forth), and they can hardly be regarded as declarative.
1.4.8.3 Destructive Updates in Rule Bodies