Part Ⅰ BASICS

1 INTRODUCTION TO DATABASE SYSTEMS

1.1 Overview

1.2 A Historical Perspective

1.3 File Systems versus a DBMS

1.4 Advantages of a DBMS

1.5 Describing and Storing Data in a DBMS

1.5.1 The Relational Model

1.5.2 Levels of Abstraction in a DBMS

1.5.3 Data Independence

1.6 Queries in a DBMS

1.7 Transaction Management

1.7.1 Concurrent Execution of Transactions

1.7.2 Incomplete Transactions and System Crashes

1.7.3 Points to Note

1.8 Structure of a DBMS

1.9 People Who Deal with Databases

1.10 Points to Review

2 THE ENTITY-RELATIONSHIP MODEL

2.1 Overview of Database Design

2.1.1 Beyond the ER Model

2.2 Entities, Attributes, and Entity Sets

2.3 Relationships and Relationship Sets

2.4 Additional Features of the ER Model

2.4.1 Key Constraints

2.4.2 Participation Constraints

2.4.3 Weak Entities

2.4.4 Class Hierarchies

2.4.5 Aggregation

2.5 Conceptual Database Design With the ER Model

2.5.1 Entity versus Attribute

2.5.2 Entity versus Relationship

2.5.3 Binary versus Ternary Relationships

2.5.4 Aggregation versus Ternary Relationships

2.6 Conceptual Design for Large Enterprises

2.7 Points to Review

3 THE RELATIONAL MODEL

3.1 Introduction to the Relational Model

3.1.1 Creating and Modifying Relations Using SQL-92

3.2 Integrity Constraints over Relations

3.2.1 Key Constraints

3.2.2 Foreign Key Constraints

3.2.3 General Constraints

3.3 Enforcing Integrity Constraints

3.4 Querying Relational Data

3.5 Logical Database Design: ER to Relational

3.5.1 Entity Sets to Tables

3.5.2 Relationship Sets (without Constraints) to Tables

3.5.3 Translating Relationship Sets with Key Constraints

3.5.4 Translating Relationship Sets with Participation Constraints

3.5.5 Translating Weak Entity Sets

3.5.6 Translating Class Hierarchies

3.5.7 Translating ER Diagrams with Aggregation

3.5.8 ER to Relational: Additional Examples

3.6 Introduction to Views

3.6.1 Views, Data Independence, Security

3.6.2 Updates on Views

3.7 Destroying/Altering Tables and Views

3.8 Points to Review

Part Ⅱ RELATIONAL QUERIES

4 RELATIONAL ALGEBRA AND CALCULUS

4.1 Preliminaries

4.2 Relational Algebra

4.2.1 Selection and Projection

4.2.2 Set Operations

4.2.3 Renaming

4.2.4 Joins

4.2.5 Division

4.2.6 More Examples of Relational Algebra Queries

4.3 Relational Calculus

4.3.1 Tuple Relational Calculus

4.3.2 Domain Relational Calculus

4.4 Expressive Power of Algebra and Calculus

4.5 Points to Review

5 SQL: QUERIES, PROGRAMMING, TRIGGERS

5.1 About the Examples

5.2 The Form of a Basic SQL Query

5.2.1 Examples of Basic SQL Queries

5.2.2 Expressions and Strings in the SELECT Command

5.3 UNION, INTERSECT, and EXCEPT

5.4 Nested Queries

5.4.1 Introduction to Nested Queries

5.4.2 Correlated Nested Queries

5.4.3 Set-Comparison Operators

5.4.4 More Examples of Nested Queries

5.5 Aggregate Operators

5.5.1 The GROUP BY and HAVING Clauses

5.5.2 More Examples of Aggregate Queries

5.6 Null Values

5.6.1 Comparisons Using Null Values

5.6.2 Logical Connectives AND, OR, and NOT

5.6.3 Impact on SQL Constructs

5.6.4 Outer Joins

5.6.5 Disallowing Null Values

5.7 Embedded SQL

5.7.1 Declaring Variables and Exceptions

