## Joins

Question 1 |

Consider a join (relation algebra) between relations r(R) and s(S) using the nested loop method. There are 3 buffers each of size equal to disk block size, out of which one buffer is reserved for intermediate results. Assuming size(r(R)) < size(s(S)), the join will have fewer number of disk block accesses if

relation r(R) is in the outer loop. | |

relation s(S) is in the outer loop. | |

join selection factor between r(R) and s(S) is more than 0.5. | |

join selection factor between r(R) and s(S) is less than 0.5. |

Question 1 Explanation:

The join between r(R) and s(S) which is using nested loop will be as follows,

For each tuple r in R do

For each tuple s in S do

If r and s satisfy the join condition then

output the tuple

The above algorithm involves (n

block transfer and (n

where,

b

b

h

To have less block accesses in nr should be less and in question it is given that size(r(R)) < size(s(S)).

To have fewer no. of disk block accesses the relation r(R) should be in outer loop.

For each tuple r in R do

For each tuple s in S do

If r and s satisfy the join condition then

output the tuple

The above algorithm involves (n

_{r}*b

_{s}+b

_{r})

block transfer and (n

_{r}+b

_{r}) seeks.

where,

b

_{r}→ no. of blocks in R

b

_{s}→ no. of blocks in S

h

_{r}→ no. of tuples in R

To have less block accesses in nr should be less and in question it is given that size(r(R)) < size(s(S)).

To have fewer no. of disk block accesses the relation r(R) should be in outer loop.

There is 1 question to complete.