Fundamentals of Database Systems 7th Edition by Ramez Elmasri, Shamkant Navathe ISBN ‎ 0133970779 ‎ 978-0133970777

Part 1 Introduction to Databases

Chapter 1 Databases and Database Users

1.1 Introduction

1.2 An Example

1.3 Characteristics of the Database Approach

1.3.1 Self-Describing Nature of a Database System

1.3.2 Insulation between Programs and Data, and Data Abstraction

1.3.3 Support of Multiple Views of the Data

1.3.4 Sharing of Data and Multiuser Transaction Processing

1.4 Actors on the Scene

1.4.1 Database Administrators

1.4.2 Database Designers

1.4.3 End Users

1.4.4 System Analysts and Application Programmers (Software Engineers)

1.5 Workers behind the Scene

1.6 Advantages of Using the DBMS Approach

1.6.1 Controlling Redundancy

1.6.2 Restricting Unauthorized Access

1.6.3 Providing Persistent Storage for Program Objects

1.6.4 Providing Storage Structures and Search Techniques for Efficient Query Processing

1.6.5 Providing Backup and Recovery

1.6.6 Providing Multiple User Interfaces

1.6.7 Representing Complex Relationships among Data

1.6.8 Enforcing Integrity Constraints

1.6.9 Permitting Inferencing and Actions Using Rules and Triggers

1.6.10 Additional Implications of Using the Database Approach

Potential for Enforcing Standards. 

Reduced Application Development Time. 

Flexibility. 

Availability of Up-to-Date Information. 

Economies of Scale. 

1.7 A Brief History of Database Applications

1.7.1 Early Database Applications Using Hierarchical and Network Systems

1.7.2 Providing Data Abstraction and Application Flexibility with Relational Databases

1.7.3 Object-Oriented Applications and the Need for More Complex Databases

1.7.4 Interchanging Data on the Web for E-Commerce Using XML

1.7.5 Extending Database Capabilities for New Applications

1.7.6 Emergence of Big Data Storage Systems and NOSQL Databases

1.8 When Not to Use a DBMS

1.9 Summary

Review Questions

Exercises

Selected Bibliography

Chapter 2 Database System Concepts and Architecture

2.1 Data Models, Schemas, and Instances

2.1.1 Categories of Data Models

2.1.2 Schemas, Instances, and Database State

2.2 Three-Schema Architecture and Data Independence

2.2.1 The Three-Schema Architecture

2.2.2 Data Independence

2.3 Database Languages and Interfaces

2.3.1 DBMS Languages

2.3.2 DBMS Interfaces

2.4 The Database System Environment

2.4.1 DBMS Component Modules

2.4.2 Database System Utilities

2.4.3 Tools, Application Environments, and Communications Facilities

2.5 Centralized and Client/Server Architectures for DBMSs

2.5.1 Centralized DBMSs Architecture

2.5.2 Basic Client/Server Architectures

2.5.3 Two-Tier Client/Server Architectures for DBMSs

2.5.4 Three-Tier and n-Tier Architectures for Web Applications

2.6 Classification of Database Management Systems

2.7 Summary

Review Questions

Exercises

Selected Bibliography

Part 2 Conceptual Data Modeling and Database Design

Chapter  3 Data Modeling Using the Entity–Relationship (ER) Model

3.1 Using High-Level Conceptual Data Models for Database Design

3.2 A Sample Database Application

3.3 Entity Types, Entity Sets, Attributes, and Keys

3.3.1 Entities and Attributes

Entities and Their Attributes. 

Composite versus Simple (Atomic) Attributes. 

Single-Valued versus Multivalued Attributes. 

Stored versus Derived Attributes. 

NULL Values. 

Complex Attributes. 

3.3.2 Entity Types, Entity Sets, Keys, and Value Sets

Entity Types and Entity Sets. 

Key Attributes of an Entity Type. 

Value Sets (Domains) of Attributes. 

3.3.3 Initial Conceptual Design of the COMPANY Database

3.4 Relationship Types, Relationship Sets, Roles, and Structural Constraints

3.4.1 Relationship Types, Sets, and Instances

3.4.2 Relationship Degree, Role Names, and Recursive Relationships

Degree of a Relationship Type. 

Relationships as Attributes. 

Role Names and Recursive Relationships. 

3.4.3 Constraints on Binary Relationship Types

Cardinality Ratios for Binary Relationships. 

Participation Constraints and Existence Dependencies. 

3.4.4 Attributes of Relationship Types

3.5 Weak Entity Types

3.6 Refining the ER Design for the COMPANY Database

3.7 ER Diagrams, Naming Conventions, and Design Issues

3.7.1 Summary of Notation for ER Diagrams

3.7.2 Proper Naming of Schema Constructs

3.7.3 Design Choices for ER Conceptual Design

3.7.4 Alternative Notations for ER Diagrams

3.8 Example of Other Notation: UML Class Diagrams

