Skip to main content
main-content

Über dieses Buch

The topic of logic programming and databases. has gained in­ creasing interest in recent years. Several events have marked the rapid evolution of this field: the selection, by the Japanese Fifth Generation Project, of Prolog and of the relational data model as the basis for the development of new machine archi­ tectures; the focusing of research in database theory on logic queries and on recursive query processing; and the pragmatic, application-oriented development of expert database systems and of knowledge-base systems. As a result, an enormous amount of work has been produced in the recent literature, coupled with the spontaneous growth of several advanced projects in this area. The goal of this book is to present a systematic overview of a rapidly evolving discipline, which is presently not described with the same approach in other books. We intend to introduce stu­ dents and researchers to this new discipline; thus we use a plain, tutorial style, and complement the description of algorithms with examples and exercises. We attempt to achieve a balance be­ tween theoretical foundations and technological issues; thus we present a careful introduction to the new language Datalog, but we also focus on the efficient interfacing of logic programming formalisms (such as Prolog and Datalog) with large databases.

Inhaltsverzeichnis

Frontmatter

Logic Programming and Databases: An Overview

Chapter 1. Logic Programming and Databases: An Overview

Abstract
This book deals with the integration of logic programming and databases to generate new types of systems, which extend the frontiers of computer science in an important direction and fulfil the needs of new applications. Several names are used to describe these systems:
a)
The term deductive database highlights the ability to use a logic programming style for expressing deductions concerning the content of a database.
 
b)
The term knowledge base management system (KBMS) highlights the ability to manage (complex) knowledge instead of (simple) data.
 
c)
The term expert database system highlights the ability to use expertise in a particular application domain to solve classes of problems, but having access over a large database.
 
Stefano Ceri, Georg Gottlob, Letizia Tanca

A Review of Relational Databases and Prolog

Chapter 2. A Review of Relational Databases and Prolog

Abstract
This chapter provides an overview of the prerequisite notions that are required in order to understand this book. The reader who has a background in these topics can skip this chapter or part of it, perhaps after taking a look at the notation.
Stefano Ceri, Georg Gottlob, Letizia Tanca

Coupling Prolog to Relational Databases

Frontmatter

Chapter 3. Prolog as a Query Language

Abstract
In Chap. 1 we provided an overview of the main reasons for the integration of database and logic programming technologies, and we established a comparison between the main features of relational databases and logic programming languages. Here we will just recall some important aspects of Prolog as a query language; these features essentially enrich the expressive power of classical query languages based on relational algebra or calculus.
Stefano Ceri, Georg Gottlob, Letizia Tanca

Chapter 4. Coupling Prolog Systems to Relational Databases

Abstract
In Chap. 3 we have seen that Prolog is a very expressive query language, one that can express queries with no counterpart in relational languages such as algebra or calculus. In this chapter, we describe how it is possible to build systems that interface Prolog to databases, providing efficient data access.
Stefano Ceri, Georg Gottlob, Letizia Tanca

Chapter 5. Overview of Systems for Coupling Prolog to Relational Databases

Abstract
This chapter presents an overview of some of the CPR systems and prototypes which have been developed for coupling Prolog to relational databases. We present:
a)
PRO-SQL, a system for coupling Prolog to the system SQL/DS, developed at the IBM Research Center at Yorktown Heights.
 
b)
EDUCE, a system for coupling Prolog to the database system Ingres, developed at the European Computer Industry Research Center in Munich.
 
c)
The ESTEAM interface, developed in the framework of the Esprit Project ESTEAM, for coupling generic Prolog and database systems
 
d)
BERMUDA, a prototype developed at the University of Winsconsin, for coupling Prolog to the Britton-Lee Intelligent Database Machine IDM 500.
 
e)
CGW, an architecture for coupling Prolog to a database system developed at Stanford University, and PRIMO, a prototype of an interface between ARITYPROLOG and the database system ORACLE, developed at the University of Modena, Italy.
 
f)
The QUINTUS interface between QUINTUS-PROLOG and the Unify Database System, a product developed by Quintus Computer Systems of Mountain View, California.
 
Stefano Ceri, Georg Gottlob, Letizia Tanca

Foundations of Datalog

Frontmatter

Chapter 6. Syntax and Semantics of Datalog

Abstract
In this chapter we give an exact syntactic and semantic definition of the Datalog query language.
Stefano Ceri, Georg Gottlob, Letizia Tanca

Chapter 7. Proof Theory and Evaluation Paradigms of Datalog

