Logic Programming and Databases

1 Logic Programming and Databases: An Overview.- 1.1 Logic Programming as Query Language.- 1.2 Prolog and Datalog.- 1.3 Alternative Architectures.- 1.4 Applications.- 1.5 Bibliographic Notes.- 2 A Review of Relational Databases and Prolog.- 2.1 Overview of Relational Databases.- 2.1.1 The Relational Model.- 2.1.2 Relational Languages.- 2.2 Prolog: A Language for Programming in Logic.- 2.3 Bibliographic Notes.- I Coupling Prolog to Relational Databases.- 3 Prolog as a Query Language.- 3.1 The Anti-Trust Control Problem.- 3.2 The Bill of Materials Problem.- 3.3 Conclusions.- 3.4 Bibliographic Notes.- 3.5 Exercises.- 4 Coupling Prolog Systems to Relational Databases.- 4.1 Architectures for Coupling Prolog and Relational Systems.- 4.1.1 Assumptions and Terminology.- 4.1.2 Components of a CPR System.- 4.1.3 Architecture of CPR Systems.- 4.2 Base Conjunctions.- 4.2.1 Determining Base Conjunctions in LCPR Systems.- 4.2.2 Improving Base Conjunctions in TCPR Systems.- 4.3 Optimization of the Prolog/Database Interface.- 4.3.1 Caching of Data.- 4.3.2 Caching of Data and Queries.- 4.3.3 Use of Subsumption.- 4.3.4 Caching Queries.- 4.3.5 Parallelism and Pre-fetching in Database Interfaces.- 4.4 Conclusions.- 4.5 Bibliographic Notes.- 4.6 Exercises.- 5 Overview of Systems for Coupling Prolog to Relational Databases.- 5.1 PRO-SQL.- 5.2 EDUCE.- 5.3 ESTEAM.- 5.4 BERMUDA.- 5.5 CGW and PRIMO.- 5.6 QUINTUS-PROLOG.- 5.7 Bibliographic Notes.- II Foundations of Datalog.- 6 Syntax and Semantics of Datalog.- 6.1 Basic Definitions and Assumptions.- 6.1.1 Alphabets, Terms, and Clauses.- 6.1.2 Extensional Databases and Datalog Programs.- 6.1.3 Substitutions, Subsumption, and Unification.- 6.2 The Model Theory of Datalog.- 6.2.1 Possible Worlds, Truth, and Herbrand Interpretations.- 6.2.2 The Least Herbrand Model.- 6.3 Conclusions.- 6.4 Bibliographic Notes.- 6.5 Exercises.- 7 Proof Theory and Evaluation Paradigms of Datalog.- 7.1 The Proof Theory of Datalog.- 7.1.1 Fact Inference.- 7.1.2 Soundness and Completeness of the Inference Rule EP.- 7.2 Least Fixpoint Iteration.- 7.2.1 Basic Results of Fixpoint Theory.- 7.2.2 Least Fixpoints and Datalog Programs.- 7.3 Backward Chaining and Resolution.- 7.3.1 The Principle of Backward Chaining.- 7.3.2 Resolution.- 7.4 Conclusions.- 7.5 Bibliographic Notes.- 7.6 Exercises.- III Optimization Methods for Datalog.- 8 Classification of Optimization Methods for Datalog.- 8.1 Criteria for the Classification of Optimization Methods.- 8.1.1 Formalism.- 8.1.2 Search Strategy.- 8.1.3 Objectives of Optimization Methods.- 8.1.4 Type of Information Considered.- 8.2 Classification of Optimization Methods.- 8.3 Translation of Datalog into Relational Algebra.- 8.4 Classification of Datalog Rules.- 8.5 The Expressive Power of Datalog.- 8.6 Bibliographic Notes.- 8.7 Exercises.- 9 Evaluation Methods.- 9.1 Bottom-up Evaluation.- 9.1.1 Algebraic Naive Evaluation.- 9.1.2 Semi-naive Evaluation.- 9.1.3 The Method of Henschen and Naqvi.- 9.2 Top-down Evaluation.- 9.2.1 Query-Subquery.- 9.2.2 The RQA/FQI Method.- 9.3 Bibliographic Notes.- 9.4 Exercises.- 10 Rewriting Methods.- 10.1 Logical Rewriting Methods.- 10.1.1 Magic Sets.- 10.1.2 The Counting Method.- 10.1.3 The Static Filtering Method.- 10.1.4 Semi-naive Evaluation by Rewriting.- 10.2 Rewriting of Algebraic Systems.- 10.2.1 Reduction to Union-Join Normal Form.- 10.2.2 Determination of Common Subexpressions.- 10.2.3 Query Subsetting and Strong Components.- 10.2.4 Marking of Variables.- 10.2.5 Reduction of Variables.- 10.2.6 Reduction of Constants.- 10.2.7 Summary of the Algebraic Approach.- 10.3 A General View of Optimization.- 10.4 Bibliographic Notes.- 10.5 Exercises.- 11 Extensions of Pure Datalog.- 11.1 Using Built-in Predicates in Datalog.- 11.2 Incorporating Negation into Datalog.- 11.2.1 Negation and the Closed World Assumption.- 11.2.2 Stratified Datalog.- 11.2.3 Perfect Models and Local Stratification.- 11.2.4 Inflationary Semantics and Expressive Power.- 11.3 Representation and Manipulation of Complex Objects.- 11.3.1 Basic Features of LDL.- 11.3.2 Semantics of Admissible LDL Programs.- 11.3.3 Data Models for Complex Objects.- 11.4 Conclusions.- 11.5 Bibliographic Notes.- 11.6 Exercises.- 12 Overview of Research Prototypes for Integrating Relational Databases and Logic Programming.- 12.1 The LDL Project.- 12.2 The NAIL! Project.- 12.3 The POSTGRES Project.- 12.4 The FIFTH GENERATION Project.- 12.5 The KIWI Project.- 12.6 The ALGRES Project.- 12.7 The PRISMA Project.- 12.8 Bibliographic Notes.