Database system concepts

Cover......Page 1
Title Page......Page 2
Copyright Page......Page 3
Dedication......Page 4
About the Authors......Page 6
Contents......Page 8
Preface......Page 16
Acknowledgments......Page 26
1.1 Database-System Applications......Page 30
1.2 Purpose of Database Systems......Page 34
1.3 View of Data......Page 37
1.4 Database Languages......Page 42
1.5 Database Design......Page 46
1.6 Database Engine......Page 47
1.7 Database and Application Architecture......Page 50
1.8 Database Users and Administrators......Page 53
1.9 History of Database Systems......Page 54
1.10 Summary......Page 58
Exercises......Page 60
Further Reading......Page 62
PART ONE RELATIONAL LANGUAGES......Page 64
2.1 Structure of Relational Databases......Page 66
2.2 Database Schema......Page 70
2.3 Keys......Page 72
2.4 Schema Diagrams......Page 75
2.5 Relational Query Languages......Page 76
2.6 The Relational Algebra......Page 77
2.7 Summary......Page 87
Exercises......Page 89
Further Reading......Page 92
3.1 Overview of the SQL Query Language......Page 94
3.2 SQL Data Definition......Page 95
3.3 Basic Structure of SQL Queries......Page 100
3.4 Additional Basic Operations......Page 108
3.5 Set Operations......Page 114
3.6 Null Values......Page 118
3.7 Aggregate Functions......Page 120
3.8 Nested Subqueries......Page 127
3.9 Modification of the Database......Page 137
3.10 Summary......Page 143
Exercises......Page 144
Further Reading......Page 153
4.1 Join Expressions......Page 154
4.2 Views......Page 166
4.3 Transactions......Page 172
4.4 Integrity Constraints......Page 174
4.5 SQL Data Types and Schemas......Page 182
4.6 Index Definition in SQL......Page 193
4.7 Authorization......Page 194
4.8 Summary......Page 202
Exercises......Page 205
Further Reading......Page 209
5.1 Accessing SQL from a Programming Language......Page 212
5.2 Functions and Procedures......Page 227
5.3 Triggers......Page 235
5.4 Recursive Queries......Page 242
5.5 Advanced Aggregation Features......Page 248
5.6 Summary......Page 260
Exercises......Page 261
Further Reading......Page 267
PART TWO DATABASE DESIGN......Page 268
6.1 Overview of the Design Process......Page 270
6.2 The Entity-Relationship Model......Page 273
6.3 Complex Attributes......Page 278
6.4 Mapping Cardinalities......Page 281
6.5 Primary Key......Page 285
6.6 Removing Redundant Attributes in Entity Sets......Page 290
6.7 Reducing E-R Diagrams to Relational Schemas......Page 293
6.8 Extended E-R Features......Page 300
6.9 Entity-Relationship Design Issues......Page 308
6.10 Alternative Notations for Modeling Data......Page 314
6.11 Other Aspects of Database Design......Page 320
6.12 Summary......Page 321
Exercises......Page 323
Further Reading......Page 329
7.1 Features of Good Relational Designs......Page 332
7.2 Decomposition Using Functional Dependencies......Page 337
7.3 Normal Forms......Page 342
7.4 Functional-Dependency Theory......Page 349
7.5 Algorithms for Decomposition Using Functional Dependencies......Page 359
7.6 Decomposition Using Multivalued Dependencies......Page 365
7.7 More Normal Forms......Page 370
7.8 Atomic Domains and First Normal Form......Page 371
7.9 Database-Design Process......Page 372
7.10 Modeling Temporal Data......Page 376
7.11 Summary......Page 380
Exercises......Page 382
Further Reading......Page 389
PART THREE APPLICATION DESIGN AND DEVELOPMENT......Page 392
8.1 Semi-structured Data......Page 394
8.2 Object Orientation......Page 405
8.3 Textual Data......Page 411
8.4 Spatial Data......Page 416
8.5 Summary......Page 423
Exercises......Page 426
Further Reading......Page 430
9.1 Application Programs and User Interfaces......Page 432
9.2 Web Fundamentals......Page 434
9.3 Servlets......Page 440
9.4 Alternative Server-Side Frameworks......Page 445
9.5 Client-Side Code and Web Services......Page 450
9.6 Application Architectures......Page 458
9.7 Application Performance......Page 463
9.8 Application Security......Page 466
9.9 Encryption and Its Applications......Page 476
9.10 Summary......Page 482
Exercises......Page 484
Further Reading......Page 491
PART FOUR BIG DATA ANALYTICS......Page 494
10.1 Motivation......Page 496
10.2 Big Data Storage Systems......Page 501
10.3 The MapReduce Paradigm......Page 512
10.4 Beyond MapReduce: Algebraic Operations......Page 523
10.5 Streaming Data......Page 529
10.6 Graph Databases......Page 537
10.7 Summary......Page 540
Exercises......Page 542
Further Reading......Page 545
11.1 Overview of Analytics......Page 548
11.2 Data Warehousing......Page 550
11.3 Online Analytical Processing......Page 556
11.4 Data Mining......Page 569
11.5 Summary......Page 579
Exercises......Page 581
Further Reading......Page 584
PART FIVE STORAGE MANAGEMENT AND INDEXING......Page 586
12.1 Overview of Physical Storage Media......Page 588
12.2 Storage Interfaces......Page 591
12.3 Magnetic Disks......Page 592
12.4 Flash Memory......Page 596
12.5 RAID......Page 599
12.6 Disk-Block Access......Page 606
12.7 Summary......Page 609
Exercises......Page 611
Further Reading......Page 613
13.1 Database Storage Architecture......Page 616
13.2 File Organization......Page 617
13.3 Organization of Records in Files......Page 624
13.4 Data-Dictionary Storage......Page 631
13.5 Database Buffer......Page 633
13.6 Column-Oriented Storage......Page 640
13.7 Storage Organization in Main-Memory Databases......Page 644
13.8 Summary......Page 646
Exercises......Page 648
Further Reading......Page 650
14.1 Basic Concepts......Page 652
14.2 Ordered Indices......Page 654
14.3 B+-Tree Index Files......Page 663
14.4 B+-Tree Extensions......Page 679
14.5 Hash Indices......Page 687
14.6 Multiple-Key Access......Page 690
14.7 Creation of Indices......Page 693
14.8 Write-Optimized Index Structures......Page 694
14.9 Bitmap Indices......Page 699
14.10 Indexing of Spatial and Temporal Data......Page 701
14.11 Summary......Page 706
Exercises......Page 708
Further Reading......Page 712
PART SIX QUERY PROCESSING AND OPTIMIZATION......Page 716
15.1 Overview......Page 718
15.2 Measures of Query Cost......Page 721
15.3 Selection Operation......Page 724
15.4 Sorting......Page 730
15.5 Join Operation......Page 733
15.6 Other Operations......Page 748
15.7 Evaluation of Expressions......Page 753
15.8 Query Processing in Memory......Page 760
15.9 Summary......Page 763
Exercises......Page 765
Further Reading......Page 769
16.1 Overview......Page 772
16.2 Transformation of Relational Expressions......Page 776
16.3 Estimating Statistics of Expression Results......Page 786
16.4 Choice of Evaluation Plans......Page 795
16.5 Materialized Views......Page 807
16.6 Advanced Topics in Query Optimization......Page 812
16.7 Summary......Page 816
Exercises......Page 818
Further Reading......Page 823
PART SEVEN TRANSACTION MANAGEMENT......Page 826
17.1 Transaction Concept......Page 828
17.2 A Simple TransactionModel......Page 830
17.3 Storage Structure......Page 833
17.4 Transaction Atomicity and Durability......Page 834
17.5 Transaction Isolation......Page 836
17.6 Serializability......Page 841
17.7 Transaction Isolation and Atomicity......Page 848
17.8 Transaction Isolation Levels......Page 850
17.9 Implementation of Isolation Levels......Page 852
17.10 Transactions as SQL Statements......Page 855
17.11 Summary......Page 857
Exercises......Page 860
Further Reading......Page 863
18.1 Lock-Based Protocols......Page 864
18.2 Deadlock Handling......Page 878
18.3 Multiple Granularity......Page 882
18.4 Insert Operations, Delete Operations, and Predicate Reads......Page 886
18.5 Timestamp-Based Protocols......Page 890
18.6 Validation-Based Protocols......Page 895
18.7 Multiversion Schemes......Page 898
18.8 Snapshot Isolation......Page 901
18.9 Weak Levels of Consistency in Practice......Page 909
18.10 Advanced Topics in Concurrency Control......Page 912
18.11 Summary......Page 923
Exercises......Page 928
Further Reading......Page 933
19.1 Failure Classification......Page 936
19.2 Storage......Page 937
19.3 Recovery and Atomicity......Page 941
19.4 Recovery Algorithm......Page 951
19.5 Buffer Management......Page 955
19.6 Failure with Loss of Non-Volatile Storage......Page 959
19.7 High Availability Using Remote Backup Systems......Page 960
19.8 Early Lock Release and Logical Undo Operations......Page 964
19.9 ARIES......Page 970
19.10 Recovery in Main-Memory Databases......Page 976
19.11 Summary......Page 977
Exercises......Page 981
Further Reading......Page 985
PART EIGHT PARALLEL AND DISTRIBUTED DATABASES......Page 988
20.1 Overview......Page 990
20.2 Centralized Database Systems......Page 991
20.3 Server System Architectures......Page 992
20.4 Parallel Systems......Page 999
20.5 Distributed Systems......Page 1015
20.6 Transaction Processing in Parallel and Distributed Systems......Page 1018
20.7 Cloud-Based Services......Page 1019
20.8 Summary......Page 1024
Exercises......Page 1027
Further Reading......Page 1030
21.1 Overview......Page 1032
21.2 Data Partitioning......Page 1033
21.3 Dealing with Skew in Partitioning......Page 1036
21.4 Replication......Page 1042
21.5 Parallel Indexing......Page 1046
21.6 Distributed File Systems......Page 1048
21.7 Parallel Key-Value Stores......Page 1052
21.8 Summary......Page 1061
Exercises......Page 1062
Further Reading......Page 1065
22.1 Overview......Page 1068
22.2 Parallel Sort......Page 1070
22.3 Parallel Join......Page 1072
22.4 Other Operations......Page 1077
22.5 Parallel Evaluation of Query Plans......Page 1081
22.6 Query Processing on Shared-Memory Architectures......Page 1090
22.7 Query Optimization for Parallel Execution......Page 1093
22.8 Parallel Processing of Streaming Data......Page 1099
22.9 Distributed Query Processing......Page 1105
22.10 Summary......Page 1115
Exercises......Page 1118
Further Reading......Page 1122
Chapter 23 Parallel and Distributed Transaction Processing......Page 1126
23.1 Distributed Transactions......Page 1127
23.2 Commit Protocols......Page 1129
23.3 Concurrency Control in Distributed Databases......Page 1140
23.4 Replication......Page 1150
23.5 Extended Concurrency Control Protocols......Page 1158
23.6 Replication with Weak Degrees of Consistency......Page 1162
23.7 Coordinator Selection......Page 1175
23.8 Consensus in Distributed Systems......Page 1179
23.9 Summary......Page 1191
Exercises......Page 1194
Further Reading......Page 1197
PART NINE ADVANCED TOPICS......Page 1202
24.1 Bloom Filter......Page 1204
24.2 Log-Structured Merge Tree and Variants......Page 1205
24.3 Bitmap Indices......Page 1211
24.4 Indexing of Spatial Data......Page 1215
24.5 Hash Indices......Page 1219
24.6 Summary......Page 1232
Exercises......Page 1234
Further Reading......Page 1235
Chapter 25 Advanced Application Development......Page 1238
25.1 Performance Tuning......Page 1239
25.2 Performance Benchmarks......Page 1259
25.3 Other Issues in Application Development......Page 1263
25.4 Standardization......Page 1266
25.5 Distributed Directory Systems......Page 1269
25.6 Summary......Page 1272
Exercises......Page 1274
Further Reading......Page 1277
Chapter 26 Blockchain Databases......Page 1280
26.1 Overview......Page 1281
26.2 Blockchain Properties......Page 1283
26.3 Achieving Blockchain Properties via Cryptographic Hash Functions......Page 1288
26.4 Consensus......Page 1292
26.5 Data Management in a Blockchain......Page 1296
26.6 Smart Contracts......Page 1298
26.7 Performance Enhancement......Page 1303
26.8 Emerging Applications......Page 1305
26.9 Summary......Page 1308
Exercises......Page 1309
Further Reading......Page 1311
PART TEN APPENDIX A......Page 1314
Appendix A Detailed University Schema......Page 1316
Index......Page 1328