5.7.2 Embedding SQL Statements

5.8 Cursors

5.8.1 Basic Cursor Definition and Usage

5.8.2 Properties of Cursors

5.9 Dynamic SQL

5.10 ODBC and JDBC

5.10.1 Architecture

5.10.2 An Example Using JDBC

5.11 Complex Integrity Constraints in SQL-92

5.11.1 Constraints over a Single Table

5.11.2 Domain Constraints

5.11.3 Assertions: ICs over Several Tables

5.12 Triggers and Active Databases

5.12.1 Examples of Triggers in SQL

5.13 Designing Active Databases

5.13.1 Why Triggers Can Be Hard to Understand

5.13.2 Constraints versus Triggers

5.13.3 Other Uses of Triggers

5.14 Points to Review

6 QUERY-BY-EXAMPLE (QBE)

6.1 Introduction

6.2 Basic QBE Queries

6.2.1 Other Features: Duplicates, Ordering Answers

6.3 Queries over Multiple Relations

6.4 Negation in the Relation-Name Column

6.5 Aggregates

6.6 The Conditions Box

6.6.1 And/Or Queries

6.7 Unnamed Columns

6.8 Updates

6.8.1 Restrictions on Update Commands

6.9 Division and Relational Completeness

6.10 Points to Review

Part Ⅲ DATA STORAGE AND INDEXING

7 STORING DATA: DISKS AND FILES

7.1 The Memory Hierarchy

7.1.1 Magnetic Disks

7.1.2 Performance Implications of Disk Structure

7.2 RAID

7.2.1 Data Striping

7.2.2 Redundancy

7.2.3 Levels of Redundancy

7.2.4 Choice of RAID Levels

7.3 Disk Space Management

7.3.1 Keeping Track of Free Blocks

7.3.2 Using OS File Systems to Manage Disk Space

7.4 Buffer Manager

7.4.1 Buffer Replacement Policies

7.4.2 Buffer Management in DBMS versus OS

7.5 Files and Indexes

7.5.1 Heap Files

7.5.2 Introduction to Indexes

7.6 Page Formats

7.6.1 Fixed-Length Records

7.6.2 Variable-Length Records

7.7 Record Formats

7.7.1 Fixed-Length Records

7.7.2 Variable-Length Records

7.8 Points to Review

8 FILE ORGANIZATIONS AND INDEXES

8.1 Cost Model

8.2 Comparison of Three File Organizations

8.2.1 Heap Files

8.2.2 Sorted Files

8.2.3 Hashed Files

8.2.4 Choosing a File Organization

8.3 Overview of Indexes

8.3.1 Alternatives for Data Entries in an Index

8.4 Properties of Indexes

8.4.1 Clustered versus Unclustered Indexes

8.4.2 Dense versus Sparse Indexes

8.4.3 Primary and Secondary Indexes

8.4.4 Indexes Using Composite Search Keys

8.5 Index Specification in SQL-92

8.6 Points to Review

9 TREE-STRUCTURED INDEXING

9.1 Indexed Sequential Access Method (ISAM)

9.2 B+ Trees: A Dynamic Index Structure

9.3 Format of a Node

9.4 Search

9.5 Insert

9.6 Delete

9.7 Duplicates

9.8 B+ Trees in Practice

9.8.1 Key Compression

9.8.2 Bulk-Loading a B+ Tree

9.8.3 The Order Concept

9.8.4 The Effect of Inserts and Deletes on Rids

9.9 Points to Review

10 HASH-BASED INDEXING

10.1 Static Hashing

10.1.1 Notation and Conventions

10.2 Extendible Hashing

10.3 Linear Hashing

10.4 Extendible Hashing versus Linear Hashing

10.5 Points to Review

Part Ⅳ QUERY EVALUATION

11 EXTERNAL SORTING

11.1 A Simple Two-Way Merge Sort

11.2 External Merge Sort

11.2.1 Minimizing the Number of Runs

11.3 Minimizing I/O Cost versus Number of I/Os

