Horn clauses and the fixpoint query hierarchy

Abstract

A logic program consists of a set of Horn clauses, and can be used to express a query on relational data bases. It is shown that logic programs express precisely the queries in YE+ (the set of queries representable by a fixpoint applied to a positive existential query). Queries expressible by logic programs are thus not first order queries in general; nor are all the first order queries expressible as logic programs. A way of adding the negation operator to logic programs is suggested. The resulting set of clausal queries equals FP, the set of first order queries closed under fixpoints (as well as -, v, 3).