시간지원 데이타베이스에서의 분할에 기초한 시간조인 알고리즘 = A Time-Join Algorithm based on Partitioning in Temporal Databases

국문 초록 (Abstract)

시간지원 데이타베이스에서 효율적인 시간조인에 대한 새로운 알고리즘을 제안하였다. 작은 릴레이션은 정렬하고 큰 릴레이션은 분할함으로서 기존의 정렬병합 알고리즘에서의 큰 릴레이션의 정렬 비용을 줄이자는 것이 주개념이다. 제안한 알고리즘의 유용성을 보이기 위하여 보조 기억 장치의 액세스 수에 관하여 비용을 분석하였으며 일반적으로 널리 알려진 정렬병합 방법과 성능 비교를 하였다. 증명을 통하여 제안된 방법이 우수한 조건들을 보였으며, 이러한 조건하에서 제안된 방법이 기존의 정렬병합 방법보다 10~30%의 성능 향상이 있음을 모의 실험을 통하여 보였다.

다국어 초록 (Multilingual Abstract)

A new algorithm is proposed in this paper which efficiently performs join in the temporal databases. The main idea is to sort the smaller relation and to partition the larger relation, and the proposed algorithm reduces the cost of sorting the larger relation. To show the usefulness of the algorithm, the cost is analyzed with respect to the number of accesses to secondary storage and compared with that of Sort-Merge algorithm. Through the comparisons, we present and verify the conditions under which the proposed algorithm always outperforms the Sort-Merge algorithm. The comparisons show that the proposed algorithm achieves 10-30% gain under those conditions.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 시간지원 데이타베이스 모델 및 기존의 조인 알고리즘
• 3. 제안 시간조인 알고리즘 및 비용
• 4. 성능 비교
• 5. 결론
• 참고문헌
• 저자소개