The Fixpoint Bounded-Variable Queries are PSPACE-Complete

  • Stefan Dziembowski


We study complexity of the evaluation of fixpoint bounded-variable
queries in relational databases. We exhibit a finite database such
that the problem whether a closed fixpoint formula using only 2 individual variables is satisfied in this database is PSPACE-complete. This clarifies the issues raised by Moshe Vardi in [Var95]. We study also the complexity of query evaluation for a number of restrictions of fixpoint logic. In particular we exhibit a sublogic for which the upper bound postulated by Vardi holds.
How to Cite
Dziembowski, S. (1996). The Fixpoint Bounded-Variable Queries are PSPACE-Complete. BRICS Report Series, 3(41).