Preface 1
1 Introduction 1
1．1 Purpose of Database Systems 1
1．2 View of Data 4
1．3 Data Models 7
1．4 Database Languages 12
1．5 Transaction Management 13
1．6 Storage Management 14
1．7 Database Administrator 15
1．8 Database Users 15
1．9 Overall System Structure 16
1．10 Summary 19
Exercises 20
Bibliographic Notes 20
2．1 Basic Concepts 23
2 Entity-Relationship Model 23
2．2 Design Issues 28
2．3 Mapping Constraints 30
2．4 Keys 34
2．5 Entity-Relationship Diagram 36
2．6 Weak Entity Sets 37
2．7 Extended E-R Features 41
2．8 Design of an E-R Database Schema 47
2．9 Reduction of an E-R Schema to Tables 52
2．10 Summary 58
Exercises 59
Bibliographic Notes 62
3 Relational Model 63
3．1 Structure of Relational Databases 63
3．2 The Relational Algebra 71
3．3 The Tuple Relational Calculus 86
3．4 The Domain Relational Calculus 90
3．5 Extended Relational-Algebra Operatios 94
3．6 Modification of the Database 100
3．7 Views 102
3．8 Summary 106
Exercises 107
Bibliographic Notes 110
4 SQL 111
4．1 Background 111
4．2 Basic Structure 113
4．3 Set Operations 120
4．4 Aggregate Functions 122
4．5 Null Values 124
4．6 Nested Subqueries 125
4．7 Derived Relations 129
4．8 Views 130
4．9 Modification of the Database 131
4．10 Joined Relations 136
4．11 Data-Definition Language 140
4．12 Embedded SQL 145
4．13 Other SQL Features 148
4．14 Summary 148
Exercises 149
Bibliographic Notes 152
5 Other Relational Languages 153
5．1 Query-by-Example 153
5．2 Quel 165
5．3Datalog 174
5．4 Summary 188
Exercises 188
Bibliographic Notes 190
6 Integrity Constraints 193
6．1 Domain Constraints 193
6．2 Referential Integrity 195
6．3 Assertions 200
6．4 Triggers 201
6．5 Functional Dependencies 202
6．6 Summary 210
Exercises 211
Bibliographic Notes 213
7 Relational Database Design 215
7．1 Pitfalls in Relational-Database Design 215
7．2 Decomposition 217
7．3 Normalization Using Functional Dependencies 221
7．4 Normalization Using Multivalued Dependencies 231
7．5 Normalization Using Join Dependencies 239
7．6 Domain-Key Normal Form 242
7．7 Alternative Approaches to Database Design 244
7．8 Summary 246
Exercises 247
Bibliographic Notes 250
8 Object-Oriented Databases 251
8．1 New Database Applications 251
8．2 The object-Oriented Data Model 253
8．3 Object-Oriented Languages 262
8．4 Persistent Programming Languages 263
8．5 Persistent C++ Systems 267
8．6 Summary 271
Exercises 272
Bibliographic Notes 272
9 Object-Relational Databases 275
9．1 Nested Relations 275
9．2 Complex Types and Object Orientation 278
9．3 Querying with Commplex Types 283
9．4 Creation of Complex Values and Objects 287
9．5 Comparison of Object-Oriented and Object-Relational Databases 288
9．6 Summary 289
Exercises 289
Bibliographic Notes 290
10 Storage and File Structure 293
10．1 Overview of Physical Storage Media 293
10．2 Magnetic Disks 296
10．3 RAID 301
10．4 Tertiary Storage 307
10．5 Storage Access 309
10．6 File Organization 312
10．7 Organization of Records in Files 318
10．8 Data-Dictionary Storage 322
10．9 Storage Structures for Object-Oriented Databases 324
10．10 Summary 332
Exercises 333
Bibliographic Notes 336
11 Indexing and Hashing 339
11．1 Basic Concepts 339
11．2 Ordered Indices 340
11．3 B+-Tree Index Files 346
11．4 B-Tree Index Files 356
11．5 Static Hashing 358
11．6 Dynamic Hashing 362
11．7 Comparison of Ordered Indexing and Hashing 369
11．8 Index Definition in SQL 371
11．9 Multiple-Key Access 372
11．10 Summary 377
Exercises 378
Bibliographic Notes 379
12 Query Processing 381
12．1 Overview 381
12．2 Catalog Information for Cost Estimation 384
12．4 Selection Operation 386
12．3 Measures of Query Cost 386
12．5 Sorting 394
12．6 Join Operation 397
12．7 Other Operations 410
12．8 Evaluation of Expressions 413
12．9 Transformation of Relational Expressions 418
12．10 Choice of Evaluation Plans 426
12．11 Summary 432
Exercises 434
Bibliographic Notes 437
13 Transactions 439
13．1 Transaction Concept 439
13．2 Transaction State 443
13．3 Implementation of Atomicity and Durability 445
13．4 Concurrent Executions 447
13．5 Serializability 451
13．6 Recoverability 456
13．7 Implementation of Isolation 457
13．8 Transaction Definition in SQL 458
13．9 Testing for Serializability 459
13．10 Summary 465
Exercises 467
Bibliographic Notes 468
14 Concurrency Control 471
14．1 Lock-Based Protocols 471
14．2 Timestamp-Based Protocols 482
14．3 Validation-Based Protocols 485
14．4 Multiple Granularity 487
14．5 Multiversion Schemes 490
14．6 Deadlock Handling 492
14．7 Insert and Delete Operations 497
14．8 Concurrency in Index Structures 500
14．9 Summary 503
Exercises 504
Bibliographic Notes 508
15 Recovery System 511
15．1 Failure Classification 511
15．2 Storage Structure 512
15．3 Recovery and Atomicity 516
15．4 Log-Based Recovery 517
15．5 Shadow Paging 525
15．6 Recovery with Concurrent Transactions 528
15．7 Buffer Management 531
15．8 Failure with Loss of Nonvolatile Storage 534
15．9 Advanced Recovery Techniques 535
15．10 Summary 539
Exercises 540
Bibliographic Notes 541
16 Database System Architectures 543
16．1 Centralized Systems 544
16．2 Client-Server Systems 545
16．3 Parallel Systems 549
16．4 Distributed Systems 555
16．5 Network Types 558
16．6 Summary 560
Exercises 561
Bibliographic Notes 562
17 Parallel Databases 565
17．1 Introduction 565
17．2 I/O Parallelism 566
17．3 Interquery Parallelism 569
17．4 Intraquery Parallelism 570
17．5 Intraoperation parallelism 571
17．6 Interoperation Parallelism 579
17．7 Design of Parallel Systems 582
Exercises 583
17．8 Summary 583
Bibliographic Notes 585
18 Distributed Databases 587
18．1 Distributed Data Storage 588
18．2 Network Transparency 593
18．3 Distributed Query Processing 596
18．4 Distributed Transaction Model 599
18．5 Commit Protocols 604
18．6 Coordinator Selection 612
18．7 Concurrency Control 613
18．8 Deadlock Handling 617
18．9 Multidatabase Systems 622
18．10 Summary 626
Exercises 628
Bibliographic Notes 631
19．1 Security and Integrity 633
19 Special Topics 633
19．2 Standardization 644
19．3 Performance Benchmarks 647
19．4 Performance Tuning 650
19．5 Time in Databases 655
19．6 User Interfaces 657
19．7 Active Databases 660
19．8 Summary 663
Exercises 664
Bibliographic Notes 666
20 Advanced Transaction Processing 669
20．1 Remote Backup Systems 669
20．2 Transaction-Processing Monitors 672
20．3 High-Performance Transaction Systems 676
20．4 Long-Duration Transactions 679
20．5 Real-Time Transaction Systems 685
20．6 Weak Levels of Consistency 686
20．7 Transactional Workflows 687
20．8 Summary 693
Exercises 694
Bibliographic Notes 695
21 New Applications 697
21．1 Decision-Support Systems 698
21．2 Data Analysis 700
21．3 Data Mining 702
21．4 Data Warehousing 708
21．5 Spatial and Geographic Databases 710
21．6 Multimedia Databases 719
21．7 Mobility and Personal Databases 722
21．8 Information-Retrieval Systems 726
21．9 Distributed Information Systems 731
21．10 The World Wide Web 733
21．11 Summary 740
Exercises 741
Bibliographic Notes 743
A Network Model 747
A．1 Basic Concepts 747
A．2 Data-Structure Diagrams 748
A．3 The DBTG CODASYL Model 750
A．4 Implementation Techniques 752
A．5 Discussion 752
B Hierarchical Model 755
B．1 Basic Concepts 755
B．2 Tree-Structure Diagrams 756
B．3 Implementation Techniques 759
B．4 The IMS Database System 760
B．5 Discussion 761
Bibliography 763
Index 809