11.3.1 Blocked I/O

11.3.2 Double Buffering

11.4 Using B+ Trees for Sorting

11.4.1 Clustered Index

11.4.2 Unclustered Index

11.5 Points to Review

12 EVALUATION OF RELATIONAL OPERATORS

12.1 Introduction to Query Processing

12.1.1 Access Paths

12.1.2 Preliminaries: Examples and Cost Calculations

12.2 The Selection Operation

12.2.1 No Index, Unsorted Data

12.2.2 No Index, Sorted Data

12.2.3 B+ Tree Index

12.2.4 Hash Index, Equality Selection

12.3 General Selection Conditions

12.3.1 CNF and Index Matching

12.3.2 Evaluating Selections without Disjunction

12.3.3 Selections with Disjunction

12.4 The Projection Operation

12.4.1 Projection Based on Sorting

12.4.2 Projection Based on Hashing

12.4.3 Sorting versus Hashing for Projections

12.4.4 Use of Indexes for Projections

12.5 The Join Operation

12.5.1 Nested Loops Join

12.5.2 Sort-Merge Join

12.5.3 Hash Join

12.5.4 General Join Conditions

12.6 The Set Operations

12.6.1 Sorting for Union and Difference

12.6.2 Hashing for Union and Difference

12.7 Aggregate Operations

12.7.1 Implementing Aggregation by Using an Index

12.8 The Impact of Buffering

12.9 Points to Review

13 INTRODUCTION TO QUERY OPTIMIZATION

13.1 Overview of Relational Query Optimization

13.1.1 Query Evaluation Plans

13.1.2 Pipelined Evaluation

13.1.3 The Iterator Interface for Operators and Access Methods

13.1.4 The System R Optimizer

13.2 System Catalog in a Relational DBMS

13.2.1 Information Stored in the System Catalog

13.3 Alternative Plans: A Motivating Example

13.3.1 Pushing Selections

13.3.2 Using Indexes

13.4 Points to Review

14 A TYPICAL RELATIONAL QUERY OPTIMIZER

14.1 Translating SQL Queries into Algebra

14.1.1 Decomposition of a Query into Blocks

14.1.2 A Query Block as a Relational Algebra Expression

14.2 Estimating the Cost of a Plan

14.2.1 Estimating Result Sizes

14.3 Relational Algebra Equivalences

14.3.1 Selections

14.3.2 Projections

14.3.3 Cross-Products and Joins

14.3.4 Selects, Projects, and Joins

14.3.5 Other Equivalences

14.4 Enumeration of Alternative Plans

14.4.1 Single-Relation Queries

14.4.2 Multiple-Relation Queries

14.5 Nested Subqueries

14.6 Other Approaches to Query Optimization

14.7 Points to Review

Part Ⅴ DATABASE DESIGN

15 SCHEMA REFINEMENT AND NORMAL FORMS

15.1 Introduction to Schema Refinement

15.1.1 Problems Caused by Redundancy

15.1.2 Use of Decompositions

15.1.3 Problems Related to Decomposition

15.2 Functional Dependencies

15.3 Examples Motivating Schema Refinement

15.3.1 Constraints on an Entity Set

15.3.2 Constraints on a Relationship Set

15.3.3 Identifying Attributes of Entities

15.3.4 Identifying Entity Sets

15.4 Reasoning about Functional Dependencies

15.4.1 Closure of a Set of FDs

15.4.2 Attribute Closure

15.5 Normal Forms

15.5.1 Boyce-Codd Normal Form

15.5.2 Third Normal Form

15.6 Decompositions

15.6.1 Lossless-Join Decomposition

15.6.2 Dependency-Preserving Decomposition

15.7 Normalization

15.7.1 Decomposition into BCNF

15.7.2 Decomposition into 3NF

15.8 Other Kinds of Dependencies

15.8.1 Multivalued Dependencies

15.8.2 Fourth Normal Form

15.8.3 Join Dependencies

15.8.4 Fifth Normal Form

15.8.5 Inclusion Dependencies