3.9 Relationship Types of Degree Higher than Two

3.9.1 Choosing between Binary and Ternary (or Higher-Degree) Relationships

3.9.2 Constraints on Ternary (or Higher-Degree) Relationships

3.10 Another Example: A UNIVERSITY Database

3.11 Summary

Review Questions

Exercises

Laboratory Exercises

Selected Bibliography

Chapter 4 The Enhanced Entity–Relationship (EER) Model

4.1 Subclasses, Superclasses, and Inheritance

4.2 Specialization and Generalization

4.2.1 Specialization

4.2.2 Generalization

4.3 Constraints and Characteristics of Specialization and Generalization Hierarchies

4.3.1 Constraints on Specialization and Generalization

4.3.2 Specialization and Generalization Hierarchies and Lattices

4.3.3 Utilizing Specialization and Generalization in Refining Conceptual Schemas

4.4 Modeling of UNION Types Using Categories

4.5 A Sample UNIVERSITY EER Schema, Design Choices, and Formal Definitions

4.5.1 A Different UNIVERSITY Database Example

4.5.2 Design Choices for Specialization/Generalization

4.5.3 Formal Definitions for the EER Model Concepts

4.6 Example of Other Notation: Representing Specialization and Generalization in UML Class Diagrams

4.7 Data Abstraction, Knowledge Representation, and Ontology Concepts

4.7.1 Classification and Instantiation

4.7.2 Identification

4.7.3 Specialization and Generalization

4.7.4 Aggregation and Association

4.7.5 Ontologies and the Semantic Web

4.8 Summary

Review Questions

Exercises

Laboratory Exercises

Selected Bibliography

Part 3 The Relational Data Model and SQL

Chapter 5 The Relational Data Model and Relational Database Constraints

5.1 Relational Model Concepts

5.1.1 Domains, Attributes, Tuples, and Relations

5.1.2 Characteristics of Relations

Ordering of Tuples in a Relation. 

Ordering of Values within a Tuple and an Alternative Definition of a Relation. 

Values and NULLs in the Tuples. 

Interpretation (Meaning) of a Relation. 

5.1.3 Relational Model Notation

5.2 Relational Model Constraints and Relational Database Schemas

5.2.1 Domain Constraints

5.2.2 Key Constraints and Constraints on NULL Values

5.2.3 Relational Databases and Relational Database Schemas

5.2.4 Entity Integrity, Referential Integrity, and Foreign Keys

5.2.5 Other Types of Constraints

5.3 Update Operations, Transactions, and Dealing with Constraint Violations

5.3.1 The Insert Operation

5.3.2 The Delete Operation

5.3.3 The Update Operation

5.3.4 The Transaction Concept

5.4 Summary

Review Questions

Exercises

Selected Bibliography

Chapter 6 Basic SQL

6.1 SQL Data Definition and Data Types

6.1.1 Schema and Catalog Concepts in SQL

6.1.2 The CREATE TABLE Command in SQL

6.1.3 Attribute Data Types and Domains in SQL

6.2 Specifying Constraints in SQL

6.2.1 Specifying Attribute Constraints and Attribute Defaults

6.2.2 Specifying Key and Referential Integrity Constraints

6.2.3 Giving Names to Constraints

6.2.4 Specifying Constraints on Tuples Using CHECK

6.3 Basic Retrieval Queries in SQL

6.3.1 The SELECT-FROM-WHERE Structure of Basic SQL Queries

6.3.2 Ambiguous Attribute Names, Aliasing, Renaming, and Tuple Variables

6.3.3 Unspecified WHERE Clause and Use of the Asterisk

6.3.4 Tables as Sets in SQL

6.3.5 Substring Pattern Matching and Arithmetic Operators

6.3.6 Ordering of Query Results

6.3.7 Discussion and Summary of Basic SQL Retrieval Queries

6.4 INSERT, DELETE, and UPDATE Statements in SQL

6.4.1 The INSERT Command

6.4.2 The DELETE Command

6.4.3 The UPDATE Command

6.5 Additional Features of SQL

6.6 Summary

Review Questions

Exercises

Selected Bibliography

Chapter  7 More SQL: Complex Queries, Triggers, Views, and Schema Modification

7.1 More Complex SQL Retrieval Queries

7.1.1 Comparisons Involving NULL and Three-Valued Logic

7.1.2 Nested Queries, Tuples, and Set/Multiset Comparisons

7.1.3 Correlated Nested Queries

7.1.4 The EXISTS and UNIQUE Functions in SQL

7.1.5 Explicit Sets and Renaming in SQL

7.1.6 Joined Tables in SQL and Outer Joins

7.1.7 Aggregate Functions in SQL

7.1.8 Grouping: The GROUP BY and HAVING Clauses

7.1.9 Other SQL Constructs: WITH and CASE

7.1.10 Recursive Queries in SQL

7.1.11 Discussion and Summary of SQL Queries

