Three well-known computer scientis　at Stanford UniveEity-Hector Garcia-Molina. Jeffrey D. Ullman, and Jennifer Widom-have written one of the most comprehensive books on database system implementation.Hector Garcia-Molina pioneered Database System Implementation at Stanford as a second database systems course for computer science majors and industry-based professionals. It focuses on the implementation of database systems,including storage structures, query processing. and transaction management. This book is valuable as an academic textbook or a professional reference.
　　This text covers a broad spectrum of knowledge and technology This carefully class-tested, highly readable presentation provides students or professionals with the next level of study. Written from the point of view of the database designer, user, and application programmer, this book provides practical advice from well-known experts on how to implement state-of-the-art database systems.

Hector Garcia-Moina is the Leonard Bosack and Sandra Lerner Professor in the Computer Sdence and Electrical Engineering Depwtments at Stanford Unirersity He has published densively in the fields of database systems, distributed systems, and digital libraries. ms research interests also include distribut6d computing systems, database systems, and digital libraries.
　　Jeffrey D.Ullmam is the Stanford W. Ascherman Professor of Computer Science 8t Stanford University He is the author or coauthor of 15 books and 170 techncal publicatons, induding A First COurse in Database Systems (Prentice HalI 1997) and Elements Of ML Programming (Prentce Hall 1998). His research interests include databa8e theory database integration, data mining, and education using the information infrastfucture. He has received numerous awards such as the Guggenheim Fellowship and election to the National Academy of Engineering. He also received the 1996 SigInod Contribution Award and the 1998 Kari V Karstrom Outstanding Educator Award.
　　Jennifer Widom is an Associate Professor in the Compute Science and EleCtrical Engineering Departments at Stanford Unirersity She has served on numerous editorial boards and program committees, she has pubished widely in computer science conferences and journals, and is co-author of A First Course in)Database Systems (Prentce Hall 1997). Her research interest8 include d8tabase systems for semistrurtured data and XML, dare warehousing, and actire database systems.

This book was designed for CS245, the second course in the database sequence at Stanfod. Here, the first database course, CS145, oove8 database design and programming, for which the book A Firat Couree in Database Spetems by Jeff UllmaJn and Jennifer Widom, PrenticesHall, 1997, was written. The CS245 course then covers implementation of a pBMS, notably storape structures, query processing, and transaction management.
　　
Use of the Book
　　We're on a quarter system at Stanford, so the principal course using this book CS245 -- is only ten weeks long. In the Winter of 1999, Hector GarciaMolina used a "beta" version of this book, and covered the following parts: Sections 2.1--2.4, all of ChaPters 3 and 4, Sections 5.1 and 5.2, Sections 6.l--6.7, Sections 7.1--7.4, all of ChaPter 8, Chapter 9 except fOr SeCtiOn 9.8, Sections 10.1--10.3,' Section 11. 1, and Section 11 .5.
　　The baiance Of ChaPters 6 and 7 (query oPtimzation) is covered in an advanced course) CS346, where students implemeot their own DBMS. Other portions of the book that are not covered in CS245 may aPpear in another advanced course, CS347, which talks about distributed databases and advanced transaction processing.
　　Schools that are on the semester system have the opportunity to combine the use of this book with its predece8sor: A First Covrse in Database Sy8tems.We recommnd u8ing that book in the first semester, coupled with a databaseapplication programming project. The second semester could cover most or aJl Of the conted of this book. An advanop to splitting the study Of databun into two courses is that students not planning to specialize in DBMS con8truction can take only the first course and be able to use databases in whatever branch of Computer Science they enter.
　　
Prerequisites
　　The course on which the book is based is rarely taken before the senior year, so we expect the reader to have a fairly broad background in the traditional areas of Computer Science. We assume that the reader has learned something about database programming, especially SQL. It is helpful to know about relational algebra and to have some faIniliarity with basic data structures. Likewise, some know1edge of file systems and operating systems is useful.
　　
Exercises
　　The book contains extensive exercises, with some for almost every section. We indicate harder exercises or parts of exercises with an exclamation point. The hardest exercises have a double exclapoation point.
　　Some of the exercises or parts are marked with a star. FOr these exercises, we shall endeavor to maintain solutions accessible through the book's Web page. These solutions are publicly available and should be used for self testing.Note that in a few cases, one exercise B asks for modification or adaptation of your solution to another exercise A. If certain parts of A have Web-published solutions, then you should expect the corresponding parts of B to have solutions as well.
　　
Support on the WOrld-Wide Web
　　The book's home page is
　　http: //www--db. stanford. edu/ ~ulInan/dbsi. html
　　Here you wil1 find solutions to starred exercises, errata as we learn of them,and backup materials. We hope to make avalable the notes for each offering of CS245 and relevant portions of other database courses, as we teach them,including homeworks, exams, and solutions.
　　
Acknowledgements
　　Thanks go to Brad Adelberg, Karen Butler, Ed Chang, Surajit Chaudhuri,Rada Chirkova, Tom Dienstbier, Xavier Faz, Tracy Fuieda, Luis Gravano, Ben Holzman, Fabien Modoux, Peter Mork, Ken Ross, Mema Roussopolous, and Jonathan Ullman for assistance gathering material and/or discovering errors in earlier drafts of this work. Remaining errors are ours) of course.
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　H. G.-M.
J. D. U.
J. W.
Stanford, CA

