Efficient bottom-up evaluation of logic programs. Raghu Ramakrishnan, Divesh Srivastava and S. Sudarshan. In recent years, much work has been directed towards evaluating logic programs and queries on deductive databases by using an iterative bottom-up fixpoint computation. The resulting techniques offer an attractive alternative to Prolog-style top-down evaluation in several situations. They are sound and complete for positive Horn clause programs, are well-suited to applications with large volumes of data (facts), and can support a variety of extensions to the standard logic programming paradigm. We present the basics of database query evaluation and logic programming evaluation, and then discuss bottom-up fixpoint evaluation. We discuss an approach based upon using a program transformation (``Magic Templates'') to restrict search, followed by fixpoint computation using a technique (``Semi-naive evaluation'') that avoids repeated inferences. The program transformation technique focuses the fixpoint evaluation, which is a forward-chaining strategy, by propagating bindings in the goal in a manner that essentially mimics the backward-chaining behavior of top-down evaluation strategies. After presenting the basic framework for bottom-up evaluation, we discuss several refinements that optimize the treatment of non-ground terms, improve memory utilization, reduce the cost of duplicate checking, and utilize the declarative semantics of the program to perform semantic query optimization in a number of ways. We also consider several extensions to the logic programming paradigm, and discuss how the bottom-up evaluation framework can be used to support these extensions. The extensions include support for negation, set-terms, constraint manipulation and quantitative reasoning. Finally, we discuss several systems based upon bottom-up evaluation, including Aditi (Univ. of Melbourne), EKS-V1 (ECRC-Munich), Glue/NAIL! (Stanford Univ.) and LDL (MCC-Austin). We have developed such a system, called CORAL, and we present this in more detail.