객체지향 데이타베이스 시스템에서 경로 인덱스를 이용하는 질의 최적화 기법

조완섭(Wan-Sup Cho),황규영(Kyu-Young Whang) 한국정보과학회 1997 정보과학회논문지(B) Vol.24 No.5

본 논문에서는 객체지향 데이타베이스에서 기존의 인덱스 뿐 아니라 경로 인덱스(path index)까지 효율적으로 이용하는 질의 최적화 기법을 제안한다. 경로 인덱스는 데이타베이스를 액세스하지 않고도 길이가 긴 경로에 대한 조건을 처리할 수 있으므로 매우 유용하지만, 기존의 질의 최적화에서는 최적의 실행 전략을 수립할 때 경로 인덱스의 잇점을 충분히 이용하는 실행 전략을 고려하지 못하고 있다. 제안된 질의 최적화 기법은 질의에 포함된 각 클래스로부터 객체를 액세스할 때 기존의 인덱스와 더불어 다수개의 (경로) 인덱스와 참조 속성(reference attributes)를 함께 이용할 수 있도록 함으로써 경로 인덱스의 잇점을 충분히 이용할 수 있도록 한다. 이를 위하여 먼저, 단순 인덱스만 다루는 기존의 인덱스 인터섹션(intersection) 기법을 객체지향 데이타베이스에서의 경로 인덱스와 참조 속성까지 수용하도록 확장한 인덱스 조인 (index join) 기법을 제안한다. 다음으로, 경로 인덱스를 이용함으로서 액세스될 필요가 없어지는 클래스들을 질의 그래프로부터 구분하여 제거하는 질의 그래프 축소 알고리즘 (query graph reduction algorithm)을 제안한다. 마지막으로, 축소된 질의 그래프에 대하여 최소 비용의 실행 전략을 신속히 생성하는 탐색 알고리즘(search algorithm)과 비용 모델을 기술한다. We propose a query optimization technique that takes advantage of path indexes in object-oriented database systems. Although path indexes provide an efficient access of complex objects (since a condition on a path expression can be evaluated by using the indexes without accessing any database objects), only few research has been done for the query optimization techniques that fully utilize the path indexes. For solving this problem, proposed query optimization technique uses multiple (path) indexes and reference attributes for accessing each class in the query. We first extend the conventional index intersection (or index AND/ORing) technique for taking accounnt of the different structures of path indexes and reference attributes of object-oriented databases. We then propose a query graph reduction algorithm for removing the classes that are to be replaced by the path index scans. We finally describe a search algorithm and cost model that generate the least-cost evaluation p]an from the reduced query graph.

객체지향 데이타베이스에서 다중값 속성을 포함한 조건의 선택률 추정 기법

조완섭(Wan-Sup Cho),박종목(Chong-Mok Park),황규영(Kyu-Young Whang) 한국정보과학회 1995 한국정보과학회 학술발표논문집 Vol.22 No.1

선택률(selectivity factor)은 전체 객체중 질의 조건을 만족하는 객체의 비율로 정의되며, 데이타베이스 성능(preformance)에 관한 연구에서 질의에 대한 처리 비용을 예측하는데 중요한 요소로 사용된다. 대부분의 객체지향 데이타베이스에서 다중값(multi-valued) 속성을 제공하고 있으나, 기존의 선택률 추정 기법은 다중값이 선택률 추정에 미치는 영향을 고려하지 않고 있다. 본 논문에서는 객체지향 데이타베이스에서 질의에 대한 처리 비용을 모델링하는데 유용한 중포 선택률을 정의하고, 다중값의 영향을 반영하여 중포 선택률을 추정하는 기법을 제안한다. 중포 선택률 추정에서 기존의 기법들을사용하면 다중값의 원소수가 많아질수록 오차가 증가하나, 제안된 기법은 다중값의 영향을 반영함으로서 정확도가 개선된다.

객체지향 데이터베이스 시스템에서 질의 최적화 기법

조완섭(Wan-Sup Cho),황규영(Kyu-Young Whang) 한국정보과학회 데이터베이스 소사이어티 1996 데이타베이스 연구 Vol.12 No.3

객체지향 데이타베이스에서 질의를 만족하는 중간 결과수의 추정 기법

조완섭(Wan-Sup Cho),박종목(Chong-Mok Park),황규영(Kyu-Young Whang) 한국정보과학회 1994 한국정보과학회 학술발표논문집 Vol.21 No.2A

