This text illustrates the main issues and concepts behind deductive databases through the description of a real system. Both theory and practice combine to advance a pragmatic approach. The book covers all related topics from basic theory to its coupling with a known database management system and its implementation on a commerical multiprocessor. An overview describes the problems related to the field. In the introduction, basic tools and references to related work give the necessary background context. Chapter two slowly begins building the concepts that finally lead to the kern algorithm used throughout the book - mixed top-down, bottom-up computation. Upon completion of the book, the reader should be able to build a deductive database. Implementation problems are exposed and solved and new strategies and algorithms with their performance behaviour are presented. Additionally the reader should also learn the benefits and drawbacks of working with an existing database and the usefulness of a parallel machine.

Table of Contents:
Preface vii 1 The Logic-Based Approach to Knowledge Bases 1 1.1 Declarative Programming 1 1.2 Logic Programming 2 1.3 Knowledge-Based Systems 3 1.4 Modeling a Knowledge-Based System 4 1.5 Interfacing a Deductive Component to a Database 6 1.6 Controlling Recursive Inference 10 2 Mixed Top-Down, Bottom-Up Execution 11 2.1 A General Interpreter for Logic Programs 13 2.2 Reducing Horn Clauses 18 2.3 Architectural Aspects 32 2.4 The Unification Process 36 2.5 Variable Analysis 39 2.6 Performance Aspects 41 3 Structures 59 3.1 Handling Structures in the Inference Mechanism 60 3.2 Handling Structures in the Database 61 4 Recursion 73 4.1 General Breadth Search Strategy for Solving Recursive Clauses 74 4.2 Linear Horn Clauses without Function Symbols 76 4.3. Linear-Recursive Horn Clauses with Structured Arguments 92 4.4 Summary 108 5 Sharing Relations 111 5.1 The Trash Concept 112 5.2 Implementation Aspects 117 5.3 Deterministic Programs 122 54 Sharing Relations in the Presence of Recursive Clauses 124 6 Semantic Aspects 141 6.1 A Declarative Language and its I/O Restrictions 142 6.2 The Logical Cut 144 6.3 Negation 146 6.4 Built-in Predicates 148 7 Building a Deductive Database with a Relational DBMS 157 7.1 Ingres 158 7.2 Software Architecture 159 7.3 The EDB Stack 159 7.4 Recursion 166 8 Parallel Processing of Deductive Databases 175 8.1 Parallelizing Logic Programs 175 8.2 Implementation of OR parallelism 178 8.3 Analyzing Performance on a Sequent Symmetry 182 Appendix: IISProlog User's Manual 189 Glossary 251 References 253 Author Index 261 Subject Index 265