CPSC 310/603: Review for Final Exam
Fall 2007

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 13 through Dec 4.

• Readings from textbook:
  • Chapter 16, sections 4 through 7
  • Chapter 8, section 6
  • Chapter 17, sections 1 and 2
  • Chapter 18, sections 1, 2 and 3
  • Chapter 19, section 1 (through 1.5) and section 3
  The chapter summaries indicate the most important concepts.

• Homework 7 and its solution

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 16 (The Rest of the Query Compiler)
  • how to use estimated size of intermediate relations to evaluate competing logical query plans
  • desired properties for estimating rules
  • algorithms/heuristics for estimating size of result of projection, product, selection, natural join, union, intersection, difference, duplicate elimination, grouping
  • how to estimate values of B, T and V
  • what is needed to convert logical query plan to physical query plan
  • know that there are various approaches for searching the space of all physical query plans (don't need to know any details)
  • know that it is important to choose a good order for doing a series of joins (or other associative and commutative operations); know that there are various approaches for deciding on a good order (don't need to know any details)
  • materialized vs. pipelined intermediate relations
  • how to choose a selection method, depending on existence of different kinds of indexes

• 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

• 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

• 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