Efficient query processing for complex spatial objects is one of the most challenging requirements in non-traditional applications such as geographic information systems, computer-aided design, and multimedia databases. The performance of spatial query processing can be improved by decomposing a complex object into a small number of simple components. This paper investigates the natural trade-off between the number and the complexity of decomposed components. In particular, we propose a new object decomposition method that can control the number of components using a parameter. This method enables the user to select the optimal trade-off by controlling the parameter. The proposed method is compared with traditional decomposition methods by an analytical study and experimental measurements. These comparisons show that our decomposition method outperforms traditional decomposition methods.
A spatial query processor based on object decomposition is implemented as a SHORE Value Added Server (VAS) directly on top of the SHORE Storage Manager (SSM). The goal in developing the query processor is to implement a sub- system that efficiently supports a well-chosen set of spatial queries. These spatial queries serve as a basis for implementing other more sophisticated operations required in special applications. Spatial queries that we implemented are the point query, region query, spatial join query, nearest neighbor query, and insert query. An efficient implementation of these basic spatial queries is the most important for good overall performance of the spatial query processor.
We provide analytical formulas that predict the performance of the spatial query processor. The major contribution of our analysis is the refinement step analysis. In contrast to several earlier investigations on this subject, we take into account the analytical formulas that predict the performance of the refinement step, since the refinement step exerts critical influence on the performance of spatial query processing. Our analysis constitutes a useful tool for spatial query optimizers that need to evaluate the cost of a complex spatial query.
복잡한 공간 객체에 대한 효율적인 질의 처리는 지리정보시스템, 컴퓨터지원설계, 멀티미디어 데이타베이스와 같은 최근의 응용 분야에서 가장 필수적인 요구사항들 중 하나이다. 공간 질의 처리의 성능은 복잡한 객체를 단순하고 적은 개수의 구성요소들로 분할함으로써 향상될 수 있다. 그런데 구성요소들을 단순하게 만들려고할 때 산출되는 구성요소들의 수는 일반적으로 많아진다. 따라서,본 논문에서는 이러한 이율 배반적인 특성에 대해 적절한 절충 값을 취함으로써 질의 처리 성능을 향상시킬 수 있는 방법을 연구하였다. 특히, 하나의 매개변수에 의해 구성요소들의 개수를 조절할 수 있는 새로운 객체 분할 방법을 제안하였다. 제안된 방법은 매개변수의 조절에 의해 사용자들에게 절충된 최적 값을 선택하여 사용할 수 있도록 지원하고 있다. 이러한 새로운 방법은 해석적분석과 실험적측정을 통한 연구에 의해 기존의 객체 분할 방법들과 성능을 비교 분석하였다. 성능 분석 결과, 제안된 새로운 방법이 기존의 다른 객체 분할 방법보다 상대적으로 성능이 우수함을 알 수 있다.
객체 분할을 기반으로 한 질의 처리기를 SHORE 저장 관리자상에서 하나의 SHORE VAS (Value Added Server)로서 구현하였다. 본 논문에서,공간 질의 처리기 개발의 목표는 보편적으로 널리 사용되는 기본적인 공간 질의들을 효율적으로 처리할 수 있는 기본시스템을 개발하는데 있다. 이러한 기본적인 공간 질의들은 특정분야에서 요구되는 다양한 공간 질의들을 구현할 때 그 기반으로써 사용되어 진다. 구현된 기본적인 공간 질의들은 점 질의,영역 질의, 공간 죠인 질의, 최근접 질의, 그리고 입력 질의이다. 기본적인 공간 질의들의 효율적인 구현은 공간 질의 처리기의 전체적인 성능 향상을 위해 가장 중요한 역할을 수행한다.
구현한 공간 질의 처리기에 대하여 그 성능을 예측할 수 있는 해석적 모델을 제안하였다. 제공된 모델의 주요 내용은 정제 단계분석이다. 즉, 이 분야에 관한 초기의 여러 연구들과는 달리 여과 단계 뿐만 아니라 정제 단계의 성능을 예측할 수 있는 해석적인 모델을 고려하였다. 정제 단계를 고려한 이유는 정제 단계가 공간질의 처리기의 성능에 중요한 영향을 미치기 때문이다. 제안된 해석적 모델은 복잡한 공간 질의의 비용을 평가하는 공간 질의 최적화기 에서 유용한 도구로써 사용될 수 있다.
