zbMATH — the first resource for mathematics

Foundations of databases. (English) Zbl 0848.68031
Amsterdam: Addison-Wesley. xviii, 685 p. (1995).
Thirty years of databases have provided to researchers many opportunities for developing theory of databases. This book present a systematic treatment of the formal theory of the logical level databases, e.g. rather abstract representation of the data including languages to create, query and modify it. The book is composed of 6 parts: A) Antechamber, B) Basics: Relational query languages, C) Constraints, D) Datalog and recursion, E) Expressiveness and complexity, F) Finale.
The contents of the book is completed by the large list of bibliography, symbol index, and index. Part A provides in three chapters a general overview of database notions, the more general theoretical background used in the rest of the book, and the formal definition of the relational model of data. The fundamentals of relational query languages is developed in part B. This part introduces three paradigms for querying relational databases: relational algebra, relational calculus, and Datalog. In chapter 4 the authors begin with the most studied class of queries called conjunctive queries. The adding union (or disjunction) and difference (or negation) yield relational algebra and calculus that are discussed in chapter 5. Obviously, the relationship to the nonrecursive Datalog with negation is presented here. Chapter 6 considers static analysis in optimization of S. Abiteboul, R. Hull, conjunctive and first-order (FO) queries, including some undecibility results for FO queries. On the other hand, the true optimality for conjunctive queries and its subsets is shown here. Part B is closed by chapter 7 which applies theoretical results to practical languages SQL, QBE, and Microsoft Access, respectively.
Part C covers in four chapters database constraints, including well-known functional and join dependencies (chapter 8), inclusion dependencies (chapter 9), and the most general dependencies expressed by certain first-order sentences (chapter 10). Chapter 11 considers dependency theory in connection with several issues of database design.
Part D is devoted to Datalog. Chapters 12 and 13 provide a detailed treatment evaluation of Datalog programs. The next chapter considers languages that provide both negation and recursion. Languages are presented from all three paradigms, i.e. they include algebra + while, calculus + fixpoint, and Datalog with negation. Chapter 15 considers approaches to incorporating negation in Datalog in detail.
More advanced material on the expressiveness and complexity of query languages is presented in part E. Chapters 16 through 18 highlight the aspects of computability and complexity specific to databases. This includes complexity measures for queries and results on the connection between languages and complexity classes. The core material provides chapter 17 discussing FO, fixpoint, and while queries.
Finally, several advanced topics, such as incomplete information (chapter 19), complex values (chapter 20), object databases (chapter 21), and dynamic aspects of databases (chapter 22), are discussed in part F.
The book is provides an excellent overview of the theory including the advanced material most of it has never been presented in book form. Each chapter is completed a number of exercises that contain many other definitions and results of the relevant databases theory. According to the authors, a balance between formalism and intuition was achieved in the book. Both researchers and practitioners can find it useful. As a textbook, it provides a lot of material for various types of databases courses. Undoubtedly, this book belongs to most important and the best books about databases in history.
Reviewer: J.Pokorny (Praha)

68P15 Database theory
68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science