오디세우스 객체관계형 DBMS를 위한 외부 조인의 설계 및 구현

Abstract

외부 조인은 조인에 참여하는 릴레이션들에서 조인 조건을 만족하지 않는 한쪽 또는 양쪽 튜플들도 결과로 반환하는 조인 연산으로 OLAP 질의 처리, 계층적 뷰(hierarchical view) 처리, 중첩 질의 처리 등의 다양한 고급 데이터베이스 응용에서 널리 사용된다. 많은 상용 DBMS에서 외부 조인을 지원하고 있으나, 상세한 구현 방법은 공개되어 있지 않다. 외부 조인은 조인에 참여하는 릴레이션들에서 조인 조건을 만족하지 않는 한쪽 또는 양쪽 튜플들도 결과로 반환하는 조인 연산으로 OLAP 질의 처리, 계층적 뷰(hierarchical view) 처리, 중첩 질의 처리(nested query processing) 등의 다양한 고급 데이터베이스 응용에서 널리 사용된다. 많은 상용 DBMS에서 외부 조인을 지원하고 있으나, 상세한 구현 방법은 공개되어 있지 않다. 본 논문에서는 한국과학기술원 멀티미디어 및 데이타베이스 연구실에서 개발하고 있는 오디세우스 객체관계형 DBMS를 위한 외부 조인을 설계하고 구현한다. 본 논문에서는 외부 조인의 처리 성능을 향상시키기 위해 다음과 같은 새로운 방법 및 구현 기법을 제안한다. 첫째, 외부 조인이 포함된 질의에 대해서 조인 연산의 결과를 임시 릴레이션(temporary relation)에 저장하는 것 대신에 다음 조인 연산의 입력으로 파이프라이닝(pipelining)시킴으로써 질의를 최적화하는 방법을 제안한다. 둘째, 질의 최적화를 위해 외부 조인을 내부 조인 또는 한쪽 외부 조인(one-sided outer join)으로 간략화하는 기존 알고리즘을 효율적으로 구현하는 기법을 제안한다.