Foundations of Databases: The Logical Level

Over the past two decades, the theory concerning the logical level of database management systems has matured and become an elegant and robust piece of science. Foundations of Databases presents indepth coverage of this theory and surveys several emerging topics. Written by three leading researchers, this advanced text presents a unifying and contemporary perspective on the field. A major effort in writing the book has been to highlight the intuitions behind the theoretical development.

Database theory is a relative newcomer to the field of computer science. Early data management systems were based on techniques from several classical areas of computer science, ranging from hardware and operating systems to data structures and programming languages. In the early seventies, a leap of abstraction from file systems produced relational databases and its accompanying theory, with logic as the catalyst. We believe that database theory has matured--that is has emerged as an elegant and robust part of science with its own identity. As such, it embodies its own peculiar brand of wisdom that deserves to be communicated not just to insiders, but to the computer science community at large.

In a nutshell, a database management system is a software system that enables the creation, maintenance, and use of large amounts of data. In contrast with many programming applications, the logical data structure--the "database schema"--used to structure a given data set is usually much smaller than the volume of that set. Furthermore, the data is persistent, evolving over time and surviving multiple invocations of the database management software. To increase usability, concurrent access to the data is usually supported with specialized protocols that guarantee a form of noninterference between interleaved transactions. Importantly, modern database management systems embody a distinction between the logical level and the physical level. The logical level focuses on an abstract representation of the data, along with languages to create, query and modify it; the physical level focuses on the underlying implementation, including the physical layout used to store the data, the indexing and clustering schemes, and the concurrency and recovery protocols.

Database theory has developed primarily around the logical level of database. (A notable exception is concurrency control, which is not addressed in this volume.) A core of fundamental material on the relational model has become well established. It consists primarily of three paradigms for query languages (algebraic, calculus-based, and deductive) and the theory of dependencies. The theory of query languages, including issues of expressiveness and complexity specific to databases, is well developed. The marriage between databases and logic programming produced deductive databases, with the main focus on the deductive query languages. Dependency theory focused initially on formalizing and applying the disparate integrity constraints that commonly arise in practice, and it went on to relate constraints with query optimization and to develop a unifying perspective for them.