Bottom-up evaluation of logic programs has recently attracted much attention in the logic programming and the deductive database field due to a number of advantages such as logical completeness and freedom from non-logical features. However, query evaluation by the bottom-up strategy may be inefficient since it may generate many irrelevant facts to a given query. As an approach to overcoming this drawback, the filtering strategy restricts generation of irrelevant facts by filters based on the bottom-up data flow evaluation. This dissertation defines a generalized filtered bottom-up evaluation formally and formalizes the static filter computation algorithm to give a formal view to static filter and its computation. Based on the formalism, the static filter is extended to stratified programs, in which rules may have negative literals, but which allow no recursive negation. The static filter, however, has its limit since it is computed at compile time using only data-independent bindings. In order to overcome the drawback of the static filtering, a new filtered bottom-up evaluation is provided using a new abstract filter which is computed by abstract interpretation at compile time. The general definition of abstract filters is presented on a general abstract domain not confined on a particular abstract domain. As a specialization, an abstract filter is computed using a new two-phase abstract interpretation. The two-phase abstract interpretation consists of a bottom-up phase followed by a top-down one and provides an approximation of success patterns of clauses relevant to a given query. This framework is specialized by considering the depth k abstraction as abstraction function. For other applications, the two-phase analysis is also applied to improving several top-down evaluation models. From the theoretical point of view, the abstract filter is shown to be at least as powerful as the static filter under some assumptions, and is compared with other related works. We implemented the two-phase abstract analyzer and the filtered bottom-up evaluator and provide experimental results which show performance of the static filter and abstract filter. The proposed approach has some merits in the following senses. The abstract filter does not incur runtime overhead except filter passing while Magic Sets does due to the computation of magic sets during evaluation. Moreover, due to the goal indepence of the bottom-up abstract interpretation, the result of the bottom-up phase can be utilized for any queries to the same program.
논리 프로그램의 상향식 수행은 논리적 완전성(completeness) 및 비논리적 특성이 없다는 점때문에 최근에 논리 프로그래밍과 연역 데이타 베이스 분야에서 많은 관심을 받고있다. 그러나 상향식 수행은 주어진 질의(query)를 답하는데 불필요한 유도(derivation)를 함으로 써 비효율적일 수 있다. 이러한 단점을 극복하기 위한 방법으로써 제안된 필터링 방법은 상향식 데이타 프로우 수행에 기초하여 필터를 이용하여 불필요한 유도 과정을 제한한다. 본 논문에서는 먼저 필터링을 이용한 상향식 수행을 정형화하고 이를 기초로 하여 정적필터와 그 계산 과정을 정형화한다. 또한, 이렇게 계산된 정적 필터가 부정(negation)을 허 용하는 논리 프로그램의 하나의 서브 클래스인 stratified프로그램에 대해서도 적용가능함을 보였다. 그러나, 정적 필터는 컴파일 시간에 data-independent 바인딩만을 이용하여 계산됨 으로 필터링 효과에 근본적인 한계를 갖고있다. 본 논문에서는 정적 필터의 이러한 단점을 보완하기 위해서, 컴파일 시간에 추상 해석(abstract interpretation)을 이용하여 계산하는 새로운 추상 필터(abstract filter)를 제안 한다. 먼저 일반적인 도메인 상에서 추상 필터를 정의하고 이를 구체화하기 위해서 깊이 k 추상 도메인상에서 새로운 추상 해석 방법인 두 페이즈 추상 해석(two-phase abstract interpretation)을 이용하여 추상 필터를 계산한다. 두 페이즈 추상 해석은 상향 페이즈(bottom-up phase)와 이를 따르는 하향 페이즈(top-down phase)로 구성되며 주어진 질의에 관련되는 절(clause)의 성공 패턴에 대한 근사값(approximation)를 제공한다. 두 페이즈 추상 해석은 다른 응용으로 상향식 수행 모델을 개선하는 데도 적용하였다. 이론적인 관점에서, 제안된 추상 필터는 깊이 k인 추상 도메인 상에서 적어도 정적 필터만큼 강력함을 보였고 다른 연구와도 비교하였다. 또한 제안된 방법을 실제 구현하여 정적필터와 추상 필터를 비교하는 실험 결과를 제공하였다. 제안된 방법은 다음과 같은 의미에서 장점을 갖는다. 추상 필터는 수행 중에 필터를 통과하는 부담을 제외하고는 실행 시간 부담이 없다. 또한 두 페이즈 분석에서 상향 페이즈는 프로그램에 대해서 한번만 수행되고 각 질의에 대해서는 상대적으로 계산 비용이 적게드는 하향식 페이즈만 수행하면 된다.
