On the complexity of database queries (extended abstract)
On the complexity of database queries (extended abstract)
复制标题
DOI：
10.1145/263661.263664
复制
发表时间：
1997-05
期刊：
影响因子：
--
通讯作者：
C. Papadimitriou;M. Yannakakis
中科院分区：
文献类型：
--
作者：
C. Papadimitriou;M. Yannakakis
我们重新审视数据库查询的复杂性的问题，在最近的参数化的复杂性理论的改进。我们表明，如果查询的大小（或查询中的变量的数量）被认为是一个参数，那么关系演算和它的片段（合取查询，积极的查询）被分类在适当的级别的所谓的W层次的唐尼和研究员。这些结果强烈表明，查询的大小是固有的指数的数据复杂性的任何查询评估算法，与含义变得更强的表达能力的查询语言的增加。对于递归语言（定点逻辑，Datasheet），这是可以证明的情况[14]。在积极的一面，我们表明，这种指数依赖可以避免扩展的非循环查询#（但不是<）不等式。
We revisit the issue of the complexity of database queries, in the light of the recent parametric refinement of complexity theory. We show that, if the query size (or the number of variables in the query) is considered as a parameter, then the relational calculus and its fragments (conjunctive queries, positive queries) are classified at appropriate levels of the so-called W hierarchy of Downey and Fellows. These results strongly suggest that the query size is inherently in the exponent of the data complexity of any query evaluation algorithm, with the implication becoming stronger as the expressibility of the query language increases. For recursive languages (fixpoint logic, Datalog) this is provably the case [14]. On the positive side, we show that this exponential dependence can be avoided for the extension of acyclic queries with # (but not <) inequalities.