The Fixpoint Bounded-Variable Queries are PSPACE-Complete

Stefan Dziembowski

November 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 ((1995)) Proceedings of the 14th ACM Symposium on Principles of Database Systems, pages 266-276). 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 as PostScript, PDF, DVI.


Last modified: 2003-06-08 by webmaster.