Declarative Logic Programming. Michael Kifer

Чтение книги онлайн.

      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 lists. XSB also provides a general aggregation capability, integrated with tables, that allows programmers to define their own aggregation operators to be applied to all answers of a query. These operators can be used in recursive rules to solve such problems as finding the length of the shortest path between a pair of nodes in a directed graph.

      XSB does minimal automatic query optimization. The general philosophy is to allow the programmer to control how the query is evaluated by determining how it is specified. This approach was inherited from XSB’s foundation in the Prolog programming language. XSB does include a few simple program transformations to improve indexing and to factor clauses to potentially reduce the polynomial complexity of some queries. But these optimizations must be explicitly invoked by the user. XSB also supports subsumptive tabling, which allows a table to be re-used if a proper instance of the original goal is encountered. This capability supports inserting a bottom-up component into the normal goal-directed computation of XSB. For example, for transitive closure, we could declare the predicate as subsumptively tabled, and then make the fully open call (i.e., where each argument is a distinct variable). In this case, there will be only one call that uses the clauses that match this predicate; every subsequent call is subsumed by that first call, and so it will suspend on the table associated with the initial open call, waiting for answers to show up that it can return. So the first answers must come from the base case, since only these answer do not require a recursive call. The next answers will come from a single use of the recursive call, and so on, simulating bottom-up computation.

      XSB does not directly provide much support for persistent data. Using Prolog, programmers can read and write files to define internal predicates. So the programmer can batch-load data files, or can read them incrementally. Some work explored evaluation-control strategies that would provide more efficient disk access patterns when accessing external data [Freire et al. 1997]. XSB also has a powerful ODBC interface to any relational database system,²⁰ so an XSB user has access to data persistence facilities.

       1.6.6 Other Systems

      Aditi was a deductive database project started in 1988 at the University of Melbourne [Vaghani et al. 1994]. Aditi-Prolog is a declarative variant of Prolog, which can be used to define predicates in the NU-Prolog system [Ramamohanarao et al. 1988]. Aditi can evaluate predicates bottom up (with optional parallelism) and in tuple-at-a-time top-down mode. Aditi provides different strategies to order literals in a clause during compilation, such as choosing the next subgoal to maximize bound variables or to minimize free variables. Aditi programs are translated to relational algebra programs, which are further optimized using programming-language and database techniques. Joins can be evaluated by several methods, which can take advantage of different tuple representations that Aditi supports. Parallelism is available both among different subgoals of a rule and among multiple rules for a predicate.

      DECLARE is the language for the Smart Data System (SDS) [Kießling et al. 1994] whose foundational work was done at the Technical University of Munich (TUM) and then continued at a research and development center during the period of 1986–1990. One of the main targets of SDS was decision making over heterogeneous data, hence it emphasizes connectivity to multiple data sources, both local and remote. DECLARE is a typed language using SQL types plus lists and supporting constraints. SDS provides distributed query processing, where evaluation plans can contain complex SQL queries executed by external systems. Also, the SDS developers were interested in search strategies beyond top-down and bottom-up techniques, in particular, using domain-specific knowledge. For example, in a rule for connecting flights, the intermediate city will generally be in the same geographic region as the source and destination cities.

      LOLA is another deductive database system from TUM [Freitag et al. 1992], which can access stored relations in external databases and predicates defined in Common Lisp. It supports type groups that collect terms into classes, such as airports and geographic regions. LOLA is translated to an intermediate language, from which it builds operator graphs that are optimized for subexpressions and indexing opportunities. These graphs are evaluated in R-Lisp, which implements an in-memory algebra for relations with complex objects. Some of the preprocessing routines are in fact written in LOLA itself.

      RDL is a production-rule system from INRIA [Kiernan et al. 1990]. It uses “if … then” rules with the consequent being a sequence of inserts, deletes, and updates of stored or virtual tables. We mention it here because unlike most production-rule systems, СКАЧАТЬ