Assignment 4

Return to Homework Assignments

Homework Assignment #2

Due: December 6, 1999

Design an algorithm and an appropriate storage structure in order to implement the relational algebra division operation (or calculus universal quantification). Your algorithm should be hash-based (you will receive partial credit for an algorithm based on sorting). Illustrate the algorithm with the following example. Consider two relations Transcript (Student-id, course-no, grade) and Course(Course-no, title). The division is to be performed between the projection of Transcript on student-id and course number and the projection of Course on course-no. The projection of the Transcript relation is called the dividend, while the projection of the Course relation is called the divisor. The result relation is called the quotient.

Give first a sequential algorithm and then show how your algorithm should be modified for a parallel shared nothing architecture.
- 2a. Parallel and distributed join algorithms are designed such that at a final site (client) the results from different processors are concatenated together wihout performing any additional relational operations. Assuming that this model is used discuss whether the fragement and replicate algorithm and the asymmetric hash join can be used to perform a semi-join operation.
- 2b. Consider the chain query :
  R1(a,A1) (join A1) R2 (A1,A2) (join A2) R3(A2,A3)...Rn-1(An-1, An) (join An-1) Rn(An-1, b).
  
  i.e., where non-adjacent relations have no common joining attributes. Let us consider the following semi-join strategies:
  S1: (Ri semijoin (Ri-1 semijoin (Ri semijoin Ri+1)))
  S2: ((Ri semijoin (Ri-1 semijoin Ri)) semijoin Ri+1).
  
  Show that one semi-join strategy is inferior to the other, in other words it hasl.sj.nec a higher communication cost. The cost of a semijoin can be estimated as :
  Cost (Ei (semijoin A) Ej ) = |Projection on A(Ej)| + co.
  
  where Ei and Ej are base relations or derived relations and |Projection on A(Ej)| is the cardinality of the join column of Ej.
Consider a distributed database system where relations can be replicated at multiple sites. Thus relation R1 is replicated at sites S2, S3 and S4; relation R2 is replicated at S1 and S4, R3 is stored only at S3 and R4 is replicated at S2 and S4. Consider a join query referencing some (or all) of the relations R1, R2,... Rn in the system. Write an algorithm which determines the mimimum number of sites covering the relations referenced by the query and produces a listing of these sites. There is no need to worry about the efficiency of your algorithm (it could take exponential time). Illustrate your algorithm with the above allocation and a query requering the join of all four relations.
Hint: the fact that R1 is replicated at sites S2, S3 and S4 can be represented as the boolean expression S11 OR S13 OR S14.
Note: algorithms should be written in higher-level pseudo-code as we have done in class.

Tue Nov 23, 1999