중첩 루프 조인

중첩 반복 조인은 N 개의 집합을 N 개의 중첩된 반복문을 사용해 조인하는 알고리즘으로, 데이터베이스 관리에 중요하게 사용된다.

알고리즘 
두 개의 관계 과 는 아래와 같이 조인된다.
 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 <r,s>
이 알고리즘은  nr*bs+ br 개의 블록 전송과 nr+br 회의 검색을 발생시킨다. 여기서 br 과 bs 는 관계 과  각각의 블록 개수, 그리고 nr 은 관계 의 튜플 개수를 의미한다.

이 알고리즘은  의 I/O를 시행한다. 과 는 과 각각에 포함된 튜플 개수를 의미하고, 이는 조인을 통해 발생될 관계의 개수를 통해 쉽게 계산할 수 있다.

블록 중첩 루프 조인 알고리즘은 관계 가 스캐닝 되는 횟수를 줄이는 것으로 추가적인 메모리 이득을 보는 중첩 반복 조인의 일반화 된 알고리즘이다.

참조 

데이터베이스 알고리즘