Preface

1 Introduction

1．1 Purpose of Database Systems

1．2 View of Data

1．3 Data Models

1．4 Database Languages

1．5 Transaction Management

1．6 Storage Management

1．7 Database Administrator

1．8 Database Users

1．9 Overall System Structure

1．10 Summary

Exercises

Bibliographic Notes

2．1 Basic Concepts

2 Entity-Relationship Model

2．2 Design Issues

2．3 Mapping Constraints

2．4 Keys

2．5 Entity-Relationship Diagram

2．6 Weak Entity Sets

2．7 Extended E-R Features

2．8 Design of an E-R Database Schema

2．9 Reduction of an E-R Schema to Tables

2．10 Summary

Exercises

Bibliographic Notes

3 Relational Model

3．1 Structure of Relational Databases

3．2 The Relational Algebra

3．3 The Tuple Relational Calculus

3．4 The Domain Relational Calculus

3．5 Extended Relational-Algebra Operatios

3．6 Modification of the Database

3．7 Views

3．8 Summary

Exercises

Bibliographic Notes

4 SQL

4．1 Background

4．2 Basic Structure

4．3 Set Operations

4．4 Aggregate Functions

4．5 Null Values

4．6 Nested Subqueries

4．7 Derived Relations

4．8 Views

4．9 Modification of the Database

4．10 Joined Relations

4．11 Data-Definition Language

4．12 Embedded SQL

4．13 Other SQL Features

4．14 Summary

Exercises

Bibliographic Notes

5 Other Relational Languages

5．1 Query-by-Example

5．2 Quel

5．3Datalog

5．4 Summary

Exercises

Bibliographic Notes

6 Integrity Constraints

6．1 Domain Constraints

6．2 Referential Integrity

6．3 Assertions

6．4 Triggers

6．5 Functional Dependencies

6．6 Summary

Exercises

Bibliographic Notes

7 Relational Database Design

7．1 Pitfalls in Relational-Database Design

7．2 Decomposition

7．3 Normalization Using Functional Dependencies

7．4 Normalization Using Multivalued Dependencies

7．5 Normalization Using Join Dependencies

7．6 Domain-Key Normal Form

7．7 Alternative Approaches to Database Design

7．8 Summary

Exercises

Bibliographic Notes

8 Object-Oriented Databases

8．1 New Database Applications

8．2 The object-Oriented Data Model

8．3 Object-Oriented Languages

8．4 Persistent Programming Languages

8．5 Persistent C++ Systems

8．6 Summary

Exercises

Bibliographic Notes

9 Object-Relational Databases

9．1 Nested Relations

9．2 Complex Types and Object Orientation

9．3 Querying with Commplex Types

9．4 Creation of Complex Values and Objects

9．5 Comparison of Object-Oriented and Object-Relational Databases

9．6 Summary

Exercises

Bibliographic Notes

10 Storage and File Structure

10．1 Overview of Physical Storage Media

10．2 Magnetic Disks

10．3 RAID

10．4 Tertiary Storage

10．5 Storage Access

10．6 File Organization

10．7 Organization of Records in Files

10．8 Data-Dictionary Storage

10．9 Storage Structures for Object-Oriented Databases

10．10 Summary

Exercises

Bibliographic Notes

11 Indexing and Hashing

11．1 Basic Concepts

11．2 Ordered Indices

11．3 B+-Tree Index Files

11．4 B-Tree Index Files

11．5 Static Hashing

11．6 Dynamic Hashing

11．7 Comparison of Ordered Indexing and Hashing

11．8 Index Definition in SQL

11．9 Multiple-Key Access

11．10 Summary

Exercises

Bibliographic Notes

12 Query Processing

12．1 Overview

12．2 Catalog Information for Cost Estimation

12．4 Selection Operation

12．3 Measures of Query Cost

12．5 Sorting

12．6 Join Operation

12．7 Other Operations

12．8 Evaluation of Expressions

12．9 Transformation of Relational Expressions

12．10 Choice of Evaluation Plans

12．11 Summary

Exercises

Bibliographic Notes

13 Transactions

13．1 Transaction Concept

13．2 Transaction State

13．3 Implementation of Atomicity and Durability

13．4 Concurrent Executions

13．5 Serializability

13．6 Recoverability

13．7 Implementation of Isolation

13．8 Transaction Definition in SQL

13．9 Testing for Serializability

13．10 Summary

Exercises

Bibliographic Notes

14 Concurrency Control

14．1 Lock-Based Protocols

14．2 Timestamp-Based Protocols

14．3 Validation-Based Protocols

14．4 Multiple Granularity

14．5 Multiversion Schemes

14．6 Deadlock Handling

14．7 Insert and Delete Operations

14．8 Concurrency in Index Structures

14．9 Summary

Exercises

Bibliographic Notes

15 Recovery System

15．1 Failure Classification

15．2 Storage Structure

15．3 Recovery and Atomicity

15．4 Log-Based Recovery

15．5 Shadow Paging

15．6 Recovery with Concurrent Transactions

15．7 Buffer Management

15．8 Failure with Loss of Nonvolatile Storage

15．9 Advanced Recovery Techniques

15．10 Summary

Exercises

Bibliographic Notes

16 Database System Architectures

16．1 Centralized Systems

16．2 Client-Server Systems

16．3 Parallel Systems

16．4 Distributed Systems

16．5 Network Types

16．6 Summary

Exercises

Bibliographic Notes

17 Parallel Databases

17．1 Introduction

17．2 I/O Parallelism

17．3 Interquery Parallelism

17．4 Intraquery Parallelism

17．5 Intraoperation parallelism

17．6 Interoperation Parallelism

17．7 Design of Parallel Systems

Exercises

17．8 Summary

Bibliographic Notes

18 Distributed Databases

18．1 Distributed Data Storage

18．2 Network Transparency

18．3 Distributed Query Processing

18．4 Distributed Transaction Model

18．5 Commit Protocols

18．6 Coordinator Selection

18．7 Concurrency Control

18．8 Deadlock Handling

18．9 Multidatabase Systems

18．10 Summary

Exercises

Bibliographic Notes

19．1 Security and Integrity

19 Special Topics

19．2 Standardization

19．3 Performance Benchmarks

19．4 Performance Tuning

19．5 Time in Databases

19．6 User Interfaces

19．7 Active Databases

19．8 Summary

Exercises

Bibliographic Notes

20 Advanced Transaction Processing

20．1 Remote Backup Systems

20．2 Transaction-Processing Monitors

20．3 High-Performance Transaction Systems

20．4 Long-Duration Transactions

20．5 Real-Time Transaction Systems

20．6 Weak Levels of Consistency

20．7 Transactional Workflows

20．8 Summary

Exercises

Bibliographic Notes

21 New Applications

21．1 Decision-Support Systems

21．2 Data Analysis

21．3 Data Mining

21．4 Data Warehousing

21．5 Spatial and Geographic Databases

21．6 Multimedia Databases

21．7 Mobility and Personal Databases

21．8 Information-Retrieval Systems

21．9 Distributed Information Systems

21．10 The World Wide Web

21．11 Summary

Exercises

Bibliographic Notes

A Network Model

A．1 Basic Concepts

A．2 Data-Structure Diagrams

A．3 The DBTG CODASYL Model

A．4 Implementation Techniques

A．5 Discussion

B Hierarchical Model

B．1 Basic Concepts

B．2 Tree-Structure Diagrams

B．3 Implementation Techniques

B．4 The IMS Database System

B．5 Discussion

Bibliography

Index