Fixpoint extensions of first-order logic and datalog-like languages

Abstract

Datalog extensions with fixpoint semantics motivated by database queries and updates are studied. The authors suggest nontrivial fixpoint extensions of first-order logic with nondeterministic and/or noninflationary semantics. Certain properties of the language FO+IFP, such as the collapse of the hierarchy (based on the nesting of fixpoints) or the existential normal form, hold for these various logics. Their expressive power is characterized.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>