The expressive power of stratified logic programs with value invention

The expressive power of the family wILOG((inverted left) perpendicular)) of relational query languages is investigated. The languages are rule based, with value invention and stratified negation. The semantics for value inven tion is based on Skolem functor terms. We study a hierarchy of languages ba sed on the number of strata allowed in programs. We first show that, in pre sence of value invention, the class of stratified programs made of two stra ta has the expressive power of the whole family, thus expressing the comput able queries. We then show that the language wILOG(not equal) of programs w ith nonequality and without negation expresses the monotone computable quer ies, and that the language wILOG(1/2,) (inverted left perpedicular) of semi positive programs expresses the semimonotone computable queries. (C) 1998 A cademic Press.