Database Management Systems Second edition 4+=+ Raghu Ramakrishnan Johannes Gehrke
CONTENTS PREFACE Part I BASICS 1 INTRODUCTION TO DATABASE SYSTEMS 1.2 A Historical Perspective 1.3 File Systems versus a DBMS 1. 4 Advantages of a DBMs 1345789 1.5 Describing and Storing Data in a DBMS 1.5.1 The Relational model 1.5.2 Levels of Abstraction in a DBMs 1.5.3 Data Independence 14 1.6 Queries in a DBMs 1.7 Transaction Management 1.7.1 Concurrent Execution of Transactions 1.7.2 Incomplete Transactions and System Crashes 1.7. 3 Points to Note 56788 1.8 Structure of a DBMS 1. 9 People Who Deal with Databases 1.10 Points to review 2 THE ENTITY-RELATIONSHIP MODEL 2.1 Overview of Database Design 2.1.1 Beyond the ER Model 2.2 Entities, Attributes, and Entity Sets Relationships and Relationship Sets 2.4 Additional features of the er model 2.4.2 Participation Constraints 2.4.3 Weak entities 2.4.4 Class hierarchies 2.4.5 Aggregation
CONTENTS PREFACE xxii Part I BASICS 1 1 INTRODUCTION TO DATABASE SYSTEMS 3 1.1 Overview 4 1.2 A Historical Perspective 5 1.3 File Systems versus a DBMS 7 1.4 Advantages of a DBMS 8 1.5 Describing and Storing Data in a DBMS 9 1.5.1 The Relational Model 10 1.5.2 Levels of Abstraction in a DBMS 11 1.5.3 Data Independence 14 1.6 Queries in a DBMS 15 1.7 Transaction Management 15 1.7.1 Concurrent Execution of Transactions 16 1.7.2 Incomplete Transactions and System Crashes 17 1.7.3 Points to Note 18 1.8 Structure of a DBMS 18 1.9 People Who Deal with Databases 20 1.10 Points to Review 21 2 THE ENTITY-RELATIONSHIP MODEL 24 2.1 Overview of Database Design 24 2.1.1 Beyond the ER Model 25 2.2 Entities, Attributes, and Entity Sets 26 2.3 Relationships and Relationship Sets 27 2.4 Additional Features of the ER Model 30 2.4.1 Key Constraints 30 2.4.2 Participation Constraints 32 2.4.3 Weak Entities 33 2.4.4 Class Hierarchies 35 2.4.5 Aggregation 37 vii
DATABASE MANAGEMENT SYSTEMS 2.5 Conceptual Database Design With the ER Model 2.5.1 Entity versus Attribute 2.5.2 Entity versus Relationship 2.5.3 Binary versus Ternary Relationships 2.5.4 Aggregation versus Ternary Relationships 2.6 Conceptual Design for Large Enterprises 2. 7 Points to review 3 THE RELATIONAL MODEL 51 3.1 Introduction to the relational model 3.1.1 Creating and Modifying Relations Using SQL-9 Constraints over rela Key Constraints Key Constraints 3.2.3 General Constraints 3.3 Enforcing Integrity Constraints 3.4 Querying Relational Data 3.5 Logical Database Design: ER to relational Entity Sets to Tables elationship Sets(without Constraints) to Tables 3.5.3 Translating Relationship Sets with Key Constraint 3.5.4 Translating Relationship Sets with Participation Constraints 3.5.5 Translating Weak Entity Sets 3.5.6 Translating Class Hierarchies 3.5.7 Translating ER Diagrams with Aggregation 3.5.8 ER to Relational: Additional Examples 3.6 Introduction to views 3.6.1 Views, Data Independe Security 79 3.6.2 Updates on Views 3.7 Destroying/ Altering Tables and Views 3.8 Points to review Part II RELATIONAL QUERIES 4 RELATIONAL ALGEBRA AND CALCULUS 4.1 Preliminaries 4.2.1 Selection and Projection 4.2.2 Set Operations 4.2.4 Joins 4.2.5 Division 4.2.6 More Examples of Relational Algebra Queries
viii Database Management Systems 2.5 Conceptual Database Design With the ER Model 38 2.5.1 Entity versus Attribute 39 2.5.2 Entity versus Relationship 40 2.5.3 Binary versus Ternary Relationships * 41 2.5.4 Aggregation versus Ternary Relationships * 43 2.6 Conceptual Design for Large Enterprises * 44 2.7 Points to Review 45 3 THE RELATIONAL MODEL 51 3.1 Introduction to the Relational Model 52 3.1.1 Creating and Modifying Relations Using SQL-92 55 3.2 Integrity Constraints over Relations 56 3.2.1 Key Constraints 57 3.2.2 Foreign Key Constraints 59 3.2.3 General Constraints 61 3.3 Enforcing Integrity Constraints 62 3.4 Querying Relational Data 64 3.5 Logical Database Design: ER to Relational 66 3.5.1 Entity Sets to Tables 67 3.5.2 Relationship Sets (without Constraints) to Tables 67 3.5.3 Translating Relationship Sets with Key Constraints 69 3.5.4 Translating Relationship Sets with Participation Constraints 71 3.5.5 Translating Weak Entity Sets 73 3.5.6 Translating Class Hierarchies 74 3.5.7 Translating ER Diagrams with Aggregation 75 3.5.8 ER to Relational: Additional Examples * 76 3.6 Introduction to Views 78 3.6.1 Views, Data Independence, Security 79 3.6.2 Updates on Views 79 3.7 Destroying/Altering Tables and Views 82 3.8 Points to Review 83 Part II RELATIONAL QUERIES 89 4 RELATIONAL ALGEBRA AND CALCULUS 91 4.1 Preliminaries 91 4.2 Relational Algebra 92 4.2.1 Selection and Projection 93 4.2.2 Set Operations 94 4.2.3 Renaming 96 4.2.4 Joins 97 4.2.5 Division 99 4.2.6 More Examples of Relational Algebra Queries 100
Contents 4. 3 Relational Calculus 4.3.1 Tuple Relational Calculus 10 4.3.2 Domain Relational Calculus 4.4 Expressive Power of Algebra and Calculus 14 4.5 Points to review 115 5 SQL: QUERIES, PROGRAMMING, TRIGGERS 119 5.2 The Form of a Basic SQL Query 5.2.1 Examples of Basic SQL Queries 5.2.2 Expressions and Strings in the SELECT Command 12 5. 3 UNION. INTERSECT and EXCEPT 5.4 Nested Queries 32 5.4.1 Introduction to Nested Queries 5.4.2 Correlated Nested Queries 5.4.3 Set-Comparison Operators 5.4.4 More Examples of Nested Que 5.5 Aggregate Operator 5.5.1 The GROUP BY and HAVING Clauses 140 5.5.2 More Examples of Aggregate Queries 5.6 Null values 5.6.1 Comparisons Using Null values 147 5.6.2 Logical Connectives AND. OR and NOT 5.6.3 Impact on SQL Constructs 148 5.6.4 Outer Joins 5.6.5 Disallowing Null values 150 5.7 Embedded SQL 5.7.1 Declaring Variables and Exceptions 5.7.2 Embedding SQL Statements 5. 8 Cursors 5.8.1 Basic Cursor Definition and Usage 153 5.8.2 Properties of Cursors 155 5.9 Dynamic SQL 5.10 ODBC and JDBC 157 5.10.1 Architecture 5.10.2 An Example Using JDBC 159 5.11 Complex Integrity Constraints in SQL-92 5.11.1 Constraints over a Single Table 5.11.2 Domain Constraints 5.11.3 Assertions: ICs over Several Tables 5.12 Triggers and Active Database 5.12.1 Examples of Triggers in SQL 5.13 Designing Active Databases 5.13. 1 Why Triggers Can Be Hard to Understand
Contents ix 4.3 Relational Calculus 106 4.3.1 Tuple Relational Calculus 107 4.3.2 Domain Relational Calculus 111 4.4 Expressive Power of Algebra and Calculus * 114 4.5 Points to Review 115 5 SQL: QUERIES, PROGRAMMING, TRIGGERS 119 5.1 About the Examples 121 5.2 The Form of a Basic SQL Query 121 5.2.1 Examples of Basic SQL Queries 126 5.2.2 Expressions and Strings in the SELECT Command 127 5.3 UNION, INTERSECT, and EXCEPT 129 5.4 Nested Queries 132 5.4.1 Introduction to Nested Queries 132 5.4.2 Correlated Nested Queries 134 5.4.3 Set-Comparison Operators 135 5.4.4 More Examples of Nested Queries 136 5.5 Aggregate Operators 138 5.5.1 The GROUP BY and HAVING Clauses 140 5.5.2 More Examples of Aggregate Queries 143 5.6 Null Values * 147 5.6.1 Comparisons Using Null Values 147 5.6.2 Logical Connectives AND, OR, and NOT 148 5.6.3 Impact on SQL Constructs 148 5.6.4 Outer Joins 149 5.6.5 Disallowing Null Values 150 5.7 Embedded SQL * 150 5.7.1 Declaring Variables and Exceptions 151 5.7.2 Embedding SQL Statements 152 5.8 Cursors * 153 5.8.1 Basic Cursor Definition and Usage 153 5.8.2 Properties of Cursors 155 5.9 Dynamic SQL * 156 5.10 ODBC and JDBC * 157 5.10.1 Architecture 158 5.10.2 An Example Using JDBC 159 5.11 Complex Integrity Constraints in SQL-92 * 161 5.11.1 Constraints over a Single Table 161 5.11.2 Domain Constraints 162 5.11.3 Assertions: ICs over Several Tables 163 5.12 Triggers and Active Databases 164 5.12.1 Examples of Triggers in SQL 165 5.13 Designing Active Databases 166 5.13.1 Why Triggers Can Be Hard to Understand 167
DATABASE MANAGEMENT SYSTEMS 5.13.2 Constraints versus Triggers 5.13.3 Other Uses of Triggers 5.14 Points to review 6 QUERY-BY-EXAMPLE (QBE 6.1 Introduction 6.2 Basic QBE Queries 6.2.1 Other Features: Duplicates, Ordering Answers 6.3 Queries over Multiple relations 6.4 Negation in the Relation-Name Column 6.5 Aggregates 6. 6 The Conditions box 6.6.1 And/Or Queries 6.7 Unnamed Columns 6.8 Updates 6.8.1 Restrictions on Update Commands 6.9 Division and Relational Completeness 187 6.10 Points to review Part III DATA STORAGE AND INDEXING 7 STORING DATA: DISKS AND FILES 195 7.1 The Memory Hierarchy 7.1.1 Magnetic Disks 7.1.2 Performance Implications of Disk Structure 7.2 RAID 7.2.1 Data Striping 7.2.2 Redundancy 7.2.3 Levels of Redundancy 7. 2. 4 Choice of RAID Levels 7.3 Disk Space Management 7.3.1 Keeping Track of Free Blocks 7.3.2 Using OS File Systems to Manage Disk Space 000 7.4 Buffer Manager 7.4.1 Buffer Replacement Policies 7.5 7.4.2 Buffer Management in DBMS versus OS 212 Files and Indexes 7.5. 1 Heap Files 7. 5.2 Introduction to Indexes 7.6 Page Formats 218 7. 6.1 Fixed-Length records 7.6.2 Variable-Length Records 219 7.7 Record Formats
x Database Management Systems 5.13.2 Constraints versus Triggers 167 5.13.3 Other Uses of Triggers 168 5.14 Points to Review 168 6 QUERY-BY-EXAMPLE (QBE) 177 6.1 Introduction 177 6.2 Basic QBE Queries 178 6.2.1 Other Features: Duplicates, Ordering Answers 179 6.3 Queries over Multiple Relations 180 6.4 Negation in the Relation-Name Column 181 6.5 Aggregates 181 6.6 The Conditions Box 183 6.6.1 And/Or Queries 184 6.7 Unnamed Columns 185 6.8 Updates 185 6.8.1 Restrictions on Update Commands 187 6.9 Division and Relational Completeness * 187 6.10 Points to Review 189 Part III DATA STORAGE AND INDEXING 193 7 STORING DATA: DISKS AND FILES 195 7.1 The Memory Hierarchy 196 7.1.1 Magnetic Disks 197 7.1.2 Performance Implications of Disk Structure 199 7.2 RAID 200 7.2.1 Data Striping 200 7.2.2 Redundancy 201 7.2.3 Levels of Redundancy 203 7.2.4 Choice of RAID Levels 206 7.3 Disk Space Management 207 7.3.1 Keeping Track of Free Blocks 207 7.3.2 Using OS File Systems to Manage Disk Space 207 7.4 Buffer Manager 208 7.4.1 Buffer Replacement Policies 211 7.4.2 Buffer Management in DBMS versus OS 212 7.5 Files and Indexes 214 7.5.1 Heap Files 214 7.5.2 Introduction to Indexes 216 7.6 Page Formats * 218 7.6.1 Fixed-Length Records 218 7.6.2 Variable-Length Records 219 7.7 Record Formats * 221