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

Question

Using the Hotel schema, assume the following indexes exist:
? 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

S1: ? roomNo=1 ? hotelNo=1 (Room)
S2: ? type=‘D’ (Room)
S3: ? hotelNo=2 (Room)
S4: ? price>100 (Room)
S5: ? type=‘S’ ? hotelNo=3 (Room)
S6: ? type=‘S’ ? price < 100 (Room)

Answer 1

S1: ? roomNo=1 ? hotelNo=1 (Room)
Use Hash: cost = 1; Linear search cost is: [10000/200]/2 = 25
S2: ? type=‘D’ (Room)
Use equality condition on clustering index:
SC type (Room) = [10000/10] = 1000
Cost: 2+ [1000/200] = 5
Linear search cost is: 50
S3: ? hotelNo=2 (Room)
Use equality on clustering index:
SC hotelNo (Room) = [10000/50] = 200
Cost: 2+ [200/200] = 3
Linear search cost is: 50
S4: ? price>100 (Room)
Use inequality on a secondary B + -tree:
Cost: 2 + [50/2 + 10000/2] = 5027
Linear search cost is: 50
S5: ? type=‘S’ ? hotelNo=3 (Room)
If use secondary index searches on each of the two components, costs are 5 and 3,
respectively (from above). Optimizer would then choose search via clustering index
on hotelNo, and check the remaining predicate in memory.
Linear search cost is: 50
S6: ? type=‘S’ ? price < 100 (Room)
Use the secondary indexes on type and price, then take the union of the two sets.
Linear search cost is: 50