Abstract

Many commercial database systems maintain histograms to summarize the contents of relations, permit efficient estimation of query result sizes, and access plan costs. In spatial database systems, most query predicates consist of topological relationship between spatial objects, and ti is ver important to estimate the selectivity of those predicates for spatial query optimizer. In this paper, we propose a selectivity estimation scheme for spatial topological predicates based on the multi-dimensional histogram and the transformation scheme. Proposed scheme applies two partition strategies on transformed object space to generate spatial histogram, and estimates the selectivity of topological predicates based on the topological characteristic of transformed space. Proposed scheme provides a way for estimating the selectivity without too much memory space usage and additional I/Os in spatial query optimizer.

히스토그램을 이용한 질의 술어의 선택도 추정은 상용 데이터베이스 시스템의 비용 기반 최적화기에서 가장 널리 사용되는 방법이다. 공간 데이터베이스 관리 시스템의 경우 객체간의 위상 관계를 이용한 술어가 주어지며, 질의 최적화를 위해서는 공간 위상 술어의 선택도 추정이 필수적이다. 이를 이해 본 논문에서는 기존의 다차원 히스토그램 기법에 차원 변환 기법을 적용한 공간 위상 술어 추정 기법을 제안한다. 제안된 기법은 차원 변환 공간상의 점으로 대응된 공간 객체로부터 두가지 분할 전략을 이용하여 공간 히스토그램을 생성한 수 변환 공간이 가지는 위상 관계를 이용하여 공간 위상 술어의 선택도를 추정한다. 제안된 기법은 공간 질의 최적화기에서 비교적 작은 메모리와 부가적인 입출력 없이 공간 위상 술어의 선택도를 추정할 수 있다.

Keywords