Database Systems: The Complete Book

Hector Garcia-Molina is the L. Bosack and S. Lerner Professor of Computer Science and Electrical Engineering at Stanford University. His research interests include digital libraries, information integration, and database applications on the Internet. He was a recipient of the SIGMOD Innovations Award and a member of PITAC (President's Information-Technology Advisory Council). He currently serves on the Board of Directors of Oracle Corp. Jeffrey D. Ullman is the Stanford W. Ascherman Professor of Computer Science (emeritus) at Stanford University. He is the author or co-author of 16 books, including Elements of ML Programming. His research interests include data mining, information integration, and electronic education. He is a member of the National Academy of Engineering, and recipient of a Guggenheim Fellowship, the Karl V. Karlstom Outstanding Educator Award, the SIGMOD Contributions and Edgar F. Codd Innovations Awards, and the Knuth Prize.Jennifer Widom is Professor of Computer Science and Electrical Engineering at Stanford University. Her research interests span many aspects of nontraditional data management. She is an ACM Fellow and a member of the National Academy of Engineering, she received the ACM SIGMOD Edgar F. Codd Innovations award in 2007 and was a Guggenheim Fellow in 2000, and she has served on a variety of program committees, advisory boards, and editorial boards.

• TABLE OF CONTENTS  1 The Worlds of Database Systems1.1 The Evolution of Database Systems1.1.1 Early Database Management Systems1.1.2 Relational Database Systems1.1.3 Smaller and Smaller Systems1.1.4 Bigger and Bigger Systems1.1.5 Information Integration1.2 Overview of a Database Management System1.2.1 Data-Definition Language Commands1.2.2 Overview of Query Processing1.2.3 Storage and Buffer Management1.2.4 Transaction Processing1.2.5 The Query Processor1.3 Outline of Database-System Studies1.4 References for Chapter 1  PART I: Relational Database Modeling  2 The Relational Model of Data2.1 An Overview of Data Models2.1.1 What is a Data Model?2.1.2 Important Data Models2.1.3 The Relational Model in Brief2.1.4 The Semistructured Model in Brief2.1.5 Other Data Models2.1.6 Comparison of Modeling Approaches2.2 Basics of the Relational Model2.2.1 Attributes2.2.2 Schemas2.2.3 Tuples2.2.4 Domains2.2.5 Equivalent Representations of a Relation2.2.6 Relation Instances2.2.7 Keys of Relations2.2.8 An Example Database Schema2.2.9 Exercises for Section 2.22.3 Defining a Relation Schema in SQL2.3.1 Relations in SQL2.3.2 Data Types2.3.3 Simple Table Declarations2.3.4 Modifying Relation Schemas2.3.5 Default Values2.3.6 Declaring Keys2.3.7 Exercises for Section 2.32.4 An Algebraic Query Language2.4.1 Why Do We Need a Special Query Language?2.4.2 What is an Algebra?2.4.3 Overview of Relational Algebra2.4.4 Set Operations on Relations2.4.5 Projection2.4.6 Selection2.4.7 Cartesian Product2.4.8 Natural Joins2.4.9 Theta-Joins2.4.10 Combining Operations to Form Queries2.4.11 Naming and Renaming2.4.12 Relationships Among Operations2.4.13 A Linear Notation for Algebraic Expressions2.4.14 Exercises for Section 2.42.5 Constraints on Relations2.5.1 Relational Algebra as a Constraint Language2.5.2 Referential Integrity Constraints2.5.3 Key Constraints2.5.4 Additional Constraint Examples2.5.5 Exercises for Section 2.52.6 Summary of Chapter 22.7 References for Chapter 23 Design Theory for Relational Databases3.1 Functional Dependencies3.1.1 Definition of Functional Dependency3.1.2 Keys of Relations3.1.3 Superkeys3.1.4 Exercises for Section 3.13.2 Rules About Functional Dependencies3.2.1 Reasoning About Functional Dependencies3.2.2 The Splitting/Combining Rule3.2.3 Trivial Functional Dependencies3.2.4 Computing the Closure of Attributes3.2.5 Why the Closure Algorithm Works3.2.6 The Transitive Rule3.2.7 Closing Sets of Function