소 결합 환경에서 순환 질의 처리를 위한 형판 연산기법

황규영(Kyu-Young Whang),홍기형(Ki-Hyung Hong),이윤준(Yoon-Joon Lee) 한국정보과학회 1991 정보과학회논문지 Vol.18 No.3

본 논문에서는 소 결합 환경하에서 순환 질의의 한 부류를 효율적으로 처리하기 위한 template 처리 기법을 제안하고, 그 정당성을 증명하였다. Template 처리 기법은 주 기억장치내의 릴레이션과 이차 기억장치에 저장되어 있는 릴레이션 사이의 비용이 비싼 결합 연산(join)을 완전히 제거함으로써 순환 질의를 효과적으로 처리한다. 본 기법으로 처리할 수 있는 질의의 부류는 Whang과 Navathe가 제안한 확장된 논리합 정규형(extended disjunctive normal form)으로 표현하였을 때, 하나의 비환형 트리(nonlooped-tree)와 하나의 단일환형 트리(single looped tree)로 표현된다. We present the template evaluation technique for efficient processing of a class of recursive logic queries in a loosely-coupled environment. Using this technique, queries are evaluated efficiently by avoiding costly joins between an in-memory relation residing in main memory and a database relation residing in the secondary storage. The queries in this class are those represented by one nonlooped tree and one single-looped tree (indicating linear recursion) in the extended disjunction normal form proposed by Whang and Navathe. We also prove the correctness of the template evaluation technique.

오디세우스 / IR : 정보 검색 기능과 밀결합된 고성능 객체 관계형 DBMS

황규영(Kyu-Young Whang),이민재(Min-Jae Lee),이재길(Jae-Gil Lee),김민수(Min-Soo Kim),한욱신(Wook-Shin Han) 한국정보과학회 2005 정보과학회 컴퓨팅의 실제 논문지 Vol.11 No.3

상용 ORDBMS 개발사들은 자신의 DBMS에 사용자 정의 타입과 사용자 정의 함수를 추가하는 확장 방법을 제공하고 있다. 이러한 확장은 상위 레벨 인터페이스를 사용하여 이루어진다. 이러한 기법을 소결합(loose-coupling)이라 부른다. 소결합의 장점은 구현하기 쉽다는 것이나, 높은 성능이 요구되는 대용량 데이타베이스에서 새로운 데이타 타입과 연산을 추가하기에는 적합하지 않다. 본 논문에서는, 이러한 요구 조건을 충족하기 위해 밀결합(tight-coupling)이라는 개념을 사용하는 것을 제안한다. 밀결합에서 새로운 데이타 타입과 연산은 DBMS의 엔진 내부에 통합된다. 따라서, 새로운 데이타 타입과 연산이 높은 성능으로 일관성 있게 제공된다. 이 밀결합 아키텍처는 정보 검색 기능과 공간 데이타베이스 기능을 한국과학기술원/첨단정보기술연구센터에서 개발 중인 객체 관계형 DBMS 오디세우스/IR에 통합하기 위해 사용되고 있다. 본 논문에서는, 오디세우스/IR을 소개하고 오디세우스/IR과 밀결합된 정보 검색 기능(미국 특허 등록)을 설명한다. 다음으로, 오디세우스/IR을 사용한 단일 시스템(non-parallel) 설정에서 2,000만건의 웹 페이지를 관리할 수 있는 웹 검색 엔진을 보인다. Conventional ORDBMS vendors provide extension mechanisms for adding user-defined types and functions to their own DBMSs. Here, the extension mechanisms are implemented using a high-level interface. We call this technique loose-coupling. The advantage of loose-coupling is that it is easy to implement. However, it is not preferable for implementing new data types and operations in large databases when high performance is required. In this paper, we propose to use the notion of tight-coupling to satisfy this requirement. In tight-coupling, new data types and operations are integrated into the core of the DBMS engine. Thus, they are supported in a consistent manner with high performance. This tight-coupling architecture is being used to incorporate information retrieval(IR) features and spatial database features into the Odysseus/IR ORDBMS that has been under development at KAIST/AITrc. In this paper, we introduce Odysseus/IR and explain its tightly-coupled IR features (U.S. patented). We then demonstrate a web search engine that is capable of managing 20 million web pages in a non-parallel configuration using Odysseus/IR.

GeoStore 국가 GIS 객체 지향 공간 객체 저장 시스템

황규영(Kyu-Young Whang),이기준(Ki-Joune Li),홍의경(Eui-Kyeong Hong),박영철(Young Chul Park) 한국정보과학회 데이터베이스 소사이어티 1998 데이타베이스 연구 Vol.13 No.4

Geographic Information Systems(GISs) are getting ever important nowadays The core of the GIS is the spatial object storage system In this paper we introduce GeoStore a spatial object storage system being developed as part of the national GIS project. GeoStore is a multi-purpose storage system that provides fast performance and that has rich functionalities for various GIS applications GeoStore has the following characteristics (1) it stores both spatial data and aspatial data of geographical objects in an integrated manner (2) it uses the multilevel grid file(MLGF) a fast spatial access method as the index (3) it provides an object-oriented modeling capability at the storage system level (4) it provides primitive spatial classes and spatial operators (5) it produces and stores topological information for fast spatial query processing and (6) it supports SDTS, a spatial data transfer standard, to interchange information with other GISs

