Problem 6. Assume that we have four relations R(A, B), S(A,C), T(A, D) and U(A, E) and the size (i.e., the number of rows) of each relation is as follows: TR = 1000, rs = 3000, TT= 4000, Tu = 2000. Also, assume that all attributes of the relations are of the same length and we use hash join, so the cost of joining X = {R, S, T,U} and Y = {R, S, T, U} is approximately: k(rx cx+ry cy) where k is a constant, rx and cx denote the number of rows and the number of columns of X, respectively, and ry and cy denote the number of rows and the number of columns of Y. Finally, assume that the size of a join is always 0.2% of the size of the cross product (i.e., ™xây = 0.002 TX.TY). Under the above assumptions, find the lowest cost plan for computing R S T U using dynamic programming and left-deep join trees. You need to complete the following table while finding the best plans (e.g., in the form of ((□□) □) in the last line) and associated costs. Subquery RAS RAT RAU SAT SAU TAU RASAT RASAU RATAU SATAU RAS TAU Size 6000 8000k Cost [= (1000-2+3000-2)k] Best Plan RS

Problem 6. Assume that we have four relations R(A, B), S(A,C), T(A, D) and U(A, E) and the size (i.e., the number of rows) of each relation is as follows: TR = 1000, rs = 3000, TT= 4000, Tu = 2000. Also, assume that all attributes of the relations are of the same length and we use hash join, so the cost of joining X = {R, S, T,U} and Y = {R, S, T, U} is approximately: k(rx cx+ry cy) where k is a constant, rx and cx denote the number of rows and the number of columns of X, respectively, and ry and cy denote the number of rows and the number of columns of Y. Finally, assume that the size of a join is always 0.2% of the size of the cross product (i.e., ™xây = 0.002 TX.TY). Under the above assumptions, find the lowest cost plan for computing R S T U using dynamic programming and left-deep join trees. You need to complete the following table while finding the best plans (e.g., in the form of ((□□) □) in the last line) and associated costs. Subquery RAS RAT RAU SAT SAU TAU RASAT RASAU RATAU SATAU RAS TAU Size 6000 8000k Cost [= (1000-2+3000-2)k] Best Plan RS

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Q: Select the statement that is correct about tree indexing and hash indexing: O B+ tree indexing works…

A: Both B+ tree indexing and hash indexing are commonly used techniques in databases to facilitate…

Q: II name(o dept_name ="Physics" (instructon)

A: In relational algebra expression, the SELECT operation (σ) is used to select a subset of the tuples…

Q: When is it better to use a dense index than a sparse index? Your answer has to be explained.

A: According to the information given:- WE have to define dense index is better than a sparse index…

Q: 1) Does proper indexing make it possible for some join queries to not need to retrieve a table entry…

A: “Since you have asked multiple question, we will solve the first question for you. If youwant any…

Q: Use the table below to convert a character key to an integer for the following questions. Letter A…

A: The Answer is

Q: I am having troubles understanding part 4: hash table with second hash· function h2 = 7 - (x mod 7).…

A: This is very simple. Note: Indexing starts with 0 (always remember) Initially, the hash table is…

Q: Search online for an MD-5 hash generator. What is the hash for your name? Try it without using…

A: In this question we have to look for MD5 HASH GENERATOR, where we need to find the hash for the name…

Q: Find any two practical applications of hashing, thoroughly investigate them, and then provide your…

