Database Systems: The Complete Book

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

• ISBN13: 9780130319951
• ISBN10: 0130319953
• Edition: 2nd
• Format: Hardcover
• Copyright: 2009-01-01
• Publisher: Prentice Hall

Summary

For Database Systems and Database Design and Application courses offered at the junior, senior and graduate levels in Computer Science departments.Written by well-known computer scientists, this introduction to database systems offers a comprehensive approach, focusing on database design, database use, and implementation of database applications and database management systems.The first half of the book provides in-depth coverage of databases from the point of view of the database designer, user, and application programmer. It covers the latest database standards SQL:1999, SQL/PSM, SQL/CLI, JDBC, ODL, and XML, with broader coverage of SQL than most other texts. The second half of the book provides in-depth coverage of databases from the point of view of the DBMS implementor. It focuses on storage structures, query processing, and transaction management. The book covers the main techniques in these areas with broader coverage of query optimization than most other texts, along with advanced topics including multidimensional and bitmap indexes, distributed transactions, and information integration techniques.Resources:Author Website http://infolab.stanford.edu/~ullman/dscb.html

Author Biography

Hector Garcia-Molina is the L. Bosack and S. Lerner Professor of Computer Science and Electrical Engineering, and Chair of the Department of Computer Science at Stanford University.

Table of Contents

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

Excerpts

At Stanford, we are on the quarter system, and as a result, our introductory database instruction is divided into two courses. The first, CS145, is designed for students who will use database systems but not necessarily take a job implementing a DBMS. It is a prerequisite for CS245, which is the introduction to DBMS implementation. Students wishing to go further in the database field then take CS345 (theory), CS346 (DBMS implementation project), and CS347 (transaction processing and distributed databases). Starting in 1997, we published a pair of books. A First Course in Database Systems was designed for CS145, and Database System Implementation was for CS245 and parts of CS346. Because many schools are on the semester system or combine the two kinds of database instruction into one introductory course, we felt that there was a need to produce the two books as a single volume. At the same time, the evolution of database systems has made a number of new topics imperative for a modern course. Thus, we have added, mostly to the application-programming area, topics such as object-relational data, SQL/PSM (stored programs), SQL/CLI (the emerging standard for the C/SQL interface), and JDBC (the same for Java/SQL). Use of the Book We recommend that two quarters be devoted to the material in this book. If you follow the Stanford approach, you would cover the first ten chapters in the first quarter and the last ten in the second quarter. Should you wish to cover the material in a single semester, then there will have to be some omitted portions. In general, we suggest that Chapters 2-7, 11-13, and 17-18 should be given highest priority, but there are pieces from each of these chapters that can be skipped. If, as we do in CS145, you give students a substantial database-application design and implementation project, then you may have to reorder the material somewhat, so that SQL instruction occurs earlier in the Book. You may wish to defer material such as dependencies, although students need normalization for design. Prerequisites We have used the book at the "mezzanine" level, in courses taken both by undergraduates and beginning graduate students. The formal prerequisites for the courses are Sophomore-level treatments of: (1) Data structures, algorithms, and discrete math, and (2) Software systems, software engineering, and programming languages. Of this material, it is important that students have at least a rudimentary understanding of such topics as: algebraic expressions and laws, logic, basic data structures such as search trees and graphs, object-oriented programming concepts, and programming environments. However, we believe that adequate background is surely acquired by the end of the Junior year in a. typical computer science program. 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 exclamation 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 exerciseBasks for modification or adaptation of your solution to another exerciseA. If certain parts ofAhave solutions, then you should expect the corresponding parts ofBto have solutions as well. Support on the World Wide Web The book's home page is http://www-db.stanford.edu/~ullman/dscb.html Here are solutions to starred exercises, errata as we learn of them, and backup materials. We are making available the notes for each offering of CS145 and CS245 as we teach them, including homeworks, projects and exams.