Adding For-Loops to First-Order Logic

We study the query language BQL: the extension of the relational algebra with for-loops. We also study FO(FOR): the extension of first-order logic with a for-loop variant of the partial fixpoint operator. In contrast to the known situation with query languages, which include while-loops instead of for-loops, BQL and FO(FOR) are not equivalent. Among the topics we investigate are: the precise relationship between BQL and FO(FOR); inflationary versus noninflationary iteration; the relationship with logics that have the ability to count; and nested versus unnested loops.

Authors

• Frank Neven
• Martin Otto
• Jurek Tyszkiewicz
• Jan Van den Bussche

Keywords

No keywords are indexed for this paper.