논리적 분할에 기초한 순환 질의의 병렬 처리 (pp.973-983) = Parallel Processing of Recursive Queries based on Logical Partition

국문 초록 (Abstract)

연역 데이타베이스에서 순환 규칙은 기존 관계 데이타베이스가 표현할 수 없었던 순환적인 추론적 사실을 표현할 수 있다. 따라서 연역 데이타베이스에서 순환 규칙은 중요한 역할을 하고 순환 규칙의 효율적인 처리 방안이 필요한데, 처리해야 할 데이타는 많아진 반면 처리 시간의 신속성이 중요시되는 현실의 요구에 부합하기 위하여 다중 프로세서(multiprocessor)환경하에서의 병렬 처리 기법이 바람직하다.
본 논문에서는 순차적 방식의 magic set 알고리즘을 효율적으로 병렬화시키는 방법을 제시하였다. magic set 의 요소는 서로 연결되어 있다는 특성을 고려하여 magic set을 논리적으로 분할한다면 프로세서 사이의 통신 비용을 절감할 수 있을 뿐만 아니라 각 프로세서가 처리해야 하는 부하도 균형적으로 유지할 수 있다. 이에 대한 타당성은 분석적 모델을 통하여 알아보았다.

다국어 초록 (Multilingual Abstract)

Because the recursive rules of a deductive databases can represent the recursive inferencing facts that the relational system can not represent, the recursive rules play important roles in deductive databases. Thus, efficient processing of the recursive rules is necessary. On the other hand, real world requires a large volume of data to be processed quickly. Consequently, it is desirable to use parallel processing techniques to process recursive rules on the multiprocessor environments.
In this paper, an efficent parallel algorithm of magic sets is proposed. If we partition the magic sets logically seeing through the property which magic sets'elements are relevant one antother, we not only reduce communication cost among processors, but also assign balanced load to each processor. The validity of this algorothm is analyzed by a simplified analytical model.

목차 (Table of Contents)

• 요약
• ABSTRACT
• 1. 서론
• 2. 연역 데이타베이스
• 3. 기존 병렬 처리 알고리즘
• 4. 효율적인 병렬 처리 알고리즘의 설계
• 5. 결론
• 참고문헌
• 저자소개