Logo - springer
Slogan - springer

Computer Science - Database Management & Information Retrieval | Logic Programming and Databases

Logic Programming and Databases

Ceri, Stefano, Gottlob, Georg, Tanca, Letizia

Softcover reprint of the original 1st ed. 1990, XIII, 284 pp. 42 figs.

Available Formats:

Springer eBooks may be purchased by end-customers only and are sold without copy protection (DRM free). Instead, all eBooks include personalized watermarks. This means you can read the Springer eBooks across numerous devices such as Laptops, eReaders, and tablets.

You can pay for Springer eBooks with Visa, Mastercard, American Express or Paypal.

After the purchase you can directly download the eBook file or read it online in our Springer eBook Reader. Furthermore your eBook will be stored in your MySpringer account. So you can always re-download your eBooks.


(net) price for USA

ISBN 978-3-642-83952-8

digitally watermarked, no DRM

Included Format: PDF

download immediately after purchase

learn more about Springer eBooks

add to marked items


Softcover (also known as softback) version.

You can pay for Springer Books with Visa, Mastercard, American Express or Paypal.

Standard shipping is free of charge for individual customers.


(net) price for USA

ISBN 978-3-642-83954-2

free shipping for individuals worldwide

usually dispatched within 3 to 5 business days

add to marked items

  • About this textbook

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.

Content Level » Lower undergraduate

Keywords » Anfrage-Optimierungstechniken - Datalog - Experten-Datenbanksystem - Extension - Prolog - computer science - database - database systems - deductive database - knowledge - knowledge base - logic - logic programming - optimization - relational database

Related subjects » Artificial Intelligence - Database Management & Information Retrieval - Software Engineering - Theoretical Computer Science

Table of contents 

