정보과학회 논문지 B : 소프트웨어 및 응용
Current Result Document : 3 / 4
| 한글제목(Korean Title) |
그리디 알고리즘에 의한 클래스 인덱싱 기법 |
| 영문제목(English Title) |
A Class Indexing Technique using Greedy Algorithm |
| 저자(Author) |
안정호
송하주
김형주
Jung-Ho Ahn
Ha-Joo Song
Hyoung-Joo Kim
|
| 원문수록처(Citation) |
VOL 25 NO. 12 PP. 1738 ~ 1748 (1998. 12) |
한글내용
(Korean Abstract) |
객체 지향 데이타베이스 시스템은 기존 관계형 데이타베이스 시스템과는 달리 클래스 및 클래스 계층구조 개념을 제공한다. 따라서 질의 또한 특정 클래스 뿐만 아니라 해당 클래스의 하위 클래스를 포함하는 클래스 계층구조 상에서 이루어진다. 이를 위해 클래스 계층 인덱스 기법을 비롯하여 여러 클래스 인덱싱 기법이 제안되었으나 성능과 실용성에 문제가 있으며, 다차원 인덱스 기법을 사용하는 것 또한 효율성이 떨어지는 단점이 있다.
본 논문은 클래스 계층구조 상에서의 질의를 효과적으로 지원하기 위한 인덱스 기법으로서 인덱스 집합 기법을 제안한다. 인덱스 집합 기법은 그리디 알고리즘을 통해 클래스 계층구조상의 여러 클래스들을 주어진 제한 조건내에서 최소의 검색 비용으로서 질의를 처리할 수 있도록 클래스들의 그룹으로 구분한 뒤, 각 그룹에 대해 B^+-트리 인덱스를 각각 할당하는 방법이다. 또한 본 논문에서는 클래스 내의 인스턴스의 수, 키 값의 분포 형태, 질의 형태에 따라 인덱스를 구성할 저장 공간 및 인덱스 검색에 따르는 비용을 예측하기 위한 비용 모델을 제시한다. 본 인덱스 집합 기법은 B^+-트리의 구조에 큰 변형을 가하지 않고 그대로 사용할 수 있기 때문에 실용적인 장점도 함께 가지고 있다.
|
영문내용
(English Abstract) |
Object-oriented database systems (OODBMS) are based on object and class concept, and thus, OODBMS should provide class hierarchy query which can probe every instance of a class and its sub-classes. Several class indexing schemes including class-hierarchy index have been proposed to support this land of queries. They, however, suffer from poor performance and lack of practicability. In addition, multi-key indexing schemes are not suitable since they are too general.
In this paper, we propose a class indexing scheme, Index Set which allocates B^ -tree indices to groups of classes by the greedy algorithm. We also introduce a cost model which can predict the space and retrieval cost of index based on the number of instances, the distribution of key values in each class, and query pattern on the class hierarchy. Our scheme has a good practical advantage that it can be easily applied to a system since it uses the well-proven B^ -tree structure.
|
| 키워드(Keyword) |
|
| 파일첨부 |
PDF 다운로드
|
