search for books and compare prices
Tables of Contents for Database Systems
Chapter/Section Title
Page #
Page Count
The Worlds of Database Systems
1
22
The Evolution of Database Systems
2
7
Early Database Management Systems
2
2
Relational Database Systems
4
1
Smaller and Smaller Systems
5
1
Bigger and Bigger Systems
6
1
Client-Server and Multi-Tier Architectures
7
1
Multimedia Data
8
1
Information Integration
8
1
Overview of a Database Management System
9
6
Data-Definition Language Commands
10
1
Overview of Query Processing
10
2
Storage and Buffer Management
12
1
Transaction Processing
13
1
The Query Processor
14
1
Outline of Database-System Studies
15
4
Database Design
16
1
Database Programming
17
1
Database System Implementation
17
2
Information Integration Overview
19
1
Summary of Chapter 1
19
1
References for Chapter 1
20
3
The Entity-Relationship Data Model
23
38
Elements of the E/R Model
24
15
Entity Sets
24
1
Attributes
25
1
Relationships
25
1
Entity-Relationship Diagrams
25
2
Instances of an E/R Diagram
27
1
Multiplicity of Binary E/R Relationships
27
1
Multiway Relationships
28
1
Roles in Relationships
29
2
Attributes on Relationships
31
1
Converting Multiway Relationships to Binary
32
1
Subclasses in the E/R Model
33
3
Exercises for Section 2.1
36
3
Design Principles
39
8
Faithfulness
39
1
Avoiding Redundancy
39
1
Simplicity Counts
40
1
Choosing the Right Relationships
40
2
Picking the Right Kind of Element
42
2
Exercises for Section 2.2
44
3
The Modeling of Constraints
47
7
Classification of Constraints
47
1
Key in the E/R Model
48
2
Representing Keys in the E/R Model
50
1
Single-Value Constraints
51
1
Referential Integrity
51
1
Referential Integrity in E/R Diagrams
52
1
Other Kinds of Constraints
53
1
Exercises for Section 2.3
53
1
Weak Entity Sets
54
5
Causes of Weak Entity Sets
54
2
Requirements for Weak Entity Sets
56
1
Weak Entity Set Notation
57
1
Exercises for Section 2.4
58
1
Summary of Chapter 2
59
1
References for Chapter 2
60
1
The Relational Data Model
61
70
Basics of the Relational Model
61
4
Attributes
62
1
Schemas
62
1
Tuples
62
1
Domains
63
1
Equivalent Representations of a Relation
63
1
Relation Instances
64
1
Exercises for Section 3.1
64
1
From E/R Diagrams to Relational Designs
65
11
From Entity Sets to Relations
66
1
From E/R Relationships to Relations
67
3
Combining Relations
70
1
Handling Weak Entity Sets
71
4
Exercises for Section 3.2
75
1
Converting Subclass Structures to Relations
76
6
E/R-Style Conversion
77
1
An Object-Oriented Approach
78
1
Using Null Values to Combine Relations
79
1
Comparison of Approaches
79
1
Exercises for Section 3.3
80
2
Functional Dependencies
82
8
Definition of Functional Dependency
83
1
Keys of Relations
84
2
Superkeys
86
1
Discovering Keys for Relations
87
1
Exercises for Section 3.4
88
2
Rules About Functional Dependencies
90
12
The Splitting/Combining Rule
90
2
Trivial Functional Dependencies
92
1
Computing the Closure of Attributes
92
3
Why the Closure Algorithm Works
95
1
The Transitive Rule
96
2
Closing Sets of Functional Dependencies
98
1
Projecting Functional Dependencies
98
2
Exercises for Section 3.5
100
2
Design of Relational Database Schemas
102
16
Anomalies
103
1
Decomposing Relations
103
2
Boyce-Codd Normal Form
105
2
Decomposition into BCNF
107
5
Recovering Information from a Decomposition
112
2
Third Normal Form
114
3
Exercises for Section 3.6
117
1
Multivalued Dependencies
118
9
Attribute Independence and Its Consequent Redundancy
118
1
Definition of Multivalued Dependencies
119
1
Reasoning About Multivalued Dependencies
120
2
Fourth Normal Form
122
1
Decomposition into Fourth Normal Form
123
1
Relationships Among Normal Forms
124
2
Exercises for Section 3.7
126
1
Summary of Chapter 3
127
2
References for Chapter 3
129
2
Other Data Models
131
58
Review of Object-Oriented Concepts
132
3
The Type System
132
1
Classes and Objects
133
1
Object Identity
133
1
Methods
133
1
Class Hierarchies
134
1
Introduction to ODL
135
12
Object-Oriented Design
135
1
Class Declarations
136
1
Attributes in ODL
136
2
Relationships in ODL
138
1
Inverse Relationships
139
1
Multiplicity of Relationships
140
1
Methods in ODL
141
3
Types in ODL
144
2
Exercises for Section 4.2
146
1
Additional ODL Concepts
147
8
Multiway Relationships in ODL
148
1
Subclasses in ODL
149
1
Multiple Inheritance in ODL
150
1
Extents
151
1
Declaring Keys in ODL
152
3
Exercises for Section 4.3
155
1
From ODL Designs to Relational Designs
155
11
From ODL Attributes to Relational Attributes
156
1
Nonatomic Attributes in Classes
157
1
Representing Set-Valued Attributes
158
2
Representing Other Type Constructors
160
2
Representing ODL Relationships
162
2
What If There Is No Key?
164
1
Exercises for Section 4.4
164
2
The Object-Relational Model
166
7
From Relations to Object-Relations
166
1
Nested Relations
167
2
References
169
1
Object-Oriented Versus Object-Relational
170
2
From ODL Designs to Object-Relational Designs
172
1
Exercises for Section 4.5
172
1
Semistructured Data
173
5
Motivation for the Semistructured-Data Model
173
1
Semistructured Data Representation
174
1
Information Integration Via Semistructured Data
175
2
Exercises for Section 4.6
177
1
XML and Its Data Model
178
8
Semantic Tags
178
1
Well-Formed XML
179
1
Document Type Definitions
180
2
Using a DTD
182
1
Attribute Lists
183
2
Exercises for Section 4.7
185
1
Summary of Chapter 4
186
1
References for Chapter 4
187
2
Relational Algebra
189
50
An Example Database Schema
190
1
An Algebra of Relational Operations
191
23
Basics of Relational Algebra
192
1
Set Operations on Relations
193
2
Projection
195
1
Selection
196
1
Cartesian Product
197
1
Natural Joins
198
1
Theta-Joins
199
2
Combining Operations to Form Queries
201
2
Renaming
203
2
Dependent and Independent Operations
205
1
A Linear Notation for Algebraic Expressions
206
1
Exercises for Section 5.2
207
7
Relational Operations on Bags
214
7
Why Bags?
214
1
Union, Intersection, and Difference of Bags
215
1
Projection of Bags
216
1
Selection on Bags
217
1
Product of Bags
218
1
Joins of Bags
219
1
Exercises for Section 5.3
220
1
Extended Operators of Relational Algebra
221
10
Duplicate Elimination
222
1
Aggregation Operators
222
1
Grouping
223
1
The Grouping Operator
224
2
Extending the Projection Operator
226
1
The Sorting Operator
227
1
Outerjoins
228
2
Exercises for Section 5.4
230
1
Constraints on Relations
231
5
Relational Algebra as a Constraint Language
231
1
Referential Integrity Constraints
232
1
Additional Constraint Examples
233
2
Exercises for Section 5.5
235
1
Summary of Chapter 5
236
1
References for Chapter 5
237
2
The Database Language SQL
239
76
Simple Queries in SQL
240
14
Projection in SQL
242
1
Selection in SQL
243
2
Comparison of Strings
245
2
Dates and Times
247
1
Null Values and Comparisons Involving NULL
248
1
The Truth-Value Unknown
249
2
Ordering the Output
251
1
Exercises for Section 6.1
252
2
Queries Involving More Than One Relation
254
10
Products and Joins in SQL
254
1
Disambiguating Attributes
255
1
Tuple Variables
256
2
Interpreting Multirelation Queries
258
2
Union, Intersection, and Difference of Queries
260
2
Exercises for Section 6.2
262
2
Subqueries
264
13
Subqueries that Produce Scalar Values
264
2
Conditions Involving Relations
266
1
Conditions Involving Tuples
266
2
Correlated Subqueries
268
2
Subqueries in From Clauses
270
1
SQL Join Expressions
270
2
Natural Joins
272
1
Outerjoins
272
2
Exercises for Section 6.3
274
3
Full-Relation Operations
277
9
Eliminating Duplicates
277
1
Duplicates in Unions, Intersections, and Differences
278
1
Grouping and Aggregation in SQL
279
1
Aggregation Operators
279
1
Grouping
280
2
Having Clauses
282
2
Exercises for Section 6.4
284
2
Database Modifications
286
6
Insertion
286
2
Deletion
288
1
Updates
289
1
Exercises for Section 6.5
290
2
Defining a Relation Schema in SQL
292
9
Data Types
292
1
Simple Table Declarations
293
1
Modifying Relation Schemas
294
1
Default Values
295
1
Indexes
295
2
Introduction to Selection of Indexes
297
3
Exercises for Section 6.6
300
1
View Definitions
301
11
Declaring Views
302
1
Querying Views
302
2
Renaming Attributes
304
1
Modifying Views
305
3
Interpreting Queries Involving Views
308
2
Exercises for Section 6.7
310
2
Summary of Chapter 6
312
1
References for Chapter 6
313
2
Constraints and Triggers
315
34
Keys and Foreign Keys
316
11
Declaring Primary Keys
316
1
Keys Declared With Unique
317
1
Enforcing Key Constraints
318
1
Declaring Foreign-Key Constraints
319
2
Maintaining Referential Integrity
321
2
Deferring the Checking of Constraints
323
3
Exercises for Section 7.1
326
1
Constraints on Attributes and Tuples
327
6
Not-Null Constraints
328
1
Attribute-Based Check Constraints
328
2
Tuple-Based Check Constraints
330
1
Exercises for Section 7.2
331
2
Modification of Constraints
333
3
Giving Names to Constraints
334
1
Altering Constraints on Tables
334
1
Exercises for Section 7.3
335
1
Schema-Level Constraints and Triggers
336
11
Assertions
337
3
Event-Condition-Action Rules
340
1
Triggers in SQL
340
4
Instead-Of Triggers
344
1
Exercises for Section 7.4
345
2
Summary of Chapter 7
347
1
References for Chapter 7
348
1
System Aspects of SQL
349
76
SQL in a Programming Environment
349
16
The Impedance Mismatch Problem
350
2
The SQL/Host Language Interface
352
1
The Declare Section
352
1
Using Shared Variables
353
1
Single-Row Select Statements
354
1
Cursors
355
3
Modifications by, Cursor
358
2
Protecting Against Concurrent Updates
360
1
Scrolling Cursors
361
1
Dynamic SQL
361
2
Exercises for Section 8.1
363
2
Procedures Stored in the Schema
365
14
Creating PSM Functions and Procedures
365
1
Some Simple Statement Forms in PSM
366
2
Branching Statements
368
1
Queries in PSM
369
1
Loops in PSM
370
2
For-Loops
372
2
Exceptions in PSM
374
2
Using PSM Functions and Procedures
376
1
Exercises for Section 8.2
377
2
The SQL Environment
379
6
Environments
379
1
Schemas
380
1
Catalogs
381
1
Clients and Servers in the SQL Environment
382
1
Connections
382
2
Sessions
384
1
Modules
384
1
Using a Call-Level Interface
385
8
Introduction to SQL/CLI
385
3
Processing Statements
388
1
Fetching Data From a Query Result
389
3
Passing Parameters to Queries
392
1
Exercises for Section 8.4
393
1
Java Database Connectivity
393
4
Introduction to JDBC
393
1
Creating Statements in JDBC
394
2
Cursor Operations in JDBC
396
1
Parameter Passing
396
1
Exercises for Section 8.5
397
1
Transactions in SQL
397
13
Serializability
397
2
Atomicity
399
2
Transactions
401
2
Read-Only Transactions
403
2
Dirty Reads
405
2
Other Isolation Levels
407
2
Exercises for Section 8.6
409
1
Security and User Authorization in SQL
410
12
Privileges
410
2
Creating Privileges
412
1
The Privilege-Checking Process
413
1
Granting Privileges
414
2
Grant Diagrams
416
1
Revoking Privileges
417
4
Exercises for Section 8.7
421
1
Summary of Chapter 8
422
2
References for Chapter 8
424
1
Object-Orientation in Query Languages
425
38
Introduction to OQL
425
11
An Object-Oriented Movie Example
426
1
Path Expressions
426
2
Select-From-Where Expressions in OQL
428
1
Modifying the Type of the Result
429
2
Complex Output Types
431
1
Subqueries
431
2
Exercises for Section 9.1
433
3
Additional Forms of OQL Expressions
436
7
Quantifier Expressions
437
1
Aggregation Expressions
437
1
Group-By Expressions
438
3
Having Clauses
441
1
Union, Intersection, and Difference
442
1
Exercises for Section 9.2
442
1
Object Assignment and Creation in OQL
443
6
Assigning Values to Host-Language Variables
444
1
Extracting Elements of Collections
444
1
Obtaining Each Member of a Collection
445
1
Constants in OQL
446
1
Creating New Objects
447
1
Exercises for Section 9.3
448
1
User-Defined Types in SQL
449
6
Defining Types in SQL
449
2
Methods in User-Defined Types
451
1
Declaring Relations with a UDT
452
1
References
452
2
Exercises for Section 9.4
454
1
Operations on Object-Relational Data
455
6
Following References
455
1
Accessing Attributes of Tuples with a UDT
456
1
Generator and Mutator Functions
457
1
Ordering Relationships on UDT's
458
2
Exercises for Section 9.5
460
1
Summary of Chapter 9
461
1
References for Chapter 9
462
1
Logical Query Languages
463
40
A Logic for Relations
463
8
Predicates and Atoms
463
1
Arithmetic Atoms
464
1
Datalog Rules and Queries
465
1
Meaning of Datalog Rules
466
3
Extensional and Intensional Predicates
469
1
Datalog Rules Applied to Hags
469
2
Exercises for Section 10.1
471
1
From Relational Algebra to Datalog
471
9
Intersection
471
1
Union
472
1
Difference
472
1
Projection
473
1
Selection
473
3
Product
476
1
Joins
476
1
Simulating Multiple Operations with Datalog
477
2
Exercises for Section 10.2
479
1
Recursive Programming in Datalog
480
12
Recursive Rules
481
1
Evaluating Recursive Datalog Rules
481
5
Negation in Recursive Rules
486
4
Exercises for Section 10.3
490
2
Recursion in SQL
492
8
Defining IDB Relations in SQL
492
2
Stratified Negation
494
2
Problematic Expressions in Recursive SQL
496
3
Exercises for Section 10.4
499
1
Summary of Chapter 10
500
1
References for Chapter 10
501
2
Data Storage
503
64
The ``Megatron 2002'' Database System
503
4
Megatron 2002 Implementation Details
504
1
How Megatron 2002 Executes Queries
505
1
What's Wrong With Megatron 2002?
506
1
The Memory Hierarchy
507
8
Cache
507
1
Main Memory
508
1
Virtual Memory
509
1
Secondary Storage
510
2
Tertiary Storage
512
1
Volatile and Nonvolatile Storage
513
1
Exercises for Section 11.2
514
1
Disks
515
10
Mechanics of Disks
515
1
The Disk Controller
516
1
Disk Storage Characteristics
517
2
Disk Access Characteristics
519
4
Writing Blocks
523
1
Modifying Blocks
523
1
Exercises for Section 11.3
524
1
Using Secondary Storage Effectively
525
8
The I/O Model of Computation
525
1
Sorting Data in Secondary Storage
526
1
Merge-Sort
527
1
Two-Phase, Multiway Merge-Sort
528
4
Multiway Merging of Larger Relations
532
1
Exercises for Section 11.4
532
1
Accelerating Access to Secondary Storage
533
13
Organizing Data by Cylinders
534
2
Using Multiple Disks
536
1
Mirroring Disks
537
1
Disk Scheduling and the Elevator Algorithm
538
3
Prefetching and Large-Scale Buffering
541
2
Summary of Strategies and Tradeoffs
543
1
Exercises for Section 11.5
544
2
Disk Failures
546
4
Intermittent Failures
547
1
Checksums
547
1
Stable Storage
548
1
Error-Handling Capabilities of Stable Storage
549
1
Exercises for Section 11.6
550
1
Recovery from Disk Crashes
550
13
The Failure Model for Disks
551
1
Mirroring as a Redundancy Technique
552
1
Parity Blocks
552
4
An Improvement: RAID 5
556
1
Coping With Multiple Disk Crashes
557
4
Exercises for Section 11.7
561
2
Summary of Chapter 11
563
2
References for Chapter 11
565
2
Representing Data Elements
567
38
Data Elements and Fields
567
5
Representing Relational Database Elements
568
1
Representing Objects
569
1
Representing Data Elements
569
3
Records
572
6
Building Fixed-Length Records
573
2
Record Headers
575
1
Packing Fixed-Length Records into Blocks
576
1
Exercises for Section 12.2
577
1
Representing Block and Record Addresses
578
11
Client-Server Systems
579
1
Logical and Structured Addresses
580
1
Pointer Swizzling
581
5
Returning Blocks to Disk
586
1
Pinned Records and Blocks
586
1
Exercises for Section 12.3
587
2
Variable-Length Data and Records
589
9
Records With Variable-Length Fields
590
1
Records With Repeating Fields
591
2
Variable-Format Records
593
1
Records That Do Not Fit in a Block
594
1
BLOBS
595
1
Exercises for Section 12.4
596
2
Record Modifications
598
4
Insertion
598
1
Deletion
599
2
Update
601
1
Exercises for Section 12.5
601
1
Summary of Chapter 12
602
1
References for Chapter 12
603
2
Index Structures
605
60
Indexes on Sequential Files
606
16
Sequential Files
606
1
Dense Indexes
607
2
Sparse Indexes
609
1
Multiple Levels of Index
610
2
Indexes With Duplicate Search Keys
612
3
Managing Indexes During Data Modifications
615
5
Exercises for Section 13.1
620
2
Secondary Indexes
622
10
Design of Secondary Indexes
623
1
Applications of Secondary Indexes
624
1
Indirection in Secondary Indexes
625
1
Document Retrieval and Inverted Indexes
626
4
Exercises for Section 13.2
630
2
B-Trees
632
17
The Structure of B-trees
633
3
Applications of B-trees
636
2
Lookup in B-Trees
638
1
Range Queries
638
1
Insertion Into B-Trees
639
3
Deletion From B-Trees
642
3
Efficiency of B-Trees
645
1
Exercises for Section 13.3
646
3
Hash Tables
649
13
Secondary-Storage Hash Tables
649
1
Insertion Into a Hash Table
650
1
Hash-Table Deletion
651
1
Efficiency of Hash Table Indexes
652
1
Extensible Hash Tables
652
1
Insertion Into Extensible Hash Tables
653
3
Linear Hash Tables
656
1
Insertion Into Linear Hash Tables
657
3
Exercises for Section 13.4
660
2
Summary of Chapter 13
662
1
References for Chapter 13
663
2
Multidimensional and Bitmap Indexes
665
48
Applications Needing Multiple Dimensions
666
9
Geographic Information Systems
666
2
Data Cubes
668
1
Multidimensional Queries in SQL
668
2
Executing Range Queries Using Conventional Indexes
670
1
Executing Nearest-Neighbor Queries Using Conventional Indexes
671
2
Other Limitations of Conventional Indexes
673
1
Overview of Multidimensional Index Structures
673
1
Exercises for Section 14.1
674
1
Hash-Like Structures for Multidimensional Data
675
12
Grid Files
676
1
Lookup in a Grid File
676
1
Insertion Into Grid Files
677
2
Performance of Grid Files
679
3
Partitioned Hash Functions
682
1
Comparison of Grid Files and Partitioned Hashing
683
1
Exercises for Section 14.2
684
3
Tree-Like Structures for Multidimensional Data
687
15
Multiple-Key Indexes
687
1
Performance of Multiple-Key Indexes
688
2
kd-Trees
690
1
Operations on kd-Trees
691
2
Adapting kd-Trees to Secondary Storage
693
2
Quad Trees
695
1
R-Trees
696
1
Operations on R-trees
697
2
Exercises for Section 14.3
699
3
Bitmap Indexes
702
8
Motivation for Bitmap Indexes
702
2
Compressed Bitmaps
704
2
Operating on Run-Length-Encoded Bit-Vectors
706
1
Managing Bitmap Indexes
707
2
Exercises for Section 14.4
709
1
Summary of Chapter 14
710
1
References for Chapter 14
711
2
Query Execution
713
74
Introduction to Physical-Query-Plan Operators
715
7
Scanning Tables
716
1
Sorting While Scanning Tables
716
1
The Model of Computation for Physical Operators
717
1
Parameters for Measuring Costs
717
2
I/O Cost for Scan Operators
719
1
Iterators for Implementation of Physical Operators
720
2
One-Pass Algorithms for Database Operations
722
11
One-Pass Algorithms for Tuple-at-a-Time Operations
724
1
One-Pass Algorithms for Unary, Full-Relation Operations
725
3
One-Pass Algorithms for Binary Operations
728
4
Exercises for Section 15.2
732
1
Nested-Loop Joins
733
4
Tuple-Based Nested-Loop Join
733
1
An Iterator for Tuple-Based Nested-Loop Join
733
1
A Block-Based Nested-Loop Join Algorithm
734
2
Analysis of Nested-Loop Join
736
1
Summary of Algorithms so Far
736
1
Exercises for Section 15.3
736
1
Two-Pass Algorithms Based on Sorting
737
12
Duplicate Elimination Using Sorting
738
2
Grouping and Aggregation Using Sorting
740
1
A Sort-Based Union Algorithm
741
1
Sort-Based Intersection and Difference
742
1
A Simple Sort-Based Join Algorithm
743
2
Analysis of Simple Sort-Join
745
1
A More Efficient Sort-Based Join
746
1
Summary of Sort-Based Algorithms
747
1
Exercises for Section 15.4
748
1
Two-Pass Algorithms Based on Hashing
749
8
Partitioning Relations by Hashing
750
1
A Hash-Based Algorithm for Duplicate Elimination
750
1
Hash-Based Grouping and Aggregation
751
1
Hash-Based Union, Intersection, and Difference
751
1
The Hash-Join Algorithm
752
1
Saving Some Disk I/O's
753
2
Summary of Hash-Based Algorithms
755
1
Exercises for Section 15.5
756
1
Index-Based Algorithms
757
8
Clustering and Nonclustering Indexes
757
1
Index-Based Selection
758
2
Joining by Using an Index
760
1
Joins Using a Sorted Index
761
2
Exercises for Section 15.6
763
2
Buffer Management
765
6
Buffer Management Architecture
765
1
Buffer Management Strategies
766
2
The Relationship Between Physical Operator Selection and Buffer Management
768
2
Exercises for Section 15.7
770
1
Algorithms Using More Than Two Passes
771
4
Multipass Sort-Based Algorithms
771
1
Performance of Multipass, Sort-Based Algorithms
772
1
Multipass Hash-Based Algorithms
773
1
Performance of Multipass Hash-Based Algorithms
773
1
Exercises for Section 15.8
774
1
Parallel Algorithms for Relational Operations
775
8
Models of Parallelism
775
2
Tuple-at-a-Time Operations in Parallel
777
2
Parallel Algorithms for Full-Relation Operations
779
1
Performance of Parallel Algorithms
780
2
Exercises for Section 15.9
782
1
Summary of Chapter 15
783
1
References for Chapter 15
784
3
The Query Compiler
787
88
Parsing
788
7
Syntax Analysis and Parse Trees
788
1
A Grammar for a Simple Subset of SQL
789
4
The Preprocessor
793
1
Exercises for Section 16.1
794
1
Algebraic Laws for Improving Query Plans
795
15
Commutative and Associative Laws
795
2
Laws Involving Selection
797
3
Pushing Selections
800
2
Laws Involving Projection
802
3
Laws About Joins and Products
805
1
Laws Involving Duplicate Elimination
805
1
Laws Involving Grouping and Aggregation
806
3
Exercises for Section 16.2
809
1
From Parse Trees to Logical Query Plans
810
11
Conversion to Relational Algebra
811
1
Removing Subqueries From Conditions
812
5
Improving the Logical Query Plan
817
2
Grouping Associative/Commutative Operators
819
1
Exercises for Section 16.3
820
1
Estimating the Cost of Operations
821
14
Estimating Sizes of Intermediate Relations
822
1
Estimating the Size of a Projection
823
1
Estimating the Size of a Selection
823
3
Estimating the Size of a Join
826
3
Natural Joins With Multiple Join Attributes
829
1
Joins of Many Relations
830
2
Estimating Sizes for Other Operations
832
2
Exercises for Section 16.4
834
1
Introduction to Cost-Based Plan Selection
835
12
Obtaining Estimates for Size Parameters
836
3
Computation of Statistics
839
1
Heuristics for Reducing the Cost of Logical Query Plans
840
2
Approaches to Enumerating Physical Plans
842
3
Exercises for Section 16.5
845
2
Choosing an Order for Joins
847
12
Significance of Left and Right Join Arguments
847
1
Join Trees
848
1
Left-Deep Join Trees
848
4
Dynamic Programming to Select a Join Order and Grouping
852
4
Dynamic Programming With More Detailed Cost Functions
856
1
A Greedy Algorithm for Selecting a Join Order
857
1
Exercises for Section 16.6
858
1
Completing the Physical-Query-Plan
859
13
Choosing a Selection Method
860
2
Choosing a Join Method
862
1
Pipelining Versus Materialization
863
1
Pipelining Unary Operations
864
1
Pipelining Binary Operations
864
3
Notation for Physical Query Plans
867
3
Ordering of Physical Operations
870
1
Exercises for Section 16.7
871
1
Summary of Chapter 16
872
2
References for Chapter 16
874
1
Coping With System Failures
875
42
Issues and Models for Resilient Operation
875
9
Failure Modes
876
1
More About Transactions
877
2
Correct Execution of Transactions
879
1
The Primitive Operations of Transactions
880
3
Exercises for Section 17.1
883
1
Undo Logging
884
13
Log Records
884
1
The Undo-Logging Rules
885
4
Recovery Using Undo Logging
889
1
Checkpointing
890
2
Nonquiescent Checkpointing
892
3
Exercises for Section 17.2
895
2
Redo Logging
897
6
The Redo-Logging Rule
897
1
Recovery With Redo Logging
898
2
Checkpointing a Redo Log
900
1
Recovery With a Checkpointed Redo Log
901
1
Exercises for Section 17.3
902
1
Undo/Redo Logging
903
6
The Undo/Redo Rules
903
1
Recovery With Undo/Redo Logging
904
1
Checkpointing an Undo/Redo Log
905
3
Exercises for Section 17.4
908
1
Protecting Against Media Failures
909
5
The Archive
909
1
Nonquiescent Archiving
910
3
Recovery Using an Archive and Log
913
1
Exercises for Section 17.5
914
1
Summary of Chapter 17
914
1
References for Chapter 17
915
2
Concurrency Control
917
72
Serial and Serializable Schedules
918
7
Schedules
918
1
Serial Schedules
919
1
Serializable Schedules
920
1
The Effect of Transaction Semantics
921
2
A Notation for Transactions and Schedules
923
1
Exercises for Section 18.1
924
1
Conflict-Serializability
925
7
Conflicts
925
1
Precedence Graphs and a Test for Conflict-Serializability
926
3
Why the Precedence-Graph Test Works
929
1
Exercises for Section 18.2
930
2
Enforcing Serializability by Locks
932
8
Locks
933
1
The Locking Scheduler
934
2
Two-Phase Locking
936
1
Why Two-Phase Locking Works
937
1
Exercises for Section 18.3
938
2
Locking Systems With Several Lock Modes
940
11
Shared and Exclusive Locks
941
2
Compatibility Matrices
943
1
Upgrading Locks
943
2
Update Locks
945
1
Increment Locks
946
3
Exercises for Section 18.4
949
2
An Architecture for a Locking Scheduler
951
6
A Scheduler That Inserts Lock Actions
951
3
The Lock Table
954
3
Exercises for Section 18.5
957
1
Managing Hierarchies of Database Elements
957
6
Locks With Multiple Granularity
957
1
Warning Locks
958
3
Phantoms and Handling Insertions Correctly
961
2
Exercises for Section 18.6
963
1
The Tree Protocol
963
6
Motivation for Tree-Based Locking
963
1
Rules for Access to Tree-Structured Data
964
1
Why the Tree Protocol Works
965
3
Exercises for Section 18.7
968
1
Concurrency Control by Timestamps
969
10
Timestamps
970
1
Physically Unrealizable Behaviors
971
1
Problems With Dirty Data
972
1
The Rules for Timestamp-Based Scheduling
973
2
Multiversion Timestamps
975
3
Timestamps and Locking
978
1
Exercises for Section 18.8
978
1
Concurrency Control by Validation
979
6
Architecture of a Validation-Based Scheduler
979
1
The Validation Rules
980
3
Comparison of Three Concurrency-Control Mechanisms
983
1
Exercises for Section 18.9
984
1
Summary of Chapter 18
985
2
References for Chapter 18
987
2
More About Transaction Management
989
58
Serializability and Recoverability
989
14
The Dirty-Data Problem
990
2
Cascading Rollback
992
1
Recoverable Schedules
992
1
Schedules That Avoid Cascading Rollback
993
1
Managing Rollbacks Using Locking
994
2
Group Commit
996
1
Logical Logging
997
3
Recovery From Logical Logs
1000
1
Exercises for Section 19.1
1001
2
View Serializability
1003
6
View Equivalence
1003
1
Polygraphs and the Test for View-Serializability
1004
3
Testing for View-Serializability
1007
1
Exercises for Section 19.2
1008
1
Resolving Deadlocks
1009
9
Deadlock Detection by Timeout
1009
1
The Waits-For Graph
1010
2
Deadlock Prevention by Ordering Elements
1012
2
Detecting Deadlocks by Timestamps
1014
2
Comparison of Deadlock-Management Methods
1016
1
Exercises for Section 19.3
1017
1
Distributed Databases
1018
5
Distribution of Data
1019
1
Distributed Transactions
1020
1
Data Replication
1021
1
Distributed Query Optimization
1022
1
Exercises for Section 19.4
1022
1
Distributed Commit
1023
6
Supporting Distributed Atomicity
1023
1
Two-Phase Commit
1024
2
Recovery of Distributed Transactions
1026
2
Exercises for Section 19.5
1028
1
Distributed Locking
1029
6
Centralized Lock Systems
1030
1
A Cost Model for Distributed Locking Algorithms
1030
1
Locking Replicated Elements
1031
1
Primary-Copy Locking
1032
1
Global Locks From Local Locks
1033
1
Exercises for Section 19.6
1034
1
Long-Duration Transactions
1035
6
Problems of Long Transactions
1035
2
Sagas
1037
1
Compensating Transactions
1038
2
Why Compensating Transactions Work
1040
1
Exercises for Section 19.7
1041
1
Summary of Chapter 19
1041
3
References for Chapter 19
1044
3
Information Integration
1047
54
Modes of Information Integration
1047
10
Problems of Information Integration
1048
1
Federated Database Systems
1049
2
Data Warehouses
1051
2
Mediators
1053
3
Exercises for Section 20.1
1056
1
Wrappers in Mediator-Based Systems
1057
7
Templates for Query Patterns
1058
1
Wrapper Generators
1059
1
Filters
1060
2
Other Operations at the Wrapper
1062
1
Exercises for Section 20.2
1063
1
Capability-Based Optimization in Mediators
1064
6
The Problem of Limited Source Capabilities
1065
1
A Notation for Describing Source Capabilities
1066
1
Capability-Based Query-Plan Selection
1067
2
Adding Cost-Based Optimization
1069
1
Exercises for Section 20.3
1069
1
On-Line Analytic Processing
1070
9
OLAP Applications
1071
1
A Multidimensional View of OLAP Data
1072
1
Star Schemas
1073
3
Slicing and Dicing
1076
2
Exercises for Section 20.4
1078
1
Data Cubes
1079
10
The Cube Operator
1079
3
Cube Implementation by Materialized Views
1082
3
The Lattice of Views
1085
2
Exercises for Section 20.5
1087
2
Data Mining
1089
8
Data-Mining Applications
1089
3
Finding Frequent Sets of Items
1092
1
The A-Priori Algorithm
1093
3
Exercises for Section 20.6
1096
1
Summary of Chapter 20
1097
1
References for Chapter 20
1098
3
Index
1101