passing, materialization, and memoization. Some methods support recursive predicates, and some can be used with intelligent backtracking. Intelligent backtracking detects cases where a join should not continue iterating from an earlier subgoal than it normally would. Consider the rule for the csInfo predicate from the initial example,
which is essentially a join of the thesis, person and area relations. Suppose we are currently considering the two rows
and fail to find any area row matching the goal
There is no reason to return to consider further person-rows, since the hw value comes from the thesis-row. The SALAD optimizer chooses among the joinprocessing options based on program requirements, as well as estimated costs and index availability. The LDL compiler can process a predicate differently depending on the binding pattern of a call. So, for example, for csInfo(b, b, f, f) (a call with the first two arguments bound and the last two free), it might choose to put person first in the join, whereas for csInfo(f, f, b, b), it might put person last in the join.
LDL++ [Arni et al. 2003] was an extension of LDL begun at MCC and completed at UCLA. LDL++ adds support for user-defined aggregates (UDAs), offering both forms that provide final results as well as versions that can return “online” results. For example, an aggregate for average might return the intermediate value after each group of 100 inputs has been examined. LDL++ also introduced a testable form of local stratification in which iterations of a predicate are explicitly indexed, and rules with negation must only use results available at a previous index.
LDL++ added access to external databases to SALAD’s internal main-memory database. LDL++ can create SQL calls to external sources that contain multiple goals, thus benefitting from the DBMS’s query optimizer.
1.6.2 CORAL
Ramakrishnan et al. [1994] developed the CORAL deductive system at the University of Wisconsin. To support imperative aspects, CORAL is “mutually embedding” with C++ code—that is, CORAL modules can be called from C++ and evaluable predicates for CORAL can be written in C++. In terms of Datalog extensions, CORAL supports structured terms in predicates and explicit multi-set values, with grouping capabilities similar to LDL sets. CORAL also provides functions, such as union and subset, to operate over multi-set values, and aggregation functions, such as sum and count, that can reduce a multi-set to a scalar. CORAL supports a generalized form of stratified negation where a predicate can depend negatively on itself, as long as no individual ground goal does. So, for example, if a predicate p can have a rule of the form
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