객체지향 데이타베이스에서는 데이타 모델의 특성으로 인하여 질의에 포함된 한 클래스의 객체들이 다른 클래스의 객체들과 부분적으로 연관되는 부분참여 현상이 빈번하다. 본 논문은 객체지향 데이타베이스의 질의 최적화에서 부분참여 현상을 고려하는 중간 결과수 (cardinality of intermediate results)의 추정 기법을 제안한다. 질의 처리 과정에서 발생하는 중간 결과수는 질의 최적화에서 대안이 되는 여러 처리 전략들의 비용을 예측하는데 중요한 요소이다. 중간 결과수 추정에 관한 기존의 연구들은 부분참여를 신중하게 고려하지는 않았으며, 이러한 경우에 큰 오차가 발생할 수 있다.

객체지향 데이타베이스에서 다단계 인덱스를 효율적으로 이용하는 조인 알고리즘

조완섭(Wan-Sup Cho),박종목(Chong-Mok Park),황규영(Kyu-Young Whang),윤용익(Yong-Ik Yoon) 한국정보과학회 1996 한국정보과학회 학술발표논문집 Vol.23 No.1A

객체지향 데이타베이스에서 다양한 종류의 다단계 인덱스(multi-level indexes)들이 제안되고 있으나 기존의 조인 알고리즘들은 이들을 효율적으로 이용하지 못하고 있다. 본 논문에서는 객체지향 데이타베이스의 고유 액세스 방법인 객체 식별자(object identifier)와 더불어 다단계 인덱스(들)를 효율적으로 이용하는 새로운 조인 알고리즘을 제안한다. 제안된 조인 알고리즘은 사용 가능한 다단계 인덱스가 존재하는 경우에는 이들을 이용함으로써 조인 비용을 줄이며, 그렇지 않은 경우에는 기존의 조인 알고리즘과 동일하게 동작한다.

주문형 비디오 시스템에서의 동적 버퍼 할당 기법

이상호,문양세,황규영,조완섭,Lee, Sang-Ho,Moon, Yang-Sae,Whang, Kyu-Young,Cho, Wan-Sup 한국정보과학회 2001 정보과학회논문지 : 시스템 및 이론 Vol.28 No.9

주문형 비디오 시스템에서 초기 대기시간과 메모리요구량의 최소화는 중요하다. 초기대기시간의 최소화는 빠른 응답시간의 서비스를 제공할 수 있게 하고 메모리 요구량의 최소화는 동일한 메로리량으로 더 많은 동시 사용자 용청을 서비스할수 있게 한다. 주문형 비디오 시스템에서는 사용자 요청에서 할달되는 버퍼 크기가 증가함에 따라 초기대기시간과 메모리 요구량이 증가하므로 사용자 요청에 할당되는 버퍼의 크키를 최소화해야한다. 그러나 기존의 정적 버퍼 할당 기법은 시스템이 완전 부하된 상태에 있다는 가정하에서 버퍼 크기를 결정하여 시스템이 불안정 부하인 경우에는 사용자 요청에서 필요 이상으로 큰 버퍼를 할당한다. 본 논문에서는 시스템의 완전 부하 상태 뿐만 아니라 불와전 부하 상태에서도 사용자 요청에게 최소 크기의 버퍼를 할당하는 동적 버퍼 할당 기법을 제안한다. 동적 버퍼 할당기법은 서비스 중인 사용자 요청 수와 이들 요청들을 서비스하는 동안에 도착하는 사용자 요청수에 기반하여 버퍼크기를 동적으로 결정한다. 또한 분석과 시뮬레이션을 통하여 동적 버퍼 할당 기법이 초기대기시간과 지원 가능한 동시 사용자 요청수에 있어서 정적 버퍼 할당 기법에 비해 크게 우수함을 보인다. 시뮬레이션 결과, 동적 버퍼 할당 기법이 정적 버퍼 할당 기법에 비해 평균 초기대기시간을 29%~65%줄이고, 다수의 디스크들로 구성된 시스템에서는 서비스한 평균 동시 사용자 요청수를 48%~67% 증가시킨것으로 나타났다. 이와같은 결과는 동적 버퍼 할당 기법이 주문형 비디오 시스템의성능과 용량을 크게 향상시킴을 보여주는것이다. In video-on-demand(VOD) systems it is important to minimize initial latency and memory requirements. The minimization of initial latency enables the system to provide services with short response time, and the minimization of memory requirements enables the system to service more concurrent user requests with the same amount of memory. In VOD systems, since initial latency and memory requirement increase according to the increment of buffer size allocated to user requests, the buffer size allocated to user requests must be minimized. The existing static buffer allocation scheme, however, determines the buffer size based on the assumption that thy system is in fully loaded state. Thus, when the system is in partially loaded state, the scheme allocates user requests unnecessarily large buffers. This paper proposes a dynamics buffer allocation scheme that allocates user requests the minimum buffer size in fully loaded state as well as a partially loaded state. This scheme dynamically determines the buffer size based on the number of user requests in service and the number of user requests arriving while servicing current requests. In addition, through analyses and simulations, this paper validates that the dynamics buffer allocation outperforms the statics buffer allocation in initial latency and the number of concurrent user requests that can be supported. Our simulation results show that, in proportion to the static buffer allocation scheme, the dynamic buffer allocation scheme reduces the average initial latency by 29%~65%, and in a systems having several disks. increases the average number of concurrent user requests by 48%~68%. Our results show that the dynamic buffer allocation scheme significantly improves the performance and reduce the capacity requirements of VOD systems.

