The exam will probably consist of seven questions. I am aiming to make it about one and a half times the size of either term test. Given the exam duration is three hours, there ought not be time pressure. The type of questions and layout of the exam will be similar to the term tests.

exercise

• E.g., What is the I/O cost of this query plan?
  How many tuples is this query likely to return? (Use assumptions of System R to estimate.)

short answer

• E.g., Which is the most apropriate join algorithm for this query?

analysis

• E.g., How would we need to modify the 2-pass sort-merge join to accommodate...

The exam is cumulative. It covers all the topics we covered in the course. The coverage will be fairly uniform over these topics.

The topics we have really added since the second test have been a fuller coverage of the overall query optimizer, and an overview of transactions and transaction management.

1. the physical database
   • the name of the game & database system architecture. (introductory materials [pdf], architecture slide [pdf])
   • memory management [Ch.13]
     1. memory & storage
        1. the memory hierarchy [Ch.13 §1]
        2. storage
           • secondary memory / disks [Ch.13 §2]
           • the I/O model & how to speed up access [Ch.13 §3]
           • coping with disk failures [Ch.13 §4]
     2. paging: disk organization & records (pdf)
        1. pagification: arranging data on disk [Ch.13 §5]
        2. the buffer pool: representing block & record addresses [Ch.13 §6]
        3. variable-length data & records [Ch.13 §7]
     3. issues with modifying records [Ch.13 §8]
   • index structures [Ch.14 §1–3,7,8]
     1. index structure basics [Ch.14 §1]
     2. B-trees [Ch.14 §2]
     3. hash-table indexes [Ch.14 §3]
2. the query processor
   1. indexes (needed for access paths) [Ch.15]
      • prefix matching
      • cost model for using
      • clustered vs unclustered
      • ...
   2. external sorting [Ch.15 §7]
      • basics Many other relational algorithms are based on this, and have the same performance issues.
      • advanced issues (e.g., double buffering, block reads and writes, etc.)
   3. query evaluation, overview (Ch.12) [Ch.15 §1, Ch.16 §1,2]
      1. access paths
      2. cost model & System R
         1. reduction factors
         2. cost estimation
      3. query trees & alternative plans
         1. pipelining
         2. optimization "rules" like pushing selects
         3. ...
   4. evaluating the relational operators [Ch.15]
      1. select & access paths
      2. project with distinct
      3. join
         1. nested loops join
            • block nested loops join
            • index nested loops join
         2. sort-merge join
            • naïve: sort first, then merge
            • 2-pass: accomplishes join in two passes
         3. hash join (two pass)
      4. the set operations
      5. aggregation
   5. relational optimizer [Ch.16]
      1. System R
      2. left-join trees
      3. pipelining
      4. general about the join-enumeration algorithm
3. database management (just the basics)
   • transaction management &concurrency control [Ch.18 §1–5]
     1. serial & serializable schedules [Ch.18 §1]
     2. conflict serializability [Ch.18 §2]
     3. locking approaches
        1. enforcing serializabilty by locks [Ch.18 §3]
        2. locking systems withseveral lock modes [Ch.18 §4]
        3. an architecture for a locking scheduler [Ch.18 §5]

   (We did not cover coping with system failure [Ch.17], or beyond relational “stand-alone” servers, as on the original schedule.)

Only topics covered both in the reading and in class are fair game.

There will be a question like Question #1 from Test #2 on the final. And there will be a question on external sorting.

The test will be closed-note, closed-book. You may bring a calculator, but the exam will be designed so that any math shouldn't need one.

There will be space on the exam packet for writing answers. I will bring extra paper, in case anyone needs it, to attach.

The exam is scheduled for three hours.

The usual rules and regulations of York University regarding final exams are in effect. Please bring identification (a picture ID) with you to the exam.