Declarative Logic Programming. Michael Kifer

introduces updates via the assert and retract pseudo-predicates in rule bodies and the heads of those rules can be naturally viewed as subroutine calls. Invocation of these subroutines can result in side effects (such as updating the database) and these subroutines can be combined into bigger and bigger subroutines. Thus, Prolog fulfills the subroutining and compositionality requirement (desideratum 2). Despite the fact that it does not fulfill any other desiderata, there is a sense in which one can say that—by-and-large—Prolog got it right, and with the right semantics all the pieces would fall in place. That “right” semantics comes in the form of Transaction Logic [Bonner and Kifer 1993, Bonner and Kifer 1994], described shortly, but first we need to explain what is wrong with Prolog’s approach. To this end, consider the following Prolog program, which purports to color graph nodes so that no pair of adjacent nodes has the same color:

      At first look, everything seems fine: we pick a node that has not been colored yet and assign it a color that is different from that of all adjacent nodes. This process continues until everything gets colored. Problems start when, after a series of color assignments, the condition not (adjacent(N, N2), colored(N2, C)) cannot be satisfied by any color C for some still uncolored node N2. In this situation, colorNode fails and so does colorGraph, leading to two problems. One is that the graph remains partially colored (due to earlier, successful coloring steps), and this partial coloring cannot be extended to full coloring. The result is that the database is left in a “garbage” state. Second, there may be a way to color the graph, if the program picked the colors in a different order, but if this right order is not chosen the first time, then the program above would neither find a correct order nor leave the database in a coherent state.

      The problem with the example above is that the predicate assert in Prolog has no logical semantics—only a procedural one, and this semantics is hard to rely on. Even though superficially it might seem that Prolog subroutines are compositional, it is not so if updates are involved: two subroutines may be working correctly by themselves but not in combination. For instance,

      By itself, the transaction above will always work correctly and will never leave us in an incoherent state. However, combining this transaction with itself to make two transfers:

      may run into problems, if Acct1 has balance less than $300. Indeed, the first transfer may come through correctly, but the second will fail due to the check Bal1 > Amt in the second transfer. If the two transfers were supposed to be done together (e.g., the seller and the broker must both be paid) then we are left in an incoherent state.

      A popular solution to “fixing” Prolog’s update operators is provided by Transaction Logic [Bonner and Kifer 1993, Bonner and Kifer 1994]. The intuitive idea is to require that all subroutines must be transactional (whence “Transaction Logic”). This qualification means that colorGraph and the double-transfer above must be treated as transactions, and one of the key aspects of a transaction is its atomicity. Atomicity refers to the property that a transaction either executes in its entirety or not at all. If a successful execution exists then the updates performed during the transaction execution are committed and become visible. If a successful execution is not possible, all the intermediate updates are undone and the database is left in the original state—as if nothing happened at all. In case of the double-transfer above, if Bal1 is greater than $300 then the transaction succeeds and the amounts are transferred out of Acct1. Otherwise, the first or the second transfers will fail and the partial changes made to the database are undone. In case of graph coloring, the program will keep searching for a correct assignment of colors. If, at some point, the condition not (adjacent(N, N2), colored(N2, C)) cannot be satisfied, some previous color assignments will be undone and other assignments will be tried until either a correct assignment is found or all assignments have been tried and rejected. Practically, this trial-and-error is implemented through backtracking and so such transactional updates are sometimes called backtrackable.

      In brief, Transaction Logic extends the classical logic with one new connective, the serial conjunction, denoted ⊗. Further extensions (such as concurrency, hypothetical updates, defeasible updates) introduced additional connectives [Bonner and Kifer 1995, Bonner and Kifer 1996, Fodor and Kifer 2011]. The Transaction Logic version of the graph-coloring example above thus looks very similarly to Prolog:

      where tinsert is a transactional insert operator. The main difference with Prolog is, of course, the transactional semantics of the program above, which is defined by extending the standard model theory of first-order logic. Details can be found in Bonner and Kifer [1993, 1994, 1995].

      In summary, the original Transaction Logic takes care of the first two desiderata on our list. A follow-up work [Bonner et al. 1993] showed that this logic is good at modeling reactive systems (specifically, event-condition-action rules), thereby fulfilling desideratum 3. The use of this logic for reasoning about actions (desideratum 4) was discussed in Bonner and Kifer [1998b] and further significant developments in this direction appeared in Rezk and Kifer [2012]. Transaction Logic also has applications to planning and Web services [Basseda and Kifer 2015b, Basseda and Kifer 2015a, Basseda et al. 2014, Roman and Kifer 2007]. Parts of this logic have been implemented in the Flora-2 system [Kifer 2015, Yang et al. 2003] and a standalone interpreter is available.¹⁷

      Finally, we mention the approach in the updates-in-rule-body category used in LDL—one of the earliest Datalog systems [Naqvi and Krishnamurthy 1988, Naqvi and Tsur 1989]. Due to the problems with the non-declarative nature of Prolog’s update operators, this system restricts the syntactic forms of the rules in which update operators can appear. Although this requirement makes it possible to give a logical semantics to such rules, the restrictions themselves are severe. For instance, they prohibit recursion through updates as well as most post-conditions, which excludes both the graph-coloring and the double-transfer examples discussed earlier.

       1.5 Evaluation Techniques

      The intended uses of Datalog required rethinking the evaluation mechanisms used for Prolog and other logic-based question-answering systems. Because of the use of definite clauses, Prolog was able to base its query evaluation mechanism on SLD resolution, using depth-first search over the SLD tree based on the rules and facts. We illustrate this top-down approach later. While Prolog-style top-down evaluation worked reasonably for many cases, particularly those where the rules and facts fit in main memory, there were several considerations that dictated developing new techniques for Datalog.

      All derivations vs. all answers. Prolog and other logic programming approaches generally focused on finding a solution to a problem or deciding the truth of a statement. (Are X and Y related?) Top-down approaches can be efficient in such cases, because the sequence of rule applications is directed by the current goal, where bottom-up approaches can derive a lot of extraneous facts that are not connected to the goal. Datalog was targeting database settings, where a collection of answers is expected. (Who are all the people related to Y?) While Prolog-style top-down evaluation can generate multiple answers by backtracking to choice points, this process may be inefficient, because there can be more than one way to derive the same answer. (In deductive terms: there can be more than one proof for some facts.) For example, if persons A and B are related because of a common ancestor C, then their relatedness can also be deduced from any ancestor D of C. Moreover, with some rule sets, there can be more than one way to derive relatedness using C. If the number of derivations greatly exceeds the number of facts, Prologlike approaches can be inefficient for finding all answers. Datalog