15.9 Points to Review

16 PHYSICAL DATABASE DESIGN AND TUNING

16.1 Introduction to Physical Database Design

16.1.1 Database Workloads

16.1.2 Physical Design and Tuning Decisions

16.1.3 Need for Database Tuning

16.2 Guidelines for Index Selection

16.3 Basic Examples of Index Selection

16.4 Clustering and Indexing

16.4.1 Co-clustering Two Relations

16.5 Indexes on Multiple-Attribute Search Keys

16.6 Indexes that Enable Index-Only Plans

16.7 Overview of Database Tuning

16.7.1 Tuning Indexes

16.7.2 Tuning the Conceptual Schema

16.7.3 Tuning Queries and Views

16.8 Choices in Tuning the Conceptual Schema

16.8.1 Settling for a Weaker Normal Form

16.8.2 Denormalization

16.8.3 Choice of Decompositions

16.8.4 Vertical Decomposition

16.8.5 Horizontal Decomposition

16.9 Choices in Tuning Queries and Views

16.10 Impact of Concurrency

16.11 DBMS Benchmarking

16.11.1 Well-Known DBMS Benchmarks

16.11.2 Using a Benchmark

16.12 Points to Review

17 SECURITY

17.1 Introduction to Database Security

17.2 Access Control

17.3 Discretionary Access Control

17.3.1 Grant and Revoke on Views and Integrity Constraints

17.4 Mandatory Access Control

17.4.1 Multilevel Relations and Polyinstantiation

17.4.2 Covert Channels, DoD Security Levels

17.5 Additional Issues Related to Security

17.5.1 Role of the Database Administrator

17.5.2 Security in Statistical Databases

17.5.3 Encryption

17.6 Points to Review

Part Ⅵ TRANSACTION MANAGEMENT

18 TRANSACTION MANAGEMENT OVERVIEW

18.1 The Concept of a Transaction

18.1.1 Consistency and Isolation

18.1.2 Atomicity and Durability

18.2 Transactions and Schedules

18.3 Concurrent Execution of Transactions

18.3.1 Motivation for Concurrent Execution

18.3.2 Serializability

18.3.3 Some Anomalies Associated with Interleaved Execution

18.3.4 Schedules Involving Aborted Transactions

18.4 Lock-Based Concurrency Control

18.4.1 Strict Two-Phase Locking (Strict 2PL)

18.5 Introduction to Crash Recovery

18.5.1 Stealing Frames and Forcing Pages

18.5.2 Recovery-Related Steps during Normal Execution

18.5.3 Overview of ARIES

18.6 Points to Review

19 CONCURRENCY CONTROL

19.1 Lock-Based Concurrency Control Revisited

19.1.1 2PL, Serializability, and Recoverability

19.1.2 View Serializability

19.2 Lock Management

19.2.1 Implementing Lock and Unlock Requests

19.2.2 Deadlocks

19.2.3 Performance of Lock-Based Concurrency Control

19.3 Specialized Locking Techniques

19.3.1 Dynamic Databases and the Phantom Problem

19.3.2 Concurrency Control in B+ Trees

19.3.3 Multiple-Granularity Locking

19.4 Transaction Support in SQL-92

19.4.1 Transaction Characteristics

19.4.2 Transactions and Constraints

19.5 Concurrency Control without Locking

19.5.1 Optimistic Concurrency Control

19.5.2 Timestamp-Based Concurrency Control

19.5.3 Multiversion Concurrency Control

19.6 Points to Review

20 CRASH RECOVERY

20.1 Introduction to ARIES

20.1.1 The Log

20.1.2 Other Recovery-Related Data Structures

20.1.3 The Write-Ahead Log Protocol

20.1.4 Checkpointing

20.2 Recovering from a System Crash

20.2.1 Analysis Phase

20.2.2 Redo Phase

20.2.3 Undo Phase

20.3 Media Recovery

20.4 Other Algorithms and Interaction with Concurrency Control

20.5 Points to Review

Part Ⅶ ADVANCED TOPICS

