Decidability and expressiveness aspects of logic queries
Oded Shmueli · 1987
This paper addresses some basic problems regarding logic programming based queries over relational databases. We re-examine the query classes H and YE+ defined by Chandra and Harel [2] We define H+ and YE++ which differ from H and YE+ in that the use of equality (=) and inequality (≠) is prohibited. We show that H+ is more expressive than YE++ and that any H+ program can be transformed into an equivalent H+ program containing a single recursive predicate without using the equality or inequality operators. As a corollary we obtain a fixpoint formula characterization of H+ queries.