Calculate the cardinality and minimum cost for each of the following Join operations:

Question

? a hash index with no overflow on the primary key attributes, roomNo/hotelNo in Room;
? a clustering index on the foreign key attribute hotelNo in Room;
? a B + -tree index on the price attribute in Room;
? a secondary index on the attribute type in Room.
nTuples(Room) = 10000 bFactor(Room) = 200
nTuples(Hotel) = 50 bFactor(Hotel) = 40
nTuples(Booking) = 100000 bFactor(Booking) = 60
nDistinct hotelNo (Room) = 50
nDistinct type (Room) = 10
nDistinct price (Room) = 500
min price (Room) = 200 max price (Room) = 50
nLevels hotelNo (I) = 2
nLevels type (I) = 2
nLevels price (I) = 2 nLfBlocks price (I) = 50

J1: Hotel hotelNo Room
Assume nBuffer = 100
J2: Hotel hotelNo Booking
J3: Room roomNo Booking
J4: Room hotelNo Hotel
J6: Booking roomNo Room

Answer 1

J1: Hotel hotelNo Room
Assume nBuffer = 100
Block Nested Loop 102, buffer has only 1 block for Hotel and Room.

52, all of Hotel fits into buffer
Indexed Nested Loop 152, using primary key index
Sort-Merge 302 unsorted
52 sorted

Hash 156 if hash index fits in memory
J2: Hotel hotelNo Booking
Block Nested Loop 33336, buffer has only 1 block for Hotel and

Booking.
16669, all of Hotel fits into buffer
Indexed Nested Loop 152, using primary key index
Sort-Merge 250007 unsorted
16669 sorted

Hash 50007 if hash index fits in memory
J3: Room roomNo Booking
Block Nested Loop 833400, buffer has only 1 block for Room and

Booking.
16717, all of Room fits into buffer
Indexed Nested Loop 30050, using clustering index
Sort-Merge 250305 unsorted
16717 sorted

Hash 50151 if hash index fits in memory
J4: Room hotelNo Hotel
Block Nested Loop 150, buffer has only 1 block for Room and

Hotel.
52, all of Room fits into buffer
Indexed Nested Loop 30050, using clustering index
Sort-Merge 302 unsorted
52 sorted

Hash 156 if hash index fits in memory
J5: Booking hotelNo Hotel
Block Nested Loop 50001, buffer has only 1 block for Hotel and

Booking.
17008, if (nBuffer-2) blocks for Booking
16669, if all of Booking fits into buffer
Indexed Nested Loop 1666716667, using linear search
Sort-Merge 250007 unsorted
16669 sorted

Hash 50007 if hash index fits in memory
J6: Booking roomNo Room
Block Nested Loop 850017, buffer has only 1 block for Booking and

Room.
25171, if (nBuffer-2) blocks for Booking
16717, all of Booking fits into buffer
Indexed Nested Loop 1666716667, using clustering index
Sort-Merge 250305 unsorted
16717 sorted

Hash 50151 if hash index fits in memory