Includes bibliographical references and index.

Contents
Preface xv
Chapter 1 Introduction
1.1 Database System Applications 1
1.2 Database Systems versus File Systems 3
1.3 View of Data 5
1.4 Data Models 7
1.5 Database Languages 11
1.6 Database Users and Administrators 13
1.7 Transaction Management 15
1.8 Database System Structure 16
1.9 Application Architectures 18
1.10 History of Database Systems 18
1.11 Summary 21
Exercises 23
Bibliographical Notes 24
PART 1 DATA MODELS
Chapter 2 Entity-Relationship Model
2.1 Basic Concepts 27
2.2 Constraints 33
2.3 Keys 35
2.4 Design Issues 37
2.5 Entity-Relationship Diagram 42
2.6 Weak Entity Sets 47
2.7 Extended E-R Features 49
2.8 Design of an E-R Database Schema 56
2.9 Reduction of an E-R Schema to Tables 62
2.10 The Unified Modeling Language UML 68
2.11 Summary 70
Exercises 72
Bibliographical Notes 77
Chapter 3 Relational Model
3.1 Structure of Relational Databases 79
3.2 The Relational Algebra 89
3.3 Extended Relational-Algebra Operations 103
3.4 Modification of the Database 111
3.5 Views 113
3.6 The Tuple Relational Calculus 118
3.7 The Domain Relational Calculus 122
3.8 Summary 126
Exercises 127
Bibliographical Notes 131
PART 2 RELATIONAL DATABASES
Chapter 4 SQL
4.1 Background 135
4.2 Basic Structure 137
4.3 Set Operations 144
4.4 Aggregate Functions 146
4.5 Null Values 148
4.6 Nested Subqueries 149
4.7 Views 154
4.8 Complex Queries 155
4.9 Modification of the Database 157
4.10 Joined Relations 163
4.11 Data-Definition Language 168
4.12 Embedded SQL 172
4.13 Dynamic SQL 175
4.14 Other SQL Features 180
4.15 Summary 182
Exercises 183
Bibliographical Notes 186
Chapter 5 Other Relational Languages
5.1 Query-by-Example 189
5.2 Datalog 203
5.3 User Interfaces and Tools 217
5.4 Summary 219
Exercises 220
Bibliographical Notes 223
Chapter 6 Integrity and Security
6.1 Domain Constraints 225
6.2 Referential Integrity 227
6.3 Assertions 232
6.4 Triggers 233
6.5 Security and Authorization 238
6.6 Authorization in SQL 244
6.7 Encryption and Authentication 248
6.8 Summary 250
Exercises 252
Bibliographical Notes 254
Chapter 7 Relational-Database Design
7.1 First Normal Form 257
7.2 Pitfalls in Relational-Database Design 258
7.3 Functional Dependencies 260
7.4 Decomposition 271
7.5 Desirable Properties of Decomposition 275
7.6 Boyce-Codd Normal Form 279
7.7 Third Normal Form 284
7.8 Fourth Normal Form 289
7.9 More Normal Forms 293
7.10 Overall Database Design Process 293
7.11 Summary 297
Exercises 299
Bibliographical Notes 303
PART 3 OBJECT-BASED DATABASES AND XML
Chapter 8 Object-Oriented Databases
8.1 Need for Complex Data Types 307
8.2 The Object-Oriented Data Model 308
8.3 Object-Oriented Languages 318
8.4 Persistent Programming Languages 318
8.5 Persistent C++ Systems 322
8.6 Persistent Java Systems 330
8.7 Summary 331
Exercises 332
Bibliographical Notes 333
Chapter 9 Object-Relational Databases
9.1 Nested Relations 335
9.2 Complex Types 337
9.3 Inheritance 342
9.4 Reference Types 346
9.5 Querying with Complex Types 348
9.6 Functions and Procedures 351
9.7 Object-Oriented versus Object-Relational 356
9.8 Summary 357
Exercises 358
Bibliographical Notes 360
Chapter 10 XML
10.1 Background 361
10.2 Structure of XML Data 364
10.3 XML Document Schema 367
10.4 Querying and Transformation 372
10.5 The Application Program Interface 380
10.6 Storage of XML Data 381
10.7 XML Applications 384
10.8 Summary 386
Exercises 388
Bibliographical Notes 390
PART 4 DATA STORAGE AND QUERYING
Chapter 11 Storage and File Structure
11.1 Overview of Physical Storage Media 393
11.2 Magnetic Disks 396
11.3 RAID 402
11.4 Tertiary Storage 410
11.5 Storage Access 412
11.6 File Organization 415
11.7 Organization of Records in Files 422
11.8 Data-Dictionary Storage 426
11.9 Storage for Object-Oriented Databases 428
11.10 Summary 438
Exercises 440
Bibliographical Notes 443
Chapter 12 Indexing and Hashing
12.1 Basic Concepts 445
12.2 Ordered Indices 446
12.3 B+-Tree Index Files 453
12.4 B-Tree Index Files 464
12.5 Static Hashing 465
12.6 Dynamic Hashing 471
12.7 Comparison of Ordered Indexing and Hashing 477
12.8 Index Definition in SQL 479
12.9 Multiple-Key Access 480
12.10 Summary 487
Exercises 489
Bibliographical Notes 491
Chapter 13 Query Processing
13.1 Overview 493
13.2 Measures of Query Cost 495
13.3 Selection Operation 496
13.4 Sorting 501
13.5 Join Operation 503
13.6 Other Operations 514
13.7 Evaluation of Expressions 518
13.8 Summary 523
Exercises 525
Bibliographical Notes 526
Chapter 14 Query Optimization
14.1 Overview 529
14.2 Estimating Statistics of Expression Results 531
14.3 Transformation of Relational Expressions 537
14.4 Choice of Evaluation Plans 544
14.5 Materialized Views 553
14.6 Summary 557
Exercises 559
Bibliographical Notes 561
PART 5 TRANSACTIONMANAGEMENT
Chapter 15 Transactions
15.1 Transaction Concept 565
15.2 Transaction State 568
15.3 Implementation of Atomicity and Durability 571
15.4 Concurrent Executions 573
15.5 Serializability 576
15.6 Recoverability 582
15.7 Implementation of Isolation 583
15.8 Transaction Definition in SQL 584
15.9 Testing for Serializability 584
15.10 Summary 586
Exercises 588
Bibliographical Notes 590
Chapter 16 Concurrency Control
16.1 Lock-Based Protocols 591
16.2 Timestamp-Based Protocols 604
16.3 Validation-Based Protocols 607
16.4 Multiple Granularity 609
16.5 Multiversion Schemes 612
16.6 Deadlock Handling 615
16.7 Insert and Delete Operations 620
16.8 Weak Levels of Consistency 623
16.9 Concurrency in Index Structures 625
16.10 Summary 629
Exercises 632
Bibliographical Notes 636
Chapter 17 Recovery System
17.1 Failure Classification 639
17.2 Storage Structure 640
17.3 Recovery and Atomicity 644
17.4 Log-Based Recovery 645
17.5 Shadow Paging 653
17.6 Recovery with Concurrent Transactions 657
17.7 Buffer Management 660
17.8 Failure with Loss of Nonvolatile Storage 663
17.9 Advanced Recovery Techniques 664
17.10 Remote Backup Systems 672
17.11 Summary 674
Exercises 677
Bibliographical Notes 679
PART 6 DATABASE SYSTEM ARCHITECTURE
Chapter 18 Database System Architectures
18.1 Centralized and Client-Server Architectures 683
18.2 Server System Architectures 687
18.3 Parallel Systems 691
18.4 Distributed Systems 697
18.5 Network Types 701
18.6 Summary 703
Exercises 705
Bibliographical Notes 707
Chapter 19 Distributed Databases
19.1 Homogeneous and Heterogeneous Databases 709
19.2 Distributed Data Storage 710
19.3 Distributed Transactions 713
19.4 Commit Protocols 716
19.5 Concurrency Control in Distributed Databases 722
19.6 Availability 730
19.7 Distributed Query Processing 735
19.8 Heterogeneous Distributed Databases 738
19.9 Directory Systems 741
19.10 Summary 746
Exercises 749
Bibliographical Notes 752
Chapter 20 Parallel Databases
20.1 Introduction 755
20.2 I/O Parallelism 756
20.3 Interquery Parallelism 760
20.4 Intraquery Parallelism 761
20.5 Intraoperation Parallelism 762
20.6 Interoperation Parallelism 770
20.7 Design of Parallel Systems 772
20.8 Summary 773
Exercises 775
Bibliographical Notes 777
PART 7 OTHER TOPICS
Chapter 21 Application Development and Adminis