CS 448/648 Assignment #4

1. Consider the pair of relations R(A,B,C) and S(X,Y,Z) and the query

From R, S

Where A = Y and Z < 10

a)Assume that R has 10,000 tuples and S has 50,000 tuples, that I/O blocks (and buffers) are 1000 bytes long, and that tuples may not cross block boundaries (i.e., each tuple is fully contained within one block).Assume also that the values for A, C, and Y require 10 bytes each, that values for B require 50 bytes, values for X require 20 bytes, and values for Z require 4 bytes.Furthermore, assume that Y is a non-nullable foreign key referencing R, and that values for Z are uniformly distributed in the range 1 to 25.How many blocks are needed to store R and S, and how many blocks are expected to be written for the output relation? Be sure to show how you calculated your answers.

b)Using a straightforward translation and the nested loops join algorithm with R as the inner relation, we obtain the following execution plan P:

foreach tuple s in S do

   foreach tuple r in R do

      if r.A = s.Y and s.Z < 10

         then output <r.A, r.B, s.Z>

Using the statistics from part a) and assuming 3 ms. to read or write a block, estimate the length of time required by execution plan P with no optimization.

c)Show the plan that would result from .pushing down the selection ahead of the join. and assuming the same join algorithm.

d)Without making any assumptions about the ordering of tuples in R, and without assuming the presence of indexes (even for primary keys), explain how knowing that A is the primary key for R could be used to further modify the plan to reduce the cost.

e)Describe a plan that could be used if there were a memory-resident index for A (i.e., no I/O is needed to read the index), and estimate the cost of your plan using the statistics from part a).

2. Assume that transactions executing an SQL program involving relations flight and fc may follow either of two possible execution sequences, modelled as: