Doubts abouts join implementation I'm studying advanced database and I can not understand some concepts related to the join.
I hope I'm in the right place to post my doubts, otherwise I'm sorry.

I realized that to make the equijoin there are several families. 
In particular, the family that is based on the Cartesian product includes three main methods: nested loops, nested blocks and nested scans.

The nested loop method iterates on the outer relation R (tipically the smaller one) and for each tuple of R, it scans the internal relation S and applies the join condition.
Then it just use the join definition: Cartesian product + selection.
The cost of this process is:

C = |R| + |R| * |S|

You can get an improvement if instead of considering the tuples, consider the pages.
In this case the cost is:

C = P_R + |R| * P_S

Why? I do not understand.

From what I remember of Operating Systems, the logical memory is divided into pages and the physical memory in frames, where the pages are of the same size of the frames.
This is done to permit the non-contiguous allocation of files.

A tuple instead of what corresponds? I guess as a record (one line) of a table, but in this context what is it?

The nested blocks method is a further improvement because in main memory maintains a block of tuples of R.
The improvement is obtained by scanning S only once for each group of tuples of R.
A version of this charging algorithm in the tuples of R memory, then proceeds to S and examines the memory to find the S tuples that match any tuple of R.
This reduces the number of necessary S scans.
In this case the cost is:

C = P_R + P_R * P_S

I must admit that I did not understand very well this algorithm.
Someone could explain it better?

Thus a block is a set of tuples? And a set of tuples form one page?
I'm very confused.

Maybe some sketch could help me, I have not found that showed the tuples.

Thank you all



If I understand correctly, this is how I imagine the logical memory, physical memory, pages and frames:


Nested loops (tuple)

Again, as I understand it:


I apologize but I have not yet understood the nested loop (pages) and nested block :(

What do you mean with "We can achieve some improvement checking the tuples stored on one page of relation S for each record in relation R"?

And with "In Block nested approach each block in the inner relation S is read once for each block in the relation R which gives you the desired cost"?

I feel a bit stupid, sorry.
First of all let us talk about the cost measure .
The cost C is calculated actually in terms of the number of disk access made in order to compute the join.

A block is defined as the smallest unit of memory which is transferred from disk to main memory during a disk access.

A page is a contiguous block of memory. (set of blocks)  

Anther term associated is the blocking factor. which is the number of records which can be present on a single block of memory. 

Suppose we need to compute the join of relation RxS
The first method we first bring the relation R in the main memory which take n(R) disk accesses (n(R)= number of records in the relation R). Note that records and tuples mean the same thing. For each record in relation R we make another disk access to bring a single record of relation S to check the join condition this gives another n(r)*n(S) disk accesses.
the total being n(r)+n(R)*n(S)

We can achieve some improvement checking the tuples stored on one page of relation S  for each record in relation R.

In Block nested approach each block in the inner relation S is read once for each block in the relation R
which gives you the desired cost