| 한글제목(Korean Title) |
동적 규칙 적용 순서에 의한 Semi-Naive 순환 질의 처리 방법 |
| 영문제목(English Title) |
A Semi-Naive Evaluation Technique Based on the Dynamic Rule-Application Order |
| 저자(Author) |
홍기형
이윤준
황규영
Ki-Hyung Hong
Yoon-Joon Lee
Kyu-Young Whang
|
| 원문수록처(Citation) |
VOL 23 NO. 04 PP. 0361 ~ 0376 (1996. 04) |
한글내용
(Korean Abstract) |
본 논문에서는, 새로운 상향식 순환 처리방법으로 규칙의 적용 순서를 실행 시점에 결정하는 동적 규칙 적용 순서에 의한 semi-naive 처리방법을 제안한다. 제안하는 처리방법은 새로운 semi-naive 알고리즘과 실행 시점에 다음에 적용할 규칙을 선택하는 선택전략들로 구성된다. 새로운 semi-naive 알고리즘은 동적 순서로 규칙을 적용하더라도 동일한 계산의 중복이 없고, 새로이 생선된 튜플을 다음의 규칙 적용에서 바로 이용할 수 있다. 본 논문에서는 순환질의 처리에 필요한 전체 규칙의 적용 횟수와 결합연산의 수가 최소가 될 수 있도록 다음에 적용할 규칙을 선택하는 세 가지 선택전략을 개발하였다. 실험적 비교를 통하여 제안하는 동적 규칙 적용 순서에 의한 semi-naive 처리방법이 기존의 순환 처리 방법에 비하여 전체 규칙 적용 횟수와 결합연산 횟수의 측면에서 뛰어난 성능을 보임을 실증하였다.
|
영문내용
(English Abstract) |
In this paper, we propose a new fixed point evaluation technique for recursions, which is based on the dynamic rule-application order. In the proposed technique (or simply DYN), 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. The semi-naive algorithm allows dynamic ordering of rule applications and makes tuples generated by a rule application immediately available in the 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.
|
| 키워드(Keyword) |
|
| 파일첨부 |
PDF 다운로드
|
