ETH Zürich » Computer Science » Theory » Cryptography

Publications: Abstract

Bounded-Variable Fixpoint Queries are {PSPACE}-complete

Stefan Dziembowski

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.