[논문]규칙 컴파일러를 위한 종료 분석 연구

강병극; 황정희; 신예호; 류근호

규칙 컴파일러를 위한 종료 분석 연구
A Study on Termination Analysis for Rule Compiler 원문보기

정보처리학회논문지. The KIPS transactions. Part D. Part D, v.8D no.6, 2001년, pp.823 - 834

강병극 (충북대학교 대학원 전자계산학과) , 황정희 (충북대학교 대학원 전자계산학과) , 신예호 (충북대학교 대학원 전자계산학과) , 류근호

초록
AI-Helper

능동 데이터베이스에서의 규칙(rule)은 트리거하는 사건이 감지되면 자동으로 규칙을 트리거하여 데이터베이스의 상태변화에 대응하는 조치를 자동으로 수행한다. 이러한 능동 규칙은 자신을 포함한 서로 다른 규칙을 트리거 할 수 있으므로 종료하지 못하고 연속적으로 실행될 가능성이 있다. 이와 같은 문제는 규칙의 종료 분석을 통해 차단할 수 있으며 규칙의 종료 분석은 규칙의 컴파일 시간에 수행하는 것이 가장 효과적이다. 따라서 이 논문에서는 규칙 종료분석기를 내장한 규칙 컴파일러를 설계하고 그 수행 모델 및 알고리즘을 제안한다. 아울러 제안 모델의 핵심이라 할 수 있는 규칙 종료 분석 알고리즘의 정형화를 통해 제안 모델의 완전성을 검증한다.

Abstract ▼ AI-Helper

In the active databases, whenever an event occurs, active rules with the matching event specifications are triggered automatically, its action will be executed. Because these rules may in turn trigger other rules including themselves, the set of rules may be executing each other indefinitely. These problem can be solved by rule termination analysis, and it is efficient for the rule termination to execute in compile time of rule. In this paper we not only design rule compiler with rule termination analyzer, but also propose its execution model and algorithm. The completeness of proposed model is verified by algorithm formalization of rule termination analysis.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

. 이 논문에서는 규칙 컴파일러를 위한 종료 분석기를 제 시하여, 능동 데이터 베이스의 핵 십 요소인 능동 규칙 의 종료 보장을 위한 규칙의 저장, 관리 그리고 정확한 종료 분석 방법을 포함하는 컴파일 과정을 제시하였디..
능동 데이터베이스에서의 능동 규칙은 자신을 포함한 서로 다른 규칙을 트리거할 수 있다는 특징이 있고 그로 인해 무한하게 실행될 가능성이 있다. 그러므로 규칙 실행의 비종료 문제를 헤결하기 위해 이 논문에서는 규칙의 종료 분석을 수행할 수 있는 기능을 네장한 규칙 컴파일러를 설 계하고 이 규칙 킴파일러의 수행 모델 및 알고리즘을 제안 하였다. 아을러 알고리즘의 정형화를 통해 제안 모델의 완 전성을 검증하였다.

가설 설정

위에 제시된 알고리즘에 의해 (그림 6)의 그래프를 이용하여 종료분석을 하기 위한 가정으로, 규칙 r2-b는 or 연산 자에 의한 복합사건이고 규칙의 우선순위가 rl-a, r2-b, r3-a의 순서로 실행된다고 할 띠], 규칙의 실행은 우선순위에 의해 rl-a가 먼저 실행되고 그의 조치 실행전에 r2-b가 실행되고 rl-a의 조치실행 완료와 r3-a가 실행되는 과정을 통해 사이클이 형성된다. 2L러나 사이클 형성의 규칙간에 비활성화 관계의 간선(rl-a, r2-b)이 존재하며, 이것은 r2-b 의 조건값이 거짓이 되어 더 이상 실행이 불가능한 규칙관계를 의미하므로 이러한 규칙 관계를 포함하고 있는 사이 클은 제거할 수 있고 종료를 보장한다.

제안 방법

