Page 211 - DCAP402_DCAO204_DATABASE MANAGEMENT SYSTEM_MANAGING DATABASE

Database Management Systems/Managing Database

Notes 4. Merge-join
5. Hash-join
6. Complex join.
The choice of join algorithm is based on the cost estimate. Let us use the following information
to elaborate the same:
MARKS (enroll no, subject code, marks): 10000 rows, 500 blocks
STUDENT (enroll no, name, dob): 2000 rows, 100 blocks

12.4.1 Nested-loop Join

Let us show the algorithm for the given relations.

To compute the theta or equi-join
for each tuple s in STUDENT
{
for each tuple m in MARKS
{
test s.enrolno = m.enrolno to see if they satisfy the join
condition if they do, output joined tuple to the result.
};
};

1. In the nested loop join there is one outer relation and one inner relation.
2. It does not use or require indices. It can be used with any kind of join condition. However,
it is expensive as it examines every pair of tuples in the two relations.

3. If there is only enough memory to hold one block of each relation, the number of disk
accesses can be calculated as:
For each tuple of STUDENT, all the MARKS tuples (blocks) that need to be accessed.

However, if both or one of the relations fit entirely in the memory, block transfer will be needed
only once, so the total number of transfers in such a case, may be calculated as:
= Number of blocks of STUDENT + Number of blocks of MARKS

= 100 + 500 = 600.
If only the smaller of the two relations fits entirely in the memory then use that as the inner
relation and the bound still holds.

Cost for the worst case:
Number of tuples of outer relation × Number of blocks of inner relation + Number of blocks of
outer relation.

2000 × 500 + 100 = 1,000,100 with STUDENT as outer relation.
There is one more possible bad case when MARKS is on outer loop and STUDENT in the inner
loop. In this case, the number of Block transfer will be:

10000 × 100 + 500 = 1,000,500 with MARKS as the outer relation.

204 LOVELY PROFESSIONAL UNIVERSITY