CS 5200 Introduction to Database Managementi Solution to Individual Assignment #6

For the following schedules:

  1. Determine whether the schedule is view-serializable, conflict-serializable, recoverable, cascadeless and/or strict. Note: you must state separately whether each one of these holds.
  2. For each of the 5 answers in the first part above, explain why or why not. In the case of the two notions of serializability, you must either give an equivalent serial schedule or a reason why the schedule is not serializable. For the other three concepts, you must give an example of a violation if the schedule does not have the property.

  1. R2(C), R1(C), R2(B), R2(A), C2, W4(B), R3(C), W3(C), C3, W4(A), R1(C), C1, R4(B), R4(A), C4

    1. The transaction conflicts are:
      1. RW 2→3 R2(C), R1(C), R2(B), R2(A), C2, W4(B), R3(C), W3(C), C3, W4(A), R1(C), C1, R4(B), R4(A), C4
      2. RW 1→3 R2(C), R1(C), R2(B), R2(A), C2, W4(B), R3(C), W3(C), C3, W4(A), R1(C), C1, R4(B), R4(A), C4
      3. RW 2→4 R2(C), R1(C), R2(B), R2(A), C2, W4(B), R3(C), W3(C), C3, W4(A), R1(C), C1, R4(B), R4(A), C4
      4. RW 2→4 R2(C), R1(C), R2(B), R2(A), C2, W4(B), R3(C), W3(C), C3, W4(A), R1(C), C1, R4(B), R4(A), C4
      5. WR 3→1 R2(C), R1(C), R2(B), R2(A), C2, W4(B), R3(C), W3(C), C3, W4(A), R1(C), C1, R4(B), R4(A), C4
    2. Not conflict serializable because the graph has a cycle on transactions 1 and 3.
    3. Not view serializable. The data item C is written only by T3. The first R1(C) reads the initial value of C so T1 must precede T3, but the second R1(C) reads the value of C written by W3(C) so T1 must follow T3.
    4. The schedule is strict.
    5. It is cascadeless because it is strict.
    6. It is recoverable because it is strict.

  2. R3(A), W1(A), W3(C), W4(B), R1(C), R2(C), C3, R2(C), R4(C), W2(B), C1, C2, C4

    1. The transaction conflicts are:
      1. RW 3→1 R3(A), W1(A), W3(C), W4(B), R1(C), R2(C), C3, R2(C), R4(C), W2(B), C1, C2, C4
      2. WR 3→1 R3(A), W1(A), W3(C), W4(B), R1(C), R2(C), C3, R2(C), R4(C), W2(B), C1, C2, C4
      3. WR 3→2 R3(A), W1(A), W3(C), W4(B), R1(C), R2(C), C3, R2(C), R4(C), W2(B), C1, C2, C4
      4. WR 3→2 R3(A), W1(A), W3(C), W4(B), R1(C), R2(C), C3, R2(C), R4(C), W2(B), C1, C2, C4
      5. WR 3→4 R3(A), W1(A), W3(C), W4(B), R1(C), R2(C), C3, R2(C), R4(C), W2(B), C1, C2, C4
      6. WW 4→2 R3(A), W1(A), W3(C), W4(B), R1(C), R2(C), C3, R2(C), R4(C), W2(B), C1, C2, C4
    2. Conflict serializable with serial order(s):
      1. 3, 1, 4, 2
      2. 3, 4, 1, 2
      3. 3, 4, 2, 1
    3. View serializable with serial order(s):
      1. 3, 1, 4, 2
      2. 3, 4, 1, 2
      3. 3, 4, 2, 1
    4. It is not strict because of any of these violations:
      1. R3(A), W1(A), W3(C), W4(B), R1(C), R2(C), C3, R2(C), R4(C), W2(B), C1, C2, C4
      2. R3(A), W1(A), W3(C), W4(B), R1(C), R2(C), C3, R2(C), R4(C), W2(B), C1, C2, C4
      3. R3(A), W1(A), W3(C), W4(B), R1(C), R2(C), C3, R2(C), R4(C), W2(B), C1, C2, C4
    5. It is not cascadeless because of one of the first two violations above.
    6. The schedule is recoverable.

  3. R1(A), W1(B), R3(C), R3(A), R4(C), R4(B), C4, W2(C), W3(C), R3(A), W3(A), C1, C3, W2(C), C2

    1. The transaction conflicts are:
      1. RW 1→3 R1(A), W1(B), R3(C), R3(A), R4(C), R4(B), C4, W2(C), W3(C), R3(A), W3(A), C1, C3, W2(C), C2
      2. WR 1→4 R1(A), W1(B), R3(C), R3(A), R4(C), R4(B), C4, W2(C), W3(C), R3(A), W3(A), C1, C3, W2(C), C2
      3. RW 3→2 R1(A), W1(B), R3(C), R3(A), R4(C), R4(B), C4, W2(C), W3(C), R3(A), W3(A), C1, C3, W2(C), C2
      4. RW 3→2 R1(A), W1(B), R3(C), R3(A), R4(C), R4(B), C4, W2(C), W3(C), R3(A), W3(A), C1, C3, W2(C), C2
      5. RW 4→2 R1(A), W1(B), R3(C), R3(A), R4(C), R4(B), C4, W2(C), W3(C), R3(A), W3(A), C1, C3, W2(C), C2
      6. RW 4→3 R1(A), W1(B), R3(C), R3(A), R4(C), R4(B), C4, W2(C), W3(C), R3(A), W3(A), C1, C3, W2(C), C2
      7. RW 4→2 R1(A), W1(B), R3(C), R3(A), R4(C), R4(B), C4, W2(C), W3(C), R3(A), W3(A), C1, C3, W2(C), C2
      8. WW 2→3 R1(A), W1(B), R3(C), R3(A), R4(C), R4(B), C4, W2(C), W3(C), R3(A), W3(A), C1, C3, W2(C), C2
      9. WW 3→2 R1(A), W1(B), R3(C), R3(A), R4(C), R4(B), C4, W2(C), W3(C), R3(A), W3(A), C1, C3, W2(C), C2
    2. Not conflict serializable because of the cycle on transactions 2 and 3.
    3. View serializable with serial order(s):
      1. 1, 4, 3, 2
    4. Not strict due to:
      1. R1(A), W1(B), R3(C), R3(A), R4(C), R4(B), C4, W2(C), W3(C), R3(A), W3(A), C1, C3, W2(C), C2
      2. R1(A), W1(B), R3(C), R3(A), R4(C), R4(B), C4, W2(C), W3(C), R3(A), W3(A), C1, C3, W2(C), C2
    5. Not cascadeless due to the first violation above.
    6. Not recoverable due to the first violation above.

  4. select p.name
      from Person p
     where exists(
             select *
               from Role r1, Role r2, RoleType t
              where r1.isMemberOf <> r2.isMemberOf
                and r1.hasMember = p.id
                and r2.hasMember = p.id
                and r1.hasRole = t.id
                and r2.hasRole = t.id
                and t.type = 'Chair'
           );
    

    Show the optimal query tree for executing this query. Treat r1.isMemberOf <> r2.isMemberOf as being an ordinary constraint (i.e., not a join constraint) in this problem. For each relational algebra operation specify the strategy that should be used. You may assume that about 5% of all roles are chairs.

    The Person table is semijoined with the subquery and then projected. So the root of the query tree is a projection on p.name, and the node below the root is a semijoin on the join constraint r1.hasMember = p.id and r2.hasMember = p.id. The smallest table is RoleType from which a single row is selected. This should be the first table in the subquery tree. This is followed by joins on the Role table twice. Then a selection is performed on the result. If there is an index available on hasRole, then an index nested loop join can be performed for the first join otherwise a sort merge join is performed. The second join can be done the same way. Since the problem does not specify whether there is an index on hasRole, either answer is acceptable for either of the joins. The fact that 5% of all roles is not relevant.

For scoring see the rubric.