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.