Computer Architecture > HESI > University of Michigan EECS 484 F19 - Homework 4 (All)

University of Michigan EECS 484 F19 - Homework 4

Document Content and Description Below

EECS 484 F19 - Homework 4 Deadline -- 6:00 PM on Tuesday, Nov 26th, 2019 Deliverables: You need to submit all your solutions in a single PDF on Gradescope. Your solutions can be either han ... dwritten or created electronically, as long as they are clear. This homework is to be done in teams of 2 students; individual work is permitted, but not recommended. Both members of each team will receive the same score; as such, it is not necessary for each team member to submit the assignment. Create a group of 2 under Homework 4 in Gradescope before you submit. No late days for homework! If you miss the due date, you get 0 points. No exceptions on this. By submitting this homework, you are agreeing to abide by the Honor Code: I have neither given nor received unauthorized aid on this assignment, nor have I concealed any violations of the Honor Code.Question 1 (12 points): Consider doing Grace Hash Join algorithm on a system with number of pages in memory equal to B, answer the following questions: 1. How many partitions do we end up having if we only do one round of hashing in the partition phase?(4 points) 2. How many partitions do we end up having if we do 2 rounds of hashing with 2 different hash function in the partitioning phase? (4 points) 3. Can we use the same hash function in partitioning phase and probing phase? Justify you answer with one or two sentences. (4 points) Question 2 (20 points): In class, we developed a cost model for various relational database operations, such as joins. We counted the total number of I/Os (i.e., writing or reading a page) required to perform each operation. From there, we could estimate the relative performance of two query plans. If we were to consider a nested-loop join vs. a hash join, for example, we might guess that using the hash join would be better because it would require fewer I/Os. In modern magnetic disks, the cost of performing a sequential read is approximately the same as that of performing a sequential write; however, you might imagine another kind of secondary storage device where this is not true. For example, it is widely accepted that when using flash memory devices, it is cheaper to read a block than it is to write a block. Therefore, you might also imagine that replacing our magnetic disk with another device would affect our cost estimates, which could in turn affect the optimizer’s plan (i.e., choice of algorithms). For this question, suppose that you are given two relations R and S, and that you want to perform a natural join between the two. Suppose the following is also true of the two relations: Number of records in R = 60,000 Number of pages in R = 5,000 Number of records in S = 180,000 Number of pages in S = 20,000 [Show More]

Last updated: 2 years ago

Preview 1 out of 4 pages

Buy Now

Instant download

We Accept: