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 vi...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.
