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},
}