# Information Security and Cryptography Research Group

## Bounded-Variable Fixpoint Queries are PSPACE-complete

### Stefan Dziembowski

Computer Science Logic '96, Lecture Notes in Computer Science, Springer-Verlag, vol. 1258, pp. 89–105, Sep 1996.

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 (Ön the Complexity of Bounded-Variable Queries", PODS 1995). 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.

## BibTeX Citation

@inproceedings{Dziemb96,
author       = {Stefan Dziembowski},
title        = {Bounded-Variable Fixpoint Queries are {PSPACE}-complete},
editor       = {Dirk van Dalen and Marc Bezem},
booktitle    = {Computer Science Logic~'96},
pages        = {89--105},
series       = {Lecture Notes in Computer Science},
volume       = {1258},
year         = {1996},
month        = {9},
publisher    = {Springer-Verlag},
}