7.2 Specifying Constraints as Assertions and Actions as Triggers

7.2.1 Specifying General Constraints as Assertions in SQL

7.2.2 Introduction to Triggers in SQL

7.3 Views (Virtual Tables) in SQL

7.3.1 Concept of a View in SQL

7.3.2 Specification of Views in SQL

7.3.3 View Implementation, View Update, and Inline Views

7.3.4 Views as Authorization Mechanisms

7.4 Schema Change Statements in SQL

7.4.1 The DROP Command

7.4.2 The ALTER Command

7.5 Summary

Review Questions

Exercises

Selected Bibliography

Chapter 8 The Relational Algebra and Relational Calculus

8.1 Unary Relational Operations: SELECT and PROJECT

8.1.1 The SELECT Operation

8.1.2 The PROJECT Operation

8.1.3 Sequences of Operations and the RENAME Operation

8.2 Relational Algebra Operations from Set Theory

8.2.1 The UNION, INTERSECTION, and MINUS Operations

8.2.2 The CARTESIAN PRODUCT (CROSS PRODUCT) Operation

8.3 Binary Relational Operations: JOIN and DIVISION

8.3.1 The JOIN Operation

8.3.2 Variations of JOIN: The EQUIJOIN and NATURAL JOIN

8.3.3 A Complete Set of Relational Algebra Operations

8.3.4 The DIVISION Operation

8.3.5 Notation for Query Trees

8.4 Additional Relational Operations

8.4.1 Generalized Projection

8.4.2 Aggregate Functions and Grouping

8.4.3 Recursive Closure Operations

8.4.4 OUTER JOIN Operations

8.4.5 The OUTER UNION Operation

8.5 Examples of Queries in Relational Algebra

8.6 The Tuple Relational Calculus

8.6.1 Tuple Variables and Range Relations

8.6.2 Expressions and Formulas in Tuple Relational Calculus

8.6.3 The Existential and Universal Quantifiers

8.6.4 Sample Queries in Tuple Relational Calculus

8.6.5 Notation for Query Graphs

8.6.6 Transforming the Universal and Existential Quantifiers

8.6.7 Using the Universal Quantifier in Queries

8.6.8 Safe Expressions

8.7 The Domain Relational Calculus

8.8 Summary

Review Questions

Exercises

Laboratory Exercises

Selected Bibliography

Chapter 9 Relational Database Design by ER- and EER-to-Relational Mapping

9.1 Relational Database Design Using ER-to-Relational Mapping

9.1.1 ER-to-Relational Mapping Algorithm

Step 1: Mapping of Regular Entity Types. 

Step 2: Mapping of Weak Entity Types. 

Step 3: Mapping of Binary 1:1 Relationship Types. 

Step 4: Mapping of Binary 1:N Relationship Types. 

Step 5: Mapping of Binary M:N Relationship Types. 

Step 6: Mapping of Multivalued Attributes. 

Step 7: Mapping of N-ary Relationship Types. 

9.1.2 Discussion and Summary of Mapping for ER Model Constructs

9.2 Mapping EER Model Constructs to Relations

9.2.1 Mapping of Specialization or Generalization

Step 8: Options for Mapping Specialization or Generalization. 

9.2.2 Mapping of Shared Subclasses (Multiple Inheritance)

9.2.3 Mapping of Categories (Union Types)

Step 9: Mapping of Union Types (Categories). 

9.3 Summary

Review Questions

Exercises

Laboratory Exercises

Selected Bibliography

Part 4 Database Programming Techniques

Chapter 10 Introduction to SQL Programming Techniques

10.1 Overview of Database Programming Techniques and Issues

10.1.1 Approaches to Database Programming

10.1.2 Impedance Mismatch

10.1.3 Typical Sequence of Interaction in Database Programming

10.2 Embedded SQL, Dynamic SQL, and SQL J

10.2.1 Retrieving Single Tuples with Embedded SQL

Connecting to the Database. 

Communication variables SQLCODE and SQLSTATE. 

Example of Embedded SQL Programming. 

10.2.2 Processing Query Results Using Cursors

General Options for a Cursor Declaration. 

10.2.3 Specifying Queries at Runtime Using Dynamic SQL

10.2.4 SQLJ: Embedding SQL Commands in Java

10.2.5 Processing Query Results in SQLJ Using Iterators

10.3 Database Programming with Function Calls and Class Libraries: SQL/CLI and JDBC

10.3.1 Database Programming with SQL/CLI Using C as the Host Language

Handles to environment, connection, statement, and description records. 

Steps in a database program. 

10.3.2 JDBC: SQL Class Library for Java Programming

JDBC drivers. 

JDBC programming steps. 

10.4 Database Stored Procedures and SQL/PSM

10.4.1 Database Stored Procedures and Functions

10.4.2 SQL/PSM: Extending SQL for Specifying Persistent Stored Modules