21 PARALLEL AND DISTRIBUTED DATABASES

21.1 Architectures for Parallel Databases

21.2 Parallel Query Evaluation

21.2.1 Data Partitioning

21.2.2 Parallelizing Sequential Operator Evaluation Code

21.3 Parallelizing Individual Operations

21.3.1 Bulk Loading and Scanning

21.3.2 Sorting

21.3.3 Joins

21.4 Parallel Query Optimization

21.5 Introduction to Distributed Databases

21.5.1 Types of Distributed Databases

21.6 Distributed DBMS Architectures

21.6.1 Client-Server Systems

21.6.2 Collaborating Server Systems

21.6.3 Middleware Systems

21.7 Storing Data in a Distributed DBMS

21.7.1 Fragmentation

21.7.2 Replication

21.8 Distributed Catalog Management

21.8.1 Naming Objects

21.8.2 Catalog Structure

21.8.3 Distributed Data Independence

21.9 Distributed Query Processing

21.9.1 Nonjoin Queries in a Distributed DBMS

21.9.2 Joins in a Distributed DBMS

21.9.3 Cost-Based Query Optimization

21.10 Updating Distributed Data

21.10.1 Synchronous Replication

21.10.2 Asynchronous Replication

21.11 Introduction to Distributed Transactions

21.12 Distributed Concurrency Control

21.12.1 Distributed Deadlock

21.13 Distributed Recovery

21.13.1 Normal Execution and Commit Protocols

21.13.2 Restart after a Failure

21.13.3 Two-Phase Commit Revisited

21.13.4 Three-Phase Commit

21.14 Points to Review

22 INTERNET DATABASES

22.1 The World Wide Web

22.1.1 Introduction to HTML

22.1.2 Databases and the Web

22.2 Architecture

22.2.1 Application Servers and Server-Side Java

22.3 Beyond HTML

22.3.1 Introduction to XML

22.3.2 XML DTDs

22.3.3 Domain-Specific DTDs

22.3.4 XML-QL: Querying XML Data

22.3.5 The Semistructured Data Model

22.3.6 Implementation Issues for Semistructured Data

22.4 Indexing for Text Search

22.4.1 Inverted Files

22.4.2 Signature Files

22.5 Ranked Keyword Searches on the Web

22.5.1 An Algorithm for Ranking Web Pages

22.6 Points to Review

23 DECISION SUPPORT

23.1 Introduction to Decision Support

23.2 Data Warehousing

23.2.1 Creating and Maintaining a Warehouse

23.3 OLAP

23.3.1 Multidimensional Data Model

23.3.2 OLAP Queries

23.3.3 Database Design for OLAP

23.4 Implementation Techniques for OLAP

23.4.1 Bitmap Indexes

23.4.2 Join Indexes

23.4.3 File Organizations

23.4.4 Additional OLAP Implementation Issues

23.5 Views and Decision Support

23.5.1 Views, OLAP, and Warehousing

23.5.2 Query Modification

23.5.3 View Materialization versus Computing on Demand

23.5.4 Issues in View Materialization

23.6 Finding Answers Quickly

23.6.1 Top N Queries

23.6.2 Online Aggregation

23.7 Points to Review

24 DATA MINING

24.1 Introduction to Data Mining

24.2 Counting Co-occurrences

24.2.1 Frequent Itemsets

24.2.2 Iceberg Queries

24.3 Mining for Rules

24.3.1 Association Rules

24.3.2 An Algorithm for Finding Association Rules

24.3.3 Association Rules and ISA Hierarchies

24.3.4 Generalized Association Rules

24.3.5 Sequential Patterns

24.3.6 The Use of Association Rules for Prediction

24.3.7 Bayesian Networks

24.3.8 Classification and Regression Rules

24.4 Tree-Structured Rules

24.4.1 Decision Trees

24.4.2 An Algorithm to Build Decision Trees

24.5 Clustering

24.5.1 A Clustering Algorithm

24.6 Similarity Search over Sequences

