CS 5200 Introduction to Database Management 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
  2. R3(A), W1(A), W3(C), W4(B), R1(C), R2(C), C3, R2(C), R4(C), W2(B), C1, C2, C4
  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

The rest of the assignment uses the schema from Assignment #4. The primary key of Role uses a tree index on (hasRole, hasMember, isMemberOf), in this order.

Consider the following query:

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.