Foundations of Databases
The Logical Level
Published on 13. February 1995
Book
Paperback/Softback
704 pages
978-0-201-53771-0 (ISBN)
Description
Written by three leading researchers in the field, this book provides in-depth coverage of the theory concerning the logical level of database management systems, including both classical and advanced topics. Features *Emphasizes query languages for the relational model including coverage of different language paradigms, expressive power, and complexity. *Presents a unified theory of dependencies, including those commonly arising in practice, and their use in optimization and schema design. *Provides theoretical underpinnings of several emerging topics, including deductive and object-oriented databases. *Includes detailed proofs and numerous examples and exercises. 0201537710B04062001
More details
Persons
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.
0201537710AB04062001
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.
0201537710AB04062001
Content
A. ANTECHAMBER.
Database Systems.
The Main Principles.
Functionalities.
Complexity and Diversity.
Past and Future.
Ties with This Book.
Bibliographic Notes.
Theoretical Background.
Some Basics.
Languages, Computability, and Complexity.
Basics from Logic.
The Relational Model.
The Structure of the Relational Model.
Named versus Unnamed Perspectives.
Notation.
Bibliographic Notes.
B. BASICS: RELATIONAL QUERY LANGUAGES.
Conjunctive Queries.
Getting Started.
Logic-Based Perspectives.
Query Composition and Views.
Algebraic Perspectives.
Adding Union.
Bibliographic Notes.
Exercises.
Adding Negation: Algebra and Calculus.
The Relational Algebras.
Nonrecursive Datalog with Negation.
The Relational Calculus.
Syntactic Restrictions for Domain Independence.
Aggregate Functions.
Digression: Finite Representations of Infinite Databases.
Bibliographic Notes.
Exercises.
Static Analysis and Optimization.
Issues in Practical Query Optimization.
Global Optimization.
Static Analysis of the Relational Calculus.
Computers with Acyclic Joins.
Bibliographic Notes.
Exercises.
Notes on Practical Languages.
SQL: The Structured Query Language.
Query-by-Example and Microsoft Access.
Confronting the Real World.
Bibliographic Notes.
Exercises.
C. CONSTRAINTS.
Functional and Join Dependency.
Motivation.
Functional and Key Dependencies.
join and Multivalued Dependencies.
The Chase.
Bibliographic Notes.
Exercises.
Inclusion Dependency.
Inclusion Dependency in Isolation.
Finite versus Infinite Implication.
Nonaxiomatizability of fd's + ind's.
Restricted Kinds of Inclusion Dependency.
Bibliographic Notes.
Exercises.
A Larger Perspective.
A Unifying Framework.
The Chase revisited.
Axiomatization.
An Algebraic Perspective.
Bibliographic Notes.
Exercises.
Design and Dependencies.
Semantic Data Models.
Normal Forms.
Universal Relation Assumption.
Bibliographic Notes.
Exercises.
D. DATALOG AND RECURSION.
Datalog.
Syntax of Datalog.
Model-Theoretic Semantics.
Fixpoint Semantics.
Proof-Theoretic Approach.
Static Program Analysis.
Bibliographic Notes.
Exercises.
Evaluation of Datalog.
Seminaive Evaluation.
Top-Down Techniques.
Magic.
Two Improvements.
Bibliographic Notes.
Exercises.
Recursion and Negation.
Algebra + While.
Calculus + Fixpoint.
Datalog with Negation.
Equivalence.
Recursion in Practical Language.
Bibliographic Notes.
Exercises.
Negation in Datalog.
The Basic Problem.
Stratified Semantics.
Well-Founded Semantics.
Expressive Power.
Negation as Failure of Brief.
Bibliographic Notes.
Exercises.
E. EXPRESSIVENESS AND COMPLEXITY.
Sizing up Languages.
Queries.
Complexity of Queries.
Languages and Complexity.
Bibliographic Notes.
Exercises.
First Order, Fixpoint and While.
Complexity of First-Order Queries.
Expressiveness of First-Order Queries.
Fixpoint and While Queries.
The Impact of Order.
Bibliographic Notes.
Exercises.
Highly Expressive Languages.
While(N)-while with Arithmetic.
While(new)-while with New Values.
While(uty)-An Untyped Extension of while.
Bibliographic Notes.
Exercises.
F. FINALE.
Incomplete Information.
Warm-Up.
Weak Representation Systems.
Conditional Tables.
The Complexity of Nulls.
Other Approaches.
Bibliographic Notes.
Exercises.
Complex Values.
Complex Value Databases.
The Algebra.
The Caculas.
Examples.
Equivalence Theorems.
Fixpoint and Deduction.
Expressive Power and Complexity.
A Practicle Query Language for Complex Values.
Bibliographic Notes.
Exercises.
Object Databases.
Informal Presentation.
Formal Definition of an OODB Model.
Languages for OODB Queries.
Languages for Methods.
Further Issues for OODB's.
Bibliographic Notes.
Exercises.
Dynamic Aspects.
Updated Languages.
Transactional Schemas.
Updating Views and Deductive Databases.
Active Databases.
Temporal Databases and Constraints.
Bibliographic Notes.
Exercises.
Bibliography.
Symbol Index.
Index. 0201537710T04062001
Database Systems.
The Main Principles.
Functionalities.
Complexity and Diversity.
Past and Future.
Ties with This Book.
Bibliographic Notes.
Theoretical Background.
Some Basics.
Languages, Computability, and Complexity.
Basics from Logic.
The Relational Model.
The Structure of the Relational Model.
Named versus Unnamed Perspectives.
Notation.
Bibliographic Notes.
B. BASICS: RELATIONAL QUERY LANGUAGES.
Conjunctive Queries.
Getting Started.
Logic-Based Perspectives.
Query Composition and Views.
Algebraic Perspectives.
Adding Union.
Bibliographic Notes.
Exercises.
Adding Negation: Algebra and Calculus.
The Relational Algebras.
Nonrecursive Datalog with Negation.
The Relational Calculus.
Syntactic Restrictions for Domain Independence.
Aggregate Functions.
Digression: Finite Representations of Infinite Databases.
Bibliographic Notes.
Exercises.
Static Analysis and Optimization.
Issues in Practical Query Optimization.
Global Optimization.
Static Analysis of the Relational Calculus.
Computers with Acyclic Joins.
Bibliographic Notes.
Exercises.
Notes on Practical Languages.
SQL: The Structured Query Language.
Query-by-Example and Microsoft Access.
Confronting the Real World.
Bibliographic Notes.
Exercises.
C. CONSTRAINTS.
Functional and Join Dependency.
Motivation.
Functional and Key Dependencies.
join and Multivalued Dependencies.
The Chase.
Bibliographic Notes.
Exercises.
Inclusion Dependency.
Inclusion Dependency in Isolation.
Finite versus Infinite Implication.
Nonaxiomatizability of fd's + ind's.
Restricted Kinds of Inclusion Dependency.
Bibliographic Notes.
Exercises.
A Larger Perspective.
A Unifying Framework.
The Chase revisited.
Axiomatization.
An Algebraic Perspective.
Bibliographic Notes.
Exercises.
Design and Dependencies.
Semantic Data Models.
Normal Forms.
Universal Relation Assumption.
Bibliographic Notes.
Exercises.
D. DATALOG AND RECURSION.
Datalog.
Syntax of Datalog.
Model-Theoretic Semantics.
Fixpoint Semantics.
Proof-Theoretic Approach.
Static Program Analysis.
Bibliographic Notes.
Exercises.
Evaluation of Datalog.
Seminaive Evaluation.
Top-Down Techniques.
Magic.
Two Improvements.
Bibliographic Notes.
Exercises.
Recursion and Negation.
Algebra + While.
Calculus + Fixpoint.
Datalog with Negation.
Equivalence.
Recursion in Practical Language.
Bibliographic Notes.
Exercises.
Negation in Datalog.
The Basic Problem.
Stratified Semantics.
Well-Founded Semantics.
Expressive Power.
Negation as Failure of Brief.
Bibliographic Notes.
Exercises.
E. EXPRESSIVENESS AND COMPLEXITY.
Sizing up Languages.
Queries.
Complexity of Queries.
Languages and Complexity.
Bibliographic Notes.
Exercises.
First Order, Fixpoint and While.
Complexity of First-Order Queries.
Expressiveness of First-Order Queries.
Fixpoint and While Queries.
The Impact of Order.
Bibliographic Notes.
Exercises.
Highly Expressive Languages.
While(N)-while with Arithmetic.
While(new)-while with New Values.
While(uty)-An Untyped Extension of while.
Bibliographic Notes.
Exercises.
F. FINALE.
Incomplete Information.
Warm-Up.
Weak Representation Systems.
Conditional Tables.
The Complexity of Nulls.
Other Approaches.
Bibliographic Notes.
Exercises.
Complex Values.
Complex Value Databases.
The Algebra.
The Caculas.
Examples.
Equivalence Theorems.
Fixpoint and Deduction.
Expressive Power and Complexity.
A Practicle Query Language for Complex Values.
Bibliographic Notes.
Exercises.
Object Databases.
Informal Presentation.
Formal Definition of an OODB Model.
Languages for OODB Queries.
Languages for Methods.
Further Issues for OODB's.
Bibliographic Notes.
Exercises.
Dynamic Aspects.
Updated Languages.
Transactional Schemas.
Updating Views and Deductive Databases.
Active Databases.
Temporal Databases and Constraints.
Bibliographic Notes.
Exercises.
Bibliography.
Symbol Index.
Index. 0201537710T04062001