10.5 Comparing the Three Approaches

10.6 Summary

Review Questions

Exercises

Selected Bibliography

Chapter 11 Web Database Programming Using PHP

11.1 A Simple PHP Example

11.2 Overview of Basic Features of PHP

11.2.1 PHP Variables, Data Types, and Programming Constructs

11.2.2 PHP Arrays

11.2.3 PHP Functions

11.2.4 PHP Server Variables and Forms

11.3 Overview of PHP Database Programming

11.3.1 Connecting to a Database

Checking for errors. 

Submitting queries and other SQL statements. 

11.3.2 Collecting Data from Forms and Inserting Records

11.3.3 Retrieval Queries from Database Tables

11.4 Brief Overview of Java Technologies for Database Web Programming

11.5 Summary

Review Questions

Exercises

Selected Bibliography

Part 5 Object, Object-Relational, and XML: Concepts, Models, Languages, and Standards

Chapter 12 Object and Object-Relational Databases

12.1 Overview of Object Database Concepts

12.1.1 Introduction to Object-Oriented Concepts and Features

12.1.2 Object Identity, and Objects versus Literals

12.1.3 Complex Type Structures for Objects and Literals

12.1.4 Encapsulation of Operations and Persistence of Objects

Encapsulation of Operations. 

Specifying Object Persistence via Naming and Reachability. 

12.1.5 Type Hierarchies and Inheritance

Simplified Model for Inheritance. 

Constraints on Extents Corresponding to a Type Hierarchy. 

12.1.6 Other Object-Oriented Concepts

Polymorphism of Operations (Operator Overloading). 

Multiple Inheritance and Selective Inheritance. 

12.1.7 Summary of Object Database Concepts

12.2 Object Database Extensions to SQL

12.2.1 User-Defined Types Using CREATE TYPE and Complex Objects

12.2.2 Object Identifiers Using Reference Types

12.2.3 Creating Tables Based on the UDTs

12.2.4 Encapsulation of Operations

12.2.5 Specifying Inheritance and Overloading of Functions

12.2.6 Specifying Relationships via Reference

12.3 The ODMG Object Model and the Object Definition Language ODL

12.3.1 Overview of the Object Model of ODMG

Objects and Literals. 

12.3.2 Inheritance in the Object Model of ODMG

12.3.3 Built-in Interfaces and Classes in the Object Model

12.3.4 Atomic (User-Defined) Objects

12.3.5 Extents, Keys, and Factory Objects

12.3.6 The Object Definition Language ODL

12.4 Object Database Conceptual Design

12.4.1 Differences between Conceptual Design of ODB and RDB

12.4.2 Mapping an EER Schema to an ODB Schema

12.5 The Object Query Language OQL

12.5.1 Simple OQL Queries, Database Entry Points, and Iterator Variables

12.5.2 Query Results and Path Expressions

12.5.3 Other Features of OQL

Specifying Views as Named Queries. 

Extracting Single Elements from Singleton Collections. 

Collection Operators (Aggregate Functions, Quantifiers). 

Ordered (Indexed) Collection Expressions. 

The Grouping Operator. 

12.6 Overview of the C++ Language Binding in the ODMG Standard

12.7 Summary

Review Questions

Exercises

Selected Bibliography

Chapter 13 XML: Extensible Markup Language

13.1 Structured, Semistructured, and Unstructured Data

13.2 XML Hierarchical (Tree) Data Model

13.3 XML Documents, DTD, and XML Schema

13.3.1 Well-Formed and Valid XML Documents and XML DTD

13.3.2 XML Schema

13.4 Storing and Extracting XML Documents from Databases

13.5 XML Languages

13.5.1 XPath: Specifying Path Expressions in XML

13.5.2 XQuery: Specifying Queries in XML

13.5.3 Other Languages and Protocols Related to XML

13.6 Extracting XML Documents from Relational Databases

13.6.1 Creating Hierarchical XML Views over Flat or Graph-Based Data

13.6.2 Breaking Cycles to Convert Graphs into Trees

13.6.3 Other Steps for Extracting XML Documents from Databases

13.7 XML/SQL: SQL Functions for Creating XML Data

13.8 Summary

Review Questions

Exercises

Selected Bibliography

Part 6 Database Design Theory and Normalization

Chapter 14 Basics of Functional Dependencies and Normalization for Relational Databases

14.1 Informal Design Guidelines for Relation Schemas

14.1.1 Imparting Clear Semantics to Attributes in Relations

Guideline 1. 

Examples of Violating Guideline 1. 

14.1.2 Redundant Information in Tuples and Update Anomalies

Insertion Anomalies. 

Deletion Anomalies. 

Modification Anomalies. 

Guideline 2. 

14.1.3 NULL Values in Tuples

Guideline 3. 

14.1.4 Generation of Spurious Tuples

Guideline 4. 

14.1.5 Summary and Discussion of Design Guidelines

14.2 Functional Dependencies

