In this paper,we deal with the problem of verifying local stratifiability of logic programs and databases presented by Przymusinski.Necessary and sufficient conditions for the local stratifiability of logic programs a...In this paper,we deal with the problem of verifying local stratifiability of logic programs and databases presented by Przymusinski.Necessary and sufficient conditions for the local stratifiability of logic programs are presented and algorithms for performing the verification are developed.Finally,we prove that a database DB containing clauses with disjunctive consequents can be easily converted into a logic program P such that DB is locally stratified iff P is locally stratified.展开更多
Since extending DATALOG to a general-purpose programming language seems very difficult, many projects have embedded a DATALOG-based query language into a procedural host language, such as CORAL, Glue-Nail, etc.Althoug...Since extending DATALOG to a general-purpose programming language seems very difficult, many projects have embedded a DATALOG-based query language into a procedural host language, such as CORAL, Glue-Nail, etc.Although DATALOG can be considered as function-free PROLOG, they are very different in many aspects. For instance, DATALOG is declarative while PROLOG isn't, DATALoG takes 'a-set-at-atime' mode of evaluation but PROLOG takes 'a-tuple-at-a-time' one, DATALOG is only a query language whereas PROLOG is a general-purpose programming language. It is thought that integrating DATALOG with PROLOG may take their advantages. KBASEP is such a language. It uses KBASE as the query language and PROLOG as its procedural host language, where KBASE is an extension of DATALOG with negation and function. This paper introduces the integration techniques used in KBASE-P system.展开更多
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.展开更多
基金Supported by the National Natural Science Foundation of China.
文摘In this paper,we deal with the problem of verifying local stratifiability of logic programs and databases presented by Przymusinski.Necessary and sufficient conditions for the local stratifiability of logic programs are presented and algorithms for performing the verification are developed.Finally,we prove that a database DB containing clauses with disjunctive consequents can be easily converted into a logic program P such that DB is locally stratified iff P is locally stratified.
文摘Since extending DATALOG to a general-purpose programming language seems very difficult, many projects have embedded a DATALOG-based query language into a procedural host language, such as CORAL, Glue-Nail, etc.Although DATALOG can be considered as function-free PROLOG, they are very different in many aspects. For instance, DATALOG is declarative while PROLOG isn't, DATALoG takes 'a-set-at-atime' mode of evaluation but PROLOG takes 'a-tuple-at-a-time' one, DATALOG is only a query language whereas PROLOG is a general-purpose programming language. It is thought that integrating DATALOG with PROLOG may take their advantages. KBASEP is such a language. It uses KBASE as the query language and PROLOG as its procedural host language, where KBASE is an extension of DATALOG with negation and function. This paper introduces the integration techniques used in KBASE-P system.
文摘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.