It has been recognized that relational database management systems do not well handle spatial data efficiently. The underlying access methods, storage managers, and query languages of the conventional systems are designed to deal with only simple data types like integer, real number, and string. However, non-traditional complex applications such as geographic information systems, computer-aided design, and computer vision are basically required to manage vector data including points, lines, and rectangles and large raster data like voice, image, and video. In this thesis, for the efficient manipulation of vector data and very large raster data, access method, storage manager, and query language are addressed.
For access method, we propose a new dynamic access method, called Binary divided Region (BR) tree, for uniform vector data and then implement search, insertion, deletion, and splitting algorithms used for the BR tree. The BR tree splits a region into two sub-regions of equal size recursively and prevents overlapping of rectangles in internal nodes by clipping objects which cause overlapping region. The proposed access method is compared with the two representative spatial access methods, R-tree and $R^+$-tree, through performance results from analytical study and simulation approach for a VLSI data. For search, when the size of a user-specified rectangular region, called query window, is relatively small, BR tree produces the best performance with respect to the number of disk accesses since it generates the smallest number of nodes and avoids overlapping of rectangles.
For storage manager, we propose a new database storage manager, called Buddy-size Segment Storage System (BSSS), to handle large raster data of any size and then implement search, insertion, append, and deletion algorithms used for the storage structure. The internal nodes of the proposed storage manager are identical to the ones proposed in Exodus. However, unlike Exodus that has fixed-size segments for leaf blocks, BSSS has binary buddy-size leaf segments. The proposed storage manager is compared with Exodus through performance results from simulation approach. BSSS performs the same as or better than Exodus for object creation time, sequential scan time, and random search time.
Geographic Structured Query Language (GSQL), which is basically an extension to the SQL, is proposed to express queries involving spatial predicates. GSQL handles spatial relationships such as intersect, cover, and nearest. In addition, a query processing technique based on spatial access methods is proposed. The proposed query processing technique handles complex objects including points, lines, or polygons. Furthermore, our query processing technique proceeds in a two-phase manner: filter phase and refinement phase. The filter phase is based on spatial access methods which manage minimum bounding rectangles (MBRs). However, since MBR objects do not provide exact object representation, the filter phase does not exactly evaluate the query and yields a set of candidate objects which may fulfill the query condition. Therefore, the candidate objects have to be examined in the refinement phase. This phase exactly detects objects finally fulfilling the query condition.
기존의 데이타베이스 시스템은 정수, 실수, 혹은 스트링과 같은 단순한 데이타 형태만을 다루기 때문에 다차원 복합 객체를 효율적으로 다룰 수 없다. 그러나 지리 정보시스템이나 컴퓨터지원설계와 같은 최근의 응용에서는 점, 선, 혹은 사각형 등의 벡터 데이타와 음성이나 이미지와 같은 긴 래스터 데이타를 처리하는 것이 요구된다. 본 논문에서는, 벡터 데이타와 긴 래스터 데이타를 효율적으로 처리하기 위해 접근기법, 저장관리기법, 그리고 질의처리기법을 제안한다.
벡터 데이타의 효율적인 저장과 검색을 위해서 새로운 접근기법인 BR 트리를 제안하고 BR 트리의 검색, 삽입, 삭제, 그리고 분할 알고리즘을 구현하였다. 또한, BR 트리와 기존의 대표적인 공간 접근기법인 R-트리와 $R^+$-트리의 성능을 해석적 모델을 통한 연구와 시뮬레이션을 통하여 분석하였다. 분석 결과에 따르면, BR 트리가 질의 영역과 객체의 크기가 상대적으로 작고 객체가 균일하게 분포할 때 디스크 접근 횟수, 분할 횟수, 삽입 시간, 그리고 저장공간 사용량에서 가장 좋은 성능을 나타낸다.
임의의 크기를 갖는 긴 래스터 데이타를 효율적으로 다루기 위해서 새로운 저장구조인 BSSS를 제안하고 BSSS의 검색, 삽입, 추가, 삭제 알고리즘을 구현하였다. BSSS는 고정된 크기의 세그먼트를 갖는 Exodus와 달리 디스크 공간을 관리하기 위해 버디 시스템을 사용함으로서 객체 생성 시간과 검색 연산에 대해서 좋은 성능을 나타낸다. 또한, BSSS는 인덱스 구조가 $B^+$-트리 구조에 기반을 두고있으므로 긴 래스터 데이타의 부분적인 삽입과 삭제 연산에 대해서 순차적인 디렉토리 구조를 갖는 WiSS나 Starburst보다 좋은 성능을 나타낸다.
공간 데이타에 대한 교역, 포함, 최근접 등의 연산을 처리하기 위해 새로운 질의어와 질의처리기법을 제안하였다. 제안된 질의처리기법은 공간 접근기법에 기반을 두고 있으며 두단계로 구성된다. 첫번째 단계인 여과단계에서는 실객체를 둘러싸는 최소의 사각형에 대하여 공간 접근기법을 적용한다. 두번째 단계인 정제단계에서는 여과단계를 거친 후보 객체에 대해 제안된 정제 알고리즘을 적용해서 주어진 질의 조건에 만족하는 최종 객체를 검출한다.