A: EXPLANATION: Digestive message. Verification of the password. Structures for Data (Programming…

Q: What is the result of the query below? SELECT * FROM table1 WHERE val1 IN (SELECT vall FROM table1…

A: A SQL query is a high level English sentence used to work with a database which could be the…

Q: What is the average time complexity to delete a key from a chaining hash table? (Assume that the…

A: Explanation: 1. It is very infrequent that a number items be hashed to same key. 2. As O(n) is…

Q: expected average chain length

A: No. Of keys that are inserted into hash table = N Size of hash table = H

Q: 12) Chain Length Homework If N items are inserted into a hash table of size H, what is the expected…

A: Given Data : N items inserted in a hashtable of length H To find : Expected average chain…

Q: Give a query that would benefit from each of the three methods of partitioning: round-robin (the…

A: Consider, for each of the three partitioning approaches, round-robin, hash partitioning, and range…

Q: The table R(x,y) currently has the following tuples (note there are duplicates): (1,2), (1,2),…

A: SOLUTION -Provided the Creation, Insertion, and Selection queries performed on given tables and gave…

Q: Learn to tell the difference between scalar, aggregate, and table-returning functions.

A: Description: It will help if you familiarise yourself with the distinctions between functions that…

Q: As a function of n, the number of bits and m the number of members in the set S, what number of hash…

Q: Find any two practical applications of hashing, thoroughly investigate them, and then provide your…

A: Introduction: Digest Message.Verifying passwords. DBMS (Programming Languages) Compiling.…

Question

Solve all parts of the table!

Problem 6.
Assume that we have four relations R(A,B), S(A,C), T(A, D) and
U(A, E) and the size (i.e., the number of rows) of each relation is as follows:
TR = 1000, rs = 3000, TT= 4000, Tu = 2000.
Also, assume that all attributes of the relations are of the same length and we use hash join, so the
cost of joining X = {R, S, T, U} and Y = {R, S, T, U} is approximately:
k(rx cx+ry Cy)
where k is a constant, rx and cx denote the number of rows and the number of columns of
X, respectively, and ry and cy denote the number of rows and the number of columns of Y.
Finally, assume that the size of a join is always 0.2% of the size of the cross product (i.e., rxxy =
0.002.rx.ry).
Under the above assumptions, find the lowest cost plan for computing R S T U using
dynamic programming and left-deep join trees. You need to complete the following table while
finding the best plans (e.g., in the form of ((□□) ►) □ in the last line) and associated costs.
Subquery
RAS
RAT
RAU
SAT
SAU
TAU
RAS T
RASMU
RATAU
SATAU
RAS TAU
Size
6000 8000k
Cost
(1000-2+3000-2)k]
Best Plan
RAS

Expert Solution

This question has been solved!

Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.

This is a popular solution!

SEE SOLUTION Check out a sample Q&A here

Step 1: Greetings

VIEW

Step 2: Dynamic programming

VIEW

Step 3: Implementation for lowest cost plan

VIEW

Solution

VIEW

Trending now

This is a popular solution!

Step by step

Solved in 4 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions

it says relation guest doesnt exist am i making a guess table
Find any two practical applications of hashing, thoroughly investigate them, and then provide your own in-depth description. a. Include references from your own research as well?
Why do Rainbow Tables use a different reduction function for each step in the hash chain?
A split at the $3200 income point creates a top and bottom partition. Compute the overall(weighted) Gini index given an income split of 32000. income is 0, 10,000, 20,000, 30,000, 40,000, 50,000, 60,000, 70,000, 80,000, and age is 0,10,20,30,40,50 (Please give correct answer with explanction)
Please solve the attached recurrence relation.
The table R(x,y) currently has the following tuples (note there are duplicates): (1,2), (1,2), (2,3), (3,4), (3,4), (4,1), (4,1), (4,1), (4,2). Compute the result of the query: SELECT R1.x, R2.y, COUNT(*) FROM R R1, R R2 WHERE R1.y = R2.x GROUP BY R1.x, R2.y; Which of the following tuples is in the result? O a. (3, 4, 6) O b. (3, 2, 6) O c. (3, 2, 2) O d. (4, 3, 2)
10. Has there been an addition to the MD series? If so, what is the name of the hashing algorithm?|
Explain why it is sometimes more efficient to compute the distance from a single source to all other nodes, even though a particular query may be answered with a partial solution.
Which of the following operations are done in a hash table?a) Insert onlyb) Search onlyc) Insert and searchd) Replace
State the difference(s) between the Short Table Look up and the Long Table Look up. How do you know which type of table look up you will need?
3
Find any two practical applications of hashing, thoroughly investigate them, and then provide your own in-depth description. a. Include references from your own research as well?