Subsumption-stratified datalog

AbstractIn this paper a new class of Datalog programs with negation called subsumption-stratified Datalog is presented. None of the conditions used to describe subsumption-stratified Datalog programs depend on a particular extensional database (EDB). So a check may be done at compile time rather than at run time. In fact a syntactical subclass with the same expressive power is given. The main idea of subsumption-stratified Datalog is to disregard derivations if they are not needed, i.e. if they will always yield false or if they are subsumed by others yielding the same result. The subsumption-model is evaluated as the semantics of subsumption-stratified Datalog. It is shown to be equivalent to some other approaches especially the well-founded and the stable model semantics. Furthermore it is shown that the expressive power of subsumption-stratified Datalog is strictly higher than the expressive power of stratified Datalog, but strictly lower than the expressive power of fixpoint logic