Database System Implementation / Edition 1

Database System Implementation / Edition 1

by Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer Widom, Jennifer D. Widom, Jeffrey D. Ullman
     
 

ISBN-10: 0130402648

ISBN-13: 9780130402646

Pub. Date: 05/28/1999

Publisher: Prentice Hall

Three well-known computer scientists at Stanford University-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 this book at Stanford as a second database systems course for computer science majors and industry-based professionals. It focuses on
See more details below

Overview

Three well-known computer scientists at Stanford University-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 this book 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. Database System Implementation is valuable as an academic textbook or a professional reference.

Noteworthy Features

  • Provides extensive coverage of query processing, including major algorithms for execution of queries and techniques for optimizing queries
  • Covers information integration, including warehousing and mediators, OLAP, and data-cube systems
  • Explains error-correction in RAID disks and covers bitmap indexes, data mining, data statistics, and pointer swizzling
  • Supports additional teaching materials found on the book's Web page at ...

Product Details

ISBN-13:
9780130402646
Publisher:
Prentice Hall
Publication date:
05/28/1999
Pages:
653
Product dimensions:
6.90(w) x 8.90(h) x 1.40(d)

Table of Contents

1 Introduction to DBMS Implementation
1(20)
1.1 Introducing: The Megatron 2000 Database System
2(4)
1.1.1 Megatron 2000 Implementation Details
2(2)
1.1.2 How Megatron 2000 Executes Queries
4(1)
1.1.3 What's Wrong With Megatron 2000?
5(1)
1.2 Overview of a Database Management System
6(5)
1.2.1 Data-Definition Language Commands
6(2)
1.2.2 Overview of Query Processing
8(1)
1.2.3 Main-Memory Buffers and the Buffer Manager
8(1)
1.2.4 Transaction Processing
9(1)
1.2.5 The Query Processor
10(1)
1.3 Outline of This Book
11(3)
1.3.1 Prerequisites
11(1)
1.3.2 Storage-Management Overview
12(1)
1.3.3 Query-Processing Overview
13(1)
1.3.4 Transaction-Processing Overview
13(1)
1.3.5 Information Integration Overview
13(1)
1.4 Review of Database Models and Languages
14(5)
1.4.1 Relational Model Review
14(1)
1.4.2 SQL Review
15(3)
1.4.3 Relational and Object-Oriented Data
18(1)
1.5 Summary of Chapter 1
19(1)
1.6 References for Chapter 1
20(1)
2 Data Storage
21(62)
2.1 The Memory Hierarchy
22(8)
2.1.1 Cache
22(1)
2.1.2 Main Memory
23(1)
2.1.3 Virtual Memory
24(1)
2.1.4 Secondary Storage
25(2)
2.1.5 Tertiary Storage
27(1)
2.1.6 Volatile and Nonvolatile Storage
28(1)
2.1.7 Exercises for Section 2.1
29(1)
2.2 Disks
30(10)
2.2.1 Mechanics of Disks
30(2)
2.2.2 The Disk Controller
32(1)
2.2.3 Disk Storage Characteristics
32(2)
2.2.4 Disk Access Characteristics
34(4)
2.2.5 Writing Blocks
38(1)
2.2.6 Modifying Blocks
39(1)
2.2.7 Exercises for Section 2.2
39(1)
2.3 Using Secondary Storage Effectively
40(9)
2.3.1 The I/O Model of Computation
41(1)
2.3.2 Sorting Data in Secondary Storage
42(1)
2.3.3 Merge-Sort
43(1)
2.3.4 Two-Phase, Multiway Merge-Sort
44(3)
2.3.5 Extension of Multiway Merging to Larger Relations
47(1)
2.3.6 Exercises for Section 2.3
48(1)
2.4 Improving the Access Time of Secondary Storage
49(14)
2.4.1 Organizing Data by Cylinders
51(1)
2.4.2 Using Multiple Disks
52(1)
2.4.3 Mirroring Disks
53(1)
2.4.4 Disk Scheduling and the Elevator Algorithm
54(4)
2.4.5 Prefetching and Large-Scale Buffering
58(1)
2.4.6 Summary of Strategies and Tradeoffs
59(2)
2.4.7 Exercises for Section 2.4
61(2)
2.5 Disk Failures
63(4)
2.5.1 Intermittent Failures
63(1)
2.5.2 Checksums
64(1)
2.5.3 Stable Storage
65(1)
2.5.4 Error-Handling Capabilities of Stable Storage
66(1)
2.5.5 Exercises for Section 2.5
67(1)
2.6 Recovery from Disk Crashes
67(13)
2.6.1 The Failure Model for Disks
67(1)
2.6.2 Mirroring as a Redundancy Technique
68(1)
2.6.3 Parity Blocks
69(4)
2.6.4 An Improvement: RAID 5
73(1)
2.6.5 Coping With Multiple Disk Crashes
73(4)
2.6.6 Exercises for Section 2.6
77(3)
2.7 Summary of Chapter 2
80(2)
2.8 References for Chapter 2
82(1)
3 Representing Data Elements
83(40)
3.1 Data Elements and Fields
83(7)
3.1.1 Representing Relational Database Elements
84(1)
3.1.2 Representing Objects
85(1)
3.1.3 Representing Data Elements
86(4)
3.2 Records
90(6)
3.2.1 Building Fixed-Length Records
91(2)
3.2.2 Record Headers
93(1)
3.2.3 Packing Fixed-Length Records into Blocks
94(1)
3.2.4 Exercises for Section 3.2
95(1)
3.3 Representing Block and Record Addresses
96(12)
3.3.1 Client-Server Systems
97(1)
3.3.2 Logical and Structured Addresses
98(1)
3.3.3 Pointer Swizzling
99(5)
3.3.4 Returning Blocks to Disk
104(1)
3.3.5 Pinned Records and Blocks
105(1)
3.3.6 Exercises for Section 3.3
105(3)
3.4 Variable-Length Data and Records
108(8)
3.4.1 Records With Variable-Length Fields
108(1)
3.4.2 Records With Repeating Fields
109(2)
3.4.3 Variable-Format Records
111(1)
3.4.4 Records That Do Not Fit in a Block
112(2)
3.4.5 BLOBS
114(1)
3.4.6 Exercises for Section 3.4
115(1)
3.5 Record Modifications
116(4)
3.5.1 Insertion
116(2)
3.5.2 Deletion
118(1)
3.5.3 Update
119(1)
3.5.4 Exercises for Section 3.5
119(1)
3.6 Summary of Chapter 3
120(2)
3.7 References for Chapter 3
122(1)
4 Index Structures
123(64)
4.1 Indexes on Sequential Files
124(18)
4.1.1 Sequential Files
124(1)
4.1.2 Dense Indexes
125(3)
4.1.3 Sparse Indexes
128(1)
4.1.4 Multiple Levels of Index
129(2)
4.1.5 Indexes With Duplicate Search Keys
131(2)
4.1.6 Managing Indexes During Data Modifications
133(7)
4.1.7 Exercises for Section 4.1
140(2)
4.2 Secondary Indexes
142(12)
4.2.1 Design of Secondary Indexes
142(2)
4.2.2 Applications of Secondary Indexes
144(1)
4.2.3 Indirection in Secondary Indexes
145(3)
4.2.4 Document Retrieval and Inverted Indexes
148(3)
4.2.5 Exercises for Section 4.2
151(3)
4.3 B-Trees
154(16)
4.3.1 The Structure of B-trees
154(3)
4.3.2 Applications of B-trees
157(2)
4.3.3 Lookup in B-Trees
159(1)
4.3.4 Range Queries
160(1)
4.3.5 Insertion Into B-Trees
161(2)
4.3.6 Deletion From B-Trees
163(3)
4.3.7 Efficiency of B-Trees
166(1)
4.3.8 Exercises for Section 4.3
167(3)
4.4 Hash Tables
170(14)
4.4.1 Secondary-Storage Hash Tables
171(1)
4.4.2 Insertion Into a Hash Table
172(1)
4.4.3 Hash-Table Deletion
172(1)
4.4.4 Efficiency of Hash Table Indexes
173(1)
4.4.5 Extensible Hash Tables
174(1)
4.4.6 Insertion Into Extensible Hash Tables
175(2)
4.4.7 Linear Hash Tables
177(3)
4.4.8 Insertion Into Linear Hash Tables
180(2)
4.4.9 Exercises for Section 4.4
182(2)
4.5 Summary of Chapter 4
184(1)
4.6 References for Chapter 4
185(2)
5 Multidimensional Indexes
187(50)
5.1 Applications Needing Multiple Dimensions
188(9)
5.1.1 Geographic Information Systems
188(1)
5.1.2 Data Cubes
189(1)
5.1.3 Multidimensional Queries in SQL
190(2)
5.1.4 Executing Range Queries Using Conventional Indexes
192(1)
5.1.5 Executing Nearest-Neighbor Queries Using Conventional Indexes
193(2)
5.1.6 Other Limitations of Conventional Indexes
195(1)
5.1.7 Overview of Multidimensional Index Structures
195(1)
5.1.8 Exercises for Section 5.1
196(1)
5.2 Hash-Like Structures for Multidimensional Data
197(12)
5.2.1 Grid Files
198(1)
5.2.2 Lookup in a Grid File
198(1)
5.2.3 Insertion Into Grid Files
199(2)
5.2.4 Performance of Grid Files
201(3)
5.2.5 Partitioned Hash Functions
204(1)
5.2.6 Comparison of Grid Files and Partitioned Hashing
205(1)
5.2.7 Exercises for Section 5.2
206(3)
5.3 Tree-Like Structures for Multidimensional Data
209(16)
5.3.1 Multiple-Key Indexes
209(2)
5.3.2 Performance of Multiple-Key Indexes
211(1)
5.3.3 kd-Trees
212(1)
5.3.4 Operations on kd-Trees
213(3)
5.3.5 Adapting kd-Trees to Secondary Storage
216(1)
5.3.6 Quad Trees
217(2)
5.3.7 R-Trees
219(1)
5.3.8 Operations on R-trees
219(3)
5.3.9 Exercises for Section 5.3
222(3)
5.4 Bitmap Indexes
225(8)
5.4.1 Motivation for Bitmap Indexes
225(2)
5.4.2 Compressed Bitmaps
227(2)
5.4.3 Operating on Run-Length-Encoded Bit-Vectors
229(1)
5.4.4 Managing Bitmap Indexes
230(2)
5.4.5 Exercises for Section 5.4
232(1)
5.5 Summary of Chapter 5
233(1)
5.6 References for Chapter 5
234(3)
6 Query Execution
237(92)
6.1 An Algebra for Queries
240(17)
6.1.1 Union, Intersection, and Difference
241(1)
6.1.2 The Selection Operator
242(2)
6.1.3 The Projection Operator
244(1)
6.1.4 The Product of Relations
245(1)
6.1.5 Joins
246(2)
6.1.6 Duplicate Elimination
248(1)
6.1.7 Grouping and Aggregation
248(3)
6.1.8 The Sorting Operator
251(1)
6.1.9 Expression Trees
252(2)
6.1.10 Exercises for Section 6.1
254(3)
6.2 Introduction to Physical-Query-Plan Operators
257(7)
6.2.1 Scanning Tables
257(1)
6.2.2 Sorting While Scanning Tables
258(1)
6.2.3 The Model of Computation for Physical Operators
258(1)
6.2.4 Parameters for Measuring Costs
259(1)
6.2.5 I/O Cost for Scan Operators
260(1)
6.2.6 Iterators for Implementation of Physical Operators
261(3)
6.3 One-Pass Algorithms for Database Operations
264(10)
6.3.1 One-Pass Algorithms for Tuple-at-a-Time Operations
266(1)
6.3.2 One-Pass Algorithms for Unary, Full-Relation Operations
267(3)
6.3.3 One-Pass Algorithms for Binary Operations
270(3)
6.3.4 Exercises for Section 6.3
273(1)
6.4 Nested-Loop Joins
274(5)
6.4.1 Tuple-Based Nested-Loop Join
275(1)
6.4.2 An Iterator for Tuple-Based Nested-Loop Join
275(1)
6.4.3 A Block-Based Nested-Loop Join Algorithm
275(3)
6.4.4 Analysis of Nested-Loop Join
278(1)
6.4.5 Summary of Algorithms so Far
278(1)
6.4.6 Exercises for Section 6.4
278(1)
6.5 Two-Pass Algorithms Based on Sorting
279(12)
6.5.1 Duplicate Elimination Using Sorting
280(2)
6.5.2 Grouping and Aggregation Using Sorting
282(1)
6.5.3 A Sort-Based Union Algorithm
283(1)
6.5.4 Sort-Based Algorithms for Intersection and Difference
284(2)
6.5.5 A Simple Sort-Based Join Algorithm
286(1)
6.5.6 Analysis of Simple Sort-Join
287(1)
6.5.7 A More Efficient Sort-Based Join
288(1)
6.5.8 Summary of Sort-Based Algorithms
289(1)
6.5.9 Exercises for Section 6.5
289(2)
6.6 Two-Pass Algorithms Based on Hashing
291(8)
6.6.1 Partitioning Relations by Hashing
292(1)
6.6.2 A Hash-Based Algorithm for Duplicate Elimination
293(1)
6.6.3 A Hash-Based Algorithm for Grouping and Aggregation
293(1)
6.6.4 Hash-Based Algorithms for Union, Intersection, and Difference
294(1)
6.6.5 The Hash-Join Algorithm
294(1)
6.6.6 Saving Some Disk I/O's
295(2)
6.6.7 Summary of Hash-Based Algorithms
297(1)
6.6.8 Exercises for Section 6.6
298(1)
6.7 Index-Based Algorithms
299(8)
6.7.1 Clustering and Nonclustering Indexes
299(1)
6.7.2 Index-Based Selection
300(3)
6.7.3 Joining by Using an Index
303(1)
6.7.4 Joins Using a Sorted Index
304(2)
6.7.5 Exercises for Section 6.7
306(1)
6.8 Buffer Management
307(6)
6.8.1 Buffer Management Architecture
307(1)
6.8.2 Buffer Management Strategies
308(2)
6.8.3 The Relationship Between Physical Operator Selection and Buffer Management
310(2)
6.8.4 Exercises for Section 6.8
312(1)
6.9 Algorithms Using More Than Two Passes

Customer Reviews

Average Review:

Write a Review

and post it to your social network

     

Most Helpful Customer Reviews

See all customer reviews >