14.2.1 Definition of Functional Dependency

14.3 Normal Forms Based on Primary Keys

14.3.1 Normalization of Relations

14.3.2 Practical Use of Normal Forms

14.3.3 Definitions of Keys and Attributes Participating in Keys

14.3.4 First Normal Form

14.3.5 Second Normal Form

14.3.6 Third Normal Form

14.4 General Definitions of Second and Third Normal Forms

14.4.1 General Definition of Second Normal Form

14.4.2 General Definition of Third Normal Form

14.4.3 Interpreting the General Definition of Third Normal Form

14.5 Boyce-Codd Normal Form

14.5.1 Decomposition of Relations not in BCNF

14.6 Multivalued Dependency and Fourth Normal Form

14.6.1 Formal Definition of Multivalued Dependency

14.7 Join Dependencies and Fifth Normal Form

14.8 Summary

Review Questions

Exercises

Laboratory Exercises

Selected Bibliography

Chapter 15 Relational Database Design Algorithms and Further Dependencies

15.1 Further Topics in Functional Dependencies: Inference Rules, Equivalence, and Minimal Cover

15.1.1 Inference Rules for Functional Dependencies

15.1.2 Equivalence of Sets of Functional Dependencies

15.1.3 Minimal Sets of Functional Dependencies

15.2 Properties of Relational Decompositions

15.2.1 Relation Decomposition and Insufficiency of Normal Forms

15.2.2 Dependency Preservation Property of a Decomposition

15.2.3 Nonadditive (Lossless) Join Property of a Decomposition

15.2.4 Testing Binary Decompositions for the Nonadditive Join Property

15.2.5 Successive Nonadditive Join Decompositions

15.3 Algorithms for Relational Database Schema Design

15.3.1 Dependency-Preserving and Nonadditive (Lossless) Join Decomposition into 3NF Schemas

15.3.2 Nonadditive Join Decomposition into BCNF Schemas

15.4 About Nulls, Dangling Tuples, and Alternative Relational Designs

15.4.1 Problems with NULL Values and Dangling Tuples

15.4.2 Discussion of Normalization Algorithms and Alternative Relational Designs

15.5 Further Discussion of Multivalued Dependencies and 4NF

15.5.1 Inference Rules for Functional and Multivalued Dependencies

15.5.2 Fourth Normal Form Revisited

15.5.3 Nonadditive Join Decomposition into 4NF Relations

15.6 Other Dependencies and Normal Forms

15.6.1 Join Dependencies and the Fifth Normal Form

15.6.2 Inclusion Dependencies

15.6.3 Functional Dependencies Based on Arithmetic Functions and Procedures

15.6.4 Domain-Key Normal Form

15.7 Summary

Review Questions

Exercises

Laboratory Exercises

Selected Bibliography

Part 7 File Structures, Hashing, Indexing, and Physical Database Design

Chapter 16 Disk Storage, Basic File Structures, Hashing, and Modern Storage Architectures

16.1 Introduction

16.1.1 Memory Hierarchies and Storage Devices1

Flash Memory. 

Optical Drives. 

Magnetic Tapes. 

16.1.2 Storage Organization of Databases

16.2 Secondary Storage Devices

16.2.1 Hardware Description of Disk Devices

Interfacing Disk Drives to Computer Systems. 

16.2.2 Making Data Access More Efficient on Disk

16.2.3 SolidState Device (SSD) Storage

16.2.4 Magnetic Tape Storage Devices

16.3 Buffering of Blocks

16.3.1 Buffer Management

Buffer management and Replacement Strategies. 

16.3.2 Buffer Replacement Strategies:

16.4 Placing File Records on Disk

16.4.1 Records and Record Types

16.4.2 Files, Fixed-Length Records, and Variable-Length Records

16.4.3 Record Blocking and Spanned versus Unspanned Records

16.4.4 Allocating File Blocks on Disk

16.4.5 File Headers

16.5 Operations on Files

16.6 Files of Unordered Records (Heap Files)

16.7 Files of Ordered Records (Sorted Files)

16.8 Hashing Techniques

16.8.1 Internal Hashing

16.8.2 External Hashing for Disk Files

16.8.3 Hashing Techniques That Allow Dynamic File Expansion

Extendible Hashing. 

Dynamic Hashing. 

Linear Hashing. 

16.9 Other Primary File Organizations

16.9.1 Files of Mixed Records

16.9.2 B-Trees and Other Data Structures as Primary Organization

16.10 Parallelizing Disk Access Using RAID Technology

16.10.1 Improving Reliability with RAID

16.10.2 Improving Performance with RAID

16.10.3 RAID Organizations and Levels

16.11 Modern Storage Architectures

16.11.1 Storage Area Networks

16.11.2 Network-Attached Storage

16.11.3 iSCSI and Other Network-Based Storage Protocols

16.11.4 Automated Storage Tiering

