**default search action**

# Foundations of Databases

- Serge Abiteboul, Richard Hull, Victor Vianu:

Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0

## Abstract

## Contents

PART A -- Antechamber 1 Database Systems 1.1 The Main Principles 1.2 Functionalities 1.3 Complexity and Diversity 1.4 Past and Future 1.5 Ties with this Book Bibliographic Notes 2 Theoretical Background 2.1 Some Basics 2.2 Languages, Computability, Complexity 2.3 Basics from Logic 3 The Relational Model Bibliographic Notes PART B -- Basics: Relational Query Languages 4 Conjunctive Queries 4.1 Getting Started 4.2 Logic-based perspectives 4.3 Query composition and views 4.4 Algebraic perspectives 4.5 Adding union Bibliographic Notes Exercises 5 Adding Negation: Algebra and Calculus 5.1 The Relational Algebras 5.2 Nonrecursive Datalog with Negation 5.3 The Relational Calculus 5.4 Syntactic Restrictions for Domain Independence 5.5 Digression: Finite Representations of Infinite Databases Bibliographic notes Exercises 6 Static Analysis and Optimization 6.1 Issues in Practical Query Optimization 6.2 Global Optimization 6.3 Static Analysis of the Relational Calculus 6.4 Computing with Acyclic Joins Bibliographic Notes Exercises 7 Notes on Practical Languages 7.1 SQL: The Structured Query Language 7.2 Query-By-Example and Microsoft Access 7.3 Confronting the Real World Bibliographic Notes Exercises PART C -- Constraints 8 Functional and Join Dependency 8.1 Motivation 8.2 Functional and Key Dependencies 8.3 Join and Multivalued Dependencies 8.4 The Chase Bibliographic Notes Exercises 9 Inclusion Dependency 9.1 Inclusion Dependency in Isolation 9.2 Finite vs. Infinite Implication 9.3 Non-axiomatizability of fds + inds 9.4 Restricted Kinds of Inclusion Dependency Bibliographic Notes Exercises 10 A Larger Perspective 10.1 A Unifying Framework 10.2 The Chase Revisited 10.3 Axiomatization 10.4 An Algebraic Perspective Bibliographic Notes Exercises 11 Design and Dependencies 11.1 Semantic Data Models 11.2 Normal Forms 11.3 Universal Relation Assumption Bibliographic Notes Exercises PART D -- Datalog and Recursion 12 Datalog 12.1 Syntax of Datalog 12.2 Model-Theoretic Semantics 12.3 Fixpoint Semantics 12.4 Proof-Theoretic Approach 12.5 Static Program Analysis Bibliographic Notes Exercises 13 Evaluation of Datalog 13.1 Semi-naive Evaluation 13.2 Top-down Techniques 13.3 Magic 13.4 Two Improvements Bibliographic Notes Exercises 14 Recursion and Negation 14.1 Algebra + {\pem { while 14.2 Calculus + Fixpoint 14.3 Datalog with Negation 14.4 Equivalence 14.5 Recursion in Practical Languages Bibliographic Notes Exercises 15 Negation in Datalog 15.1 The Basic Problem 15.2 The Stratified Semantics 15.3 The Well-Founded Semantics 15.3.1 A Declarative Semantics for datalog$^\neg $ 15.3.2 A Fixpoint Definition 15.3.3 Well-founded and Stratified Semantics Agree 15.4 Expressive Power 15.5 Negation as Failure in Brief Bibliographic Notes Exercises PART E -- Expressiveness and Complexity 16 Sizing Up Languages 16.1 Queries 16.2 Complexity of queries 16.3 Languages and Complexity Bibliographic Notes Exercises 17 First-Order, Fixpoint and While 17.1 Complexity of the First-Order Queries 17.2 Expressiveness of the First-Order Queries 17.3 The Fixpoint and While Queries 17.4 The Impact of Order Bibliographic Notes Exercises 18 Highly Expressive Languages 18.1 While$_N$ -- while with Arithmetic 18.2 While$_{new}$ -- while with New Values 18.3 While$_{uty}$ -- an Untyped Extension of while Bibliographic Notes Exercises PART F -- Finale 19 Incomplete Information 19.1 Warm up 19.2 Weak Representation Systems 19.3 Conditional Tables 19.4 The Complexity of Nulls 19.5 Other Approaches Bibliographic Notes Exercises 20 Complex Values 20.1 Complex Value Databases 20.2 The Algebra 20.3 The Calculus 20.4 Examples 20.5 Equivalence Theorems 20.6 Fixpoint and Deduction 20.7 Expressive Power and Complexity 20.8 A Practical Query Language for Complex Values Bibliographic Notes Exercises 21 Object Databases 21.1 Informal Presentation 21.2 Formal Definition of an OODB Model 21.3 Languages for OODB Queries 21.4 Languages for Methods 21.4.1 A Model with Imperative Methods 21.4.2 Method Schemas 21.5 Further Issues for OODBs Bibliographic Notes Exercises 22 Dynamic Aspects 22.1 Update Languages 22.2 Transactional Schemas 22.3 Updating Views and Deductive Databases 22.4 Updating Incomplete Information 22.5 Active Databases 22.6 Temporal Databases and Constraints Bibliographic Notes Exercises Bibliography Index