Table of Contents
A. ANTECHAMBER. Database Systems.
The Main Principles.
Complexity and Diversity.
Past and Future.
Ties with This Book.
Bibliographic Notes.Theoretical Background.
Languages, Computability, and Complexity.
Basics from Logic.The Relational Model.
The Structure of the Relational Model.
Named versus Unnamed Perspectives.
B. BASICS: RELATIONAL QUERY LANGUAGES. Conjunctive Queries.
Query Composition and Views.
Exercises.Adding Negation: Algebra and Calculus.
The Relational Algebras.
Nonrecursive Datalog with Negation.
The Relational Calculus.
Syntactic Restrictions for Domain Independence.
Digression: Finite Representations of Infinite Databases.
Exercises.Static Analysis and Optimization.
Issues in Practical Query Optimization.
Static Analysis of the Relational Calculus.
Computers with Acyclic Joins.
Exercises.Notes on Practical Languages.
SQL: The Structured Query Language.
Query-by-Example and Microsoft Access.
Confronting the Real World.
C. CONSTRAINTS. Functional and Join Dependency.
Functional and Key Dependencies.
join and Multivalued Dependencies.
Inclusion Dependency in Isolation.
Finite versus Infinite Implication.
Nonaxiomatizability of fd's + ind's.
Restricted Kinds of Inclusion Dependency.
Exercises.A Larger Perspective.
A Unifying Framework.
The Chase revisited.
An Algebraic Perspective.
Exercises.Design and Dependencies.
Semantic Data Models.
Universal Relation Assumption.
D. DATALOG AND RECURSION. Datalog.
Syntax of Datalog.
Static Program Analysis.
Exercises.Evaluation of Datalog.
Exercises.Recursion and Negation.
Algebra + While.
Calculus + Fixpoint.
Datalog with Negation.
Recursion in Practical Language.
Exercises.Negation in Datalog.
The Basic Problem.
Negation as Failure of Brief.
E. EXPRESSIVENESS AND COMPLEXITY. Sizing up Languages.
Complexity of Queries.
Languages and Complexity.
Exercises.First Order, Fixpoint and While.
Complexity of First-Order Queries.
Expressiveness of First-Order Queries.
Fixpoint and While Queries.
The Impact of Order.
Exercises.Highly Expressive Languages.
While(N)-while with Arithmetic.
While(new)-while with New Values.
While(uty)-An Untyped Extension of while.
F. FINALE. Incomplete Information.
Weak Representation Systems.
The Complexity of Nulls.
Complex Value Databases.
Fixpoint and Deduction.
Expressive Power and Complexity.
A Practicle Query Language for Complex Values.
Formal Definition of an OODB Model.
Languages for OODB Queries.
Languages for Methods.
Further Issues for OODB's.
Updating Views and Deductive Databases.
Temporal Databases and Constraints.
Exercises.Bibliography. Symbol Index. Index. 0201537710T04062001
About the Author
Serge Abiteboul received his Ph.D. in computer science from the University of Southern California, and is now a director de recherch&eactute; at I.N.R.I.A. in France.About Richard Hull
Richard Hull received his Ph.D. in mathematics from the University of California, Berkeley. He is an associate professor at the University of Southern California in Computer Science, currently on leave and visiting the University of Colorado, Boulder.
Victor Vianu received his Ph.D. in computer science from the University of Southern California, San Diego, where he is currently professor of Computer Science. He spends a portion of each year visiting the I.N.R,I.A.