Suppose we are given a database with the following schema. Users User IDINTEGER,

Question

Suppose we are given a database with the following schema. Users User IDINTEGER, Name CHAR(30), Age INTEGER, ReviewCount INTEGER) Businesses (BusinessID INTEGER, BName CHAR(30), City CHAR(20), State CHAR(2) Checkins (BusinessIDINTEGER, Weekdays INTEGER, Weekends INTEGER) Reviews (ReviewID INTEGER, UserIDINTEGER, BusinessID INTEGER, Stars REAL) Reviews (UserID) is a foreign key referring to Users (UserID). Reviews (BusinessID) is a foreign key referring to Businesses (BusinessID). Checkins (BusinessID) is a foreign key referring to Businesses (BusinessID) A page is 8 kB in size. The RDBMS buffer pool has 10,000 pages, all of which are usable. Initially, the buffer pool is empty. The relation instances have the following statistics. Assume there are no NULL values. Each integer or real is 8B, and each character is 1B (so as an example CHAR(20) is 20B). Additionally, the record id of each tuple is 8B. Relation Number of Pages Number of Tuples 75,684 10m. Users 41,504 5mm Businesses 19,532 5mm Checkins Reviews 488,282 100m

Explanation / Answer

As per the below record:

Relation

Number of Pages

Number of Tuples

Users

75,684

10m

Businesses

41,504

5m

Checkins

19,532

5m

Review

488,282

100m

It is a key-key join and both tables are already sorted on BusinessID. The exact costs are listed below:

Sort-Merge Join = Businesses + Checkins

This is already in lower bound

Sort-Merge Join = 41,504 + 19,532

= 61,036

As per Index Nested Loop Join, the cost will be too high

Block Nested Loop Join = 19,532 + [1.4 * 19,532/ 9,998] * 41,504

= 19,532 + [1.4 * 19, 532/9, 998] * 41, 504

= 19,532 + [1.4 * 1.95] * 41, 504

= 19,532 + 2.735*41,504

= 19,532 + 113,514.56

= 133,045 (approx)

Hash Join = 3 × (41, 504 + 19, 532)

= 3* 61,036

= 183,108

Thus, the lowest I/O cost is for Sort-Merge Join, which simply scans both tables in their existing order.

Relation

Number of Pages

Number of Tuples

Users

75,684

10m

Businesses

41,504

5m

Checkins

19,532

5m

Review

488,282

100m

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.