데이터웨어하우스에서 유전자 알고리즘을 이용한 구체화된 뷰 선택 기법

서지정보

· 발행기관 : 한국정보처리학회
· 수록지 정보 : 정보처리학회논문지D / 11권 / 2호 / 325 ~ 338페이지
· 저자명 : 이민수

초록

데이터 웨어하우스는 복잡한 질의 및 분석을 위해서 다양한 종류의 여러 정보 출처들로부터 정보를 모아서 저장한다. 일반적으로 웨어하우스에는 자주 실행되는 질의들을 미리 계산해서 구체화된 뷰의 형태로 저장한다. 웨어하우스를 설계할 때 가장 중요한 일들 중의 하나는 웨어하우스에서 유지될 구체화된 뷰의 선택이다. 이것은 뷰들의 유지를 위해 제한된 시간이 주어졌을때, 모든 질의들에 대한 총 질의 응답 시간을 최소화 하는 방법으로 일련의 뷰들을 선택하는 것이다(유지-비용 뷰 선택 문제). 본 논문에서는 최적에 가까운 일련의 뷰들을 계산하기 위해 유전자 알고리즘을 사용하여 유지-비용 뷰 선택 문제에 대한 효율적인 해결책을 제안한다. 특히 OR 뷰 그래프들의 관점에서의 유지-비용 뷰 선택 문제를 다룬다. 본 논문의 접근방식은 휴리스틱 방법을 사용한 기존의 탐색-기반 접근 방식들에 비해서, 시간 복잡도에서 큰 향상을 보여준다. 본 논문의 알고리즘은 최적의 질의 비용에 비해 10%이내의 추가비용만을 갖는 해결책을 제시하면서도 실행시간 측면에서는 매우 향상된 선형 증가만을 보인다. 본 논문의 알고리즘에 대한 프로토타입을 구현하였으며 이것을 사용하여 논문에서 제안하는 접근방식의 분석을 수행하였다.

참고자료

· 없음