Declarative Logic Programming. Michael Kifer

      as long as the advised is acyclic, meaning a goal can never depend negatively on itself.

      CORAL programs are structured into modules, where different optimizations and evaluation techniques are applied to different modules. CORAL offers a variety of program rewriting techniques, including Magic Templates [Ramakrishnan 1991] and variants. The programmer can annotate a module to indicate which kind of rewriting to use. Other annotations on a per-predicate basis can control aspects such as duplicate elimination, aggregate selection (for example, retain only minimum-cost paths), and prioritization of newly derived facts for use in further deductions. The evaluation technique can be selected on a per-module basis, as well. A CORAL module can be evaluated bottom-up, using semi-naïve evaluation, or top-down in “pipelined” fashion, which provides a cursor-like functionality to retrieve query answers, but does not retain derived results.

      CORAL supports persistent EDB data via either file storage or the EXODUS storage manager [Carey et al. 1986]. Data in files is loaded all at once when first accessed, whereas EXODUS can load pages of tuples incrementally.

       1.6.3 Glue-Nail

      Glue and Nail are a pair of set-oriented languages developed at Stanford University to work together cleanly [Derr et al. 1994]. Glue is a procedural language, whereas Nail is a declarative logic language originally developed as part of the NAIL! system [Morris et al. 1986]. Glue provides for control structures, update operations, and I/O. Its basic computation is a join operation, which can take any combination of stored relations, Glue procedures, and Nail predicates.

      Glue and Nail support structured terms, including literals and terms with variables in predicate and function names, an extension of HiLog syntax referred to as NailLog. Sets are handled differently than in the previous systems described. Rather than sets being a new kind of structured term, each set value is a predicate with a distinct name, parameterized by one or more values. So, for instance, to construct advisee sets as in an earlier example, we can use the Glue assignment statement

      One such set would be

      and the value advisees(lvk) can be passed around as a name for this extent. Glue also supports subgoals that compute aggregates over tuples defined by previous subgoals in an assignment statement.

      Both Glue and Nail are compiled into an intermediate language, IGlue, which can execute joins, tests and data movement. The Nail compiler uses two variants of Magic Sets, and decides which evaluation strategy to use at run time, which can be semi-naïve, stratified, or alternating fixpoint [Morishita 1993]. The Glue compiler analyzes the possible matches for each subgoal (which can be large because of the use of variables in predicate names), and limits the run-time tests to those predicates and procedures that could possibly match. There is also an IGlue-to-IGlue static optimizer that performs various data-flow analyses, including constant propagation. The optimizer also detects cases where a virtual relation can have at most one tuple, and provides a simpler data structure for that relation. The IGlue interpreter also has an optimizer for use at run time. The need for this component arises from the fact that during iterative computation (such as for a recursive predicate), the size of relations can change, hence the optimal execution plan for a join can change. The IGlue interpreter will therefore reoptimize a query if a relation’s cardinality changes by more than a factor of two up or down.

      The Glue-Nail systems keeps all data in main memory during execution, but reads EDB relations from disk initially, and writes query results back to disk.

       1.6.4 EKS

      EKS is a Knowledge-Base Management System (KBMS) initially developed at the European Computer-Industry Research Center (ECRC) and later transferred to commercial interests [Vieille et al. 1992]. EKS is callable from MegaLog, an extended Prolog system that provides efficient disk-based storage via BANG files, a data organization similar to grid files that support look up on multiple attributes [Freeston 1987].

      While EKS does not have complex terms, it does support negation and several other language features—the and and or connectives, aggregation, explicit quantifiers, evaluable predicates—that are translated into an extended Datalog. It supports general integrity constraints in the form of yes-no queries on base and virtual predicates that need to be satisfied if an update is to be allowed. For example, a constraint might require that the person and area mentioned in any thesis-fact have corresponding facts in the person and area tables:

      Constraints are supported via propagation rules and transactions. The propagation rules determine which facts actually have to be checked upon update. For example, deletion of a area-fact requires checking only for any thesis-facts that have that area. Transactions can roll back an update if any constraints are violated. The transaction capability supports other features, such as hypothetical reasoning in which “what-if” queries can be run over temporary updates.

      EKS rule compilation begins with determining an evaluation order on subgoals that satisfies any restrictions on binding patterns for the corresponding predicates. Such restrictions can arise from evaluable predicates, the use of negation, or virtual rules whose own rules induced binding restrictions. The rules are then translated into programs consisting of BANG operators—such as join, select, and difference—plus control constructs. These programs implement a breadth-first, top-down search of the rules, using the Query-Subquery approach to avoid solving the same goal repeatedly.

      As mentioned, EKS relies on BANG files for external storage. BANG files are designed to accommodate the need to look up facts (and clause heads in general) based on alternative combinations of attributes, since a predicate can occur with varying binding patterns.

      EKS was transferred to the French computer company Bull, and became the basis for the VALIDITY deductive object-oriented database [Vieille 1998]. VALIDITY became the property of Next Century Media, which used it to support targeted advertising.

       1.6.5 XSB

      The XSB Logic Programming System was developed by David S. Warren and his students at Stony Brook University in the early 1990s and is being constantly enhanced and extended to this day. It is a conservative extension of the Prolog programming language, by the addition of tables in which subgoal calls and answers are maintained to avoid redundant computation—an embodiment of the memoization strategy discussed in Section 1.5.2.1. In the context of a relational language, such as Prolog, where a single predicate (or procedure) call can have multiple (or no) answers, tabling changes the termination characteristics of the language, avoiding many infinite loops that are notorious in Prolog. With tabling, XSB is complete and terminating for Datalog programs [Chen and Warren 1996], and as such can be considered as an implementation of an in-memory deductive database system [Sagonas et al. 1994].

      Being an extension of Prolog, XSB can be used as a procedural programming language [Warren et al. 2007], just as Prolog. The programmer determines which predicates are to be tabled, either by explicitly declaring them to be tabled or by providing an auto_table directive telling the system to chose predicates to table. Thus, the programmer can use the Prolog language to provide the necessary procedural capabilities, such as loading files, generating output, and controlling query evaluation.

      XSB, as an extension of Prolog, includes function symbols and complex terms, including lists. Of course, termination is not guaranteed if the programmer uses them, but they provide programmers with the ability to program their own extensions. So programmers, for example, can use Prolog builtins, such as findall and setof, to collect lists of goal solutions and then use Prolog’s list-processing capabilities to compute arbitrary functions over those