@article{Dziembowski_1996, title={The Fixpoint Bounded-Variable Queries are PSPACE-Complete}, volume={3}, url={https://tidsskrift.dk/brics/article/view/20023}, DOI={10.7146/brics.v3i41.20023}, abstractNote={We study complexity of the evaluation of fixpoint bounded-variable<br />queries in relational databases. We exhibit a finite database such<br />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.}, number={41}, journal={BRICS Report Series}, author={Dziembowski, Stefan}, year={1996}, month={Jun.} }