数据库系统实现(英文版)

图书标准信息

• 作者 Hector Garcia-Molina
• 出版社 机械工业出版社
• 出版时间 2002-01
• 版次 1
• ISBN 9787111091615
• 定价 42.00元
• 装帧 平装
• 开本 其他
• 纸张 胶版纸
• 页数 653页

【目录】

1 Introduction to DBMS Implementation1.1 Introducing: The Megatron 2000 Database System1.1.1 Megatron 2000 Implementation Details1.1.2 How Megatron 2000 Executes Queries1.1.3 What's Wrong With Megatron 2000?1.2 Overview of a Database Management System1.2.1 DataDefinition Language Commands1.2.2 Overview of Query Processing1.2.3 Main--Memory Buffers and the Buffer Manager1.2.4 Thansaction Processing1.2.5 The Query Processor1.3 Outline of This Book1.3.1 Prerequisites1.3.2 Storage-- M anagement Overview1.3.3 Query-Proce8sing Overview1.3.4 Thansaction- P rocessing Overview1.3.5 Information Integration Overview1.4 Review of Database Models and Languages1.4.1 Relational Model Review1.4.2 SQL Review1.4.3 Re1ational and Object-Oriented Data1.5 Summary of Chapter 11.6 References for Chapter 12 Data Storage2.1 The Memory Hierarchy2.1.1 Cache2.1.2 Main Memory2.1.3 Virtual Memory2.1.4 Secondary Storage2.1.5 Tertiary Storage2.1.6 Volatile and Nonvolatile Storage2.1.7 Exercises for Section 2.12.2 Disks2.2.1 Mechanics Of Disks2.2.2 The Disk Controller2.2.3 Disk Storage Characteristics2.2.4 Disk Access Characteristics2.2.5 Writing Blocks2.2.6 Modifying Blocks2.2.7 Exercises for Section 2.22.3 Using Secondary Storage Effectively2.3.1 The I/O Model of Computation2.3.2 Sorting Data in SecondaJry Storage2.3.3 Merge-Sort2.3.4 Two-Phase, Multiway Merge--Sort2.3.5 Extension of Multiway Merging to Larger Relatbos2.3.6 Exercises for Section 2.32.4 Improving the Access Time of Secondary Storage2.4.1 Organizing Data by Cylinders2.4.2 Using Multiple Disks2.4.3 Mirroring Disks2.4.4 Disk Scheduling and the Elevator Algorithm2.4.5 Prefetching and Large-Scale Buffering2.4.6 SummaJry.of Strategies and nadeoffe2.4.7 Exercises fOr Section 2.42.5 Disk Failures2.5.1 1ntermittent Falures2.5.2 Checksums2.5.3 Stable Storage2.5.4 Error-Handling Capabilities of Stable Storage2.5.5 Exercises for Section 2.52.6 Recovery from Disk Crashes2.6.1 The Failure Model for Disks2.6.2 Mirroring as a Redundancy Technique2.6.3 Paxity Blocks2.6.4 An Improvment: RAID 52.6.5 Coping With Multiple Disk Cfashes2.6.6 Exercises for Section 2.62.7 Summary.of ChaPter 22.8 References for ChaPter 23 Representing Datu Elements3.1 Data Elements and Fields3.1.1 Representing Relational Database Elements3.1.2 Representing Objects3.1.3 Representing Data Elements3.2 Records3.2.1 Building Fixed-Length Records3.2.2 Record Headers3.2.3 Packing Fixed-Length Records into Blocks3.2.4 Exercises for Section 3.23.3 Represention Block and Record Addresses3.3.1 Client--Server Systems3.3.2 LogicaJ and Structured Addresses.3.3.3 Pointer Swizzling3.3.4 Returning Blocks to Disk3.3.5 Pinned Records and Blocks3.3.6 Exercises for Section 3.33.4 Variable-Length Data and Records3.4.1 Records With Variable-Length Fields3.4.2 Records With Repeating Fields3.4.3 Variable-Format Records3.4.4 Records That Do Not Fit in a Block3.4.5 BLOBS3.4.6 Exercises for Section 3.43.5 Record Modifications3.5.1 Insertion3.5.2 Deletion3.5.3 Update3.5.4 Exercises for Section 3.53.6 Summary of Chapter 33.7 References for Chapter 34 Index Structure84.1 Indexes on Sequential Files4.1.1 Sequential Files4.1.2 Dense Indexes4.1.3 Sparse Indexes4.1.4 Multiple Levels of Index4.1.5 Indexes With Duplicate Search Keys4.1.6 Managing Indexes During Data Modifications4.1.7 Exercises fOr Section 4.14.2 Secondary Indexes4.2.1 Design of Secondary Indexes4.2.2 Applications of Secondary Indexes4.2.3 Indirection in Secondaxy Indexes4.2.4 Document Retrieval and Inverted Indexes4.2.5 Exercises fOr Section 4.24.3 B-nees4.3.1 The Structure of B--trees4.3.2 Applications of B-trees4.3.3 Lookup in B-Trees4.3.4 Range Queries4.3.5 Insertion Into B-nees4.3.6 Deletion nom B-nees4.3.7 Efficiency of B-Trees4.3.8 Exercises fOr Section 4.34.4 Hash Tables4.4.1 Secondary-Storage Hash Tables4.4.2 Insertion Into a Hash Table4.4.3 Hash-Table Deletion4.4.4 Efficiency of Hash Table Indexes4.4.5 Extensible Hash Tables4.4.6 Insertion Into Extensible Hash Tables4.4.7 Linear Hash Tables4.4.8 Insertion 1nto Linear Hash Tables4.4.9 Exercises fOr Section 4.44.5 Summary Of Chapter 44.6 References for Chapter 45 Multidimensional Indexes5.1 Applications Needing Multiple Dimensions5.1.1 GWaPhic Information System85.1.2 Data Cubes5.1.3 Multidimensional Queries in SQL5.1.4 Executing Range Queries Using Conventional 1ndexes5.1.5 Executing Nearest--Neighbor Queries Using ConventionalIndexes5.1.6 Other Limitations of Conventional Indexes5.1.7 Overview of Multidimensional Index Strllctures5.1.8 Exercises for Section 5.15.2 Hash-Like Structures for Multidimensional Data5.2.1 Grid Files5.2.2 Lookup in a Grid File5.2.3 Insertion Into Grid Files5.2.4 Performance Of Grid Files5.2.5 Patitioned Hash minctions5.2.6 Comparison of Grid Files and Partitioned Hashing5.2.7 Exercises for Section 5.25.3 Thee-Like Structures fOr Multidimensional Data5.3.1 Multiple-Key Indexes5.3.2 Performance of MultiplesKey Indexes5.3.3 kdnees5.3.4 Operations on kdnees5.3.5 AdaPting kdThees to Secondary Storage5.3.6 Quad Thees5.3.7 RTrees5.3.8 Operations on Rtrees5.3.9 Exercises for Section 5.35.4 Bitmap Indexes5.4.1 Motivation for Bitmap Indexes5.4.2 Compressed BitmaPS5.4.3 Operating.on Run-Lengt h- Encoded Bit- Vectors5.4.4 Managing BitmaP Indexes5.4.5 Exercises for Section 5.45.5 Summary of Chapter 55.6 References for Chapter 56 Query Execution6.1 An Algebra for Queries6.1.1 Union, Intersection, and Difference6.1.2 The Selection Operator6.1.3 The Projection Operator6.1.4 The Product of Relations6.1.5 Joins6.1.6 Duplicate Elimination6.1.7 Grouping and Aggregaion6.1.8 The Sorting Operator6.1.9 Expression nees6.1.10 Exercises for Section 6.16.2 Introduction to Physical-Query-Plan Operators6.2.1 Scanning Tables6.2.2 Sorting While Scanning Tables6.2.3 The Model of Computation for Physical Operators6.2.4 Parameters for Measuring Costs6.2.5 I/O Cost for Scan Operators6.2.6 Iterators for Implementation of Physical Operators6.3 One-Pass Algorithms for Database Operations6.3.1 One--Pass Algorithms for TUplesat-aTime Operations6.3.2 One-Pass Algorithms for Unary, FulLRelation Operai6.3.3 One-Pass Algorithms for Binary Operations6.3.4 Exercises for Section 6.36.4 Nested-Loop Joins6.4.1 Tuple-Based Nested-Loop Join6.4.2 An Iterator for Thple--Based Nested--Loop Join6.4.3 A Block-Based Nested--Loop Join Algorithm6.4.4 Analysis of Nested-Loop Join6.4.5 Summary of AlgOrithms so Far6.4.6 Exercises fOr Section 6.46.5 TwcaPass Algorithms Based on Sorting6.5.1 Duplicate Elimination Using Sorting6.5.2 Grouping and Aggregation Using Sorting6.5.3 A Sort-Based Union Algorithm6.5.4 Sort-Based Algorithms for Intersection and Difference6.5.5 A Simple Sort--Based Join Algorithm6.5.6 Analysis of Simple Sort-Join6.5.7 A More Efficient Sort-Based Join6.5.8 Summary Of Sort-Based Algorithms6.5.9 Exercises for Section 6.56.6 Two-Pass AlgOrithms Based on Hashing6.6.1 Partitioning Relations by Hashing6.6.2 A Hash-Based Algorithm for Duplicate Elimination6.6.3 A Hash--Based Algorithm for Grouping and Aggrgation6.6.4 Hash-Based Algorithms for Union, Intersection, and Dif ference6.6.5 The Hash-Join Algorithm6.6.6 Saving Some Disk I/O's6.6.7 Summary of Hash-Based Algorithms6.6.8 Exercises for Section 6.66.7 Index-Based Algorithms6.7.1 Clustering and Nonclustering Indexes6.7.2 Index--Based Selection6.7.3 Joining by Using an Index6.7.4 Joins Using a Sorted Index6.7.5 Exercises for Section 6.76.8 Buffer Management6.8.1 Buffer Management Architecture6.8.2 Buffer Manapement Strategies6.8.3 The Relationship Between Physical Operator Selection and Buffer Management6.8.4 Exercises for Section 6.86.9 Algorithms Using More Than Two Passes6.9.1 Multipass Sort-Based Algorithms6.9.2 Performance of Multipass, Sort--Based Algorithms6.9.3 Multipass Hash-Based Algorithms6.9.4 Performance of Multipass Hash-Based Algorithms6.9.5 Exercises fOr Section 6.96.10 PaxaJlel Algorithms fOr Relational Operations.6.10.1 Models of Paxallelism6.10.2 Tuple-at-aTime Operations in Parallel6.10.3 Parallel Algorithms for Full--Relation Operations6.10.4 Performance of Parallel Algorithms6.10.5 Exercises for Section 6.106.11 SummaJry of Chapter 66.12 References for ChaPter 67 The Query Compiler7.1 Parsing7.1.1 Syntax Analysis and Parse nees7.1.2 A Grammar for a Simple Subset of SQL7.1.3 The Preprocessor7.1.4 Exercises for Section 7.17.2 Algebraic Laws for Improving Query Plans7.2.1 Commutative and Associative Laws7.2.2 Laws Involving Selection7.2.3 Pushing Selections7.2.4 Laws Involving Projection7.2.5 Laws About Joins and Products7.2.6 Laws Involving Duplicate Elimination7.2.7 Laws lnvolving Grouping and Aggregation7.2.8 Exercises for Section 7.27.3 From PaJrse Thees to Logical Query Plans7.3.1 Conversion to Relational Algebra7.3.2 Removing Subqueries nom Conditions7.3.3 Improving the Logical Query Plan7.3.4 Grouping Associative/Commutat ive O perators7.3.5 Exercises for Section 7.37.4 Estimating the Cost of Operations7.4.1 Estimating Sizes of Illtermediate ffelations7.4.2 Estimating the Size of a PrOjectiOn7.4.3 Estimating the Size of a Selectbo7.4.4 Estimating the Size of a Join7.4.5 Natural Joins With Multiple Join Attributes7.4.6 Joins of Many Relations7.4.7 Estim8ting Sizes fOr Other Operations7.4.8 Exercises for Section 7.47.5 Introduction to Cost-Based Plan Selection7.5.1 Obtaining Estimates for Size Parameters7.5.2 Incremental Computation of Statistics7.5.3 Heuristics for Reducing the Cost of Logical Query P7.5.4 Approaches to Enumerating Physical Plans7.5.5 Exercises for Section 7.57.6 Choosing an Order for Joins7.6.1 Significance of Left and mght Join ArgUments7.6.2 Join nees7.6.3 Left-Deep Join nees7.6.4 Dynarnic Programming to Select a Join Order and Gr7.6.5 Dynamic Programming With More Detailed Cost fu7.6.6 A Greedy Algorithm for Selecting a Join Order7.6.7 Exercises for Section 7.67.7 Completing the Physical-Query--Plan Selection7.7.1 Choosing a Selection Method7.7.2 Choosing a Join Method7.7.3 Pipelining Versus Materialization7.7.4 Pipelining Unary Operations7.7.5 Pipelining Binary Operations7.7.6 Notation for Physical Query PlaJns7.7.7 Ordering Of Physical Operations7.7.8 Exercises for Section 7.77.8 Summary of Chapter 77.9 References for ChaPter 78 Coping With System Failures8.1 Issues and Models fOr Resilient Operation8.1.1 Failure Modes8.1.2 More About nansactions8.1.3 Correct Execution of nansactions8.1.4 The Primitive Operations of Transactions8.1.5 Exercises for Section 8.18.2 Undo Logging8.2.1 Log Records8.2.2 The UndthLogging Rules8.2.3 Recovery Using Undo Logging8.2.4 Checkpointing8.2.5 Nonquiescent Checkpointing8.2.6 Exercises for Section 8.28.3 Redo Logging8.3.1 The Redo--Logging Rule8.3.2 RetiOvery With Redo Logging8.3.3 Checkpointing a Redo Log8.3.4 Recovery With a Checkpointed Redo Log8.3.5 Exercises for Section 8.38.4 Undo/Redo Logging8.4.1 The Undo/Redo Rules8.4.2 Recovery With Undo/Redo Logging8.4.3 Checkpointing aJn Undo/Redo Log8.4.4 Exercises for Section 8.48.5 Protecting Against Media Failures8.5.1 The Archive8.5.2 Nonquiescent Archiving8.5.3 Recovery Using an Archive and Log8.5.4 Exercises for Section 8.58.6 Summaxy of Chapter 88.7 References for ChaPter 89 Concurrency Control9.1 Serial and Serializable Schedules9.1.1 Schedules9.1.2 Serial Schedules9.1.3 Serializable Schedules9.1.4 The Effect of Transaction Semantics9.1.5 A Notation for nansactions and Schedules9.1.6 Exercises for Section 9.19.2 Conflict - Serializability9.2.1 Confiicts9.2.2 Precedence Graphs and a Test for Conflict-Serializability9.2.3 Why the Precedence--Graph Test Works9.2.4 Exercises for Section 9.29.3 Enforcing Serializability by Locks9.3.1 Locks9.3.2 The Locking Scheduler9.3.3 Two--Phase Locking9.3.4 Why Two-Phase Locking Works9.3.5 Exercises for Section 9.39.4 Locking Systems With Several Lock Modes9.4.1 Shared and Exclusive Locks9.4.2 Compatibility Matrices9.4.3 Upgrading Locks9.4.4 Update Locks9.4.5 Increment Locks9.4.6 Exercises for Section 9.49.5 An Architecture for a Locking Scheduler9.5.1 A Scheduler That Inserts Lock Actions9.5.2 The Lock Table9.5.3 Exercises for Section 9.59.6 Managing Hierarchies of DatabaJse Elements9.6.1 Locks With Multiple Granularity9.6.2 Warning Locks9.6.3 Phantoms and Handling Insertions Correctly9.6.4 Exercises fOr Section 9-69.7 The Tree Protocol9.7.1 Motivation for nee-Based Locking9.7.2 Rules for Access to Tree-Structured Data9.7.3 Why the nee Protocol Works9.7.4 Exercises for Section 9.79.8 Concurrency COntrol by TimeStamps9.8.1 Timestamps9.8.2 Physically Unrealizable Behaviors9.8.3 Problems With Dirty Data9.8.4 The Rules fOr Timestamp-Based Scheduling9.8.5 Multiversion Timestamps9.8.6 Timestaznps and Locking9.8.7 Exercises for Section 9.89.9 Concurrency Control by Validation9.9.1 Architecture of a Validation-Based Scheduler9.9.2 The Validation Rules9.9.3 Comparison Of Three Concurrency-Control Mechanisms9.9.4 Exercises for Section 9.99.10 Summary Of ChaPter 99.11 References for ChaPter 910 More About nansaction Managemeot10.1 Thansactions that Read Uncommitted Data10.1.1 The Dirty-Data Problem10.1.2 Cascading Rollback10.1.3 Managing Rollbacks10.1.4 Group Commit10.1.5 Logical Logging10.1.6 Exercises for Section 10.110.2 View Serializability10.2.1 View Equivalence10.2.2 PolygraPhs and the Test for View-Serializability10.2.3 Testing for View-Serializability10.2.4 Exercises for Section 10.210.3 Resolving Deadlocks10.3.1 Deedlock Detection by Timeout10.3.2 The Waits-For GraPh10.3.3 Deadlock Prevention by Ordering Elements10.3.4 Detecting Deadlocks by Timestamps10.3.5 Comparison of Deadloch Management Methods10.3.6 Exercises for Section 10.310.4 Distributed Databases10.4.1 Distribution of Data10.4.2 Distributed nansactions10.4.3 Data Replication10.4.4 Distributed Query Optimization10.4.5 Exercises for SeCtion 10.410.5 Distributed Commit10.5.1 Supporting Distributed Atomicity10.5.2 TwcrPhase Commit10.5.3 Recovery of Distributed' Thansactions10.5.4 Exercises for Section 10.510.6 Distributed Locking10.6.1 Centralized Lock Systems10.6.2 A Cost Model for Distributed Locking Algorithms10.6.3 Locking Replicated Elements10.6.4 Primary-CoPy Locking10.6.5 Global Locks Wom Local Locks10.6.6 Exercises for Section 10.610.7 Long--Duration nansactions10.7.1 Problems of Long nansactions10.7.2 sasas10.7.3 Compensating nansactions10.7.4 Why Compensating nansactions Work10.7.5 Exercises for Section 10.710.8 Summary of ChaPter 1010.9 References for ChaPter 1011 Information Integration11.1 Modes of Information Illtegration11.1.1 Problems of Information Integration11.1.2 Federated Database Systems11.1.3 Data Waehouses11.1.4 Mediators11.1.5 Exercises for Section 11.111.2 WraPpers in Mediator-Based Systems11.2.1 Templates for Query Patterns11.2.2 WraPper Generators11.2.3 Filters11.2.4 Other Operations at the Wrapper11.2.5 Exercises for Section 11.211.3 On--Line AnaJytic Processing11.3.1 OLAP Applications11.3.2 A Multidimensional View of OLAP Data11.3.3 StaJr Schemas11.3.4 Slicing and Dicing11.3.5 Exercises for Section 11.311.4 Data Cubes11.4.1 The Cube Operator11.4.2 Cube Implementation by Materialized Views11.4.3 The Lattice of Views11.4.4 Exercises for Section 11.411.5 Data Mining11.5.1 Data-Mining Applications11.5.2 Association-Rule Mining11.5.3 The A-Priori Algorithm11.6 Summary of Chapter 1111.7 References for Chapter 11Index