그러므로 (그림 7)의 알고리즘에 의해 그래프에 존재하는 사이클을 제거하여 종료분석을 수행한다. 1차 분석에서는 복합사건의 실행여부를 고려하여 사이클을 제거하고 2차 분석에서는 사이클을 형성하는 규칙간에 서로 다른 규칙을 비활성화 시키는 관계가 존재하는지를 고려하고 사이클을 제거하여 종료 분석한다.
규칙 컴파일러는 올바르게 정의된 규칙 구문을 규칙 베이스에 저장할 수 있는 각 요소의 규칙 정보 형태와 구문 트리를 형성하며 규칙 집합의 종료 여부를 결정하기 위한 종료 분석을 수행한다. 그리고 규칙 집합의 종료가 결정되면 구문 분석의 결과로써 형성된 규칙의 각 요소 즉, 규칙의 사건, 조건, 조치 절에 대한 실행 계획도 함께 저장되어 관리된다.
[19]에서는 트리거 그래프와 활성화 그래프를 이용하였 고 [II]에서는 트리거 그래프와 활성화 3래프 그리고 비활성화 그래프를 이용하였다. 그러나 이 논문에서는, 전자의 규칙 실행 가능성만을 표현하여 종료 결정이 명 료하지 않은 문제점과 후자의 규칙 관계 정보를 결합 해야 하는 복잡성을 개선한 트리거 그래프와 비활성화 결함ri 래프를 사용하여 빠른 분석 결정을 유도한다.
그러나 기존의 연구에서는 단순한 규칙언어를 사용하는 규칙에 대해서만 종료 분석의 수행 방법을 제시하였을 뿐 사건절에 명세되는 다양한 요소 즉, 복합사건과 규칙 실행 시점을 나타내는 before, after[7, 8]를 고려하고 있지 않다. 그러므로 이 논문에서는 이러한 기존의 총료 분석 방법의 문제점을 개선하여 규칙의 실행의미롤 반영한 종료 분석 방법의 충료 분석기를 제시하고, 이를 위해 기존의 트리거 그레프를 변형한다. 아울러 규칙의 조건설을 이용하여 형성 되는 비활성화 그레프를 결합함으로써 분석 과정의 복잡성 을 단순화시키며, 이 분석 방범에 의한 분석기를 내장한 규 칙 컴파일러 구조를 세안한다.
이와 같은 정적 규칙 종료 분석을 수행하기 위해서는 규칙 컴파일러가 능동규칙을 컴파일하는 과정에서 규치 의 종료 분석을 수행할 수 있는 기능을 내장해야 한다. 따라서 이 논문에서는 규칙 종료 분석이 가능한 규칙 컴파일러에 대한 연구의 일환으로 규칙 종료분석기를 내장한 규칙 컴파일러를 설계하고 그 수행 모델 및 알고리즘을- 제안한디..
그러므로 규칙간에 형성되는 비활성화 관 계 [15]는 규칙 종료 분석에 정확성을 제공하는 요소가 된다. 따라서 이 논문에서는 기존의 트리거 si래프에 비활성 화 관계를 나타내는 비활성화 그래프를 걸합하여 종료 분 석한다- 비활성화 관계의 규칙은 다음의 조건에 의해 그래 프에 표현된다.
이 논문의 종료 분석기는 기존의 분석방법에서의 문제점 인 분석 대상의 규칙범위를 북합사건을 고려함으로써 확장 하였고 실행 시짐을 의미하는 before, after 규칙의 특성을 반영함으로써 분석 결과에 정확성을 기할 수 있었다. 또한 효율적인 분석과정을 위해 기존의 트리거 그래프 변형 및 비활성화 그래프를 결합하여 규칙의 실행관계를 쉽게 식별 할 수 있도록 하였고, 쪈속적으로 실행 가능한 사이클 분석을 간결하게 할 수 있도룩 하였다.
사용자에 의해 규칙이 정의되면 규칙의 종료 분석을 위해 규칙베이스에 있는 기존의 규칙중에서 정의된 규칙과 같은 테이블을 목표로 하는 규칙들에 대한 정보를 가지고 종료 분석을 하게 된다. 종료분석에 사용되는 정보에는 사 건 명세, 조건 명서】, 조치 명세, 트리거하는 관계를 표현하는 트리 거 규칙 (TR: Triggered Rule), 비 활성화 관계를 나타내는 비 활성 화 규칙 (DR : Deactivated Rule), 활성화 관계를 나타내는 활성화 규칙(AR : Activated Rule), 규칙 적용 에 관계된 목표 테이블(TT: Target Table), 규칙 실행 시 점을 표현하는 BefoEEE)와 After(AF).
그러므로 이 논문에서는 이러한 기존의 총료 분석 방법의 문제점을 개선하여 규칙의 실행의미롤 반영한 종료 분석 방법의 충료 분석기를 제시하고, 이를 위해 기존의 트리거 그레프를 변형한다. 아울러 규칙의 조건설을 이용하여 형성 되는 비활성화 그레프를 결합함으로써 분석 과정의 복잡성 을 단순화시키며, 이 분석 방범에 의한 분석기를 내장한 규 칙 컴파일러 구조를 세안한다.
. 아울러 제안 모델의 핵심이라 할 수 있는 규칙 종료 분석 알고리즘의 정형화를 통해 제안 모델의 완전성을 검증한다.
앞에서 규칙의 실행의미를 고려하고 규칙간의 트리거 관 계와 비활성화 관계의 결합 그래프를 이용하는 종료 분석 하는 방법을 제시하였다. 이 장에서는 규칙 종료분석 결과 의 정확성을 입증하기 위해 앞에서 제시한 종료 분석 방법에 대한 개념을 정의하여 증명한다.
규칙 컴파일러는 규칙 언어로 정의된 능동 규칙을 실행 가능한 규칙으로 컴파일해 주는 규칙 처리기의 일부로서, 규칙 집합의 종료 여부를 분석하는 종료 분석기를 핵심 요 소로 한다. 이 분석기는 그래프 형성과 사이클 분석의 2단 계로 구성되벼, 입력된 규칙 집합이 실제로 실행되었을 때 무한하게 반복적으로 실행되지 않고 종료할 수 있는가를 분석하고 정의된 규칙의 올바른 수행 여부를 예측, 수정하는 최적화 과정을 수행하도록 하였다. 그러므로 규치 컴파 일러를 거친 규칙 집합은 종료를 보장할 수 있다.
사용자에 의해 규칙이 정의되면 규칙의 종료 분석을 위해 규칙베이스에 있는 기존의 규칙중에서 정의된 규칙과 같은 테이블을 목표로 하는 규칙들에 대한 정보를 가지고 종료 분석을 하게 된다. 종료분석에 사용되는 정보에는 사 건 명세, 조건 명서】, 조치 명세, 트리거하는 관계를 표현하는 트리 거 규칙 (TR: Triggered Rule), 비 활성화 관계를 나타내는 비 활성 화 규칙 (DR : Deactivated Rule), 활성화 관계를 나타내는 활성화 규칙(AR : Activated Rule), 규칙 적용 에 관계된 목표 테이블(TT: Target Table), 규칙 실행 시 점을 표현하는 BefoEEE)와 After(AF). 기본사건(PE : Primitive event)과 복합사건(CE : Compositive event)를 구별 하는 사건의 형태 (Event Type)가 있다.

