Relational queries computable in polynomial time (Extended Abstract)
Relational queries computable in polynomial time (Extended Abstract)
复制标题
可在多项式时间内计算的关系查询（扩展摘要）
DOI：
--
复制
发表时间：
1982
期刊：
影响因子：
--
通讯作者：
N. Immerman
中科院分区：
文献类型：
--
作者：
N. Immerman
关系数据库的查询语言受到了相当大的关注。在1972年Codd [Cod 72]表明，两种自然的数学语言的查询--一个代数和其他版本的一阶谓词演算--具有相同的权力的表达能力。像Codd的关系演算一样有表现力的查询语言有时被称为完备的。然而，这个术语有误导性，因为许多有趣的查询不能用完全语言表达.
在本文中，我们显示：
定理2：固定点层次结构在第一个固定点级别崩溃。
也就是说，任何可以用几个最小不动点应用程序表示的查询都可以用一个最小不动点来表示。我们还显示：
定理1：设L是一个由关系演算和最小不动点算子组成的查询语言。假设L包含定义域上的全序关系（例如字典序）的关系符号。那么可以用L表示的查询就是可以在多项式时间内计算的查询。
定理1是M.瓦尔迪[Var 82]。它给出了一个简单的语法分类，这些查询可以在多项式时间内回答。当然，在数据库的大小上需要多项式时间的查询通常是非常昂贵的。我们还考虑了用于表达不太复杂的查询的较弱的语言。
Query languages for relational databases have received considerable attention. In 1972 Codd [Cod72] showed that two natural mathematical languages for queries-&-mdash;one algebraic and the other a version of first order predicate calculus-&-mdash;had identical powers of expressibility. Query languages which are as expressive as Codd's Relational Calculus are sometimes called complete. This term is misleading, however, because many interesting queries are not expressible in -&-ldquo;complete-&-rdquo; languages.
In this paper we show:
Theorem 2: The Fixpoint Hierarchy collapses at the first fixpoint level.
That is, any query expressible with several applications of least fixpoint can already be expressed with one. We also show:
Theorem 1: Let L be a query language consisting of relational calculus plus the least fixpoint operator. Suppose that L contains a relation symbol for a total ordering relation on the domain (e.g. lexicographic ordering). Then the queries expressible in L are exactly the queries computable in polynomial time.
Theorem 1 was discovered independantly by M. Vardi [Var82]. It gives a simple syntactic categorization of those queries which can be answered in polynomial time. Of course queries requiring polynomial time in the size of the database are usually prohibitatively expensive. We also consider weaker languages for expressing less complex queries.