1 Logic Programming and Databases: An Overview.- 1.1 Logic Programming as Query Language.- 1.2 Prolog and Datalog.- 1.3 Alternative Architectures.- 1.4 Applications.- 1.5 Bibliographic Notes.- 2 A Review of Relational Databases and Prolog.- 2.1 Overview of Relational Databases.- 2.1.1 The Relational Model.- 2.1.2 Relational Languages.- 2.2 Prolog: A Language for Programming in Logic.- 2.3 Bibliographic Notes.- I Coupling Prolog to Relational Databases.- 3 Prolog as a Query Language.- 3.1 The Anti-Trust Control Problem.- 3.2 The Bill of Materials Problem.- 3.3 Conclusions.- 3.4 Bibliographic Notes.- 3.5 Exercises.- 4 Coupling Prolog Systems to Relational Databases.- 4.1 Architectures for Coupling Prolog and Relational Systems.- 4.1.1 Assumptions and Terminology.- 4.1.2 Components of a CPR System.- 4.1.3 Architecture of CPR Systems.- 4.2 Base Conjunctions.- 4.2.1 Determining Base Conjunctions in LCPR Systems.- 4.2.2 Improving Base Conjunctions in TCPR Systems.- 4.3 Optimization of the Prolog/Database Interface.- 4.3.1 Caching of Data.- 4.3.2 Caching of Data and Queries.- 4.3.3 Use of Subsumption.- 4.3.4 Caching Queries.- 4.3.5 Parallelism and Pre-fetching in Database Interfaces.- 4.4 Conclusions.- 4.5 Bibliographic Notes.- 4.6 Exercises.- 5 Overview of Systems for Coupling Prolog to Relational Databases.- 5.1 PRO-SQL.- 5.2 EDUCE.- 5.3 ESTEAM.- 5.4 BERMUDA.- 5.5 CGW and PRIMO.- 5.6 QUINTUS-PROLOG.- 5.7 Bibliographic Notes.- II Foundations of Datalog.- 6 Syntax and Semantics of Datalog.- 6.1 Basic Definitions and Assumptions.- 6.1.1 Alphabets, Terms, and Clauses.- 6.1.2 Extensional Databases and Datalog Programs.- 6.1.3 Substitutions, Subsumption, and Unification.- 6.2 The Model Theory of Datalog.- 6.2.1 Possible Worlds, Truth, and Herbrand Interpretations.- 6.2.2 The Least Herbrand Model.- 6.3 Conclusions.- 6.4 Bibliographic Notes.- 6.5 Exercises.- 7 Proof Theory and Evaluation Paradigms of Datalog.- 7.1 The Proof Theory of Datalog.- 7.1.1 Fact Inference.- 7.1.2 Soundness and Completeness of the Inference Rule EP.- 7.2 Least Fixpoint Iteration.- 7.2.1 Basic Results of Fixpoint Theory.- 7.2.2 Least Fixpoints and Datalog Programs.- 7.3 Backward Chaining and Resolution.- 7.3.1 The Principle of Backward Chaining.- 7.3.2 Resolution.- 7.4 Conclusions.- 7.5 Bibliographic Notes.- 7.6 Exercises.- III Optimization Methods for Datalog.- 8 Classification of Optimization Methods for Datalog.- 8.1 Criteria for the Classification of Optimization Methods.- 8.1.1 Formalism.- 8.1.2 Search Strategy.- 8.1.3 Objectives of Optimization Methods.- 8.1.4 Type of Information Considered.- 8.2 Classification of Optimization Methods.- 8.3 Translation of Datalog into Relational Algebra.- 8.4 Classification of Datalog Rules.- 8.5 The Expressive Power of Datalog.- 8.6 Bibliographic Notes.- 8.7 Exercises.- 9 Evaluation Methods.- 9.1 Bottom-up Evaluation.- 9.1.1 Algebraic Naive Evaluation.- 9.1.2 Semi-naive Evaluation.- 9.1.3 The Method of Henschen and Naqvi.- 9.2 Top-down Evaluation.- 9.2.1 Query-Subquery.- 9.2.2 The RQA/FQI Method.- 9.3 Bibliographic Notes.- 9.4 Exercises.- 10 Rewriting Methods.- 10.1 Logical Rewriting Methods.- 10.1.1 Magic Sets.- 10.1.2 The Counting Method.- 10.1.3 The Static Filtering Method.- 10.1.4 Semi-naive Evaluation by Rewriting.- 10.2 Rewriting of Algebraic Systems.- 10.2.1 Reduction to Union-Join Normal Form.- 10.2.2 Determination of Common Subexpressions.- 10.2.3 Query Subsetting and Strong Components.- 10.2.4 Marking of Variables.- 10.2.5 Reduction of Variables.- 10.2.6 Reduction of Constants.- 10.2.7 Summary of the Algebraic Approach.- 10.3 A General View of Optimization.- 10.4 Bibliographic Notes.- 10.5 Exercises.- 11 Extensions of Pure Datalog.- 11.1 Using Built-in Predicates in Datalog.- 11.2 Incorporating Negation into Datalog.- 11.2.1 Negation and the Closed World Assumption.- 11.2.2 Stratified Datalog.- 11.2.3 Perfect Models and Local Stratification.- 11.2.4 Inflationary Semantics and Expressive Power.- 11.3 Representation and Manipulation of Complex Objects.- 11.3.1 Basic Features of LDL.- 11.3.2 Semantics of Admissible LDL Programs.- 11.3.3 Data Models for Complex Objects.- 11.4 Conclusions.- 11.5 Bibliographic Notes.- 11.6 Exercises.- 12 Overview of Research Prototypes for Integrating Relational Databases and Logic Programming.- 12.1 The LDL Project.- 12.2 The NAIL! Project.- 12.3 The POSTGRES Project.- 12.4 The FIFTH GENERATION Project.- 12.5 The KIWI Project.- 12.6 The ALGRES Project.- 12.7 The PRISMA Project.- 12.8 Bibliographic Notes.

Popular Content within this publication 



Read this Book on Springerlink

Services for this book

New Book Alert

Get alerted on new Springer publications in the subject area of Database Management.