Database Systems: The Complete Book

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

Edition: 2nd

ISBN13: 9780130319951

ISBN10: 0130319953

Format: Hardcover

Pub. Date: 2009-01-01

Publisher(s): Prentice Hall

Upgraded Edition: Click here!

Other versions by this Author

List Price: ~~$132.00~~

Rent Textbook

Select for Price

Add to Cart

There was a problem. Please try again later.

New Textbook

We're Sorry
Sold Out

Used Textbook

We're Sorry
Sold Out

eTextbook

We're Sorry
Not Available

Buy from our Marketplace starting at $5.75

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.

The Worlds of Database Systems

(22)

The Evolution of Database Systems

(7)

Early Database Management Systems

(2)

Relational Database Systems

(1)

Smaller and Smaller Systems

(1)

Bigger and Bigger Systems

(1)

Client-Server and Multi-Tier Architectures

(1)

Multimedia Data

(1)

Information Integration

(1)

Overview of a Database Management System

(6)

Data-Definition Language Commands

(1)

Overview of Query Processing

(2)

Storage and Buffer Management

(1)

Transaction Processing

(1)

The Query Processor

(1)

Outline of Database-System Studies

(4)

Database Design

(1)

Database Programming

(1)

Database System Implementation

(2)

Information Integration Overview

(1)

Summary of Chapter 1

(1)

References for Chapter 1

(3)

The Entity-Relationship Data Model

(38)

Elements of the E/R Model

(15)

Entity Sets

(1)

Attributes

(1)

Relationships

(1)

Entity-Relationship Diagrams

(2)

Instances of an E/R Diagram

(1)

Multiplicity of Binary E/R Relationships

(1)

Multiway Relationships

(1)

Roles in Relationships

(2)

Attributes on Relationships

(1)

Converting Multiway Relationships to Binary

(1)

Subclasses in the E/R Model

(3)

Exercises for Section 2.1

(3)

Design Principles

(8)

Faithfulness

(1)

Avoiding Redundancy

(1)

Simplicity Counts

(1)

Choosing the Right Relationships

(2)

Picking the Right Kind of Element

(2)

Exercises for Section 2.2

(3)

The Modeling of Constraints

(7)

Classification of Constraints

(1)

Key in the E/R Model

(2)

Representing Keys in the E/R Model

(1)

Single-Value Constraints

(1)

Referential Integrity

(1)

Referential Integrity in E/R Diagrams

(1)

Other Kinds of Constraints

(1)

Exercises for Section 2.3

(1)

Weak Entity Sets

(5)

Causes of Weak Entity Sets

(2)

Requirements for Weak Entity Sets

(1)

Weak Entity Set Notation

(1)

Exercises for Section 2.4

(1)

Summary of Chapter 2

(1)

References for Chapter 2

(1)

The Relational Data Model

(70)

Basics of the Relational Model

(4)

Attributes

(1)

Schemas

(1)

Tuples

(1)

Domains

(1)

Equivalent Representations of a Relation

(1)

Relation Instances

(1)

Exercises for Section 3.1

(1)

From E/R Diagrams to Relational Designs

(11)

From Entity Sets to Relations

(1)

From E/R Relationships to Relations

(3)

Combining Relations

(1)

Handling Weak Entity Sets

(4)

Exercises for Section 3.2

(1)

Converting Subclass Structures to Relations

(6)

E/R-Style Conversion

(1)

An Object-Oriented Approach

(1)

Using Null Values to Combine Relations

(1)

Comparison of Approaches

(1)

Exercises for Section 3.3

(2)

Functional Dependencies

(8)

Definition of Functional Dependency

(1)

Keys of Relations

(2)

Superkeys

(1)

Discovering Keys for Relations

(1)

Exercises for Section 3.4

(2)

Rules About Functional Dependencies

(12)

The Splitting/Combining Rule

(2)

Trivial Functional Dependencies

(1)

Computing the Closure of Attributes

(3)

Why the Closure Algorithm Works

(1)

The Transitive Rule

(2)

Closing Sets of Functional Dependencies

(1)

Projecting Functional Dependencies

(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.

Database Systems: The Complete Book

Rent Textbook

New Textbook

Used Textbook

eTextbook

How Marketplace Works:

Summary

Author Biography

Table of Contents

Excerpts

Digital License