Sixth Edition Database System Concepts Abraham Silberschatz.Henry F.Korth.S.Sudarshan
Contents Chapter 1 Introduction 1 3 1.11 Specialty Databases 26 1.4 Database Languages 9 1.12 Database Users and Administrators 27 1.5 Relational Databases 12 1.13 History of Database Systems 29 1.6 Database Design 15 1.14 Summary 31 1.7 Data Storage and Querying 20 Exercises 33 1.8 Transaction Management 22 Bibliographical Notes 35 1.9 Database Architecture 23 PART ONE RELATIONAL DATABASES Chapter 2 Introduction to the Relational Model 2.1 Structure of Relational Databases 39 2.6 Relational Operations 48 22 Database Schema 42 2.7 Summary 52 45 Exercises 2 ma Diagrams 46 Bibliographical Notes55 Relational Query Languages 47 Chapter 3 Introduction to SQL 3.1 Overview of the SQL Query 3.7 Aggregate Functions 84 Language 57 3.8 Nested Subqueries 90 3.2 SOL Data Definition 58 3.9 Modification of the Database 98 3.3 Basic Structure of SOL Oueries 63 3.10 Summary 104 3.4 Additional Basic Operations 74 cise 105 rations Bibliographical Notes 112 3.6 Null Values 83
Contents Chapter 1 Introduction 1.1 Database-System Applications 1 1.2 Purpose of Database Systems 3 1.3 View of Data 6 1.4 Database Languages 9 1.5 Relational Databases 12 1.6 Database Design 15 1.7 Data Storage and Querying 20 1.8 Transaction Management 22 1.9 Database Architecture 23 1.10 Data Mining and Information Retrieval 25 1.11 Specialty Databases 26 1.12 Database Users and Administrators 27 1.13 History of Database Systems 29 1.14 Summary 31 Exercises 33 Bibliographical Notes 35 PART ONE RELATIONAL DATABASES Chapter 2 Introduction to the Relational Model 2.1 Structure of Relational Databases 39 2.2 Database Schema 42 2.3 Keys 45 2.4 Schema Diagrams 46 2.5 Relational Query Languages 47 2.6 Relational Operations 48 2.7 Summary 52 Exercises 53 Bibliographical Notes 55 Chapter 3 Introduction to SQL 3.1 Overview of the SQL Query Language 57 3.2 SQL Data Definition 58 3.3 Basic Structure of SQL Queries 63 3.4 Additional Basic Operations 74 3.5 Set Operations 79 3.6 Null Values 83 3.7 Aggregate Functions 84 3.8 Nested Subqueries 90 3.9 Modification of the Database 98 3.10 Summary 104 Exercises 105 Bibliographical Notes 112 v
Contents Chapter 4 Intermediate SQL 4.1 Join Expressions 113 4.6 Authorization 143 42 Views 120 4.7 Summary 150 4.3 Transactions 127 Exercises 152 4.4 Integrity Constraints 128 Bibliographical Notes 156 45 SQL Data Types and Schemas 136 Chapter 5 Advanced SQI 5.1 Accessing SQL From a Programming d Procedures 173 Exercises 211 5.4 Recursive Queries*187 Bibliographical Notes 216 Chapter 6 Formal Relational Query Languages 6.1 The Relational Algebra 217 6.4 Summary 248 6.2 The Tuple Relational Calculus 239 Exercises 249 6.3 The Domain Relational Calculus 245 Bibliographical Notes 254 PART TWO DATABASE DESIGN Chapter 7 Database Design and the E-R Model 262 7.8 Extended E-R Features 295 7.9At ve Notations for Modeling 269 Data 304 7.10 Other Aspects of Database Design 310 Entity Sets 272 7.1I Summary 313 7.5 Entity-Relationship Diagrams 274 Exercises 315 7.6 Reduction to Relational Schemas 283 Bibliographical Notes 321 7.7 Entity-Relationship Design Issues 290
vi Contents Chapter 4 Intermediate SQL 4.1 Join Expressions 113 4.2 Views 120 4.3 Transactions 127 4.4 Integrity Constraints 128 4.5 SQL Data Types and Schemas 136 4.6 Authorization 143 4.7 Summary 150 Exercises 152 Bibliographical Notes 156 Chapter 5 Advanced SQL 5.1 Accessing SQL From a Programming Language 157 5.2 Functions and Procedures 173 5.3 Triggers 180 5.4 Recursive Queries** 187 5.5 Advanced Aggregation Features** 192 5.6 OLAP** 197 5.7 Summary 209 Exercises 211 Bibliographical Notes 216 Chapter 6 Formal Relational Query Languages 6.1 The Relational Algebra 217 6.2 The Tuple Relational Calculus 239 6.3 The Domain Relational Calculus 245 6.4 Summary 248 Exercises 249 Bibliographical Notes 254 PART TWO DATABASE DESIGN Chapter 7 Database Design and the E-R Model 7.1 Overview of the Design Process 259 7.2 The Entity-Relationship Model 262 7.3 Constraints 269 7.4 Removing Redundant Attributes in Entity Sets 272 7.5 Entity-Relationship Diagrams 274 7.6 Reduction to Relational Schemas 283 7.7 Entity-Relationship Design Issues 290 7.8 Extended E-R Features 295 7.9 Alternative Notations for Modeling Data 304 7.10 Other Aspects of Database Design 310 7.11 Summary 313 Exercises 315 Bibliographical Notes 321
Contents vii Chapter 8 Relational Database Design 8.1 Features of Good Relational 86 Decomposition Using Multivalued igns 323 denci mains and First Normal 8 More Normal Forms 360 Form 327 8.8 Database-Design Process 36 8.3 Decomposition Using Functional 8.9 Modeling Temporal Data 364 Dependencies 329 8.10 Summary 367 8.4 Functional-Dependency Theory 338 Exercises 368 8.5 Algorithms for Decomposition 348 Bibliographical Notes 374 Chapter 9 Application Design and Development 9.1 Application Programs and User 9.6 Application Performance 400 Interfaces 375 9.7 Application Security 402 9.2 Web Fundamentals 377 9.8 Encryption and Its Applications 411 9.3 Servlets and JSP 383 9.9 Summary 417 9.4 Application Architectures 391 Exercises 419 95 Rapid Application Development 396 Bibliographical Notes 426 PART THREE DATA STORAGE AND QUERYING Chapter 10 Storage and File Structure 10.1 Overview of Physical Storage 10.6 Organization of Records in Files 457 Media 429 10.7 Data-Dictionary Storage 462 10.2 Magnetic Disk and Flash Storage 432 10.8 Database Buffer 464 10.3RAD441 10.9 Summary 468 10.4 Tertiary Storage 449 Exercises 470 10.5 File Organization 451 Bibliographical Notes 473 Chapter 11 Indexing and Hashing 11.1 Basic Concepts 475 11.8 Comparison of Ordered Indexing and 11.2 Ordered Indices 476 Hashing 523 11.3 B+-Tree Index Files 485 11.9 Bitmap Indices 524 11.4 B+-Tree Extensions 500 11.10 Index Definition in SQL 528 11.5 Multiple-Key Access 506 1111 Sur 529 11.6 Static Hashi 509 Exe 532 11.7 Dynamic Hashing 515 Bibliographical Notes 536
Contents vii Chapter 8 Relational Database Design 8.1 Features of Good Relational Designs 323 8.2 Atomic Domains and First Normal Form 327 8.3 Decomposition Using Functional Dependencies 329 8.4 Functional-Dependency Theory 338 8.5 Algorithms for Decomposition 348 8.6 Decomposition Using Multivalued Dependencies 355 8.7 More Normal Forms 360 8.8 Database-Design Process 361 8.9 Modeling Temporal Data 364 8.10 Summary 367 Exercises 368 Bibliographical Notes 374 Chapter 9 Application Design and Development 9.1 Application Programs and User Interfaces 375 9.2 Web Fundamentals 377 9.3 Servlets and JSP 383 9.4 Application Architectures 391 9.5 Rapid Application Development 396 9.6 Application Performance 400 9.7 Application Security 402 9.8 Encryption and Its Applications 411 9.9 Summary 417 Exercises 419 Bibliographical Notes 426 PART THREE DATA STORAGE AND QUERYING Chapter 10 Storage and File Structure 10.1 Overview of Physical Storage Media 429 10.2 Magnetic Disk and Flash Storage 432 10.3 RAID 441 10.4 Tertiary Storage 449 10.5 File Organization 451 10.6 Organization of Records in Files 457 10.7 Data-Dictionary Storage 462 10.8 Database Buffer 464 10.9 Summary 468 Exercises 470 Bibliographical Notes 473 Chapter 11 Indexing and Hashing 11.1 Basic Concepts 475 11.2 Ordered Indices 476 11.3 B+-Tree Index Files 485 11.4 B+-Tree Extensions 500 11.5 Multiple-Key Access 506 11.6 Static Hashing 509 11.7 Dynamic Hashing 515 11.8 Comparison of Ordered Indexing and Hashing 523 11.9 Bitmap Indices 524 11.10 Index Definition in SQL 528 11.11 Summary 529 Exercises 532 Bibliographical Notes 536
viii Contents Chapter 12 Query Processing 12.1 Overview 537 12.6 Other Operations 563 12.2 Measures of Query Cost 540 12 7 Evaluation of Exp essions 567 12.3 Selection Operation 541 12.8 Summary 572 12.4 Sorting 546 Exercises 574 12.5 Join Operation 549 Bibliographical Notes577 Chapter 13 Query Optimization 13.1 Overview 579 13.5 Materialized Views**607 13.2 Transformation of Relational 13.6 Advanced Topics in Query Expressions 582 13.3 Estimating Statistics of Expression 13.7S av615 Results 590 Exer 617 13.4 Choice of Evaluation Plans 598 Bibliographical Notes 622 PART FOUR■ TRANSACTION MANAGEMENT Chapter 14 Transactions 14.1 Transaction Concept 627 14.7 Transaction Isolation and 14.2 A Sir mple Tra n Model 629 Atomicity 646 14.3S Str 632 148T on Isolation Levels 648 14.4 T micity and 14.mplementation of i 650 63 1410 SQL Statements 14.5 on Isolation 635 1411 14.6 Serializability 641 Exercises 657 Bibliographical Notes 660 Chapter 15 Concurrency Control 15.8 Inse s,Delete Operations, g674 15.3 Multiple Granularity ate R 69 67 of Consistency in 15.4 Timestamp-Based Protocols 682 Practice 701 15.5 Validation-Based Protocols 686 15.10 Concurrency in Index Structures**704 15.6 Multiversion Schemes 689 15.11 Summary 708 15.7 Snapshot Isolation 692 Exercises 712 Bibliographical Notes 718
viii Contents Chapter 12 Query Processing 12.1 Overview 537 12.2 Measures of Query Cost 540 12.3 Selection Operation 541 12.4 Sorting 546 12.5 Join Operation 549 12.6 Other Operations 563 12.7 Evaluation of Expressions 567 12.8 Summary 572 Exercises 574 Bibliographical Notes 577 Chapter 13 Query Optimization 13.1 Overview 579 13.2 Transformation of Relational Expressions 582 13.3 Estimating Statistics of Expression Results 590 13.4 Choice of Evaluation Plans 598 13.5 Materialized Views** 607 13.6 Advanced Topics in Query Optimization** 612 13.7 Summary 615 Exercises 617 Bibliographical Notes 622 PART FOUR TRANSACTION MANAGEMENT Chapter 14 Transactions 14.1 Transaction Concept 627 14.2 A Simple Transaction Model 629 14.3 Storage Structure 632 14.4 Transaction Atomicity and Durability 633 14.5 Transaction Isolation 635 14.6 Serializability 641 14.7 Transaction Isolation and Atomicity 646 14.8 Transaction Isolation Levels 648 14.9 Implementation of Isolation Levels 650 14.10 Transactions as SQL Statements 653 14.11 Summary 655 Exercises 657 Bibliographical Notes 660 Chapter 15 Concurrency Control 15.1 Lock-Based Protocols 661 15.2 Deadlock Handling 674 15.3 Multiple Granularity 679 15.4 Timestamp-Based Protocols 682 15.5 Validation-Based Protocols 686 15.6 Multiversion Schemes 689 15.7 Snapshot Isolation 692 15.8 Insert Operations, Delete Operations, and Predicate Reads 697 15.9 Weak Levels of Consistency in Practice 701 15.10 Concurrency in Index Structures** 704 15.11 Summary 708 Exercises 712 Bibliographical Notes 718