Foundations of Deductive Databases and Logic Programming

Foundations of Deductive Databases and Logic Programming

by Jack Minker
Released May 2014
Publisher(s): Morgan Kaufmann
ISBN: 9781483221120

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description


Foundations of Deductive Databases and Logic Programming focuses on the foundational issues concerning deductive databases and logic programming. The selection first elaborates on negation in logic programming and towards a theory of declarative knowledge. Discussions focus on model theory of stratified programs, fixed point theory of nonmonotonic operators, stratified programs, semantics for negation in terms of special classes of models, relation between closed world assumption and the completed database, negation as a failure, and closed world assumption. The book then takes a look at negation as failure using tight derivations for general logic programs, declarative semantics of logic programs with negation, and declarative semantics of deductive databases and logic programs. The publication tackles converting AND-control to OR-control by program transformation, optimizing dialog, equivalences of logic programs, unification, and logic programming and parallel complexity. Topics include parallelism and structured and unstructured data, parallel algorithms and complexity, solving equations, most general unifiers, systems of equations and inequations, equivalences of logic programs, and optimizing recursive programs. The selection is a valuable source of data for researchers interested in pursuing further studies on the foundations of deductive databases and logic programming.

Table of contents

  1. Front Cover
  2. Foundations of Deductive Databases and Logic Programming
  3. Copyright Page
  4. Table of Contents
  5. Dedication
  6. Introduction
    1. Background
    2. Workshop on Foundations of Deductive Databases and Logic Programming
    3. Overview of Book
    4. Future Directions
    5. Summary
    6. Acknowledgments
    7. References
  7. PART I: NEGATION AND STRATIFIED DATABASES
    1. Chapter 1. Negation in Logic Programming
      1. Abstract
      2. Introduction
      3. Fixpoint Models
      4. The Closed World Assumption (1/3)
      5. The Closed World Assumption (2/3)
      6. The Closed World Assumption (3/3)
      7. The Completed Database (1/3)
      8. The Completed Database (2/3)
      9. The Completed Database (3/3)
      10. The Relation between the Closed World Assumption and the Completed Database
      11. Negation as Failure (1/3)
      12. Negation as Failure (2/3)
      13. Negation as Failure (3/3)
      14. Semantics for Negation in Terms of Special Classes of Models (1/2)
      15. Semantics for Negation in Terms of Special Classes of Models (2/2)
      16. Semantics for Negation as Failure in Terms of 3-Valued Logic (1/2)
      17. Semantics for Negation as Failure in Terms of 3-Valued Logic (2/2)
      18. Acknowledgments
      19. References
    2. Chapter 2. Towards a Theory of Declarative Knowledge
      1. Abstract
      2. Introduction
      3. Preliminaries
      4. Stratified Programs
      5. From Models to Fixed Points
      6. Fixed Point Theory of Nonmonotonic Operators (1/2)
      7. Fixed Point Theory of Nonmonotonic Operators (2/2)
      8. Model Theory of Stratified Programs (1/3)
      9. Model Theory of Stratified Programs (2/3)
      10. Model Theory of Stratified Programs (3/3)
      11. An Elementary Interpreter (1/3)
      12. An Elementary Interpreter (2/3)
      13. An Elementary Interpreter (3/3)
      14. Existence of the Interpreter (1/2)
      15. Existence of the Interpreter (2/2)
      16. Other Views of Negation and Stratified Programs
      17. Completions of Programs
      18. Related Work
      19. References
    3. Chapter 3. Negation as Failure Using Tight Derivations for General Logic Programs
      1. Abstract
      2. Introduction
      3. General Logic Programs and Safe Negation
      4. Rule-based Negation-as-Failure Semantics
      5. Counter-Intuitive Meanings of Rule-based Semantics
      6. Tree-oriented Semantics for Negation as Failure (1/2)
      7. Tree-oriented Semantics for Negation as Failure (2/2)
      8. Freedom from Recursive Negation
      9. Practical Algorithms
      10. Conclusion
      11. Acknowledgments
      12. References
    4. Chapter 4 On the Declarative Semantics of Logic Programs with Negation
      1. Abstract
      2. Introduction
      3. Logic Programs and Circumscription
      4. Iterated Fixed Points
      5. Proof of Theorem 1
      6. Proof of Theorem 3
      7. Acknowledgments
      8. References
    5. Chapter 5. On the Declarative Semantics of Deductive Databases and Logic Programs
      1. Abstract
      2. Introduction
      3. Minimal Model Semantics
      4. Minimal Model Semantics Is Not Sufficient for General Databases
      5. Perfect Model Semantics (1/3)
      6. Perfect Model Semantics (2/3)
      7. Perfect Model Semantics (3/3)
      8. Relation to Prioritized Circumscription
      9. Acknowledgments
      10. References
    6. Chapter 6. On Domain Independent Databases
      1. Abstract
      2. Introduction
      3. Basic Concepts
      4. Domain Independent Formulas
      5. Domain Independent Databases (1/2)
      6. Domain Independent Databases (2/2)
      7. On Correct Answers
      8. Conclusions
      9. Acknowledgments
      10. References
  8. PART II: FUNDAMENTAL ISSUES IN DEDUCTIVE DATABASES AND IMPLEMENTATION
    1. Chapter 7. Foundations of Semantic Query Optimization for Deductive Databases
      1. Abstract
      2. Introduction
      3. Overview of Semantic Query Optimization
      4. Assumptions
      5. Semantic Compilation (1/3)
      6. Semantic Compilation (2/3)
      7. Semantic Compilation (3/3)
      8. Semantic Query Transformation (1/2)
      9. Semantic Query Transformation (2/2)
      10. Extensions
      11. Acknowledgments
      12. References
    2. Chapter 8. Intelligent Query Answering in Rule Based Systems
      1. Abstract
      2. Introduction
      3. Basic Notions
      4. Rules in Answers-Rule Transformation (1/4)
      5. Rules in Answers-Rule Transformation (2/4)
      6. Rules in Answers-Rule Transformation (3/4)
      7. Rules in Answers-Rule Transformation (4/4)
      8. Infinite Answers, Functions, and Predicates in the Answers for Queries
      9. Conclusions
      10. Appendix
      11. Acknowledgment
      12. References
    3. Chapter 9. A Theorem-Proving Approach to Database Integrity
      1. Abstract
      2. Introduction
      3. Definitions
      4. The Proof Procedure (1/2)
      5. The Proof Procedure (2/2)
      6. The Consistency Method for Checking Integrity Constraints in Deductive Databases (1/4)
      7. The Consistency Method for Checking Integrity Constraints in Deductive Databases (2/4)
      8. The Consistency Method for Checking Integrity Constraints in Deductive Databases (3/4)
      9. The Consistency Method for Checking Integrity Constraints in Deductive Databases (4/4)
      10. Formalizing the Inference Rules for Implicit Deletions: The First Approach
      11. Formalizing the Inference Rules for Implicit Deletions: The Second Approach
      12. Comparison with Simplification Methods for Integrity Checking (1/2)
      13. Comparison with Simplification Methods for Integrity Checking (2/2)
      14. Correctness and Completeness of the Consistency Method
      15. Conclusion
      16. Acknowledgments
      17. References
    4. Chapter 10. A Logic-based Language for Database Updates
      1. Abstract
      2. Introduction
      3. Syntax of DLP
      4. Informal Introduction to DLP
      5. Formal Semantics of DLP
      6. Implementation Issues of DLP
      7. View Updates
      8. Correctness Conditions for Translators
      9. Defining View Update Translators
      10. Conclusion
      11. Acknowledgments
      12. References
    5. Chapter 11. Compiling the GCWA in Indefinite Deductive Databases
      1. Abstract
      2. Introduction
      3. Indefinite Databases and GCWA Inference
      4. Compilation and Representation Alternatives
      5. Compiling the GCWA in a Non-Recursive IDDB (1/2)
      6. Compiling the GCWA in a Non-Recursive IDDB (2/2)
      7. NH-lnheritance
      8. Compiling Unit Queries in Recursive IDDB
      9. Complex Query Evaluation by Decomposition
      10. Summary and Further Work
      11. Acknowledgment
      12. Appendix
      13. References
    6. Chapter 12. Performance Evaluation of Data Intensive Logic Programs
      1. Abstract
      2. Introduction
      3. The Methods (1/6)
      4. The Methods (2/6)
      5. The Methods (3/6)
      6. The Methods (4/6)
      7. The Methods (5/6)
      8. The Methods (6/6)
      9. Framework for Performance Evaluation (1/2)
      10. Framework for Performance Evaluation (2/2)
      11. Notation and Preliminary Derivations
      12. Analysis of the Query Evaluation Strategies (1/5)
      13. Analysis of the Query Evaluation Strategies (2/5)
      14. Analysis of the Query Evaluation Strategies (3/5)
      15. Analysis of the Query Evaluation Strategies (4/5)
      16. Analysis of the Query Evaluation Strategies (5/5)
      17. Graphical Comparison of the Costs (1/2)
      18. Graphical Comparison of the Costs (2/2)
      19. Related Work
      20. Conclusions and Caveats
      21. Acknowledgments
      22. References
    7. Chapter 13. A Superjoin Algorithm for Deductive Databases
      1. Abstract
      2. Introduction
      3. Background
      4. The Super join Algorithm
      5. Superjoin and Deductive Databases (1/2)
      6. Superjoin and Deductive Databases (2/2)
      7. Conclusions
      8. Acknowledgments
      9. Appendix 1
      10. Appendix 2
      11. References
  9. PART III: UNIFICATION AND LOGIC PROGRAMS
    1. Chapter 14. Logic Programming and Parallel Complexity
      1. Abstract
      2. Introduction
      3. Parallel Algorithms and Complexity
      4. Parallelism and Unstructured Data (1/4)
      5. Parallelism and Unstructured Data (2/4)
      6. Parallelism and Unstructured Data (3/4)
      7. Parallelism and Unstructured Data (4/4)
      8. Parallelism and Structured Data (1/2)
      9. Parallelism and Structured Data (2/2)
      10. Conclusions
      11. Acknowledgments
      12. References
    2. Chapter 15. Unification Revisited
      1. Abstract
      2. Introduction
      3. On the Definitions of mgus
      4. Preliminary Definitions
      5. Solving Equations (1/2)
      6. Solving Equations (2/2)
      7. Most General Unifiers (1/2)
      8. Most General Unifiers (2/2)
      9. Anti-unification and Most General Solutions (1/2)
      10. Anti-unification and Most General Solutions (2/2)
      11. Systems of Equations and Inequations (1/2)
      12. Systems of Equations and Inequations (2/2)
      13. Acknowledgments
      14. References
    3. Chapter 16. Equivalences of Logic Programs
      1. Abstract
      2. Introduction
      3. Semantics Of Logic Programs
      4. Subsumption-Equivalence (1/2)
      5. Subsumption-Equivalence (2/2)
      6. Equivalences of Logic Programs
      7. Reasoning in the Herbrand Universe
      8. Equivalences of Logic Programs in Differing Languages
      9. Discussion
      10. Acknowledgments
      11. References
    4. Chapter 17. Optimizing Datalog Programs
      1. Abstract
      2. Introduction
      3. Preliminaries (1/2)
      4. Preliminaries (2/2)
      5. Optimizing Recursive Programs
      6. Tuple-Generating Dependencies (1/3)
      7. Tuple-Generating Dependencies (2/3)
      8. Tuple-Generating Dependencies (3/3)
      9. Determining Equivalence
      10. Conclusion and Open Problems
      11. Acknowledgments
      12. Appendix
      13. Reference
    5. Chapter 18. Converting AND-Control to OR-Control by Program Transformation
      1. Abstract
      2. Introduction
      3. Translation of Network Specifications
      4. A Variant of the Dataflow Network Representation
      5. Deriving the Program
      6. OR-Control of the Derived Program
      7. An Alternative Route to the Transformed Program
      8. Conclusions
      9. Acknowledgments
      10. References
  10. Authors
  11. Referees
  12. Author Index (1/2)
  13. Author Index (2/2)
  14. Subject Index (1/5)
  15. Subject Index (2/5)
  16. Subject Index (3/5)
  17. Subject Index (4/5)
  18. Subject Index (5/5)

Product information

  • Title: Foundations of Deductive Databases and Logic Programming
  • Author(s): Jack Minker
  • Release date: May 2014
  • Publisher(s): Morgan Kaufmann
  • ISBN: 9781483221120