文章基本信息

标题：The Fixpoint Bounded-Variable Queries are PSPACE-Complete
本地全文：下载
作者：Stefan Dziembowski
期刊名称：BRICS Report Series
印刷版ISSN：0909-0878
出版年度：1996
卷号：3
期号：41
出版社：Aarhus University
摘要：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 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.