16.11.5 Object-Based Storage

16.12  Summary

Review Questions

Exercises

Selected Bibliography

Chapter 17 Indexing Structures for Files and Physical Database Design

17.1 Types of Single-Level Ordered Indexes

17.1.1 Primary Indexes

17.1.2 Clustering Indexes

17.1.3 Secondary Indexes

17.1.4 Summary

17.2 Multilevel Indexes

17.3 Dynamic Multilevel Indexes Using B-Trees and B+-Trees

17.3.1 Search Trees and B-Trees

Search Trees. 

B-Trees. 

17.3.2 B+-Trees

Search, Insertion, and Deletion with B+-Trees. 

Variations of B-Trees and B+-Trees. 

17.4 Indexes on Multiple Keys

17.4.1 Ordered Index on Multiple Attributes

17.4.2 Partitioned Hashing

17.4.3 Grid Files

17.5 Other Types of Indexes

17.5.1 Hash Indexes

17.5.2 Bitmap Indexes

Bitmaps for B+-Tree Leaf Nodes. 

17.5.3 Function-Based Indexing

17.6 Some General Issues Concerning Indexing

17.6.1 Logical versus Physical Indexes

17.6.2 Index Creation

Index Creation Process: 

Indexing of Strings: 

17.6.3 Tuning Indexes

17.6.4 Additional Issues Related to Storage of Relations and Indexes

Using an Index for Managing Constraints and Duplicates: 

Inverted Files and Other Access Methods: 

Using Indexing Hints in Queries: 

Column-Based Storage of Relations: 

17.7 Physical Database Design in Relational Databases

17.7.1 Factors That Influence Physical Database Design

A. Analyzing the Database Queries and Transactions. 

B. Analyzing the Expected Frequency of Invocation of Queries and Transactions. 

C. Analyzing the Time Constraints of Queries and Transactions. 

D. Analyzing the Expected Frequencies of Update Operations. 

E. Analyzing the Uniqueness Constraints on Attributes. 

17.7.2 Physical Database Design Decisions

Design Decisions about Indexing. 

17.8  Summary

Review Questions

Exercises

Selected Bibliography

Part 8 Query Processing and Optimization

Chapter 18 Strategies for Query Processing1

18.1 Translating SQL Queries into Relational Algebra and Other Operators

18.1.1 Additional Operators Semi-Join and Anti-Join

18.2 Algorithms for External Sorting

18.3 Algorithms for SELECT Operation

18.3.1 Implemention Options for the SELECT Operation

Search Methods for Simple Selection. 

18.3.2 Search Methods for Conjunctive Selection

18.3.3 Search Methods for Disjunctive Selection

18.3.4 Estimating the Selectivity of a Condition

Information in the Database Catalog. 

18.4 Implementing the JOIN Operation

18.4.1 Methods for Implementing Joins

18.4.2 How Buffer Space and Choice of Outer-Loop File Affect Performance of Nested-Loop Join

18.4.3 How the Join Selection Factor Affects Join Performance

18.4.4 General Case for Partition-Hash Join

18.4.5 Hybrid Hash-Join

18.5 Algorithms for PROJECT and Set Operations

18.5.1 Use of Anti-Join for SET DIFFERENCE (or EXCEPT or MINUS in SQL)

18.6 Implementing Aggregate Operations and Different Types of JOINs

18.6.1 Implementing Aggregate Operations

18.6.2 Implementing Different Types of JOINs

Outer Joins. 

Implementing Semi-Join and Anti-Join. 

Implementing Non-Equi-Join 

18.7 Combining Operations Using Pipelining

18.7.1 Iterators for implementing Physical Operations

18.8 Parallel Algorithms for Query Processing

18.8.1 Operator-Level Parallelism

Sorting. 

Selection. 

Projection and Duplicate Elimination. 

Join. 

Aggregation. 

Set Operations. 

18.8.2 Intraquery Parallelism

18.8.3 Interquery Parallelism

18.9 Summary

Review Questions

Exercises

Selected Bibliography

Chapter 19 Query Optimization

19.1 Query Trees and Heuristics for Query Optimization

19.1.1 Notation for Query Trees and Query Graphs

19.1.2 Heuristic Optimization of Query Trees

Example of Transforming a Query. 

General Transformation Rules for Relational Algebra Operations. 

Outline of a Heuristic Algebraic Optimization Algorithm. 

Summary of Heuristics for Algebraic Optimization. 

19.2 Choice of Query Execution Plans

19.2.1 Alternatives for Query Evaluation

19.2.2 Nested Subquery Optimization

19.2.3 Subquery (View) Merging Transformation

GROUP-BY View-Merging: 

19.2.4 Materialized Views

Incremental View Maintenance. 

Join: 

Selection: 

Projection: 

Intersection: 

Aggregation (Group By): 

19.3 Use of Selectivities in Cost-Based Optimization

19.3.1 Cost Components for Query Execution

