An Indexing Framework for Improving Data Consistency of Triple Database

Abstract

시맨틱 웹에서의 데이터 양이 증가함에 따라, 대용량의 데이터를 유연한 형식으로 저장하고 시스템 간의 정보 공유를 하는 것은 필수적인 항목이 되었다. 트리플(Triple)은 시맨틱 웹에서 사용되는 유연한 데이터 표현 방식의 표준으로, 만약 기업이 보유하고 있는 관계 데이터베이스 기반의 컨텐츠 데이터를 트리플 형식으로 표현할 경우, 그 유연성과 활용성 때문에 다양한 목적으로 시맨틱 웹에서 데이터를 활용할 수 있다. 본 논문에서는 트리플을 기반으로 한 트리플 데이터베이스의 신뢰도를 확보하기 위하여, 트리플 데이터베이스를 기업에서 사용하기 위한 필수적인 요소들을 구현하였다. 첫째, 트리플 데이터베이스를 위한 무결성 제약 조건을 제안한다. 무결성 제약 조건은 관계 데이터베이스로부터 추출된 것으로, 정확하게 동일한 의미를 가지고 트리플 데이터베이스에 적용되도록 해석되었다. 또한 정보의 손실 없이 데이터를 트리플로 바꾸어 저장하는 것뿐만 아니라, 저장된 트리플을 빠른 질의 처리 속도와 더불어 유용하게 사용하는 것도 실용성의 측면에서 중요하다. 그러나 현재까지의 트리플 기반 인덱스 연구들은 트리플이 중복되어 색인되거나, 하나의 트리 안에 너무 많은 색인 키를 저장하는 문제를 가지고 있다. 이러한 문제를 해결하기 위하여 둘째로 트리플 데이터베이스를 위한 새로운 인덱스 구조를 제안한다. 새로운 인덱스 구조는 트리플의 중복을 최소화하는 구조로 설계되었으며, 트리플 구성 요소에 기반하여 인덱스 트리를 분리함으로써 보다 빠르고 가벼운 색인 키 검색을 가능하게 한다. 셋째, 트리플 데이터베이스를 위한 새로운 단축 경로 선택(Shortcut Selection) 기법을 제안한다. 단축 경로 선택 기법은 트리플 데이터베이스에서 질의를 수행할 때 가장 많이 발생하는 성능 저하 요인인 자기 조인(Self-Join)을 해결하기 위한 방법이다. 일반적으로 한 번의 질의를 위해 트리플 테이블 전체가 조인에 참가할 경우 막대한 질의 비용이 발생하게 된다. 제안하는 새로운 단축 경로 선택 기법은 조인이 발생하는 질의에 대해 미리 시작점으로부터 끝점까지 이어지는 단축 경로에 해당하는 트리플을 우선적으로 추가하여 조인을 사전에 차단하는 기법으로써, 기존 연구에서 고려하고 있지 않은 트리플 그래프 특성에 기반한 단축 경로 우선 차단과 데이터베이스 갱신을 고려한 갱신 빈도(Update Frequency) 기반의 이득 계산(Benefit Calculation) 모델을 새롭게 설계하였다. 다양한 분야의 데이터를 이용한 질의 시간 측정 등의 실험을 통하여, 본 연구에서 제시한 기법들이 트리플 데이터베이스를 효율적으로 사용하는 데 최신 연구 대비 향상된 성능을 보인다는 것을 검증하였다.

As more data are provided in Semantic Web, processing large amounts of data with flexible format, and interlinking the applications with utilization have become important. In relational databases, a user must acquaint with the schema information to execute certain query on database. Triple is a well-knows flexible data representation format in Semantic Web. If we represent the content in relational database in triple data format, system can utilize the enterprise data with flexibility for various purposes. To guarantee the reliability of triple database, the enforcement of integrity constraints on triple database is required. Integrity constraints are retrieved from the relational database, and translated into triple database with exact same meaning. Triple database can get reliability and consistency by adapting the concept of the enforcement of integrity constraints. Not only representing content by triple data format without the loss of information, but also organizing triples efficiently is important to use triple database practically. However, most existing triple index techniques suffer from data duplication and the problem of large index sizes. In the thesis, we analyze the drawback of existing triple indexing methods from the viewpoint of the reliability and effectiveness of a triple database. We also consider the issues that need to be addressed to build a triple index for the management of relational database-based triple data. As a result, we propose Tridex: a lightweight B+-tree triple index, designed to facilitate efficient processing of triple database. Tridex is beneficial in reduced size of index tree and less data redundancy. In addition, we propose the enhanced shortcut selection methods in triple database. Triples are commonly represented as a directed graph. With a given triple graph, retrieving data by particular paths can be very expensive due to the self-join problem in triple database. To reduce the self-join operations during query execution, we extend the concept of shortcut, a direct path between specific nodes. By adding appropriate shortcuts in triple database, self-join operations in triple database can be reduced. We propose a reduced candidate shortcut selection considering the maintenance of triple database. The experimental evaluations compare our approach with the state-of-the-art approaches and show adequate performance with less building time in terms of effectiveness and efficiency.