On the implementation of data intensive logic programs
Raghu Ramakrishnan · 1987
The problem of efficiently implementing recursive database queries expressed as logic programs has received much attention. This has been motivated by a desire to extend the query language of a relational database to a general purpose language. This is a necessary step in the evolution of knowledge bases, which are sophisticated databases providing support for expert system applications. Databases typically contain gigabytes of facts and organize this data carefully in order to optimize relational operations such as the join. Top-down resolution based strategies (for example, Prolog) do not use this data organization effectively. Further, top-down strategies suffer from the fact that their implementations, for efficiency reasons, are usually incomplete, and so they do not realize the declarative semantics of logic programming. Thus, alternative methods which are complete are also of interest in the context of a general purpose logic programming language. Several approaches based on bottom-up evaluation have been proposed to deal with these problems. However, the criticism of bottom-up methods has been that they generally do not succeed in restricting the computation by utilizing information in the query. We examine these evaluation methods and identify a common factor, sideways information passing, that is used to restrict computation. This provides a framework in terms of which various evaluation methods can be compared. We define this notion formally, and use it to generalize a family of bottom-up evaluation methods proposed in the literature. We also treat rules that extend Horn Clause logic programs with layered negation and set generation. Our results show that bottom-up methods can implement any sideways information passing strategy, and thus answer the chief criticism of them. The issues of choosing an information passing strategy and an evaluation method for a given query require an understanding of performance measures. While we have no conclusive answers, we make an important first step with a performance analysis that examines several evaluation methods over a range of workloads. Finally, we examine the important issue of safety, that is, whether a query has a finite set of answers.