|
Abstract : |
Abstract. We study the complexity of the evaluation of bounded-variable fixpoint queries in relational databases. We exhibit a finite database such that the problem of deciding whether a closed fixpoint formula using only 2 individual variables is satisfied in this database is PSPACE-complete. This clarifies the issues raised by Vardi in [Var95]. 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. 1, |
