Database Management Systems

Database Management Systems (2nd Ed.)......Page 1
Table of Contents......Page 2
Preface......Page 17
Part I: Basics......Page 25
Ch1 Introduction to Database Systems......Page 27
1.1 Overview......Page 28
1.2 A Historical Perspective......Page 29
1.3 File Systems versus a DBMS......Page 31
1.4 Advantages of a DBMS......Page 32
1.5 Describing and Storing Data in a DBMS......Page 33
1.7 Transaction Management......Page 39
1.8 Structure of a DBMS......Page 42
1.9 People Who Deal with Databases......Page 44
1.10 Points to Review......Page 45
Exercises......Page 46
Bibliographical Notes......Page 47
2.1 Overview of Database Design......Page 48
2.2 Entities, Attributes, and Entity Sets......Page 50
2.3 Relationships and Relationship Sets......Page 51
2.4 Additional Features of the ER Model......Page 54
2.5 Conceptual Database Design With the ER Model......Page 62
2.6 Conceptual Design for Large Enterprises*......Page 68
2.7 Points to Review......Page 69
Ch3 Relational Model......Page 75
3.1 Introduction to the Relational Model......Page 76
3.2 Integrity Constraints over Relations......Page 80
3.3 Enforcing Integrity Constraints......Page 86
3.4 Querying Relational Data......Page 88
3.5 Logical Database Design: ER to Relational......Page 90
3.6 Introduction to Views......Page 102
3.7 Destroying/Altering Tables and Views......Page 106
3.8 Points to Review......Page 107
Part II: Relational Queries......Page 113
4.1 Preliminaries......Page 115
4.2 Relational Algebra......Page 116
4.3 Relational Calculus......Page 130
4.4 Expressive Power of Algebra and Calculus*......Page 138
4.5 Points to Review......Page 139
Ch5 SQL: Queries, Programming, Triggers......Page 143
5.2 The Form of a Basic SQL Query......Page 145
5.3 UNION, INTERSECT, and EXCEPT......Page 153
5.4 Nested Queries......Page 156
5.5 Aggregate Operators......Page 162
5.6 Null Values*......Page 171
5.7 Embedded SQL*......Page 174
5.8 Cursors*......Page 177
5.9 Dynamic SQL*......Page 180
5.10 ODBC and JDBC*......Page 181
5.11 Complex Integrity Constraints in SQL-92*......Page 185
5.12 Triggers and Active Databases......Page 188
5.13 Designing Active Databases......Page 190
5.14 Points to Review......Page 192
6.1 Introduction......Page 201
6.2 Basic QBE Queries......Page 202
6.3 Queries over Multiple Relations......Page 204
6.5 Aggregates......Page 205
6.6 The Conditions Box......Page 207
6.8 Updates......Page 209
6.9 Division and Relational Completeness*......Page 211
6.10 Points to Review......Page 213
Part III: Data Storage & Indexing......Page 217
Ch7 Storing Data: Disks & Files......Page 219
7.1 The Memory Hierarchy......Page 220
7.2 RAID......Page 224
7.3 Disk Space Management......Page 231
7.4 Buffer Manager......Page 232
7.5 Files and Indexes......Page 238
7.6 Page Formats*......Page 242
7.7 Record Formats*......Page 245
7.8 Points to Review......Page 248
Ch8 File Organizations & Indexes......Page 254
8.1 Cost Model......Page 255
8.2 Comparison of Three File Organizations......Page 256
8.3 Overview of Indexes......Page 261
8.4 Properties of Indexes......Page 263
8.6 Points to Review......Page 268
Ch9 Tree-Structured Indexing......Page 271
9.1 Indexed Sequential Access Method (ISAM)......Page 272
9.2 B+ Trees: A Dynamic Index Structure......Page 277
9.3 Format of a Node......Page 278
9.4 Search......Page 279
9.5 Insert......Page 281
9.6 Delete*......Page 284
9.7 Duplicates*......Page 289
9.8 B+ Trees in Practice*......Page 290
9.9 Points to Review......Page 296
10.1 Static Hashing......Page 302
10.2 Extendible Hashing*......Page 304
10.3 Linear Hashing*......Page 310
10.4 Extendible Hashing versus Linear Hashing*......Page 315
10.5  Points to Review......Page 316
Part IV: Query Evaluation......Page 323
Ch11 External Sorting......Page 325
11.1 A Simple Two-Way Merge Sort......Page 326
11.2 External Merge Sort......Page 329
11.3 Minimizing I/O Cost versus Number of I/Os......Page 333
11.4 Using B+ Trees for Sorting......Page 336
11.5  Points to Review......Page 339
Ch12 Evaluation of Relational Operators......Page 343
12.1 Introduction to Query Processing......Page 344
12.2 The Selection Operation......Page 345
12.3 General Selection Conditions*......Page 349
12.4 The Projection Operation......Page 353
12.5 The Join Operation......Page 357
12.6 The Set Operations*......Page 373
12.7 Aggregate Operations*......Page 374
12.8 The Impact of Buffering*......Page 376
12.9 Points to Review......Page 377
Ch13 Introduction to Query Optimization......Page 383
13.1 Overview of Relational Query Optimization......Page 384
13.2 System Catalog in a Relational DBMS......Page 389
13.3 Alternative Plans: A Motivating Example......Page 392
13.4 Points to Review......Page 397
Ch14 A Typical Relational Query Optimizer......Page 398
14.1 Translating SQL Queries into Algebra......Page 399
14.2 Estimating the Cost of a Plan......Page 402
14.3 Relational Algebra Equivalences......Page 407
14.4 Enumeration of Alternative Plans......Page 411
14.5 Nested Subqueries......Page 423
14.6 Other Approaches to Query Optimization......Page 426
14.7 Points to Review......Page 427
Part V: Database Design......Page 439
Ch15 Schema Refinement & Normal Forms......Page 441
15.1 Introduction to Schema Refinement......Page 442
15.2 Functional Dependencies......Page 446
15.3 Examples Motivating Schema Refinement......Page 447
15.4 Reasoning about Functional Dependencies......Page 451
15.5 Normal Forms......Page 454
15.6 Decompositions......Page 458
15.7 Normalization......Page 462
15.8 Other Kinds of Dependencies*......Page 468
15.9 Points to Review......Page 474
Ch16 Physical Database Design & Tuning......Page 481
16.1 Introduction to Physical Database Design......Page 482
16.2 Guidelines for Index Selection......Page 484
16.3 Basic Examples of Index Selection......Page 487
16.4 Clustering and Indexing*......Page 489
16.5 Indexes on Multiple-Attribute Search Keys*......Page 494
16.6 Indexes that Enable Index-Only Plans*......Page 495
16.7 Overview of Database Tuning......Page 498
16.8 Choices in Tuning the Conceptual Schema*......Page 501
16.9 Choices in Tuning Queries and Views*......Page 506
16.10 Impact of Concurrency*......Page 508
16.11 DBMS Benchmarking*......Page 509
16.12 Points to Review......Page 511
17.1 Introduction to Database Security......Page 521
17.2 Access Control......Page 522
17.3 Discretionary Access Control......Page 523
17.4 Mandatory Access Control*......Page 532
17.5 Additional Issues Related to Security*......Page 536
17.6 Points to Review......Page 541
Part VI: Transaction Management......Page 545
18.1 The Concept of a Transaction......Page 547
18.2 Transactions and Schedules......Page 550
18.3 Concurrent Execution of Transactions......Page 551
18.4 Lock-Based Concurrency Control......Page 556
18.5 Introduction to Crash Recovery......Page 557
18.6 Points to Review......Page 561
19.1 Lock-Based Concurrency Control Revisited......Page 564
19.2 Lock Management......Page 567
19.3 Specialized Locking Techniques......Page 573
19.4 Transaction Support in SQL-92*......Page 579
19.5 Concurrency Control without Locking......Page 583
19.6 Points to Review......Page 588
20.1 Introduction to ARIES......Page 595
20.2 Recovering from a System Crash......Page 602
20.3 Media Recovery......Page 610
20.4 Other Algorithms and Interaction with Concurrency Control......Page 611
20.5 Points to Review......Page 612
Part VII: Advanced Topics......Page 619
Ch21 Parallel & Distributed Databases......Page 621
21.1 Architectures for Parallel Databases......Page 622
21.2 Parallel Query Evaluation......Page 624
21.3 Parallelizing Individual Operations......Page 626
21.4 Parallel Query Optimization......Page 630
21.5 Introduction to Distributed Databases......Page 631
21.6 Distributed DBMS Architectures......Page 632
21.7 Storing Data in a Distributed DBMS......Page 634
21.8 Distributed Catalog Management......Page 635
21.9 Distributed Query Processing......Page 638
21.10 Updating Distributed Data......Page 643
21.11 Introduction to Distributed Transactions......Page 648
21.12 Distributed Concurrency Control......Page 649
21.13 Distributed Recovery......Page 651
21.14 Points to Review......Page 656
Ch22 Internet Databases......Page 666
22.1 The World Wide Web......Page 667
22.2 Architecture......Page 669
22.3 Beyond HTML......Page 675
22.4 Indexing for Text Search......Page 687
22.5 Ranked Keyword Searches on the Web......Page 691
22.6 Points to Review......Page 695
Ch23 Decision Support......Page 701
23.1 Introduction to Decision Support......Page 702
23.2 Data Warehousing......Page 703
23.3 OLAP......Page 706
23.4 Implementation Techniques for OLAP......Page 714
23.5 Views and Decision Support......Page 718
23.6 Finding Answers Quickly......Page 723
23.7 Points to Review......Page 726
24.1 Introduction to Data Mining......Page 731
24.2 Counting Co-occurrences......Page 732
24.3 Mining for Rules......Page 737
24.4 Tree-Structured Rules......Page 746
24.5 Clustering......Page 750
24.6 Similarity Search over Sequences......Page 753
24.7 Additional Data Mining Tasks......Page 755
24.8  Points to Review......Page 756
Ch25 Object-Database Systems......Page 760
25.1 Motivating Example......Page 761
25.2 User-Defined Abstract Data Types......Page 766
25.3 Structured Types......Page 768
25.4 Objects, Object Identity, and Reference Types......Page 772
25.5 Inheritance......Page 774
25.6 Database Design for an ORDBMS......Page 777
25.7 New Challenges in Implementing an ORDBMS......Page 783
25.8 OODBMS......Page 789
25.9 Comparing RDBMS with OODBMS and ORDBMS......Page 793
25.10 Points to Review......Page 795
26.1 Types of Spatial Data and Queries......Page 801
26.2 Applications Involving Spatial Data......Page 803
26.3 Introduction to Spatial Indexes......Page 805
26.4 Indexing Based on Space-Filling Curves......Page 807
26.5 Grid Files......Page 810
26.6 R Trees: Point and Region Data......Page 813
26.8 Points to Review......Page 819
Ch27 Deductive Databases......Page 823
27.1 Introduction to Recursive Queries......Page 824
27.2 Theoretical Foundations......Page 827
27.3 Recursive Queries with Negation......Page 832
27.4 Efficient Evaluation of Recursive Queries......Page 837
27.5 Points to Review......Page 842
28.1 Advanced Transaction Processing......Page 846
28.2 Integrated Access to Multiple Data Sources......Page 848
28.4 Main Memory Databases......Page 849
28.5 Multimedia Databases......Page 850
28.6 Geographic Information Systems......Page 851
28.7 Temporal and Sequence Databases......Page 852
28.9 Summary......Page 853
A.1 Requirements Analysis......Page 855
A.3 Logical Database Design......Page 856
A.4 Schema Refinement......Page 859
A.5 Physical Database Design......Page 860
A.6 Security......Page 862
A.7 Application Layers......Page 864
B.1 What\'s Available......Page 866
B.2 Overview of Minibase Assignments......Page 867
B.3 Acknowledgments......Page 869
References......Page 871
Subject Index......Page 903
Author Index......Page 920
Backcover......Page 931