《database system implementation = 数据库系统实现 (英文版） P653》求取 ⇩

1Introduction to DBMS Implementation1

1.1Introducing: The Megatron 2000 Database System2

1.1.1 Megatron 2000 Implementation Details2

1.1.2 How Megatron 2000 Executes Queries4

1.1.3 What's Wrong With Megatron 2000?5

1.2Overview of a Database Management System6

1.2.1 Data-Definition Language Commands6

1.2.2 Overview of Query Processing8

1.2.3 Main-Memory Buffers and the Buffer Manager8

1.2.4 Transaction Processing9

1.2.5 The Query Processor10

1.3Outline of This Book11

1.3.1 Prerequisites11

1.3.2 Storage-Management Overview12

1.3.3 Query-Processing Overview13

1.3.4 Transaction-Processing Overview13

1.3.5 Information Integration Overview13

1.4Review of Database Models and Languages14

1.4.1 Relational Model Review14

1.4.2 SQL Review15

1.4.3 Relational and Object-Oriented Data18

1.5 Summary of Chapter119

1.6 References for Chapter120

2Data Storage21

2.1The Memory Hierarchy22

2.1.1 Cache22

2.1.2 Main Memory23

2.1.3 Virtual Memory24

2.1.4 Secondary Storage25

2.1.5 Tertiary Storage27

2.1.6 Volatile and Nonvolatile Storage28

2.1.7 Exercises for Section 2.129

2.2Disks30

2.2.1 Mechanics of Disks30

2.2.2 The Disk Controller32

2.2.3 Disk Storage Characteristics32

2.2.4 Disk Access Characteristics34

2.2.5 Writing Blocks38

2.2.6 Modifying Blocks39

2.2.7 Exercises for Section 2.239

2.3Using Secondary Storage Effectively40

2.3.1 The I/O Model of Computation41

2.3.2 Sorting Data in Secondary Storage42

2.3.3 Merge-Sort43

2.3.4 Two-Phase, Multiway Merge-Sort44

2.3.5 Extension of Multiway Merging to Larger Relations47

2.3.6 Exercises for Section 2.348

2.4Improving the Access Time of Secondary Storage49

2.4.1 Organizing Data by Cylinders51

2.4.2 Using Multiple Disks52

2.4.3 Mirroring Disks53

2.4.4 Disk Scheduling and the Elevator Algorithm54

2.4.5 Prefetching and Large-Scale Buffering58

2.4.6 Summary of Strategies and Tradeoffs59

2.4.7 Exercises for Section 2.461

2.5Disk Failures63

2.5.1 Intermittent Failure63

2.5.2 Checksums64

2.5.3 Stable Storage65

2.5.4 Error-Handling Capabilities of Stable Storage66

2.5.5 Exercises for Section 2.567

2.6Recovery from Disk Crashes67

2.6.1 The Failure Model for Disks67

2.6.2 Mirroring as a Redundancy Technique68

2.6.3 Parity Blocks69

2.6.4 An Improvement: RAID 573

2.6.5 Coping With Multiple Disk Crashes73

2.6.6 Exercises for Section 2.677

2.7 Summary of Chapter 280

2.8 References for Chapter 282

3 Representing Data Elements83

3.1Data Elements and Fields83

3.1.1 Representing Relational Database Elements84

3.1.2 Representing Objects85

3.1.3 Representing Data Elements86

3.2Records90

3.2.1 Building Fixed-Length Records91

3.2.2 Record Headers93

3.2.3 Packing Fixed-Length Records into Blocks94

3.2.4 Exercises for Section 3.295

3.3Representing Block and Record Addresses96

3.3.1 Client-Server Systems97

3.3.2 Logical and Structured Addresses98

3.3.3 Pointer Swizzling99

3.3.4 Returning Blocks to Disk104

3.3.5 Pinned Records and Blocks105

3.3.6 Exercises for Section 3.3105

3.4Variable-Length Data and Records108

3.4.1 Records With Variable-Length Fields108

3.4.2 Records With Repeating Fields109

3.4.3 Variable-Format Records111

3.4.4 Records That Do Not Fit in a Block112

3.4.5 BLOBS114

3.4.6 Exercises for Section 3.4115

3.5Record Modifications116

3.5.1 Insertion116

3.5.2 Deletion118

3.5.3 Update119

3.5.4 Exercises for Section 3.5119

3.6 Summary of Chapter 3120

3.7 References for Chapter 3122

4Index Structures123

4.1Indexes on Sequential Files124

4.1.1 Sequential Files124

4.1.2 Dense Indexes125

4.1.3 Sparse Indexes128

4.1.4 Multiple Levels of Index129

4.1.5 Indexes With Duplicate Search Keys131

4.1.6 Managing Indexes During Data Modifications133

4.1.7 Exercises for Section 4.1140

4.2Secondary Indexes142

4.2.1 Design of Secondary Indexes142

4.2.2 Applications of Secondary Indexes144

4.2.3 Indirection in Secondary Indexes145

4.2.4 Document Retrieval and Inverted Indexes148

4.2.5 Exercises for Section 4.2151

4.3B-Trees154

4.3.1 The Structure of B-trees154

4.3.2 Applications of B-trees157

4.3.3 Lookup in B-Trees159

4.3.4 Range Queries160

4.3.5 Insertion Into B-Trees161

4.3.6 Deletion From B-Trees163

4.3.7 Efficiency of B-Trees166

4.3.8 Exercises for Section 4.3167

4.4Hash Tables170

4.4.1 Secondary-Storage Hash Tables171

4.4.2 Insertion Into a Hash Table172

4.4.3 Hash-Table Deletion172

4.4.4 Efficiency of Hash Table Indexes173

4.4.5 Extensible Hash Tables174

4.4.6 Insertion Into Extensible Hash Tables175

4.4.7 Linear Hash Tables177

4.4.8 Insertion Into Linear Hash Tables180

4.4.9 Exercises for Section 4.4182

4.5 Summary of Chapter 4184

4.6 References for Chapter 4185

5Multidimensional Indexes187

5.1Applications Needing Multiple Dimensions188

5.1.1 Geographic Information Systems188

5.1.2 Data Cubes189

5.1.3 Multidimensional Queries in SQL190

5.1.4 Executing Range Queries Using Conventional Indexes192

5.1.5 Executing Nearest-Neighbor Queries Using Conventional Indexes193

5.1.6 Other Limitations of Conventional Indexes195

5.1.7 Overview of Multidimensional Index Structures195

5.1.8 Exercises for Section 5.1196

5.2Hash-Like Structures for Multidimensional Data197

5.2.1 Grid Files198

5.2.2 Lookup in a Grid File198

5.2.3 Insertion Into Grid Files199

5.2.4 Performance of Grid Files201

5.2.5 Partitioned Hash Functions204

5.2.6 Comparison of Grid Files and Partitioned Hashing205

5.2.7 Exercises for Section 5.2206

5.3Tree-Like Structures for Multidimensional Data209

5.3.1 Multiple-Key Indexes209

5.3.2 Performance of Multiple-Key Indexes211

5.3.3 kd-Trees212

5.3.4 Operations on kd-Trees213

5.3.5 Adapting kd-Trees to Secondary Storage216

5.3.6 Quad Trees217

5.3.7 R-Trees219

5.3.8 Operations on R-trees219

5.3.9 Exercises for Section 5.3222

5.4Bitmap Indexes225

5.4.1 Motivation for Bitmap Indexes225

5.4.2 Compressed Bitmaps227

5.4.3 Operating on Run-Length-Encoded Bit-Vectors229

5.4.4 Managing Bitmap Indexes230

5.4.5 Exercises for Section 5.4232

5.5 Summary of Chapter 5233

5.6 References for Chapter 5234

6Query Execution237

6.1An Algebra for Queries240

6.1.1 Union, Intersection, and Difference241

6.1.2 The Selection Operator242

6.1.3 The Projection Operator244

6.1.4 The Product of Relations245

6.1.5 Joins246

6.1.6 Duplicate Elimination248

6.1.7 Grouping and Aggregation248

6.1.8 The Sorting Operator251

6.1.9 Expression Trees252

6.1.10 Exercises for Section 6.1254

6.2Introduction to Physical-Query-Plan Operators257

6.2.1 Scanning Tables257

6.2.2 Sorting While Scanning Tables258

6.2.3 The Model of Computation for Physical Operators258

6.2.4 Parameters for Measuring Costs259

6.2.5 I/O Cost for Scan Operators260

6.2.6 Iterators for Implementation of Physical Operators261

6.3One-Pass Algorithms for Database Operations264

6.3.1 One-Pass Algorithms for Tuple-at-a-Time Operations266

6.3.2 One-Pass Algorithms for Unary, Full-Relation Operations267

6.3.3 One-Pass Algorithms for Binary Operations270

6.3.4 Exercises for Section 6.3273

6.4Nested-Loop Joins274

6.4.1 Tuple-Based Nested-Loop Join275

6.4.2 An Iterator for Tuple-Based Nested-Loop Join275

6.4.3 A Block-Based Nested-Loop Join Algorithm275

6.4.4 Analysis of Nested-Loop Join278

6.4.5 Summary of Algorithms so Far278

6.4.6 Exercises for Section 6.4278

6.5Two-Pass Algorithms Based on Sorting279

6.5.1 Duplicate Elimination Using Sorting280

6.5.2 Grouping and Aggregation Using Sorting282

6.5.3 A Sort-Based Union Algorithm283

6.5.4 Sort-Based Algorithms for Intersection and Difference284

6.5.5 A Simple Sort-Based Join Algorithm286

6.5.6 Analysis of Simple Sort-Join287

6.5.7 A More Efficient Sort-Based Join288

6.5.8 Summary of Sort-Based Algorithms289

6.5.9 Exercises for Section 6.5289

6.6Two-Pass Algorithms Based on Hashing291

6.6.1 Partitioning Relations by Hashing292

6.6.2 A Hash-Based Algorithm for Duplicate Elimination293

6.6.3 A Hash-Based Algorithm for Grouping and Aggregation293

6.6.4 Hash-Based Algorithms for Union, Intersection, and Dif-ference294

6.6.5 The Hash-Join Algorithm294

6.6.6 Saving Some Disk I/O's295

6.6.7 Summary of Hash-Based Algorithms297

6.6.8 Exercises for Section 6.6298

6.7Index-Based Algorithms299

6.7.1 Clustering and Nonclustering Indexes299

6.7.2 Index-Based Selection300

6.7.3 Joining by Using an Index303

6.7.4 Joins Using a Sorted Index304

6.7.5 Exercises for Section 6.7306

6.8Buffer Management307

6.8.1 Buffer Management Architecture307

6.8.2 Buffer Management Strategies308

6.8.3 The Relationship Between Physical Operator Selection and Buffer Management310

6.8.4 Exercises for Section 6.8312

6.9Algorithms Using More Than Two Passes313

6.9.1 Multipass Sort-Based Algorithms313

6.9.2 Performance of Multipass, Sort-Based Algorithms314

6.9.3 Multipass Hash-Based Algorithms315

6.9.4 Performance of Multipass Hash-Based Algorithms315

6.9.5 Exercises for Section 6.9316

6.10 Parallel Algorithms for Relational Operations317

6.10.1 Models of Parallelism317

6.10.2 Tuple-at-a-Time Operations in Parallel320

6.10.3 Parallel Algorithms for Full-Relation Operations321

6.10.4 Performance of Parallel Algorithms322

6.10.5 Exercises for Section 6.10324

6.11 Summary of Chapter 6325

6.12 References for Chapter 6327

7The Query Compiler329

7.1Parsing330

7.1.1 Syntax Analysis and Parse Trees330

7.1.2 A Grammar for a Simple Subset of SQL331

7.1.3 The Preprocessor336

7.1.4 Exercises for Section 7.1337

7.2Algebraic Laws for Improving Query Plans337

7.2.1 Commutative and Associative Laws338

7.2.2 Laws Involving Selection340

7.2.3 Pushing Selections343

7.2.4 Laws Involving Projection345

7.2.5 Laws About Joins and Products348

7.2.6 Laws Involving Duplicate Elimination348

7.2.7 Laws Involving Grouping and Aggregation349

7.2.8 Exercises for Section 7.2351

7.3From Parse Trees to Logical Query Plans354

7.3.1 Conversion to Relational Algebra354

7.3.2 Removing Subqueries From Conditions355

7.3.3 Improving the Logical Query Plan362

7.3.4 Grouping Associative/Commutative Operators364

7.3.5 Exercises for Section 7.3365

7.4Estimating the Cost of Operations366

7.4.1 Estimating Sizes of Intermediate Relations367

7.4.2 Estimating the Size of a Projection368

7.4.3 Estimating the Size of a Selection369

7.4.4 Estimating the Size of a Join371

7.4.5 Natural Joins With Multiple Join Attributes374

7.4.6 Joins of Many Relations375

7.4.7 Estimating Sizes for Other Operations378

7.4.8 Exercises for Section 7.4379

7.5Introduction to Cost-Based Plan Selection380

7.5.1 Obtaining Estimates for Size Parameters381

7.5.2 Incremental Computation of Statistics384

7.5.3 Heuristics for Reducing the Cost of Logical Query Plans385

7.5.4 Approaches to Enumerating Physical Plans388

7.5.5 Exercises for Section 7.5391

7.6Choosing an Order for Joins393

7.6.1 Significance of Left and Right Join Arguments393

7.6.2 Join Trees394

7.6.3 Left-Deep Join Trees395

7.6.4 Dynamic Programming to Select a Join Order and Grouping398

7.6.5 Dynamic Programming With More Detailed Cost Functions402

7.6.6 A Greedy Algorithm for Selecting a Join Order403

7.6.7 Exercises for Section 7.6404

7.7Completing the Physical-Query-Plan Selection406

7.7.1 Choosing a Selection Method406

7.7.2 Choosing a Join Method409

7.7.3 Pipelining Versus Materialization409

7.7.4 Pipelining Unary Operations410

7.7.5 Pipelining Binary Operations411

7.7.6 Notation for Physical Query Plans414

7.7.7 Ordering of Physical Operations417

7.7.8 Exercises for Section 7.7418

7.8 Summary of Chapter 7419

7.9 References for Chapter 7421

8Coping With System Failures423

8.1Issues and Models for Resilient Operation424

8.1.1 Failure Modes424

8.1.2 More About Transactions426

8.1.3 Correct Execution of Transactions427

8.1.4 The Primitive Operations of Transactions429

8.1.5 Exercises for Section 8.1432

8.2 Undo Logging432

8.2.1Log Records433

8.2.2 The Undo-Logging Rules434

8.2.3 Recovery Using Undo Logging436

8.2.4 Checkpointing439

8.2.5 Nonquiescent Checkpointing440

8.2.6 Exercises for Section 8.2444

8.3Redo Logging445

8.3.1 The Redo-Logging Rule446

8.3.2 Recovery With Redo Logging447

8.3.3 Checkpointing a Redo Log448

8.3.4 Recovery With a Checkpointed Redo Log450

8.3.5 Exercises for Section 8.3451

8.4Undo/Redo Logging451

8.4.1 The Undo/Redo Rules452

8.4.2 Recovery With Undo/Redo Logging453

8.4.3 Checkpointing an Undo/Redo Log454

8.4.4 Exercises for Section 8.4456

8.5Protecting Against Media Failures457

8.5.1 The Archive458

8.5.2 Nonquiescent Archiving459

8.5.3 Recovery Using an Archive and Log461

8.5.4 Exercises for Section 8.5462

8.6 Summary of Chapter 8462

8.7 References for Chapter 8464

9Concurrency Control467

9.1Serial and Serializable Schedules468

9.1.1 Schedules468

9.1.2 Serial Schedules469

9.1.3 Serializable Schedules470

9.1.4 The Effect of Transaction Semantics471

9.1.5 A Notation for Transactions and Schedules473

9.1.6 Exercises for Section 9.1474

9.2Conflict-Serializability475

9.2.1 Conflicts475

9.2.2 Precedence Graphs and a Test for Conflict-Serializability476

9.2.3 Why the Precedence-Graph Test Works479

9.2.4 Exercises for Section 9.2481

9.3Enforcing Serializability by Locks483

9.3.1 Locks483

9.3.2 The Locking Scheduler485

9.3.3 Two-Phase Locking486

9.3.4 Why Two-Phase Locking Works487

9.3.5 Exercises for Section 9.3488

9.4Locking Systems With Several Lock Modes490

9.4.1 Shared and Exclusive Locks491

9.4.2 Compatibility Matrices493

9.4.3 Upgrading Locks494

9.4.4 Update Locks495

9.4.5 Increment Locks497

9.4.6 Exercises for Section 9.4499

9.5An Architecture for a Locking Scheduler502

9.5.1 A Scheduler That Inserts Lock Actions502

9.5.2 The Lock Table504

9.5.3 Exercises for Section 9.5507

9.6Managing Hierarchies of Database Elements508

9.6.1 Locks With Multiple Granularity508

9.6.2 Warning Locks509

9.6.3 Phantoms and Handling Insertions Correctly512

9.6.4 Exercises for Section 9.6514

9.7The Tree Protocol514

9.7.1 Motivation for Tree-Based Locking514

9.7.2 Rules for Access to Tree-Structured Data515

9.7.3 Why the Tree Protocol Works516

9.7.4 Exercises for Section 9.7520

9.8Concurrency Control by Timestamps521

9.8.1 Timestamps521

9.8.2 Physically Unrealizable Behaviors522

9.8.3 Problems With Dirty Data523

9.8.4 The Rules for Timestamp-Based Scheduling525

9.8.5 Multiversion Timestamps527

9.8.6 Timestamps and Locking528

9.8.7 Exercises for Section 9.8530

9.9Concurrency Control by Validation530

9.9.1 Architecture of a Validation-Based Scheduler531

9.9.2 The Validation Rules532

9.9.3 Comparison of Three Concurrency-Control Mechanisms535

9.9.4 Exercises for Section 9.9536

9.10 Summary of Chapter 9536

9.11 References for Chapter 9539

10 More About Transaction Management541

10.1 Transactions that Read Uncommitted Data541

10.1.1 The Dirty-Data Problem542

10.1.2 Cascading Rollback544

10.1.3 Managing Rollbacks545

10.1.4 Group Commit546

10.1.5 Logical Logging548

10.1.6 Exercises for Section 10.1551

10.2 View Serializability552

10.2.1 View Equivalence552

10.2.2 Polygraphs and the Test for View-Serializability553

10.2.3 Testing for View-Serializability556

10.2.4 Exercises for Section 10.2557

10.3 Resolving Deadlocks558

10.3.1 Deadlock Detection by Timeout558

10.3.2 The Waits-For Graph559

10.3.3 Deadlock Prevention by Ordering Elements561

10.3.4 Detecting Deadlocks by Timestamps563

10.3.5 Comparison of Deadlock-Management Methods566

10.3.6 Exercises for Section 10.3566

10.4 Distributed Databases568

10.4.1 Distribution of Data568

10.4.2 Distributed Transactions570

10.4.3 Data Replication570

10.4.4 Distributed Query Optimization571

10.4.5 Exercises for Section 10.4572

10.5 Distributed Commit572

10.5.1 Supporting Distributed Atomicity573

10.5.2 Two-Phase Commit573

10.5.3 Recovery of Distributed Transactions576

10.5.4 Exercises for Section 10.5578

10.6 Distributed Locking579

10.6.1 Centralized Lock Systems579

10.6.2 A Cost Model for Distributed Locking Algorithms579

10.6.3 Locking Replicated Elements581

10.6.4 Primary-Copy Locking581

10.6.5 Global Locks From Local Locks582

10.6.6 Exercises for Section 10.6584

10.7 Long-Duration Transactions584

10.7.1 Problems of Long Transactions585

10.7.2 Sagas587

10.7.3 Compensating Transactions588

10.7.4 Why Compensating Transactions Work590

10.7.5 Exercises for Section 10.7590

10.8 Summary of Chapter 10591

10.9 References for Chapter 10593

11 Information Integration595

11.1 Modes of Information Integration595

11.1.1 Problems of Information Integration596

11.1.2 Federated Database Systems597

11.1.3 Data Warehouses599

11.1.4 Mediators601

11.1.5 Exercises for Section 11.1604

11.2 Wrappers in Mediator-Based Systems605

11.2.1 Templates for Query Patterns606

11.2.2 Wrapper Generators607

11.2.3 Filters608

11.2.4 Other Operations at the Wrapper610

11.2.5 Exercises for Section 11.2611

11.3 On-Line Analytic Processing612

11.3.1 OLAP Applications613

11.3.2 A Multidimensional View of OLAP Data614

11.3.3 Star Schemas615

11.3.4 Slicing and Dicing618

11.3.5 Exercises for Section 11.3620

11.4 Data Cubes621

11.4.1 The Cube Operator622

11.4.2 Cube Implementation by Materialized Views625

11.4.3 The Lattice of Views628

11.4.4 Exercises for Section 11.4630

11.5 Data Mining632

11.5.1 Data-Mining Applications632

11.5.2 Association-Rule Mining635

11.5.3 The A-Priori Algorithm636

11.6 Summary of Chapter 11639

11.7 References for Chapter 11640

Index643