Consider the following two relations: Sailors(sid: integer, sname: string, ratin
ID: 3714248 • Letter: C
Question
Consider the following two relations: Sailors(sid: integer, sname: string, rating: integer, age: real), where attribute sid is the primary key of the relation, and Reserves(sid: integer,_bid integer,_day: _date), where all three attributes collectively are the primary key of the relation There is only one index in the database, namely, a hash index on attribute sid of the Sailors relation. Consider the natural join of Sailors and Reserves: SELECT FROM Sailors S, Reserves R WHERE S.sid-R.sid Explain how you can improve the "naive" nested loops algorithm that we covered in class so that you can take advantage of the hash index on Sailors.sid when computing the above natural join.
Consider the following two relations: Sailors(sid: integer, sname: string, rating: integer, age: real), where attribute sid is the primary key of the relation, and Reserves(sid: integer,_bid integer,_day: _date), where all three attributes collectively are the primary key of the relation There is only one index in the database, namely, a hash index on attribute sid of the Sailors relation. Consider the natural join of Sailors and Reserves: SELECT FROM Sailors S, Reserves R WHERE S.sid-R.sid Explain how you can improve the "naive" nested loops algorithm that we covered in class so that you can take advantage of the hash index on Sailors.sid when computing the above natural join.Explanation / Answer
Answer:
We have a hash index on attribute sid of the relation Sailors.
Given query is SELECT * FROM Sailors S, Reserves R WHERE S.sid = R.sid
Therefore, the nested loops algorithm for the query is given below:
for each tuple s in Sailors do
for each tuple r in Reserves do
if s.sid == r.sid then add <s, r> to result
This algorithm takes one tuple from Sailors and searches every tuples from Reserves to search for the condition s.sid == r.sid which requires the number of searches equal to the number of tuples in the relation Reserves.
Since we have a hash index on attribute sid of the relation Sailors, we can reduce this number of searches by using the following Index Nesed Loop Join algorithm
for each tuple r in Reserves do
for each tuple s in Sailors where s.sid == r.sid do //Use hash index in order to search such tuple in O(1)
add <s r> to result
NB: Hope it helps to get your answer. Let me know any concern to help you better.