19.3.2 Catalog Information Used in Cost Functions

19.3.3 Histograms

19.4 Cost Functions for SELECT Operation

19.4.1 Example of Optimization of Selection Based on Cost Formulas:

19.5 Cost Functions for the JOIN Operation

19.5.1 Join Selectivity and Cardinality for Semi-Join and Anti-Join

Semi-Join 

Anti-Join 

19.5.2 Example of Join Optimization Based on Cost Formulas

19.5.3 Multirelation Queries and JOIN Ordering Choices

19.5.4 Physical Optimization

19.5.5 Dynamic Programming Approach to Join Ordering

19.6 Example to Illustrate Cost-Based Query Optimization

19.7 Additional Issues Related to Query Optimization

19.7.1 Displaying the System’s Query Execution Plan

19.7.2 Size Estimation of Other Operations

Projection: 

Set Operations: 

Aggregation: 

19.7.3 Plan Caching

19.7.4 Top-k Results Optimization

19.8 An Example of Query Optimization in Data Warehouses

19.9 Overview of Query Optimization in Oracle18

19.9.1 Physical Optimizer

19.9.2 Global Query Optimizer

19.9.3 Adaptive Optimization

19.9.4 Array Processing

19.9.5 Hints

19.9.6 Outlines

19.9.7 SQL Plan Management

19.10 Semantic Query Optimization

19.11 Summary

Review Questions

Exercises

Selected Bibliography

Part 9 Transaction Processing, Concurrency Control, and Recovery

Chapter 20 Introduction to Transaction Processing Concepts and Theory

20.1 Introduction to Transaction Processing

20.1.1 Single-User versus Multiuser Systems

20.1.2 Transactions, Database Items, Read and Write Operations, and DBMS Buffers

20.1.3 Why Concurrency Control Is Needed

The Lost Update Problem. 

The Temporary Update (or Dirty Read) Problem. 

The Incorrect Summary Problem. 

The Unrepeatable Read Problem. 

20.1.4 Why Recovery Is Needed

Types of Failures. 

20.2 Transaction and System Concepts

20.2.1 Transaction States and Additional Operations

20.2.2 The System Log

20.2.3 Commit Point of a Transaction

20.2.4 DBMS-Specific Buffer Replacement Policies

Domain Separation (DS) Method. 

Hot Set Method. 

The DBMIN Method. 

20.3 Desirable Properties of Transactions

20.4 Characterizing Schedules Based on Recoverability

20.4.1 Schedules (Histories) of Transactions

Conflicting Operations in a Schedule. 

20.4.2 Characterizing Schedules Based on Recoverability

20.5 Characterizing Schedules Based on Serializability

20.5.1 Serial, Nonserial, and Conflict-Serializable Schedules

Conflict Equivalence of Two Schedules. 

Serializable Schedules. 

20.5.2 Testing for Serializability of a Schedule

20.5.3 How Serializability Is Used for Concurrency Control

20.5.4 View Equivalence and View Serializability

20.5.5 Other Types of Equivalence of Schedules

20.6 Transaction Support in SQL

20.7 Summary

Review Questions

Exercises

Selected Bibliography

Chapter 21 Concurrency Control Techniques

21.1 Two-Phase Locking Techniques for Concurrency Control

21.1.1 Types of Locks and System Lock Tables

Binary Locks. 

Shared/Exclusive (or Read/Write) Locks. 

Conversion (Upgrading, Downgrading) of Locks. 

21.1.2 Guaranteeing Serializability by Two-Phase Locking

Basic, Conservative, Strict, and Rigorous Two-Phase Locking. 

21.1.3 Dealing with Deadlock and Starvation

Deadlock Prevention Protocols. 

Deadlock Detection. 

Timeouts. 

Starvation. 

21.2 Concurrency Control Based on Timestamp Ordering

21.2.1 Timestamps

21.2.2 The Timestamp Ordering Algorithm for Concurrency Control

Basic Timestamp Ordering (TO). 

Strict Timestamp Ordering (TO). 

Thomas’s Write Rule. 

21.3 Multiversion Concurrency Control Techniques

21.3.1 Multiversion Technique Based on Timestamp Ordering

21.3.2 Multiversion Two-Phase Locking Using Certify Locks

21.4 Validation (Optimistic) Techniques and Snapshot Isolation Concurrency Control

21.4.1 Validation-Based (Optimistic) Concurrency Control

21.4.2 Concurrency Control Based on Snapshot Isolation

21.5 Granularity of Data Items and Multiple Granularity Locking

21.5.1 Granularity Level Considerations for Locking

21.5.2 Multiple Granularity Level Locking

21.6 Using Locks for Concurrency Control in Indexes

21.7 Other Concurrency Control Issues

21.7.1 Insertion, Deletion, and Phantom Records

21.7.2 Interactive Transactions

21.7.3 Latches

21.8 Summary

Review Questions

Exercises

