CPSC 310/603: Review for Final Exam
Fall 2005

The final exam will be comprehensive, although there will be somewhat diproportionate emphasis on the material since Exam 2.

In addition to the material to review listed on the review sheets for Exams 1 and 2, review this material:

• Lectures from Nov 14 through Dec 2.

• Readings from textbook:
  • Chapter 8, section 6
  • Chapter 17
  • Chapter 18, through section 5 except: skip 18.2.3, 18.3.4
  • Chapter 19, sections 1 and 3
  The chapter summaries indicate the most important concepts.

• Homeworks 11 and 12 and their solutions

The format of the exam will be some short answers and some "work-out" problems similar to the homeworks. Here are some suggestions for things to know relating to the material since Exam 2:

• Chapter 17 (Coping with System Failures)
  • Failure model assumed and why it is reasonable
  • Need for atomicity
  • Undo logging - what to do during normal operation, what to do after failure
  • Redo logging - what to do during normal operation, what to do after failure
  • Undo/redo logging - what to do during normal operation, what to do after failure; its benefits over undo logging and redo logging
  • quiescent checkpointing
  • non-quiescent checkpointing for undo/redo logging
  • how to handle disk (i.e., "media") failures

• Chapter 18 (Concurrency Control)
  • Definitions of serial schedule, serializable schedule, conflict-serializable schedule
  • How to construct the precedence graph for a schedule and how to use it to determine whether the schedule is conflict-serializable
  • The two-phase locking (2PL) algorithm for the case of exclusive locks and what it accomplishes
  • How to generalize 2PL for exclusive locks to the case of other kinds of locks (especially shared locks and increment locks) using the compatibility matrix
  • pros and cons of locking large objects vs. small objects
  • general idea of optimistic concurrency control

• Chapter 19 (More About Transaction Management)
  • Definitions of schedules that are recoverable, avoid cascading rollback, and strict
  • definition of strict 2PL and what it accomplishes
  • Venn diagram relating serial, strict, ACR, recoverable and serializable schedules
  • how to use waits-for graph to detect deadlock
  • how to use resource ordering and timeouts to prevent deadlock
  • wound-wait and wait-die algorithms
  • comparison of these methods
  • distinction between physical DB state and logical DB state and fact that recovery rolls back to same logical, but not necessarily same physical, DB state