Efficient evaluation of recursive queries is an important issue in deductive database systems, since it may often require many costly join operations. In this thesis, we study on processing recursive queries focused on two optimization approaches: minimizing the temporary relations created in the evaluation without causing duplicate computation and maximizing the effect of each rule application. Deductive queries can be represented by graphs, and the evaluation of them starts with identification of strongly connected components (SCCs) in the graphs. Then each SCC can be processed bottomup in a partial order between SCCs. The graphs for recursive queries have at least one non-trivial SCC that has at least one cycle, and we call such a non-trivial SCC the recursion. Two optimization approaches mainly concern the recursive queries that have SCCs with more than one cycle. We call those recursive queries complex recursive queries.
For complex recursive queries, we may have to create many temporary relations in their evaluation. Since creating many temporary relations causes an adverse effect on the performance, we should minimize the number of temporary relations created in the evaluation. In this thesis, we identify the lower bound on the number of temporary relations that are absolutely needed in the evaluation of queries. The evaluation with only the minimum number of temporary relations, however, may involve duplicate computation. We develop a technique to reduce the number of temporary relations so that there is no duplicate computation in the evaluation.
Conventional fixed point evaluation techniques process recursions by applying all rules repeatedly over an initial set of tuples (i.e., a given extensional database instance) until no new tuples are generated, but there is no specific order in which rules are applied. One can speed up the evaluation by applying rules in an appropriate order. In this thesis, we propose a new fixed point evaluation technique, called the dynamically ordered semi-naive evaluation (or simply DYN), in which the next rule to be applied is determined at run time dynamically. DYN consists of a semi-naive algorithm and a set of selection strategies. We develop the semi-naive algorithm so as to allow dynamic ordering of rule applications. It also makes tuples, which is generated by a rule application, immediately available in subsequent rule applications. After each rule application, the selection strategies determine the next rule by considering the syntactic structure of recursion and some information about the intermediate result up to the present. We develop these selection strategies so that the total number of rule applications and joins can be reduced. Through experimental comparisons, we show that DYN outperforms the previous evaluation techniques in terms of the total number of rule applications and joins.
연역 데이타베이스 시스템에서 순환 질의(recursive query)의 효율적 처리는 중요한 문제이다. 본 논문에서는 순환 질의의 효율적 처리를 위한 두 가지 최적화 방법에 대하여 연구한다. 하나는 순환 질의 처리 시에 생성하여야 하는 임시 릴레이션(temporary relation)의 수를 최소화하는 것이고, 다른 하나는 순환 질의 처리시에 반복적으로 일어나는 규칙의 적용 효과를 최대화하는 것이다. 일반적으로 연역 질의(deductive query)는 그래프로 표현할 수 있다. 질의의 처리는 그래프에서 강결합 요소(strongly connected component)들을 찾은 다음, 그래프 상에 정의된 강결합 요소 사이의 부분 순서(partial order)에 따라 각 강결합 요소를 상향 처리(bottom-up) 하는 것이다. 순환 질의를 표현한 그래프에는 사이클(cycle)을 갖는 강결합 요소가 하나 이상 존재하며, 이러한 강결합 요소를 순환(recursion)이라고 한다. 본 논문에서 연구하는 두 가지 최적화 방법은 둘 이상의 사이클이 결합된 강결합 요소를 갖는 복잡한 순환 질의에 대한 최적화 방법이다.
복잡한 순환 질의를 처리하기 위해서는 많은 수의 임시 릴레이션이 필요하다. 일반적으로 많은 수의 임시 릴레이션을 생성하는 것은 질의 처리 성능에 나쁜 영향을 주기때문에 가능하면 질의 처리시 생성하여야 하는 임시 릴레이션의 수를 줄여야 한다. 본 논문에서는 먼저 연역 질의 처리시에 반드시 생성하여야 하는 임시 릴레이션 수의 최소값(lower bound)을 밝힌다. 그런데, 최소 수의 임시 릴레이션만을 생성하여 질의를 처리할 때는 동일한 계산의 중복이 발생할 수 있다. 이러한 중복 계산이 발생하지 않는 범위에서 임시 릴레이션의 수를 감소시키는 기법을 제안한다.
기존의 고정점 계산 방법(fixed point evaluation technique)들은 순환을 처리할때, 주어진 초기 튜플의 집합 (외연 데이타베이스 인스탄스: extensional database instance)을 이용하여 순환에 포함된 모든 규칙(rule)을 새로운 튜플이 생성되지 않을때 까지 반복 적용한다. 그러나 규칙을 어떤 순서로 적용할 것인지는 특별히 주어지지 않았다. 그렇지만 규칙을 적용하는 순서는 순환 처리의 성능에 큰 영향을 미칠 수 있다. 본 논문에서는 새로운 고정점 계산 방법인 동적 순서에 의한 semi-naive 처리방법(dynamically ordered semi-naive evaluation)을 제안한다. 동적 순서에 의한 semi-naive 처리 방법은 규칙의 적용 순서를 실행 시점에 결정한다. 이 방법은 동적 순서를 가능하도록 하는 semi-naive 알고리듬과 실행시에 다음에 적용할 규칙을 결정하는 규칙 선택 전략들로 구성된다. 또한, semi-naive알고리듬은 한 규칙의 적용으로 생성된 새로운 튜플이 다음 규칙의 적용 시에 즉시 이용될 수 있도록 한다. 하나의 규칙을 적용한 다음, 규칙 선택 전략들은 순환의 구조와 그때까지의 중간 결과를 이용하여 다음에 적용할 규칙을 선택한다. 각 규칙 선택 전략은 각 규칙의 적용 효과를 평가하여 최대 효과를 가질 것으로 예상되는 규칙을 다음 규칙으로 선택하므로써, 순환 처리에 필요한 전체 규칙의 적용 수와 전체 조인 수를 감소시킨다. 제안한 동적 순서에의한 처리 방법이 전체 규칙 적용 횟수와 조인 수의 측면에서 기존의 방법에 비하여 우수한 성능을 보인다는 것을 실험을 통하여 입증하였다.