관계 데이타베이스에서의 인덱스 선정

황규영(Kyu Young Whang) 한국정보과학회 1988 정보과학회논문지 Vol.15 No.3

본 논문에서는 관계 데이타베이스를 위한 인덱스 선택 알고리즘을 제시하였다. 문제점은 트랜잭션 처리를 위한 평균비용을 최소로 하는 인덱스의 최적집합을 찾는 것이다. 여기서 비용은 입출력 회수에 의해 측정된다. 제시된 알고리즘은 드롭(DROP) 휴리스틱이라고 불리는 방법을 사용한다. 알고리즘의 최적도를 결정하기 위한 광범위한 시험에서도 이 알고리즘은 모든 경우에 최적해를 찾았고 알고리즘의 시간 복잡도는 가능한 모든 대안을 전부 탐색하는 방법에 비해서 현저한 향상을 보여 주었다. 더욱이 본 논문은 이 알고리즘을 클러스터링 성질(릴레이션이 정렬된 순서로 저장된다)을 포함하도록 확장하고 또 다중화일 데이타베이스의 응용을 위해서도 확장하였다. An index selection algorithm for relational databases is presented. The problem concerns finding an optimal set of indexes that minimizes the average cost of processing transactions. This cost is measured in terms of the number of I/O accesses. The algorithm presented employs a heuristic approach called DROP heuristic. In an extensive test to determine the optimality of the algorithm, it found optimal solutions in all cases. The time complexity of the algorithm shows a substantial improvement when compared with the approach of exhaustively searching through all possible alternatives. The algorithm is further extended to incorporate the clustering property (the relation is stored in a sorted order) and also is extended for application to multiple-file databases.

Issues in Object-Oriented Database Systems Research

Kyu-Young Whang(황규영) 한국정보과학회 데이터베이스 소사이어티 1991 데이타베이스 연구 Vol.7 No.1

오디세우스/Geo : 지리정보시스템을 위한 객체지향 멀티미디어 DBMS

황규영(Kyu-Young Whang),홍의경(Eui Kyeong Hong),이기준(Ki-Joune Li),이민재(Min-Jae Lee),한욱신(Wook-Shin Han) 한국정보과학회 1999 정보과학회지 Vol.17 No.11

Softlnfra21 : 소프트웨어 기반 및 응용 기술 기획 사업

황규영(Kyu-Young Whang) 한국정보과학회 1999 정보과학회지 Vol.17 No.10

KMEDIA - 2 : 지능형 입출력을 지원하는 PC용 하이퍼미디어 시스템 및 멀티미디어 저작도구

