본문으로 이동

중첩 루프 조인

위키백과, 우리 모두의 백과사전.

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

알고리즘

[편집]

두 개의 관계 는 아래와 같이 조인된다.

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를 시행한다. 각각에 포함된 튜플 개수를 의미하고, 이는 조인을 통해 발생될 관계의 개수를 통해 쉽게 계산할 수 있다.

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

같이 보기

[편집]

각주

[편집]