성능/효과

1, 2차의 분석과정을 마친 결과로써 규칙들의 관계를 표 현한 그래프에 사이클이 존재하지 않는다면 규치집합은 종 료를 보장한다고 결정할 수 있다. (그림 8)은 규칙 종료 분석을 수행하는 알고리즘이다.
and 연산자에 의한 복합사건의 규칙 rre 잠정적으로 트리 거하는 규칙관계 TR(n, 盘, TR(m, r, ) 관계에서 발생하는 사건이 규칙의 사건절에 명세되어 있는 모든 사건과 일치 해야 규칙 明가 트리거 가능하다는 것을 의미하고, or 연산 자에 외한 복합사건일 때는 규칙 占에 명세되어 있는 사건 중 어느 히-나만 TR(h, rj), TRh, rj) 관계에서 발생하면 트 리거 될 수 있다는 것을 말한다.
전파 알고리즘은 입 릭으로 질의 (query)와 수정 (modification)을 받 아 insert, delete, update의 연산자를 결과로 출력한다. 그리고 이러한 결과를 이용한 종료 분석에서는 활성화 그레프 에 있는 두 규칙의 조치와 王건을 전파 알고리즘에 적용하여 결과로써 insert, update operation이 나오면 활성화 할 수 있고, delete operation 또는 아무런 operation도 출력되 지 않으면 이 규치 관계의 간선은 그래프에 포함되지 않는 다는 결정을 한다.
그러므로 규칙 실행의 비종료 문제를 헤결하기 위해 이 논문에서는 규칙의 종료 분석을 수행할 수 있는 기능을 네장한 규칙 컴파일러를 설 계하고 이 규칙 킴파일러의 수행 모델 및 알고리즘을 제안 하였다. 아을러 알고리즘의 정형화를 통해 제안 모델의 완 전성을 검증하였다.
이 논문의 종료 분석기는 기존의 분석방법에서의 문제점 인 분석 대상의 규칙범위를 북합사건을 고려함으로써 확장 하였고 실행 시짐을 의미하는 before, after 규칙의 특성을 반영함으로써 분석 결과에 정확성을 기할 수 있었다. 또한 효율적인 분석과정을 위해 기존의 트리거 그래프 변형 및 비활성화 그래프를 결합하여 규칙의 실행관계를 쉽게 식별 할 수 있도록 하였고, 쪈속적으로 실행 가능한 사이클 분석을 간결하게 할 수 있도룩 하였다.