24.6.1 An Algorithm to Find Similar Sequences

24.7 Additional Data Mining Tasks

24.8 Points to Review

25 OBJECT-DATABASE SYSTEMS

25.1 Motivating Example

25.1.1 New Data Types

25.1.2 Manipulating the New Kinds of Data

25.2 User-Defined Abstract Data Types

25.2.1 Defining Methods of an ADT

25.3 Structured Types

25.3.1 Manipulating Data of Structured Types

25.4 Objects, Object Identity, and Reference Types

25.4.1 Notions of Equality

25.4.2 Dereferencing Reference Types

25.5 Inheritance

25.5.1 Defining Types with Inheritance

25.5.2 Binding of Methods

25.5.3 Collection Hierarchies, Type Extents, and Queries

25.6 Database Design for an ORDBMS

25.6.1 Structured Types and ADTs

25.6.2 Object Identity

25.6.3 Extending the ER Model

25.6.4 Using Nested Collections

25.7 New Challenges in Implementing an ORDBMS

25.7.1 Storage and Access Methods

25.7.2 Query Processing

25.7.3 Query Optimization

25.8 OODBMS

25.8.1 The ODMG Data Model and ODL

25.8.2 OQL

25.9 Comparing RDBMS with OODBMS and ORDBMS

25.9.1 RDBMS versus ORDBMS

25.9.2 OODBMS versus ORDBMS: Similarities

25.9.3 OODBMS versus ORDBMS: Differences

25.10 Points to Review

26 SPATIAL DATA MANAGEMENT

26.1 Types of Spatial Data and Queries

26.2 Applications Involving Spatial Data

26.3 Introduction to Spatial Indexes

26.3.1 Overview of Proposed Index Structures

26.4 Indexing Based on Space-Filling Curves

26.4.1 Region Quad Trees and Z-Ordering: Region Data

26.4.2 Spatial Queries Using Z-Ordering

26.5 Grid Files

26.5.1 Adapting Grid Files to Handle Regions

26.6 R Trees: Point and Region Data

26.6.1 Queries

26.6.2 Insert and Delete Operations

26.6.3 Concurrency Control

26.6.4 Generalized Search Trees

26.7 Issues in High-Dimensional Indexing

26.8 Points to Review

27 DEDUCTIVE DATABASES

27.1 Introduction to Recursive Queries

27.1.1 Datalog

27.2 Theoretical Foundations

27.2.1 Least Model Semantics

27.2.2 Safe Datalog Programs

27.2.3 The Fixpoint Operator

27.2.4 Least Model = Least Fixpoint

27.3 Recursive Queries with Negation

27.3.1 Range-Restriction and Negation

27.3.2 Stratification

27.3.3 Aggregate Operations

27.4 Efficient Evaluation of Recursive Queries

27.4.1 Fixpoint Evaluation without Repeated Inferences

27.4.2 Pushing Selections to Avoid Irrelevant Inferences

27.5 Points to Review

28 ADDITIONAL TOPICS

28.1 Advanced Transaction Processing

28.1.1 Transaction Processing Monitors

28.1.2 New Transaction Models

28.1.3 Real-Time DBMSs

28.2 Integrated Access to Multiple Data Sources

28.3 Mobile Databases

28.4 Main Memory Databases

28.5 Multimedia Databases

28.6 Geographic Information Systems

28.7 Temporal and Sequence Databases

28.8 Information Visualization

28.9 Summary

A DATABASE DESIGN CASE STUDY: THE INTERNET SHOP

A.1 Requirements Analysis

A.2 Conceptual Design

A.3 Logical Database Design

A.4 Schema Refinement

A.5 Physical Database Design

A.5.1 Tuning the Database

A.6 Security

A.7 Application Layers

B THE MINIBASE SOFTWARE

B.1 What's Available

B.2 Overview of Minibase Assignments

B.2.1 Overview of Programming Projects

B.2.2 Overview of Nonprogramming Assignments

B.3 Acknowledgments

REFERENCES

SUBJECT INDEX

AUTHOR INDEX