객체지향 데이타베이스에서 중첩 술어의 선택률 추정 기법

조완섭,박종목,황규영(Wan-Sup Cho),Chong-Mok Park,Kyu-Young Whang 한국정보과학회 1996 정보과학회논문지(B) Vol.23 No.8

본 논문에서는 객체지향 데이타베이스에서 다대다 관계(many-to-many relationship)와 부분 참여(partial participation)의 영향을 반영한 중첩 술어(nested predicate)의 선택률(selectivity) 추정기법을 제안 한다. 중첩 술어에 대한 선택률은 중첩 술어가 부과된 경로식(path expression)의 시작 클래스(starting class)에서 조건을 만족하는 객체의 비율로 정의하며, 데이타베이스 시스템의 성능을 연구하는 분야에서 질의에 대한 처리 비용을 예측하는데 중요한 요소로 사용된다. 중첩 술어에 포함된 경로식 내의 인접한 두 클래스는 다대다 관계를 가지는 경우와 두 클래스의 객체들이 관계에 부분 참여하는 경우가 빈번하지만 기존 연구에서는 이러한 경우를 신중히 고려하지는 못하고 있다. 비용 분석 결과, 제안된 기법은 다대다 관계나 부분 참여를 포함하는 중첩 술어에 대하여 기존의 기법들보다 선택률 추정의 정확도를 크게 개선한다. 제안된 기법은 다대다 관계와 부분 참여의 영향을 반영하기 위하여 기존 기법보다 정교한 통계치를 사용한다. 논문에서는 객체지향 데이타베이스의 특징을 이용하여 정교한 통계치를 쉽게 구하는 방법도 제시한다. 또한, 데이타베이스의 성능을 연구하는 분야에서 중첩 선택률이 이용되는 응용 분야를 구체적으로 제시한다. We propose a new selectivity estimation technique for a nested predicate - a condition on a path expression - in object-oriented databases. The selectivity for a nested predicate - the ratio of the number of qualified objects of the starting class in the path expression included in the nested predicate to the total number of objects in the class - is an important factor for estimating the query evaluation cost in query optimization or physical database design. Proposed technique takes into account the effects of many-to-many relationships and partial participations of classes. Although many-to-many relationships and partial participations occur frequently in object-oriented queries, they have not been considered seriously in previous techniques. The cost analysis shows that the proposed technique provides significent gain in accuracy when many-to-many relationships and/or partial participations are involved in the query. We also present an efficient method for obtaining the detailed statistics used in the proposed technique by utilizing the common features of object-oriented databases. We finally present three typical application areas of the proposed technique.

부분참여 클래스를 포함하는 객체지향 질의를 만족하는 객체수의 추정 기법

박종목(Chong-Mok Park),황규영(Kyu-Young Whang),조완섭(Wan-Sup Cho) 한국정보과학회 1994 정보과학회논문지 Vol.21 No.7