후속연구

향후 연구방향으로는 이 논문에서 제안한 종료 분석기를 내장한 규칙 컴파일러를 구현하여 늠동 데이터베이스 시스템의 응용 분야에 적용 및 활용할 계획이디..

참고문헌 (19)

Jeong-Scok Park, Ye Ho Shin, Kwang Woo Nam, Keun Ho Ryu, 'Incremental Condition Evaluation for Active Temporal Rules,' Jurnal of KISS(B), Vol.26, No.4, April, pp.462-472, 1999
C. Zaniold, S. Ceri, C. Faloutsos, R. T. Snodgrass, V. S. Subrahmanian, R. Zicari, 'Design Principles for Active Rules,' Chapter 4, Advacnced Database Systems, Morgan Kaufman Pub, 1997
A. Vaduva, S. Gatziu, Klaus R. Dittrich, 'Investigating Termination in Active Database Systems with Expressive Rule Languages,' RIDS, pp.149-164, 1997
Baralis E., Ceri S., Paraboschi S ; 'Run-Time Detection of Non-Terminating Active Rule System,' Proc. of the 4th Intl. Conf. on Deductive and Object-Oriented Databases, DOOD'95, Singapore, December, 1995
Baralis E., Ceri S., Paraboschi S ; 'Improved Rule Analysis by Means of Triggering and Activation Graphs,' Proc. of 2nd intl. Workshop on Rules in Database Systems, RIDS'95, Athens, Greece, September, 1995
S. Ceri, J. Widom. 'Application of Active Databases,' Active Database Systems-Triggers and Rules for Advanced Databases Processing, Morgan Kaufmann pub, 1996
Mattos, Nelson M., An Overview of the SQL3 Standard, Database Technology Institute IBM-Santa Teresa Lab., Jul. 1996
ANSVISO/lEC International Standard (IS), Database Language SQL-Part 2 : Foundation (SQL/Foundation), ISO/IEC 9075-2 : 1999 (E), September, 1999
Ye Ho Shin, Jeong Hee Hwang, Keun Ho Ryu, 'Termination Analyzer including Rule Execution Semantics,' 정보처리학회논문지D, 제8-D권 제5호, pp.513-522
S. Yeung, T. Wang LING 'Unrolling Cycle to Decide Trigger Termination,' Proc 25th VLDB Conf. Edinburgh, pp.483-493, 1999
D. Montesi, M, Bagnato, C. Dallera. 'Termination Analysis in Active Database,' Database Engineering and Applications, 1999.IDEAS'99 International Symposium Proceedings, pp.288-297. 1999
E. Baralis, S. Ceri and S. Paraboschi, 'Modularization Techniques for Active Rules Design,' ACM Trasaction on Database Systems, pp.1-29, March, 1996

상세보기
K. Baralis and J. Widom, 'An Algebric approach to rule analysis in expert Database Systems,' Proc 20th VLDB Con, Santiago, Chile, September, 1994
Sc Man O, 'Introduction of Compiler,' Jungiksa pub, 1994
J. Bailey, L. Crnogorac, K. Ramamohanarao, H. Sondergaard. 'Abstract Inter - pretation of Active Rules and Its Use in Termination Analysis,' ICD'97, Leeture Notes in Computer Science, 99. pp.199-202, 1997
A. Aiken, J. M. Hellerstein, 'Behavior of database production rules : Termination, Confluence, and Observable determinism,' In Proceeding of the ACM SIGMOD conf. pp.59-68, San Diego, California, June, 1992
A. Aiken, J. M. Hellerstein, J. Widom, 'Static Analysis Techniques for Predicting the Behavior of Active Database Rules,' ACM Transaction on Database System, Vol.20, No.1, pp.3-41, March, 1995

상세보기
S. Ceri and J. Widom, 'Deriving Production Rules for Constraint Maintenance. In Dennis McLeod, Ron SacksDavid, and Hans Schek,' editors, Proc. Sixteenth Int'l Conf. on Very Large Data Bases, pp.566-577, Brisbane, Australia, August, 1990
E. Baralis. 'Rule Analysis,' Chapter 3, Active Rules in Database Systems, Springer-Verlag pub, 1999

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증