Chapters marked with an asterisk can be dropped without loss of continuity, and the remaining material in the chapters through Recovery can be covered in a first course that gives a broad introduction to databases. Dependencies between chapters have been kept to a minimum, and other choices of material to emphasize or omit can be made as well. For more on the organization of chapters, click here.
Chapters on Object-Databases, Active and Deductive Databases and Decision Support (OLAP, Data Warehousing and Data Mining) are included, although they are not listed below. (The TOC will be updated to include details of these chapters shortly.)
PREFACE ix
Acknowledgements xiv
Introduction to Database Management Systems 1
1.1 Who Deals with Databases? 3
1.2 Data Models 5
1.3 Levels of Abstraction in a DBMS 7
1.4 The Concept of a Transaction 10
1.5 Structure of a DBMS 14
1.6 Summary 16
Introduction to the Relational Model 19
2.1 Relations 20
2.2 Integrity Constraints 22
2.3 Query Languages 25
2.4 Summary 29
Storing Data: Disks and Files 32
3.1 Disks and Tapes 32
3.2 Disk Space Management 35
3.3 Buffer Manager 37
3.4 Record Formats * 42
3.5 Page Formats * 45
3.6 Files and Access Methods 48
3.7 Mapping Relations to Files 52
3.8 Summary 55
Introduction to File Organizations 60
4.1 Cost Model 61
4.2 Comparison of Three File Organizations 62
4.3 Introduction to Indexes 68
4.4 Summary 76
Tree Structured Indexing 79
5.1 Indexed Sequential Access Method (ISAM) * 79
5.2 B+ Trees: A Dynamic Index Structure 85
5.3 Format of a Node 86
5.4 Search 87
5.5 Insert 89
5.6 Delete * 93
5.7 Duplicates * 98
5.8 B+ Trees in Practice * 99
5.9 Summary 104
Hash-Based Indexing 111
6.1 Static Hashing 112
6.2 Extendible Hashing * 113
6.3 Linear Hashing * 119
6.4 Extendible Hashing vs. Linear Hashing * 125
6.5 Summary 126
External Sorting 133
7.1 Introduction 133
7.2 A Simple Two-Way Merge Sort 134
7.3 External Merge Sort 135
7.4 Using B+ Trees for Sorting * 140
7.5 Summary 144
Relational Algebra and Calculus 147
8.1 Relational Algebra 149
8.2 Relational Calculus 163
8.3 Expressive Power of Algebra vs. Calculus * 170
8.4 Summary 172
SQL: The Query Language 176
9.1 The Form of a Basic SQL Query 178
9.2 UNION, INTERSECT and EXCEPT 184
9.3 Nested Queries 187
9.4 Aggregate Operators 193
9.5 Null Values * 202
9.6 Embedded SQL * 205
9.7 Cursors * 208
9.8 Dynamic SQL * 212
9.9 Summary 213
Creating and Modifying Relations in SQL 219
10.1 Introduction to The Data Definition Language (DDL) 219
10.2 Integrity Constraints 221
10.3 Inserting, Deleting and Updating Rows 226
10.4 Summary 231
Security and Views 234
11.1 Views 236
11.2 Access Control 240
11.3 Discretionary Access Control * 241
11.4 Mandatory Access Control * 251
11.5 Additional Issues Related to Security * 255
11.6 Summary 260
Query-By-Example (QBE) 265
12.1 Introduction 265
12.2 Basic QBE Queries 266
12.3 Queries Over Multiple Relations 268
12.4 Negation in the Relation-name Column 269
12.5 Aggregates 270
12.6 Conditions Box 271
12.7 Unnamed Columns 274
12.8 Updates 275
12.9 Division in QBE, Relational Completeness * 277
12.10 Summary 279
Implementation of Relational Operations 282
13.1 Introduction 282
13.2 The Selection Operation 284
13.3 The Join Operation 291
13.4 The Projection Operation * 307
13.5 The Set Operations * 311
13.6 Aggregate Operations * 312
13.7 The Impact of Buffering 314
13.8 Summary 315
Relational Query Optimization 322
14.1 An Example Illustrating Query Optimization 324
14.2 Overview of Relational Query Optimization 330
14.3 Statistics and Reduction Factors * 336
14.4 Relational Algebra Equivalences * 339
14.5 Enumeration of Alternative Plans * 343
14.6 Nested Subqueries * 356
14.7 A Note on Other Approaches to Query Optimization * 359
14.8 Summary 359
Conceptual Database Design and the ER Model 368
15.1 The Entity-Relationship Model 369
15.2 Additional Features of the ER Model 375
15.3 Conceptual Design Using the ER Model 387
15.4 Conceptual Design for Large Enterprises 398
15.5 Summary 399
Schema Refinement and Normal Forms for Relations 407
16.1 Functional Dependencies 409
16.2 Motivating Examples 410
16.3 Reasoning About FDs 416
16.4 Normal Forms 419
16.5 Decompositions 423
16.6 Normalization 428
16.7 Other Kinds of Dependencies * 435
16.8 Summary 441
Physical Database Design and Database Tuning 449
17.1 Introduction 449
17.2 Overview of Index Selection 452
17.3 Basic Examples Illustrating Choice of Indexes 455
17.4 Clustering and Indexing * 457
17.5 Indexes on Multiple-Attribute Search Keys * 463
17.6 Indexes that Enable Index-Only Plans * 464
17.7 Overview of Database Tuning 467
17.8 Choices in Tuning the Conceptual Schema * 470
17.9 Tuning Queries and Views 475
17.10 Impact of Concurrency * 477
17.11 Summary 478
Concurrency Control 489
18.1 Transactions and Schedules 490
18.2 Notions of Consistency 492
18.3 Lock-Based Concurrency Control 496
18.4 Lock Management * 503
18.5 Specialized Locking Techniques * 510
18.6 Transaction Support in SQL-92 * 516
18.7 Concurrency Control Without Locking * 520
18.8 Summary 525
Crash Recovery and Transaction Rollback 532
19.1 Overview of ARIES 533
19.2 Normal Execution * 534
19.3 Recovering From a System Crash * 541
19.4 Media Recovery * 550
19.5 Other Algorithms, Interaction with Concurrency Control * 550
19.6 Summary 552
Parallel and Distributed Databases 557
20.1 Parallel Databases 558
20.2 Introduction to Distributed Databases 562
20.3 Distributed DBMS Architectures 563
20.4 Storing Data 565
20.5 Distributed Catalog Management 567
20.6 Distributed Query Optimization and Processing 569
20.7 Updating Distributed Data 576
20.8 Distributed Transaction Management 581
20.9 Distributed Concurrency Control 582
20.10 Distributed Recovery 585
20.11 Summary 590
REFERENCES 600
INDEX 627
July 12, 1996
Raghu Ramakrishnan [raghu@cs.wisc.edu]