(美)Hector Garcia-Molina,Jeffrey D.Ullman,Jennifer Widom：Hector Garcia-Molina: 是斯坦福大学计算机科学与电气工程系的Leonard Bosack和Sandra Lerner教授。他在数据库系统、分布式系统和数字图书馆领域中发表了大量论文。他的研究兴趣包括分布式计算系统、数据库系统和数字图书馆。
Jeffrey D.Ullman: 斯坦福大学计算机科学系Stanford W. Ascherman教授，数据库技术专家。他独立或合作出版了15本著作，发表了170多篇技术论文。他的研究兴趣包括数据库理论，数据库集成，数据挖掘和利用信息基础设施进行教育。他获得了Guggenheim Fellowship等多种奖励，并被推选进入美国国家工程院。他还被授予1996年度Sigmod贡献奖和1998年度Karl V.Karstrom杰出教育家奖。 他先后在Prentice Hall出版了A First Course in Database Systems, Database Systems Implementation, Elements of ML Porgramming等著作。
Jennifer Widom: Jennifer Widom 于1987年在康奈尔大学获得计算机科学博士学位，现为斯坦福大学计算机科学与电气工程系教授。她是ACM Fellow、Guggenheim Fellow和美国国家工程院成员，并且是多个编辑委员会、程序委员会和顾问委员会的成员。她的研究兴趣包括半结构化数据的数据库系统和XML、数据仓库以及主动数据库系统。