Abstract
The aim of this chapter is to show how the answer to a Datalog program can be computed. In order to achieve a computational approach to Datalog, in Sect. 7.1 we develop the proof theory of this language. We show how new facts can be inferred from an extensional database by use of a Datalog program. We then demonstrate that our proof-theoretic method is sound and complete, i.e., that it computes exactly what it should according to the model-theoretic semantics of Datalog. The proof theory of Datalog leads to a first algorithm “INFER” for processing Datalog programs. This algorithm iteratively computes new facts from facts that have already been established by using a forward chaining technique.
Stefano Ceri, Georg Gottlob, Letizia Tanca

Optimization Methods for Datalog

Frontmatter

Chapter 8. Classification of Optimization Methods for Datalog

Abstract
In this chapter, we provide a classification of optimization methods for evaluating Datalog goals. We use orthogonal classification criteria in order to identify various classes of methods; then, each class will be dealt with in a separate section. A systematic overview of methods is required, since optimization can be achieved using a variety of techniques, and understanding their relationships is not obvious.
Stefano Ceri, Georg Gottlob, Letizia Tanca

Chapter 9. Evaluation Methods

Abstract
In this chapter, we present methods for evaluating a Datalog program, namely, for generating the actual set of tuples which satisfy a given user’s goal for a given set of Datalog rules. We deal with bottom-up and top-down evaluation methods in two separate sections. Evaluation methods are expressed using either of the logic and algebraic formalisms introduced in the previous chapter, and in fact we do not stress the choice of formalism very much, given the equivalence between them.
Stefano Ceri, Georg Gottlob, Letizia Tanca

Chapter 10. Rewriting Methods

Abstract
In this chapter we introduce a number of rewriting methods for Datalog programs. Section 10.1 presents rewriting methods that apply directly to Datalog programs: the Magic Sets, Counting, Static Filtering and Semi-naive Evaluation by Rewriting. Section 10.2 presents a structured approach to the optimization of algebraic systems; it consists of a number of preliminary steps, after which the optimization methods of reduction of variables and reduction of constants are applied.
Stefano Ceri, Georg Gottlob, Letizia Tanca

Chapter 11. Extensions of Pure Datalog

Abstract
The Datalog syntax we have been considering so far corresponds to a very restricted subset of first order logic and is often referred to as pure Datalog. Several extensions of pure Datalog have been proposed in the literature or are currently under investigation.
Stefano Ceri, Georg Gottlob, Letizia Tanca

Chapter 12. Overview of Research Prototypes for Integrating Relational Databases and Logic Programming

Abstract
This chapter presents an overview of some of the research prototypes which are under development for the integration of relational databases and logic programming. We present:
a)
The LDL project, under development at Microelectronics and Computer Technology Corporation (MCC) at Austin, Texas. The project’s goal is to implement an integrated system for processing queries in Logic Data Language (LDL), a language which extends Datalog.
 
b)
The NAIL! project·(Not Another Implementation of Logic!), under development at Stanford University with the support of NSF and IBM. NAIL! processes queries in Datalog, but interfaces a conventional SQL database system (running on IBM PC/RT).
 
c)
The POSTGRES system, under development at Berkeley University. POSTGRES is a large project for developing a new generation database system, extending relational technology to support complex objects, data types, and rules (called alerts or triggers); in this chapter, we focus on rule management.
 
d)
The FIFTH GENERATION Project, under development at the Institute for New Generation Computer Technology (ICOT) in Tokio, Japan. The guiding principle of the project is to select Prolog as unifying element for the development of computer architecture, programming style, and database approach. In this chapter, we illustrate features related to the development of knowledge bases.
 
e)
The Advanced Database Interface (ADE) of the KIWI Esprit project, sponsored by the EEC. KIWI is a joint effort for the development of knowledge bases, programmed through an object-oriented language (OOPS), and interfaced to an existing relational database. ADE is joint effort of the University of Calabria, of CRAI, and of ENIDATA (Italy).
 
f)
The ALGRES Project, under development in the frame of the METEOR Esprit project, sponsored by the EEC. The ALGRES project extends the relational model to support nonnormalized relations and a fixpoint operator, and supports Datalog as programming language. ALGRES is a joint effort of the Politecnico di Milano and of TXT-Techint (Italy).
 
g)
The PRISMA project, under development at the University of Twente in Enschede, the Centre for Mathematics and Computer Science in Amsterdam, and Philips Research Laboratories in Eindhoven, sponsored by the Dutch research fund SPIN. PRISMA is a large project for the development of a multiprocessor, main-memory, relational database machine that supports a logic interface, called PRISMAlog.
 
Stefano Ceri, Georg Gottlob, Letizia Tanca

Backmatter

Weitere Informationen