질의 최적화에서 술어(predicate)를 만족하는 객체수(중간 결과수)의 정확한 추정은 질의의 처리 비용을 계산하는데 중요한 요소이다. 본 논문에서는 객체지향 질의에 포함된 클래스가 다른 클래스와의 관계(relationship)에 부분참여(partial participation) 할 가능성이 높음을 밝히고, 이러한 경우를 고려한 중간 결과수 추정기법을 제안한다. 기존의 기법들은 부분참여를 신중하게 고려하지는 않았으며, 이러한 경우에 큰 오차가 발생할 수 있다. 제안된 기법은 부분참여를 고려하기 위하여 기존의 기법보다 세분화된 통계 정보를 사용한다. 본 논문에서는 객체지향 데이타베이스의 특징을 이용하여 이러한 통계 정보를 효율적으로 구하는 방법도 제안한다. Estimating the number of objects satisfying a predicate is an important factor for estimating the cost of a query in query optimization. We first show that an object-oriented query often involves partial participation of classes in a relationship Then, we present a new techniques for estimating the number of objects satisfying a predicate in such a query. Partial participation has not been considered seriously in existing techniques The proposed method uses more detailed statistics to accomodate partial participation We also present an efficient method for obtaining these statistics using the unique properties of the object-oriented databases.

Stochastic VOQL : 시각적 객체 질의어

김정희,조완섭,이석균,황규영,Kim, Jeong-Hee,Cho, Wan-Sup,Lee, Suk-Kyoon,Whang, Kyung-Young 대한전자공학회 2001 電子工學會論文誌-CI (Computer and Information) Vol.38 No.5

객체지향 데이터베이스를 위한 시각적 질의어(visual query language)의 설계에서 복잡한 질의 조건을 간단하고도 직관적으로 표현할 수 있도록 지원하는 것이 중요한 연구과제가 되고 있다. 본 논문에서는 시각적 객체지향 질의어인 VOQL(Visual Object Query Language)을 제안한다. VOQL은 그래프와 밴다이어그램(Venn Diagram)을 결합한 시각적 표현 기법을 사용하여 객체지향 데이터베이스의 스키마(schema)와 질의어를 하나의 통일된 시각적 표시법으로 표현하며, 객체지향 질의어에 포함된 한정된 경로식(quantified path expression), 집합 연산자, 상속 등의 객체지향 특성도 간단한 시각적 표시법을 이용하여 표현한다. VOQL의 가장 큰 특징은 기존의 시각적 개체지향 질의어들에 비하여 간단하고 직관적인 구문과 의미를 가지며, 뛰어난 질의 표현력을 가진다는 점이다. Expressing complex query conditions in a concise and intuitive way has been a challenge in the design of visual object-oriented query languages. We propose a visual query language called VOQL (Visual Object oriented Query Language) for object oriented databases. By employing the visual notation of graph and Venn diagram, the database schema and the advanced features of object oriented queries such as multi-valued path expressions and quantifiers can be represented in a simple way. VOQL has such good features as simple and intuitive syntax, well-defined semantics, and excellent expressive power of object-oriented queries compared with previous visual object-oriented query languages.

KAIST Object Storage System with Variable - Length Attributes (KAOSS - VLA) : 가변길이 속성을 지원하는 관계형 데이타 저장 시스템

문양세(Yang-Sae Moon),조완섭(Wan-Sup Cho),김상욱(Sang-Wook Kim),김원영(Won-Young Kim),이영구(Young-Koo Lee),황규영(Kyu-Young Whang) 한국정보과학회 1994 한국정보과학회 학술발표논문집 Vol.21 No.2A

데이타베이스 관리 시스템은 데이타를 저장하고 관리하는 부분, 동시성 제어 및 회복 기능을 지원하는 부분, 질의어를 처리하는 부분, 질의어를 최적화하는 부분등으로 구성되어 있다. 저장 시스템은 데이타를 저장하고 관리하는 부분으로 데이타베이스의 엔진에 해당되어 성능에 직접적인 영향을 주는 중요한 역할을 한다. 본 논문에서는 UNLX 상에서 단일 사용자용 저장 시스템인 KAIST Object Storage System with Variable-Length Attributes(KAOSS-VLA)를 설계하고 구현하였다. 구현한 저장 시스템은 디스크를 관리하는 디스크 관리자, 버퍼 풀을 관리하는 버퍼 관리자, 데이타 페이지와 튜플을 관리하는 튜플 관리자, B+-트리 색인을 관리하는 B+-트리 관리자, 그리고 편리한 인터페이스를 제공하는 스캔 관라자의 다섯부분으로 구성되어 있다. 본 논문에서 구현한 저장 시스템은 첫째, 가변길이 속성을 허용함으로써 가변길이 튜플과 키를 지원하고, 둘째, 중복키와 다중키를 지원하며, 셋째, 두가지의 다른 스캔 인터페이스를 제공한다.