Database system concepts

Cover......Page 1
Title Page......Page 2
Copyright......Page 3
Contents......Page 6
1.1 Database-System Applications......Page 28
1.2 Purpose of Database Systems......Page 30
1.3 View of Data......Page 33
1.4 Database Languages......Page 36
1.5 Relational Databases......Page 39
1.6 Database Design......Page 42
1.7 Data Storage and Querying......Page 47
1.8 Transaction Management......Page 49
1.9 Database Architecture......Page 50
1.10 Data Mining and Information Retrieval......Page 52
1.11 Specialty Databases......Page 53
1.12 Database Users and Administrators......Page 54
1.13 History of Database Systems......Page 56
1.14 Summary......Page 58
Exercises......Page 61
Bibliographical Notes......Page 62
PART ONE: RELATIONAL DATABASES......Page 64
2.1 Structure of Relational Databases......Page 66
2.2 Database Schema......Page 69
2.3 Keys......Page 72
2.4 Schema Diagrams......Page 73
2.5 Relational Query Languages......Page 74
2.6 Relational Operations......Page 75
2.7 Summary......Page 79
Exercises......Page 81
Bibliographical Notes......Page 82
3.1 Overview of the SQL Query Language......Page 84
3.2 SQL Data Definition......Page 85
3.3 Basic Structure of SQL Queries......Page 90
3.4 Additional Basic Operations......Page 101
3.5 Set Operations......Page 106
3.6 Null Values......Page 110
3.7 Aggregate Functions......Page 111
3.8 Nested Subqueries......Page 117
3.9 Modification of the Database......Page 125
3.10 Summary......Page 131
Exercises......Page 135
Bibliographical Notes......Page 139
4.1 Join Expressions......Page 140
4.2 Views......Page 147
4.3 Transactions......Page 154
4.4 Integrity Constraints......Page 155
4.5 SQL Data Types and Schemas......Page 163
4.6 Authorization......Page 170
4.7 Summary......Page 177
Exercises......Page 182
Bibliographical Notes......Page 183
5.1 Accessing SQL From a Programming Language......Page 184
5.2 Functions and Procedures......Page 200
5.3 Triggers......Page 207
5.4 Recursive Queries**......Page 214
5.5 Advanced Aggregation Features**......Page 219
5.6 OLAP**......Page 224
5.7 Summary......Page 236
Exercises......Page 239
Bibliographical Notes......Page 243
6.1 The Relational Algebra......Page 244
6.2 The Tuple Relational Calculus......Page 266
6.3 The Domain Relational Calculus......Page 272
6.4 Summary......Page 275
Exercises......Page 279
Bibliographical Notes......Page 281
PART TWO: DATABASE DESIGN......Page 284
7.1 Overview of the Design Process......Page 286
7.2 The Entity-Relationship Model......Page 289
7.3 Constraints......Page 296
7.4 Removing Redundant Attributes in Entity Sets......Page 299
7.5 Entity-Relationship Diagrams......Page 301
7.6 Reduction to Relational Schemas......Page 310
7.7 Entity-Relationship Design Issues......Page 317
7.8 Extended E-R Features......Page 322
7.9 Alternative Notations for Modeling Data......Page 331
7.10 Other Aspects of Database Design......Page 337
7.11 Summary......Page 340
Exercises......Page 346
Bibliographical Notes......Page 348
8.1 Features of Good Relational Designs......Page 350
8.2 Atomic Domains and First Normal Form......Page 354
8.3 Decomposition Using Functional Dependencies......Page 356
8.4 Functional-Dependency Theory......Page 365
8.5 Algorithms for Decomposition......Page 375
8.6 Decomposition Using Multivalued Dependencies......Page 382
8.7 More Normal Forms......Page 387
8.8 Database-Design Process......Page 388
8.9 Modeling Temporal Data......Page 391
8.10 Summary......Page 394
Exercises......Page 399
Bibliographical Notes......Page 401
9.1 Application Programs and User Interfaces......Page 402
9.2 Web Fundamentals......Page 404
9.3 Servlets and JSP......Page 410
9.4 Application Architectures......Page 418
9.5 Rapid Application Development......Page 423
9.6 Application Performance......Page 427
9.7 Application Security......Page 429
9.8 Encryption and Its Applications......Page 438
9.9 Summary......Page 444
Exercises......Page 448
Bibliographical Notes......Page 453
PART THREE: DATA STORAGE AND QUERYING......Page 454
10.1 Overview of Physical Storage Media......Page 456
10.2 Magnetic Disk and Flash Storage......Page 459
10.3 RAID......Page 468
10.4 Tertiary Storage......Page 476
10.5 File Organization......Page 478
10.6 Organization of Records in Files......Page 484
10.7 Data-Dictionary Storage......Page 489
10.8 Database Buffer......Page 491
10.9 Summary......Page 495
Exercises......Page 499
Bibliographical Notes......Page 500
11.1 Basic Concepts......Page 502
11.2 Ordered Indices......Page 503
11.3 B[sub(+)]-Tree Index Files......Page 512
11.4 B[sub(+)]-Tree Extensions......Page 527
11.5 Multiple-Key Access......Page 533
11.6 Static Hashing......Page 536
11.7 Dynamic Hashing......Page 542
11.8 Comparison of Ordered Indexing and Hashing......Page 550
11.9 Bitmap Indices......Page 551
11.10 Index Definition in SQL......Page 555
11.11 Summary......Page 556
Exercises......Page 561
Bibliographical Notes......Page 563
12.1 Overview......Page 564
12.2 Measures of Query Cost......Page 567
12.3 Selection Operation......Page 568
12.4 Sorting......Page 573
12.5 Join Operation......Page 576
12.6 Other Operations......Page 590
12.7 Evaluation of Expressions......Page 594
12.8 Summary......Page 599
Exercises......Page 603
Bibliographical Notes......Page 604
13.1 Overview......Page 606
13.2 Transformation of Relational Expressions......Page 609
13.3 Estimating Statistics of Expression Results......Page 617
13.4 Choice of Evaluation Plans......Page 625
13.5 Materialized Views**......Page 634
13.6 Advanced Topics in Query Optimization**......Page 639
13.7 Summary......Page 642
Exercises......Page 647
Bibliographical Notes......Page 649
PART FOUR: TRANSACTION MANAGEMENT......Page 652
14.1 Transaction Concept......Page 654
14.2 A Simple Transaction Model......Page 656
14.3 Storage Structure......Page 659
14.4 Transaction Atomicity and Durability......Page 660
14.5 Transaction Isolation......Page 662
14.6 Serializability......Page 668
14.7 Transaction Isolation and Atomicity......Page 673
14.8 Transaction Isolation Levels......Page 675
14.9 Implementation of Isolation Levels......Page 677
14.10 Transactions as SQL Statements......Page 680
14.11 Summary......Page 682
Exercises......Page 685
Bibliographical Notes......Page 687
15.1 Lock-Based Protocols......Page 688
15.2 Deadlock Handling......Page 701
15.3 Multiple Granularity......Page 706
15.4 Timestamp-Based Protocols......Page 709
15.5 Validation-Based Protocols......Page 713
15.6 Multiversion Schemes......Page 716
15.7 Snapshot Isolation......Page 719
15.8 Insert Operations, Delete Operations, and Predicate Reads......Page 724
15.9 Weak Levels of Consistency in Practice......Page 728
15.10 Concurrency in Index Structures**......Page 731
15.11 Summary......Page 735
Exercises......Page 743
Bibliographical Notes......Page 745
16.1 Failure Classification......Page 748
16.2 Storage......Page 749
16.3 Recovery and Atomicity......Page 753
16.4 Recovery Algorithm......Page 762
16.5 Buffer Management......Page 765
16.6 Failure with Loss of Nonvolatile Storage......Page 770
16.7 Early Lock Release and Logical Undo Operations......Page 771
16.8 ARIES**......Page 777
16.9 Remote Backup Systems......Page 783
16.10 Summary......Page 786
Exercises......Page 791
Bibliographical Notes......Page 793
PART FIVE: SYSTEM ARCHITECTURE......Page 794
17.1 Centralized and Client–Server Architectures......Page 796
17.2 Server System Architectures......Page 799
17.3 Parallel Systems......Page 804
17.4 Distributed Systems......Page 811
17.5 Network Types......Page 815
17.6 Summary......Page 818
Exercises......Page 820
Bibliographical Notes......Page 821
18.1 Introduction......Page 824
18.2 I/O Parallelism......Page 825
18.3 Interquery Parallelism......Page 829
18.4 Intraquery Parallelism......Page 830
18.5 Intraoperation Parallelism......Page 831
18.6 Interoperation Parallelism......Page 840
18.7 Query Optimization......Page 841
18.8 Design of Parallel Systems......Page 842
18.9 Parallelism on Multicore Processors......Page 844
18.10 Summary......Page 846
Exercises......Page 850
Bibliographical Notes......Page 851
19.1 Homogeneous and Heterogeneous Databases......Page 852
19.2 Distributed Data Storage......Page 853
19.3 Distributed Transactions......Page 857
19.4 Commit Protocols......Page 859
19.5 Concurrency Control in Distributed Databases......Page 866
19.6 Availability......Page 874
19.7 Distributed Query Processing......Page 881
19.8 Heterogeneous Distributed Databases......Page 884
19.9 Cloud-Based Databases......Page 888
19.10 Directory Systems......Page 897
19.11 Summary......Page 902
Exercises......Page 909
Bibliographical Notes......Page 910
PART SIX: DATA WAREHOUSING, DATA MINING, AND INFORMATION RETRIEVAL......Page 912
20.1 Decision-Support Systems......Page 914
20.2 Data Warehousing......Page 916
20.3 Data Mining......Page 920
20.4 Classification......Page 921
20.5 Association Rules......Page 931
20.6 Other Types of Associations......Page 933
20.7 Clustering......Page 934
20.8 Other Forms of Data Mining......Page 935
20.9 Summary......Page 936
Exercises......Page 939
Bibliographical Notes......Page 941
21.1 Overview......Page 942
21.2 Relevance Ranking Using Terms......Page 944
21.3 Relevance Using Hyperlinks......Page 947
21.4 Synonyms, Homonyms, and Ontologies......Page 952
21.5 Indexing of Documents......Page 954
21.6 Measuring Retrieval Effectiveness......Page 956
21.7 Crawling and Indexing the Web......Page 957
21.8 Information Retrieval: Beyond Ranking of Pages......Page 958
21.9 Directories and Categories......Page 962
21.10 Summary......Page 964
Exercises......Page 967
Bibliographical Notes......Page 968
PART SEVEN: SPECIALTY DATABASES......Page 970
22.1 Overview......Page 972
22.2 Complex Data Types......Page 973
22.3 Structured Types and Inheritance in SQL......Page 976
22.4 Table Inheritance......Page 981
22.5 Array and Multiset Types in SQL......Page 983
22.6 Object-Identity and Reference Types in SQL......Page 988
22.7 Implementing O-R Features......Page 990
22.8 Persistent Programming Languages......Page 991
22.10 Object-Oriented versus Object-Relational......Page 1000
22.11 Summary......Page 1002
Exercises......Page 1005
Bibliographical Notes......Page 1007
23.1 Motivation......Page 1008
23.2 Structure of XML Data......Page 1013
23.3 XML Document Schema......Page 1017
23.4 Querying and Transformation......Page 1025
23.5 Application Program Interfaces to XML......Page 1035
23.6 Storage of XML Data......Page 1036
23.7 XML Applications......Page 1043
23.8 Summary......Page 1046
Exercises......Page 1050
Bibliographical Notes......Page 1051
PART EIGHT: ADVANCED TOPICS......Page 1054
24.1 Performance Tuning......Page 1056
24.2 Performance Benchmarks......Page 1072
24.3 Other Issues in Application Development......Page 1075
24.4 Standardization......Page 1078
24.5 Summary......Page 1083
Exercises......Page 1085
Bibliographical Notes......Page 1086
25.1 Motivation......Page 1088
25.2 Time in Databases......Page 1089
25.3 Spatial and Geographic Data......Page 1091
25.4 Multimedia Databases......Page 1103
25.5 Mobility and Personal Databases......Page 1106
25.6 Summary......Page 1112
Exercises......Page 1115
Bibliographical Notes......Page 1116
26.1 Transaction-Processing Monitors......Page 1118
26.2 Transactional Workflows......Page 1123
26.3 E-Commerce......Page 1129
26.4 Main-Memory Databases......Page 1132
26.5 Real-Time Transaction Systems......Page 1135
26.6 Long-Duration Transactions......Page 1136
26.7 Summary......Page 1142
Exercises......Page 1145
Bibliographical Notes......Page 1146
PART NINE: CASE STUDIES......Page 1148
27.1 Introduction......Page 1150
27.2 User Interfaces......Page 1151
27.3 SQL Variations and Extensions......Page 1153
27.4 Transaction Management in PostgreSQL......Page 1164
27.5 Storage and Indexing......Page 1173
27.6 Query Processing and Optimization......Page 1178
27.7 System Architecture......Page 1181
Bibliographical Notes......Page 1182
28.1 Database Design and Querying Tools......Page 1184
28.2 SQL Variations and Extensions......Page 1185
28.3 Storage and Indexing......Page 1189
28.4 Query Processing and Optimization......Page 1199
28.5 Concurrency Control and Recovery......Page 1207
28.6 System Architecture......Page 1210
28.7 Replication, Distribution, and External Data......Page 1215
28.8 Database Administration Tools......Page 1216
Bibliographical Notes......Page 1218
29.1 Overview......Page 1220
29.2 Database-Design Tools......Page 1221
29.3 SQL Variations and Extensions......Page 1222
29.4 Storage and Indexing......Page 1227
29.5 Multidimensional Clustering......Page 1230
29.6 Query Processing and Optimization......Page 1234
29.7 Materialized Query Tables......Page 1239
29.8 Autonomic Features in DB2......Page 1241
29.9 Tools and Utilities......Page 1242
29.10 Concurrency Control and Recovery......Page 1244
29.11 System Architecture......Page 1246
29.12 Replication, Distribution, and External Data......Page 1247
29.13 Business Intelligence Features......Page 1248
Bibliographical Notes......Page 1249
30.1 Management, Design, and Querying Tools......Page 1250
30.2 SQL Variations and Extensions......Page 1255
30.3 Storage and Indexing......Page 1260
30.4 Query Processing and Optimization......Page 1263
30.5 Concurrency and Recovery......Page 1268
30.6 System Architecture......Page 1273
30.7 Data Access......Page 1275
30.8 Distributed Heterogeneous Query Processing......Page 1277
30.9 Replication......Page 1278
30.10 Server Programming in .NET......Page 1280
30.11 XML Support......Page 1285
30.12 SQL Server Service Broker......Page 1288
30.13 Business Intelligence......Page 1290
Bibliographical Notes......Page 1294
PART TEN: APPENDICES......Page 1296
A.1 Full Schema......Page 1298
A.2 DDL......Page 1299
A.3 Sample Data......Page 1303
Bibliography......Page 1310
Index......Page 1342