4. Summary of Correct Formulas with Annotations
Join Strategy	Formula	Annotations
Page-Oriented NLJ	(\text{Cost} = \text{NPages}(R) + \text{NPages}(R) \times \text{NPages}(S))	Treats each page of R as an outer loop and scans S entirely for each page of R.
Block-Oriented NLJ	(\text{Cost} = \text{NPages}(R) + \lceil \frac{\text{NPages}(R)}{B-2} \rceil \times \text{NPages}(S))	Processes multiple pages of R simultaneously by leveraging B-2 buffer pages for R and S.
Multi-Pass Hash Join	(\text{Cost} = 3 \times (\text{NPages}(R) + \text{NPages}(S)))	Involves three passes: partitioning R and S, building hash tables, and probing.
Optimized Single-Pass Hash Join	(\text{Cost}_{Hash_Optimized} = \text{NPages}(R) + \text{NPages}(S))	Achievable when R fits entirely into memory. Requires B ≥ NPages(R) + 2 buffer pages.
Sort-Merge Join (SMJ)	(\text{Cost}_{SMJ} = 2 \times \text{NPages}(R) \times \text{num_passes}(R) + 2 \times \text{NPages}(S) \times \text{num_passes}(S) + \text{NPages}(R) + \text{NPages}(S))	Accounts for sorting both R and S across multiple passes and then merging them. Requires accurate calculation of num_passes based on buffer size.
Lowest Possible Cost	(\text{Lowest Cost} = \min(\text{Cost}{SMJ}, \text{Cost}{Hash_Optimized}, \text{Cost}{Hash}, \text{Cost}{NLJ}))	Determines the most cost-efficient join strategy based on available buffer pages and relation sizes.
Minimum Buffer Size	(\text{Minimum Buffer} = \text{NPages}(R) + 2)	Ensures that the entire outer relation R can be loaded into memory with additional buffer pages for processing and reading the inner relation S.   Q1 Introduction  (Total marks for Q1: 5 marks)

Consider two relations A and B. A has 80,000 tuples, and B has 100,000 tuples. Both relations store 100 tuples per page. Consider the following SQL statement:

SELECT *

  FROM A INNER JOIN B

    ON A.a = B.a;
We wish to evaluate an equijoin between A and B, with an equality condition A.a = B.a. There are 102 buffer pages available for this operation. Both relations are stored as (unsorted) heap files. Neither relation has any indexes built on it.

Consider the alternative join strategies described below and calculate the cost of each alternative. Evaluate the algorithms using the number of disk I/O's (i.e., pages) as the cost. Question 1 1 pts
Q1.1

Page-oriented Nested Loops Join. Consider A as the outer relation. (1 mark)

[do not give any decimals]


 
Flag question: Question 2
Question 2 1 pts
Q1.2

Block-oriented Nested Loops Join. Consider A as the outer relation. (1 mark)

[do not give any decimals]


 
Flag question: Question 3
Question 3 1 pts
Q1.3

Sort-Merge Join. Assume that Sort-Merge Join can be done in 2 passes. (1 mark)

[do not give any decimals]


 
Flag question: Question 4
Question 4 1 pts
Q1.4

Hash Join (1 mark)

[do not give any decimals]


 
Flag question: Question 5
Question 5 0.5 pts
Q1.5A

Assuming that no indexes are built on any of the two relations, and assuming that sufficient buffer space is available:

What would be the lowest possible cost to perform this query ? (0.5 mark)
[do not give any decimals]


 
Flag question: Question 6
Question 6 0.5 pts
Q1.5B

 Assuming that no indexes are built on any of the two relations, and assuming that sufficient buffer space is available:

       B. What would be the minimum buffer size required to achieve this cost from Q1.5A? (0.5 mark)

[do not give any decimals]. ANSWER ALL QUESTIONS, AND YOU MUST REFERENCE THE FORMULAS GIVEN ABOVE AS THEY ARE CORRECT.