1 Introduction to DBMS Implementation
1.1 Introducing: The Megatron 2000 Database System
1.1.1 Megatron 2000 Implementation Details
l.1.2 How Megatron 2000 Executes Queries
1.1.3 What's Wrong With Megatron 2000
1.2 Overview of a Database Management System
1.2.1 DataDefinition Language Commands
1.2.2 Overview of Query Processing
1.2.3 Main--Memory Buffers and the Buffer Manager
1.2.4 Thansaction Processing
1.2.5 The Query Processor
1.3 Outline of This Book
1.3. 1 Prerequisites
1.3.2 Storage-- M anagement Overview
1.3.3 Query-Proce8sing Overview
1.3.4 Thansaction- P rocessing Overview
1.3.5 Information Integration Overview
1.4 Review of Database Models and Languages
1.4.1 Relational Model Review
1.4.2 SQL Review
1.4.3 Re1ational and Object-Oriented Data
1.5 Summary of Chapter 1
1.6 References for Chapter 1
2 Data Storage
2.1 The Memory Hierarchy
2.1.1 Cache
2.1.2 Main Memory
2.1.3 Virtual Memory
2.1.4 Secondary Storage
2.1.5 Tertiary Storage
2.1.6 Volatile and Nonvolatile Storage
2.1.7 Exercises for Section 2.1
2.2 Disks
2.2.1 Mechanics Of Disks
2.2.2 The Disk Controller
2.2.3 Disk Storage Characteristics
2.2.4 Disk Access Characteristics
2.2.5 Writing Blocks
2.2.6 Modifying Blocks
2.2.7 Exercises for Section 2.2
2.3 Using Secondary Storage Effectively
2.3.1 The I/O Model of Computation
2.3.2 Sorting Data in SecondaJry Storage
2.3.3 Merge-Sort
2.3.4 Two-Phase, Multiway Merge--Sort
2.3.5 Extension of Multiway Merging to Larger Relatbos
2.3.6 Exercises for Section 2.3
2.4 Improving the Access Time of Secondary Storage
2.4.1 Organizing Data by Cylinders
2.4.2 Using Multiple Disks
2.4.3 Mirroring Disks
2.4.4 Disk Scheduling and the Elevator Algorithm
2.4.5 Prefetching and Large-Scale Buffering
2.4.6 SummaJry.of Strategies and nadeoffe
2.4.7 Exercises fOr Section 2.4
2.5 Disk Failures
2.5.1 1ntermittent Falures
2.5.2 Checksums
2.5.3 Stable Storage
2.5.4 Error-Handling Capabilities of Stable Storage
2.5.5 Exercises for Section 2.5
2.6 Recovery from Disk Crashes
2.6.1 The Failure Model for Disks
2.6.2 Mirroring as a Redundancy Technique
2.6.3 Paxity Blocks
2.6.4 An Improvment: RAID 5
2.6.5 Coping With Multiple Disk Cfashes
2.6.6 Exercises for Section 2.6
2.7 Summary.of ChaPter 2
2.8 References for ChaPter 2
3 Representing Datu Elements
3.1 Data Elements and Fields
3.1.1 Representing Relational Database Elements
3.1.2 Representing Objects
3.1.3 Representing Data Elements
3.2 Records
3.2.1 Building Fixed-Length Records
3.2.2 Record Headers
3.2.3 Packing Fixed-Length Records into Blocks
3.2.4 Exercises for Section 3.2
3.3 Represention Block and Record Addresses
3.3.1 Client--Server Systems
3.3.2 LogicaJ and Structured Addresses.
3.3.3 Pointer Swizzling
3.3.4 Returning Blocks to Disk
3.3.5 Pinned Records and Blocks
3.3.6 Exercises for Section 3.3
3.4 Variable-Length Data and Records
3.4.1 Records With Variable-Length Fields
3.4.2 Records With Repeating Fields
3.4.3 Variable-Format Records
3.4.4 Records That Do Not Fit in a Block
3.4.5 BLOBS
3.4.6 Exercises for Section 3.4
3.5 Record Modifications
3.5.1 Insertion
3.5.2 Deletion
3.5.3 Update
3.5.4 Exercises for Section 3.5
3.6 Summary of Chapter 3
3.7 References for Chapter 3
4 Index Structure8
4.1 Indexes on Sequential Files
4.1.1 Sequential Files
4.1.2 Dense Indexes
4.1.3 Sparse Indexes
4.1.4 Multiple Levels of Index
4.1.5 Indexes With Duplicate Search Keys
4.1.6 Managing Indexes During Data Modifications
4.1.7 Exercises fOr Section 4.1
4.2 Secondary Indexes
4.2.1 Design of Secondary Indexes
4.2.2 Applications of Secondary Indexes
4.2.3 Indirection in Secondaxy Indexes
4.2.4 Document Retrieval and Inverted Indexes
4.2.5 Exercises fOr Section 4.2
4.3 B-nees
4.3.l The Structure of B--trees
4.3.2 Applications of B-trees
4.3.3 Lookup in B-Trees
4.3.4 Range Queries
4.3.5 Insertion Into B-nees
4.3.6 Deletion nom B-nees
4.3.7 Efficiency of B-Trees
4.3.8 Exercises fOr Section 4.3
4.4 Hash Tables
4.4.1 Secondary-Storage Hash Tables
4.4.2 Insertion Into a Hash Table
4.4.3 Hash-Table Deletion
4.4.4 Efficiency of Hash Table Indexes
4.4.5 Extensible Hash Tables
4.4.6 Insertion Into Extensible Hash Tables
4.4.7 Linear Hash Tables
4.4.8 Insertion 1nto Linear Hash Tables
4.4.9 Exercises fOr Section 4.4
4.5 Summary Of Chapter 4
4.6 References for Chapter 4
5 Multidimensional Indexes
5.1 Applications Needing Multiple Dimensions
5.1.1 GWaPhic Information System8
5.1.2 Data Cubes
5.1.3 Multidimensional Queries in SQL
5.1.4 Executing Range Queries Using Conventional 1ndexes
5.1.5 Executing Nearest--Neighbor Queries Using ConventionalIndexes
5.1.6 Other Limitations of Conventional Indexes
5.1.7 Overview of Multidimensional Index Strllctures
5.1.8 Exercises for Section 5.1
5.2 Hash-Like Structures for Multidimensional Data
5.2.l Grid Files
5.2.2 Lookup in a Grid File
5.2.3 Insertion Into Grid Files
5.2.4 Performance Of Grid Files
5.2.5 Patitioned Hash minctions
5.2.6 Comparison of Grid Files and Partitioned Hashing
5.2.7 Exercises for Section 5.2
5.3 Thee-Like Structures fOr Multidimensional Data
5.3.l Multiple-Key Indexes
5.3.2 Performance of MultiplesKey Indexes
5.3.3 kdnees
5.3.4 Operations on kdnees
5.3.5 AdaPting kdThees to Secondary Storage
5.3.6 Quad Thees
5.3.7 RTrees
5.3.8 Operations on Rtrees
5.3.9 Exercises for Section 5.3
5.4 Bitmap Indexes
5.4.1 Motivation for Bitmap Indexes
5.4.2 Compressed BitmaPS
5.4.3 Operating.on Run-Lengt h- Encoded Bit- Vectors
5.4.4 Managing BitmaP Indexes
5.4.5 Exercises for Section 5.4
5.5 Summary of Chapter 5
5.6 References for Chapter 5
6 Query Execution
6.1 An Algebra for Queries
6.1.1 Union, Intersection, and Difference
6.1.2 The Selection Operator
6.1.3 The Projection Operator
6.1.4 The Product of Relations
6.1.5 Joins
6.1.6 Duplicate Elimination
6.1.7 Grouping and Aggregaion
6.1.8 The Sorting Operator
6.1.9 Expression nees
6. 1. l0 Exercises for Section 6.1
6.2 Introduction to Physical-Query-Plan Operators
6.2.l Scanning Tables
6.2.2 Sorting While Scanning Tables
6.2.3 The Model of Computation for Physical Operators
6.2.4 Parameters for Measuring Costs
6.2.5 I/O Cost for Scan Operators
6.2.6 Iterators for Implementation of Physical Operators
6.3 One-Pass Algorithms for Database Operations
6.3.l One--Pass Algorithms for TUplesat-aTime Operations
6.3.2 One-Pass Algorithms for Unary, FulLRelation Operai
6.3.3 One-Pass Algorithms for Binary Operations
6.3.4 Exercises for Section 6.3
6.4 Nested-Loop Joins
6.4.1 Tuple-Based Nested-Loop Join
6.4.2 An Iterator for Thple--Based Nested--Loop Join
6.4.3 A Block-Based Nested--Loop Join Algorithm
6.4.4 Analysis of Nested-Loop Join
6.4.5 Summary of AlgOrithms so Far
6.4.6 Exercises fOr Section 6.4
6.5 TwcaPass Algorithms Based on Sorting
6.5.1 Duplicate Elimination Using Sorting
6.5.2 Grouping and Aggregation Using Sorting
6.5.3 A Sort-Based Union Algorithm
6.5.4 Sort-Based Algorithms for Intersection and Difference
6.5.5 A Simple Sort--Based Join Algorithm
6.5.6 Analysis of Simple Sort-Join
6.5.7 A More Efficient Sort-Based Join
6.5.8 Summary Of Sort-Based Algorithms
6.5.9 Exercises for Section 6.5
6.6 Two-Pass AlgOrithms Based on Hashing
6.6.1 Partitioning Relations by Hashing
6.6.2 A Hash-Based Algorithm for Duplicate Elimination
6.6.3 A Hash--Based Algorithm for Grouping and Aggrgation
6.6.4 Hash-Based Algorithms for Union, Intersection, and Dif ference
6.6.5 The Hash-Join Algorithm
6.6.6 Saving Some Disk I/O's
6.6.7 Summary of Hash-Based Algorithms
6.6.8 Exercises for Section 6.6
6.7 Index-Based Algorithms
6.7.1 Clustering and Nonclustering Indexes
6.7.2 Index--Based Selection
6.7.3 Joining by Using an Index
6.7.4 Joins Using a Sorted Index
6.7.5 Exercises for Section 6.7
6.8 Buffer Management
6.8.l Buffer Management Architecture
6.8.2 Buffer Manapement Strategies
6.8.3 The Relationship Between Physical Operator Selection and Buffer Management
6.8.4 Exercises for Section 6.8
6.9 Algorithms Using More Than Two Passes
6.9.1 Multipass Sort-Based Algorithms
6.9.2 Performance of Multipass, Sort--Based Algorithms
6.9.3 Multipass Hash-Based Algorithms
6.9.4 Performance of Multipass Hash-Based Algorithms
6.9.5 Exercises fOr Section 6.9
6.l0 PaxaJlel Algorithms fOr Relational Operations.
6.10.1 Models of Paxallelism
6.10.2 Tuple-at-aTime Operations in Parallel
6.10.3 Parallel Algorithms for Full--Relation Operations
6.l0.4 Performance of Parallel Algorithms
6.10.5 Exercises for Section 6.10
6.1l SummaJry of Chapter 6
6.12 References for ChaPter 6
7 The Query Compiler
7.1 Parsing
7.1.1 Syntax Analysis and Parse nees
7.1.2 A Grammar for a Simple Subset of SQL
7.1.3 The Preprocessor
7.1.4 Exercises for Section 7.1
7.2 Algebraic Laws for Improving Query Plans
7.2.1 Commutative and Associative Laws
7.2.2 Laws Involving Selection
7.2.3 Pushing Selections
7.2.4 Laws Involving Projection
7.2.5 Laws About Joins and Products
7.2.6 Laws Involving Duplicate Elimination
7.2.7 Laws lnvolving Grouping and Aggregation
7.2.8 Exercises for Section 7.2
7.3 From PaJrse Thees to Logical Query Plans
7.3.1 Conversion to Relational Algebra
7.3.2 Removing Subqueries nom Conditions
7.3.3 Improving the Logical Query Plan
7.3.4 Grouping Associative/Commutat ive O perators
7.3.5 Exercises for Section 7.3
7.4 Estimating the Cost of Operations
7.4.1 Estimating Sizes of Illtermediate ffelations
7.4.2 Estimating the Size of a PrOjectiOn
7.4.3 Estimating the Size of a Selectbo
7.4.4 Estimating the Size of a Join
7.4.5 Natural Joins With Multiple Join Attributes
7.4.6 Joins of Many Relations
7.4.7 Estim8ting Sizes fOr Other Operations
7.4.8 Exercises for Section 7.4
7.5 Introduction to Cost-Based Plan Selection
7.5.1 Obtaining Estimates for Size Parameters
7.5.2 Incremental Computation of Statistics
7.5.3 Heuristics for Reducing the Cost of Logical Query P
7.5.4 Approaches to Enumerating Physical Plans
7.5.5 Exercises for Section 7.5
7.6 Choosing an Order for Joins
7.6.1 Significance of Left and mght Join ArgUments
7.6.2 Join nees
7.6.3 Left-Deep Join nees
7.6.4 Dynarnic Programming to Select a Join Order and Gr
7.6.5 Dynamic Programming With More Detailed Cost fu
7.6.6 A Greedy Algorithm for Selecting a Join Order
7.6.7 Exercises for Section 7.6
7.7 Completing the Physical-Query--Plan Selection
7.7.l Choosing a Selection Method
7.7.2 Choosing a Join Method
7.7.3 Pipelining Versus Materialization
7.7.4 Pipelining Unary Operations
7.7.5 Pipelining Binary Operations
7.7.6 Notation for Physical Query PlaJns
7.7.7 Ordering Of Physical Operations
7.7.8 Exercises for Section 7.7
7.8 Summary of Chapter 7
7.9 References for ChaPter 7
8 Coping With System Failures
8.l Issues and Models fOr Resilient Operation
8.1.1 Failure Modes
8.1.2 More About nansactions
8.1.3 Correct Execution of nansactions
8.1.4 The Primitive Operations of Transactions
8.1.5 Exercises for Section 8.1
8.2 Undo Logging
8.2.1 Log Records
8.2.2 The UndthLogging Rules
8.2.3 Recovery Using Undo Logging
8.2.4 Checkpointing
8.2.5 Nonquiescent Checkpointing
8.2.6 Exercises for Section 8.2
8.3 Redo Logging
8.3.1 The Redo--Logging Rule
8.3.2 RetiOvery With Redo Logging
8.3.3 Checkpointing a Redo Log
8.3.4 Recovery With a Checkpointed Redo Log
8.3.5 Exercises for Section 8.3
8.4 Undo/Redo Logging
8.4.1 The Undo/Redo Rules
8.4.2 Recovery With Undo/Redo Logging
8.4.3 Checkpointing aJn Undo/Redo Log
8.4.4 Exercises for Section 8.4
8.5 Protecting Against Media Failures
8.5.1 The Archive
8.5.2 Nonquiescent Archiving
8.5.3 Recovery Using an Archive and Log
8.5.4 Exercises for Section 8.5
8.6 Summaxy of Chapter 8
8.7 References for ChaPter 8
9 Concurrency Control
9.1 Serial and Serializable Schedules
9.l.1 Schedules
9.1.2 Serial Schedules
9.1.3 Serializable Schedules
9.l.4 The Effect of Transaction Semantics
9.1.5 A Notation for nansactions and Schedules
9.1.6 Exercises for Section 9.1
9.2 Conflict - Serializability
9.2.1 Confiicts
9.2.2 Precedence Graphs and a Test for Conflict-Serializability
9.2.3 Why the Precedence--Graph Test Works
9.2.4 Exercises for Section 9.2
9.3 Enforcing Serializability by Locks
9.3.1 Locks
9.3.2 The Locking Scheduler
9.3.3 Two--Phase Locking
9.3.4 Why Two-Phase Locking Works
9.3.5 Exercises for Section 9.3
9.4　Locking Systems With Several Lock Modes
9.4.1 Shared and Exclusive Locks
9.4.2 Compatibility Matrices
9.4.3 Upgrading Locks
9.4.4 Update Locks
9.4.5 Increment Locks
9.4.6 Exercises for Section 9.4
9.5 An Architecture for a Locking Scheduler
9.5.1 A Scheduler That Inserts Lock Actions
9.5.2 The Lock Table
9.5.3 Exercises for Section 9.5
9.6 Managing Hierarchies of DatabaJse Elements
9.6.1 Locks With Multiple Granularity
9.6.2 Warning Locks
9.6.3 Phantoms and Handling Insertions Correctly
9.6.4 Exercises fOr Section 9-6
9.7 The Tree Protocol
9.7.1 Motivation for nee-Based Locking
9.7.2 Rules for Access to Tree-Structured Data
9.7.3 Why the nee Protocol Works
9.7.4 Exercises for Section 9.7
9.8 Concurrency COntrol by TimeStamps
9.8.1 Timestamps
9.8.2 Physically Unrealizable Behaviors
9.8.3 Problems With Dirty Data
9.8.4 The Rules fOr Timestamp-Based Scheduling
9.8.5 Multiversion Timestamps
9.8.6 Timestaznps and Locking
9.8.7 Exercises for Section 9.8
9.9 Concurrency Control by Validation
9.9.1 Architecture of a Validation-Based Scheduler
9.9.2 The Validation Rules
9.9.3 Comparison Of Three Concurrency-Control Mechanisms
9.9.4 Exercises for Section 9.9
9.10 Summary Of ChaPter 9
9.1l References for ChaPter 9
10 More About nansaction Managemeot
10.1 Thansactions that Read Uncommitted Data
10.1.1 The Dirty-Data Problem
10.1.2 Cascading Rollback
10.1.3 Managing Rollbacks
10.1.4 Group Commit
10.1.5 Logical Logging
10.1.6 Exercises for Section 10.1
10.2 View Serializability
10.2.1 View Equivalence
l0.2.2 PolygraPhs and the Test for View-Serializability
10.2.3 Testing for View-Serializability
10.2.4 Exercises for Section 10.2
10.3 Resolving Deadlocks
l0.3.l Deedlock Detection by Timeout
l0.3.2 The Waits-For GraPh
10.3.3 Deadlock Prevention by Ordering Elements
10.3.4 Detecting Deadlocks by Timestamps
10.3.5 Comparison of Deadloch Management Methods
l0.3.6 Exercises for Section 10.3
10.4 Distributed Databases
10.4.1 Distribution of Data
10.4.2 Distributed nansactions
10.4.3 Data Replication
10.4.4 Distributed Query Optimization
10.4.5 Exercises for SeCtion 10.4
10.5 Distributed Commit
10.5.1 Supporting Distributed Atomicity
10.5.2 TwcrPhase Commit
l0.5.3 Recovery of Distributed' Thansactions
l0.5.4 Exercises for Section 10.5
10.6 Distributed Locking
10.6.1 Centralized Lock Systems
10.6.2 A Cost Model for Distributed Locking Algorithms
10.6.3 Locking Replicated Elements
10.6.4 Primary-CoPy Locking
10.6.5 Global Locks Wom Local Locks
l0.6.6 Exercises for Section 10.6
10.7 Long--Duration nansactions
10.7.1 Problems of Long nansactions
10.7.2 sasas
10.7.3 Compensating nansactions
10.7.4 Why Compensating nansactions Work
10.7.5 Exercises for Section 10.7
10.8 Summary of ChaPter 10
l0.9 References for ChaPter 10
11 Information Integration
1l.1 Modes of Information Illtegration
11.1.1 Problems of Information Integration
11.1.2 Federated Database Systems
11.1.3 Data Waehouses
11.1.4 Mediators
11.1.5 Exercises for Section 11. 1
11.2 WraPpers in Mediator-Based Systems
11.2.1 Templates for Query Patterns
l1.2.2 WraPper Generators
11.2.3 Filters
11.2.4 Other Operations at the Wrapper
11.2.5 Exercises for Section l1 .2
11.3 On--Line AnaJytic Processing
11.3.1 OLAP Applications
11.3.2 A Multidimensional View of OLAP Data
11.3.3 StaJr Schemas
11.3.4 Slicing and Dicing
11.3.5 Exercises for Section 11.3
l1.4 Data Cubes
11.4.l The Cube Operator
11.4.2 Cube Implementation by Materialized Views
11.4.3 The Lattice of Views
11.4.4 Exercises for Section 11.4
11.5 Data Mining
11.5.1 Data-Mining Applications
11.5.2 Association-Rule Mining
11.5.3 The A-Priori Algorithm
11.6 Summary of Chapter 11
11.7 References for Chapter 11
Index