CSE 444 Final

December 8, 2000

2:30pm – 4:20pm

Name___________________________________

Total number of points: 100

Total time: 1h 50’

 

1.      [30 points] Consider the E/R diagram below:


















a.      [5 points] Considering the Buys relationship, we know that each purchase is for the benefit of a single employee, and is approved by a single manager. Add arrows to the diagram to indicate this situation. Also, indicate whether the arrows capture faithfully this information.


b.      [5 points] Continue to assume the constraint at point a. Create a relational schema to represent this data by giving the SQL statements for creating the tables. The statements should include all primary and foreign keys. The following information is known about the attribute domains: id consists of 10 characters, phone has 10 characters, name has up to 30 characters, level is an integer, amount is an integer, and purchaseNo has 20 characters.





















c.      [10 points] Write SQL queries to compute the following:

                                                               i.      Employee Smith is a high spender. For each manager, compute the total amount of all purchases approved by that manager for the benefit of Smith. Your query should print the manager id, name and the total amount of purchases approved









                                                             ii.      Find all purchases in which the approving manager and the beneficiary employee are the same person. List the purchase number, the purchase amount, and the name of the employee (manager).














d.      [10 points] John, a new database administrator had a bad day: he accidentally deleted all tuples in the Manager table. Help John recover the lost data. Specifically, write a sequence of SQL statements that will populate the Manager table by using other information in the database. The following information about the company helps you recover the data:

                                                               i.      Each manager manages at least one employee

                                                             ii.      The level of a manager is defined as follows. Managers that manage only regular employees (i.e. that are not managers) have level=1. Managers that manage only regular employees and managers of level 1 have level=2, etc. John knows that the highest manager in the company is the CEO and his level is 4.

















2.      [20 points]

a.      [10 points] Let X,Y be sets of attributes of a relational schema. Prove or disprove the following statements. In each case you have to either indicate “yes”, or to indicate “no” and provide a set of functional dependencies and sets of attributes X and Y that violates the statement.

                                                               i.      X Y  implies  X+ Y+.






                                                             ii.      X+ Ý Y+  =  (X Ý Y) +








                                                            iii.      X+ Ü Y+  =  (X Ü Y) +






b.      [10 points] Find all minimal keys in the relation below and find all non-trivial functional dependencies satisfied by this relation.

A

B

C

D

1

1

1

1

1

1

1

2

2

1

1

1

1

2

1

3

2

2

2

4






























3.      [30 points] Consider the following schema:
Product(id(4), name(16), manufacturer(20), category(10), color(10), webpage(40))
Sales(pid(4), quantity(4), shippingaddress(20), date(12), shippingmethod(10))
Each attribute has a fixed length, with the size (in bytes) indicated by the number in parentheses. The number of tuples in each relation is:
T(Product) = 1,000,000
T(Sales) = 2,000,000
The size of one disk block is 1000 bytes, and there are 101 buffers available in main memory.

a.      [5 points] Compute the number of blocks taken by each table:

B(Product) =


B(Sales) =


b.      [5 points] Consider the logical plan below:













Assume the following physical plan: the join is implemented as a block-nested loop join, its result is pipelined into the selection operator, and, from there, pipelined into the projection operators. Compute the total cost of this physical plan.






c.      [10 points] Derive a new logical plan by pushing selections and projections down as far as possible (you have to draw a plan).


















d.      [10 points] Consider a physical plan for your new logical plan in which all selections and projects are pipelined and the join is a block-nested loop join. Further assume that 1% of all Products are in category “Gizmo” and that 20% of all Sales have a quantity over 100. Compute the cost of your plan.

























 

4.      [20 points] A database has five elements, X, Y, Z, U, V. The two questions below ask us to recover the database after a system crash

a.     

<start T1>

<T1,X,3>

<start T2>

<T2,Y,1>

<start ckpt(T1,T2)>

<T1,X,4>

<start T3>

<commit T1>

<T2,Y,2>

<T3,Z,5>

<commit T2>

<end ckpt>

<start T4>

<T4,U,8>

<start ckpt(T3,T4)>

<start T5>

<T4,U,9>

<T5,X,10>

<commit T5>

<start T6>

<T6,Y,12>

 
[10 points] Assuming we maintain an undo log whose content, after the crash, is:
















Recover the database, assuming that after the crash the five elements have the values below. Indicate which portion of the log you needed to inspect, and which transactions have to be executed again.
X=1
Y=2
Z=3
U=4
V=5

b.     

<start T1>

<T1,X,3>

<start T2>

<T2,Y,1>

<start T3>

<T3,Z,5>

<T2,Y,2>

<commit T2>

<start ckpt(T1,T3)>

<T1,X,4>

<start T4>

<end ckpt>

<commit T1>

<T3,Y,2>

<T4,U,8>

<start ckpt(T3,T4)>

<start T5>

<T4,U,9>

<T5,X,10>

<commit T4>

<start T6>

<T6,Y,12>

 
[10 points] Assuming we maintain a redo log whose content, after the crash, is:


















Recover the database, assuming that after the crash the five elements have the values below. Indicate which portion of the log you needed to inspect, and which transactions have to be executed again.
X=1
Y=2
Z=3
U=4
V=5