CSE 444

University of Washington

Winter 2000

Homework 5

See the web page for some homework guidelines and policies.

DUE: at beginning of class, Friday March 3

  1. (12 points) Exercise 14.8, Parts 1, 2, and 3. Remember that a "join order" is the order in which relations appear in the leaves of the plan tree; thus "A join B" is a different join order from "B join A".

  2. (32 points) For this question you will use the same database and relation instances you used for HW 3. Follow this link if you need to re-create this database. Do not add any rows or indices to this database -- create it precisely as we have given it to you. Answer the questions below for each of the following two join algorithms:

    1. Index Nested Loops Join
    2. Sort Merge Join

    Here are the questions:

    1. Write an SQL query whose execution plan contains the algorithm. The query must consist of exactly one query block ("select...from...where... group by...order by...", where the "where", "group by", and "order by" clauses are optional). The query need not return any rows.
    2. Draw the SQL Server plan tree using the notation of Chapter 13; see Figures 13.3, 13.6, and 13.7 for examples.
    3. Why did the optimizer choose the plan it did instead of plans using other join algorithms? (Please be specific; "because it's faster" isn't a good answer here.)
    4. How good are the row count estimates produced by the optimizer at each node of the query tree? For each node, compare the actual count with the optimizer's estimate and list both these numbers in your answer.

  3. (12 points) Exercise 18.2. In your answer for Part (1), include a schedule that demonstrates "interference" -- i.e., one of the three common anomalies described in the chapter.

  4. (16 points) Exercise 19.4, Parts 2 and 3. Here's what we mean by "describe how the CC method handles the sequence": Describe all actions (reads, writes, locks, unlocks, commits, aborts, waits) taken by the DBMS in the order they are taken, as governed by the CC protocol. If a deadlock is detected, abort the deadlocked XACT with the highest number (e.g., T5 would be aborted before T3).

  5. (15 points) Exercise 19.2, Parts 1, 2, 4, 5, and 7. Instead of the classes of schedules listed in the exercise, consider only the following classes of schedules: conflict-serializable, recoverable, avoids-cascading-aborts, and strict. Assume that no other XACTs are active in the DBMS during the schedule.

  6. (13 points)
    1. Exercise 20.4. Assume a checkpoint was taken just prior to LSN 00, and that the dirty page table and XACT table were empty at the time of the checkpoint.
    2. For the log you came up with in the last part of the previous question, answer the questions of Exercise 20.3, Parts 2a-2c. Assume that the system crashed immediately after the last log record you recorded was written to disk.