Stefan Dziembowski
Bounded-Variable Fixpoint Queries are PSPACE-complete
Computer Science Logic '96, LNCS, Springer, vol. 1258, pp. 89-105, Sep 1996.
Abstract 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 ("On 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.
Available files: [ Postscript] [ PDF] [ BibTeX ]
Bounded-Variable Fixpoint Queries are PSPACE-complete
Computer Science Logic '96, LNCS, Springer, vol. 1258, pp. 89-105, Sep 1996.
Abstract 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 ("On 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.
Available files: [ Postscript] [ PDF] [ BibTeX ]