# D64 Study Questions

I've listed some questions that you might find useful for studying for the final. These are mostly taken from old homework which means that they were based on a different book. Bear this in mind if you run across something that looks unfamiliar.

1. All of the parts of this question are about the following SQL query:

```SELECT *
FROM Student,Enrollment,Course
WHERE class = 1
AND Student.id = Enrollment.id
AND Enrollment.courseNum = Course.number```
The schema of the three relations is:
• Student(id,name,class)
• Course(number,name)
• Enrollment(id,courseNum,grade,quarter) - Note that the combination of id and courseNum do not constitute a key since a student can take a course multiple times.

Here are some parameters you may need in this problem:

• Pages are 4kb.
• Records of Student are 400 bytes long - id is 4 bytes.
• Records of Course are 200 bytes long.
• Records of Enrollment are 100 bytes long - grade is 1 byte.
• T(Student) = 10000, T(Course) = 500, T(Enrollment) = 25000
• V(Student,class) = 4, V(Enrollment,grade) = 10
• You have 500 buffer pages.
• Block ptrs and dbptrs are 5 bytes.
• All B+Trees have 80% occupancy.
• There is a primary B+Tree index on class.
• There is a secondary B+Tree index on grade.

1. (50 pts.) Follow the dynamic programming algorithm from the book to compute the optimal logical query plan. Show all of your work and do not cut corners even though you're tempted to since the query is so simple.
2. (50 pts.) For the optimal join order, pick the optimal physical query plan. In this part, you should try to minimize the number of I/Os required by the plan. You should consider three join algorithms: sort-merge joins, index joins, and nested loop joins. Show all of your work.

2. Consider the following execution:
1. T1 inserts into P1 (page 1)
4. T1 commit
6. T2 deletes from P1
7. T3 deletes from P3
8. T1 end
9. T2 abort
11. T2 end

Answer the following questions.  For all of them, assume that separate buffer pages are available to store the log tail.  Further, assume that the buffer manager uses LRU replacement. This question is based on the recovery scheme passed out in the extra chapter.
1. For each point in the execution listed below, show the log, transaction table, dirty page table, LSN on each page in both memory and on the disk, and the minimum log record that must have been flushed to disk.
1. After step 5 assuming that there are 3 buffer pages available.
2. After step 8 assuming that there are 3 buffer pages available.
3. After step 11 assuming that there are 3 buffer pages available.
4. After step 8 assuming that there are 2 buffer pages available.
2. Assume that there are 3 buffer pages available and that the DBMS crashed after step 8.  Show all of the information requested in the last part after the analysis phase, the redo phase, and the undo phase.
3. Assume that there are 3 buffer pages available and that the DBMS crashed after step 8.  It also crashes during the undo phase of recovery after writing two new log records.  Repeat the previous question for the DBMS when it tries to recover for the second time.

NOTE: This problem was from a different book so ignore the details we didn't cover.

3. Consider the following classes of schedules: serializable, conflict serializable, recoverable, avoids-cascading abort, and strict.  For each of the following schedules, state which of the above classes it belongs to.  If you cannot decide whether a schedule belongs to a certain class based on the listed actions, explain briefly.

The actions are listed in the order that they are scheduled.  if a commit or abort is not shown, the schedule is incomplete.

1. T1:R(X), T2:W(X), T1:W(X), T2: Abort, T1:Commit
2. T1:W(X), T2:R(X), T1:W(X), T2: Commit

4. Consider the following two transactions:

```T1: read(A);
if (A == 0) then B=B+1;
write(B);```
```T2: read(B);