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