황규영(Kyu-Young Whang),오영환(Yung-Hwan Oh),양현승(Hyun-Seung Yang),한태숙(Tai-Sook Han),최기선(Key-Sun Choi),이흥규(Heung-Kyu Lee),노웅기(Woong-Kee Loh),최환진(Hwan-Jin Choi),고병기(Byong-ki Ko),우균(Gyun Woo),서광준(Kwang-Jun Seo 한국정보과학회 1994 한국정보과학회 학술발표논문집 Vol.21 No.2A

본 논문에서는 PC용 하이퍼미디어 시스템인 KMEDIA-1을 확장하여 지능형 입출력을 지원하는 KMEDIA-2 (KAIST Hyper MEDIA-2)에 대하여 기술한다. 지능형 입출력이란 자연언어 질의를 통한 정보 검색, 음성 명령어 인식 및 음성 합성, 영상 인식 인터페이스를 의미한다. KMEDIA-2는 이외에 멀티미디어 객체 동기화, 스크립트 언어, wavelet 변환을 이용한 정영상 압축 및 복원 기능과 디지탈 동영상을 지원하며, 하부 저장 구조로서 객체지향 저장 시스템인 KAIST-MMDB를 사용하여 하이퍼미디어 정보를 저장한다.

주기억장치 저장시스템에서 트랜잭션 - 일관성을 유지하는 비정지 체크포인팅에 기반한 회복기법의 설계 및 구현

권영식(Young-Sik Kwon),문양세(Yang-Sae Moon),장지웅(Ji-Woong Chang),황규영(Kyu-Young Whang) 한국정보과학회 1998 한국정보과학회 학술발표논문집 Vol.25 No.1B

회복기능은 저장시스템 내에 저장된 데이타베이스를 일관성 있는 상태로 유지해주는 기능이다. 본 논문에서는 주기억장치 저장시스템의 회복기법에서 필요한 기능을 분석하고 설계 시의 고려사항을 도출한다. 다음으로 분석한 기능과 설계 고려사항을 바탕으로 주기억장치 저장시스템에서의 회복기법을 설계하고 구현한다. 본 논문에서는 트랜잭션을 관리하는 트랜잭션 관리자, 주기적으로 주기억장치 데이타베이스를 안전한 기억장치에 저장하는 백업 관리자, 그리고 시스템이 재시작 하는 경우에 데이타베이스의 일관성을 재구성해주는 회복 관리자의 세 부분으로 나누어 회복기법을 설계하고 구현하였다. 본 논문에서 설계하고 구현한 저장 시스템은 다음과 같은 특징을 갖는다. 첫째, 트랜잭션-일관성을 유지하는 데이타베이스를 체크포인트하며, 둘째, 백업 과정과 트랜잭션과의 병렬성을 제공한다. 셋째, 트랜잭션의 수행에 영향을 미치는 회복기능을 최소화하여 높은 성능을 제공한다.

프리픽스 매취 조인을 이용한 XML 문서에 대한 분기 경로 질의 처리

박영호(Young-Ho Park),한욱신(Wook-Shin Han),황규영(Kyu-Young Whang) 한국정보과학회 2005 정보과학회논문지 : 데이타베이스 Vol.32 No.4

본 논문에서는 정보 검색(Information Retrieval, IR) 기술과 새로운 인스턴스 조인 기술을 이용하여 방대하고도 이질적인 XML 문서들에 대한 부분 매취 질의(Partial Match Query)를 처리하는 새로운 방법으로, XIR-Branching을 제안한다. 부분 매취 질의는 경로 표현식에 조상-후손 관계성 (descendent-or-self axis) "//"를 가지는 질의로 정의되며, 선형 경로 표현식(Linear Path Expression, LPE)과 분기 경로 표현식(Branching Path Expression, BPE)으로 구분된다. 일반적 형식의 부분 매취 질의는 분기하는 경로들을 만드는 분기 조건들을 가진다. XIR-Branching의 목적은 이질적인 스키마들을 가진 방대한 문서들에 주어지는 부분 매취 질의를 효과적으로 지원하는 것이다. XIR-Branching은 관계형 테이블을 사용하는 전통적인 스키마-레벨 방법들(XRel, XParent, XIR-Linear[21])에 그 기초를 두고, 역 인덱스(inverted index) 기술과 새롭게 소개하는 인스턴스-레벨 조인 기술인 프리픽스 매취 조인(Prefix Match Join)을 사용하여 질의 처리 효율성과 확장성을 향상시킨다. 전자는 LPE를 처리하기 위한 기술로 XIR-Linear[21]에서 사용한 방법이다. 후자는 BPE를 처리하기 위한 기술로 본 논문에서 새롭게 제안하는 기술이며, 전통적인 방법에서 사용하는 포함 관계 조인(containment join) 보다 효과적인 방법으로 결과 노드(result node)를 찾는다. 기존 연구인 XIR-Linear는 역 인덱스를 사용하여 LPE 처리에 우수한 성능을 보이고 있지만, BPE 처리 방법을 다루지 않았다. 그러나, 더욱 구체적이고 일반적인 질의를 위해서는 BPE도 처리할 수 있어야 한다. 본 논문에서는 BPE까지 다룰 수 있는 새로운 방법으로 기존의 XIR-Linear를 확장한 XIR-Branching을 제안한다. 제안하는 방법은 스키마-레벨 방법으로 질의 대상 후보 집합을 크게 줄인 후, 인스턴스-레벨 조인 방법인 프리픽스 매취 조인으로 최종 결과 집합을 효과적으로 구하는 방법이다. XIR-Branching의 우수성을 보이기 위해 기존 BPE 처리 방법인 XRel, XParent와 비교 분석을 수행한다. 마지막으로, 성능 평가를 통하여 XIR-Branching이 기존 방법들에 비해 수십에서 수백배 효과적이고 확장성 또한 뛰어남을 보인다. We propose XIR-Branching, a novel method for processing partial match queries on heterogeneous XML documents using information retrieval(IR) techniques and novel instance join techniques. A partial match query is defined as the one having the descendent-or-self axis "//" in its path expression. In its general form, a partial match query has branch predicates forming branching paths. The objective of XIR-Branching is to efficiently support this type of queries for large-scale documents of heterogeneous schemas. XIR-Branching has its basis on the conventional schema-level methods using relational tables(e.g., XRel, XParent, XIR-Linear[21]) and significantly improves their efficiency and scalability using two techniques: an inverted index technique and a novel prefix match join. The former supports linear path expressions as the method used in XIR-Linear[21]. The latter supports branching path expressions, and allows for finding the result nodes more efficiently than containment joins used in the conventional methods. XIR-Linear shows the efficiency for linear path expressions, but does not handle branching path expressions. However, we have to handle branching path expressions for querying more in detail and general. The paper presents a novel method for handling branching path expressions. XIR-Branching reduces a candidate set for a query as a schema-level method and then, efficiently finds a final result set by using a novel prefix match join as an instance-level method. We compare the efficiency and scalability of XIR-Branching with those of XRel and XParent using XML documents crawled from the Internet. The results show that XIR-Branching is more efficient than both XRel and XParent by several orders of magnitude for linear path expressions, and by several factors for branching path expressions.