Selected Bibliography

Chapter 22 Database Recovery Techniques

22.1 Recovery Concepts

22.1.1 Recovery Outline and Categorization of Recovery Algorithms

22.1.2 Caching (Buffering) of Disk Blocks

22.1.3 Write-Ahead Logging, Steal/No-Steal, and Force/No-Force

22.1.4 Checkpoints in the System Log and Fuzzy Checkpointing

22.1.5 Transaction Rollback and Cascading Rollback

22.1.6 Transaction Actions That Do Not Affect the Database

22.2 NO-UNDO/REDO Recovery Based on Deferred Update

22.3 Recovery Techniques Based on Immediate Update

22.4 Shadow Paging

22.5 The ARIES Recovery Algorithm

22.6 Recovery in Multidatabase Systems

22.7 Database Backup and Recovery from Catastrophic Failures

22.8 Summary

Review Questions

Exercises

Selected Bibliography

Part 10 Distributed Databases, NOSQL Systems, and Big Data

Chapter 23 Distributed Database Concepts

23.1 Distributed Database Concepts

23.1.1 What Constitutes a DDB

23.1.2 Transparency

23.1.3 Availability and Reliability

23.1.4 Scalability and Partition Tolerance

23.1.5 Autonomy

23.1.6 Advantages of Distributed Databases

23.2 Data Fragmentation, Replication, and Allocation Techniques for Distributed Database Design

23.2.1 Data Fragmentation and Sharding

Horizontal Fragmentation (Sharding). 

Vertical Fragmentation. 

Mixed (Hybrid) Fragmentation. 

23.2.2 Data Replication and Allocation

23.2.3 Example of Fragmentation, Allocation, and Replication

23.3 Overview of Concurrency Control and Recovery in Distributed Databases

23.3.1 Distributed Concurrency Control Based on a Distinguished Copy of a Data Item

Primary Site Technique. 

Primary Site with Backup Site. 

Primary Copy Technique. 

Choosing a New Coordinator Site in Case of Failure. 

23.3.2 Distributed Concurrency Control Based on Voting

23.3.3 Distributed Recovery

23.4 Overview of Transaction Management in Distributed Databases

23.4.1 Two-Phase Commit Protocol

23.4.2 Three-Phase Commit Protocol

23.4.3 Operating System Support for Transaction Management

23.5 Query Processing and Optimization in Distributed Databases

23.5.1 Distributed Query Processing

23.5.2 Data Transfer Costs of Distributed Query Processing

23.5.3 Distributed Query Processing Using Semijoin

23.5.4 Query and Update Decomposition

23.6 Types of Distributed Database Systems

23.6.1 Federated Database Management Systems Issues

Semantic Heterogeneity. 

23.7 Distributed Database Architectures

23.7.1 Parallel versus Distributed Architectures

23.7.2 General Architecture of Pure Distributed Databases

23.7.3 Federated Database Schema Architecture

23.7.4 An Overview of Three-Tier Client/Server Architecture

23.8 Distributed Catalog Management

23.9 Summary

Review Questions

Exercises

Selected Bibliography

Chapter 24 NOSQL Databases and Big Data Storage Systems

24.1 Introduction to NOSQL Systems

24.1.1 Emergence of NOSQL Systems

24.1.2 Characteristics of NOSQL Systems

NOSQL characteristics related to distributed databases and distributed systems. 

NOSQL characteristics related to data models and query languages. 

24.1.3 Categories of NOSQL Systems

24.2 The CAP Theorem

24.3 Document-Based NOSQL Systems and MongoDB

24.3.1 MongoDB Data Model

24.3.2 MongoDB CRUD Operations

24.3.3 MongoDB Distributed Systems Characteristics

Replication in MongoDB. 

Sharding in MongoDB. 

24.4 NOSQL Key-Value Stores

24.4.1 DynamoDB Overview

DynamoDB data model. 

DynamoDB Distributed Characteristics. 

24.4.2 Voldemort Key-Value Distributed Data Store

24.4.3 Examples of Other Key-Value Stores

Oracle key-value store. 

Redis key-value cache and store. 

Apache Cassandra. 

24.5 Column-Based or Wide Column NOSQL Systems

24.5.1 Hbase Data Model and Versioning

Hbase data model. 

24.5.2 Hbase CRUD Operations

24.5.3 Hbase Storage and Distributed System Concepts

24.6 NOSQL Graph Databases and Neo4j

24.6.1 Neo4j Data Model

24.6.2 The Cypher Query Language of Neo4j

24.6.3 Neo4j Interfaces and Distributed System Characteristics

24.7 Summary

Review Questions

Selected Bibliography

Appendix A Alternative Diagrammatic Notations for ER Models

Appendix B Parameters of Disks

Appendix C Overview of the QBE Language

C.1 Basic Retrievals in QBE

C.2 Grouping, Aggregation, and Database Modification in QBE

Bibliography

Index