Bottom-up Evaluation of Datalog with Negation  

作　　者：施伯乐 周傲英 

机构地区：[1]DepartmentofComputerScience,FudanUniversity,Shanghai200433 [2]DepartmentofComputerScience,FudanUniversit

出　　处：《Journal of Computer Science & Technology》1994年第3期229-244,共16页计算机科学技术学报（英文版）

摘　　要：Declarative semantics gives the meaning of a logic program in terms of properties,while the procedural semantics gives the meaning in terms of the execution or evalua-tion of the program. From the database point of view, the procedural semantics of theprogram is equally important. This paper focuses on the study of the bottom-up eval-uation of the WFM semantics of datalog- programs. To compute the WFM, first, thestability transformation is revisited, and a new operator Op and its fixpoint are defined.Based on this, a fixpoint semantics, called oscillating fixpoint model semantics, is de-fined. Then, it is shown that for any datalog program the oscillating fixpoint model isidentical to its WFM. So, the oscillating fixpoint model can be viewed as an alternative(constructive) definition of WFM. The underlying operation (or transformation) forreaching the oscillating fixpoint provides a potential of bottom-up evaluation. For thesake of computational feasibility, the strongly range-restricted program is considered,and an algorithm used to compute the oscillating fixpoint is described.Declarative semantics gives the meaning of a logic program in terms of properties,while the procedural semantics gives the meaning in terms of the execution or evalua-tion of the program. From the database point of view, the procedural semantics of theprogram is equally important. This paper focuses on the study of the bottom-up eval-uation of the WFM semantics of datalog- programs. To compute the WFM, first, thestability transformation is revisited, and a new operator Op and its fixpoint are defined.Based on this, a fixpoint semantics, called oscillating fixpoint model semantics, is de-fined. Then, it is shown that for any datalog program the oscillating fixpoint model isidentical to its WFM. So, the oscillating fixpoint model can be viewed as an alternative(constructive) definition of WFM. The underlying operation (or transformation) forreaching the oscillating fixpoint provides a potential of bottom-up evaluation. For thesake of computational feasibility, the strongly range-restricted program is considered,and an algorithm used to compute the oscillating fixpoint is described.

关 键 词：Deductive database logic programming NEGATION bottom-up evaluation 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]