중첩 루프 조인 문서 원본 보기

{{위키데이터 속성 추적}}
{{기계 번역|날짜=2022-09-30}} '''중첩 반복 조인'''은 N 개의 집합을 N 개의 중첩된 반복문을 사용해 조인하는 알고리즘으로, 데이터베이스 관리에 중요하게 사용된다.<ref>https://technet.microsoft.com/en-us/library/ms191318(v=sql.105).aspx</ref>
== 알고리즘 ==
두 개의 관계 <math>R</math>과 <math>S</math>는 아래와 같이 조인된다.
 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>
이 알고리즘은  n<sub>r</sub>*b<sub>s</sub>+ b<sub>r</sub> 개의 블록 전송과 n<sub>r</sub>+b<sub>r</sub> 회의 검색을 발생시킨다. 여기서 b<sub>r</sub> 과 b<sub>s</sub> 는 관계 <math>R</math>과 <math>S</math> 각각의 블록 개수, 그리고 n<sub>r</sub> 은 관계 <math>R</math>의 튜플 개수를 의미한다.

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

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

== 같이 보기 ==
* [[해시 조인]]
== 각주 ==
{{각주}}

{{전거 통제}}

[[분류:데이터베이스 알고리즘]]