제 3항에 있어서,상기 반복 분할하는 단계는 상기 분할된 그룹의 크기가 1 또는 분할될 단말 엔트리가 없을 때까지 반복 수행하는 것을 특징으로 하는 분할-트리 중첩 루프 조인 방법.

데이터베이스로부터 외부 색인 R의 단말 엔트리들을 읽어온 후 R 트리로 정렬하는 단계와;상기 정렬된 R의 단말 엔트리들을 시간 구간에 대응하는 복수 개의 윈도우를 생성하는 단계와; 내부 색인 S의 단말 엔트리들을 소정의 그룹의 부분 트리로 분할하는 단계와;상기 분할된 각 부분 트리와 상기 생성된 각 윈도우에 속하는 단말 엔트리 간의 비교를 통해 겹침을 검색하는 단계를 포함하는 분할-트리 중첩 루프 조인 방법.

제 1항에 있어서,상기 부분 트리로 분할하는 단계는, 상기 S의 단말 엔트리에 대한 공집합을 형성하는 단계와; 상기 형성된 공집합에 상기 S 단말 엔트리를 채우는 단계와; 상기 형성된 공집합을 두 개의 그룹으로 분할하는 단계와; 상기 분할된 두 개의 그룹을 각각 분할된 두 개의 그룹의 크기보다 작은 크기의 그룹으로 분할하는 단계를 포함하는 것을 특징으로 하는 분할-트리 중첩 루프 조인 방법.

제 2항에 있어서,상기 작은 크기로 분할된 그룹을 다시 그보다 작은 크기의 그룹으로 반복 분할하는 단계를 더 포함하는 것을 특징으로 하는 분할-트리 중첩 루프 조인 방법.

제 2항에 있어서,상기 두 개의 그룹으로 분할하는 단계는,상기 단말 엔트리들로부터 겹침이 큰 2개의 단말 엔트리를 검색하는 단계와;상기 검색된 겹침이 큰 2개의 단말 엔트리를 각각 서로 다른 두 그룹에 삽입하는 단계와;상기 삽입된 2개의 단말 엔트리를 제외한 나머지 단말 엔트리들을 상기 두 그룹에 삽입된 엔트리와 각각 겹치는 영역이 작은 그룹을 선택하여 해당 그룹에 삽입하는 단계를 포함하는 것을 특징으로 하는 분할-트리 중첩 루프 조인 방법.

제 5항에 있어서, 상기 두 그룹의 크기를 비교하여 어느 한 그룹의 크기가 나머지 한 그룹의 크기보다 0.5배 더 크다면 상기 나머지 단말 엔트리들을 작은 크기의 그룹에 삽입하는 것을 특징으로 하는 분할-트리 중첩 루프 조인 방법.

제 6항에 있어서,상기 작은 크기의 그룹에 상기 나머지 단말 엔트리를 삽입할 때 상기 두 그룹의 크기가 비슷하게 될 때까지 삽입하는 것을 특징으로 하는 분할-트리 중첩 루프 조인 방법.

제 5항에 있어서,상기 겹치는 영역이 작은 그룹을 선택하여 해당 그룹에 삽입하는 단계에서 상기 겹치는 영역이 작거나 겹치는 영역이 없이 떨어진 그룹을 선택하여 삽입하는 것을 특징으로 하는 분할-트리 중첩 루프 조인 방법.