CSE5331 Database Systems II
Spring 2000

Old Final Exam

1. Consider the following extended entity-relationship (EER) diagram:

   

   where the letter U indicates specialization, not a category.

   1. (14 points) Map this EER diagram into a relational schema. Indicate a foreign key by using an arrow from the foreign key to the primary key.

   2. (14 points) Use O2 class declarations to model the previous EER schema. All relationships must be expressed using the O2 relationship syntax (as it was done in the second project).

2. (22 points total) Consider the following schedule:
   
   

   t1

   t2

   t3

   t4

   t5

   t6

   t7

   t8

   t9

   t10

   t11

   t12

   t13

   T1

   R(Z)

   R(Y)

   W(Y)

   R(X)

   W(X)

   T2

   R(Y)

   R(Z)

   W(Y)

   W(Z)

   T3

   R(X)

   W(X)

   R(Y)

   W(Y)

   1. (7 points) Draw the serializability graph for this schedule and state whether the schedule is serializable or not. If it is serializable, write down the equivalent serial order; if it is not, explain why.
   2. (15 points) Trace the actions of the basic timestamp ordering protocol when applied to this schedule as follows: Write the timestamps of every transaction and the equivalent serial order of the schedule. Write a table that contains the values of all RS and WS after each operation. If a transaction is aborted, remove its remaining operations from the schedule and continue with the other transactions (without restarting the aborted transaction). Write down which transactions are committed and which are aborted, if any. Assume that the first operation of a schedule is done at time 1. Assume that RS and WS (read- and write-stamps) of all items are zeros before the schedule starts.

3. (17 points) Consider the following SQL query:

   select e.name, s.name, p.pname, w.hours, d.dname
     from EMPLOYEE e, EMPLOYEE s, WORKS_ON w, PROJECT p, DEPARTMENT d
   where e.dno=5 and w.hours>20 and p.location='Arlington'
     and e.superssn=s.ssn and e.ssn=w.ssn and w.pno=p.pno and p.dno=d.dno
   

   Draw the final query tree of this query that consists of relational algebra expressions after you apply the heuristic optimization transformations learned in class.

4. (18 points total) Suppose that we represent undirected graphs as follows: edge(X,Y) represents a graph edge between the nodes X and Y. Note that edge(X,Y) implies edge(Y,X) and vice versa but only one of these two is given as a fact. For example, the facts at the left represent the graph at the right:

           edge(1,2)                                          
           edge(2,3)                1 - 2 --- 3             
           edge(1,6)                |   |                  
           edge(2,4)                |   4     7---8         
           edge(6,4)                | /   \                  
           edge(4,5)                6-------5          
           edge(6,5)                                          
           edge(7,8)
   

   1. (8 points) Give a set of recursive rules for the derived predicate is_connected(X,Y) that indicates that there is a path that connects node X to node Y (if X is different from Y) For example, we should be able to deduce from the above tree that is_connected(1,4).

   2. (10 points) Write a program in pseudo-code that uses the semi-naive bottom-up evaluation method to evaluate your rules for is_connected(X,Y). This program should only use relational operators, assignments, and a while-loop.

5. (15 points total) Consider the following ER diagram:

   ...

   1. (7 points) Construct the network data structure diagram (show all attributes in records and give names to all links).
   2. (8 points) Express the following query in DBTG statements:

      Print the course name and the section number of every course offered by the CSE department.