The complexity of higher-order queries
The complexity of higher-order queries
复制标题
高阶查询的复杂度
DOI：
10.1016/j.ic.2015.07.003
复制
发表时间：
2015
影响因子：
1
通讯作者：
Benedikt M
中科院分区：
文献类型：
--
作者：
Benedikt M
高阶转换在数据管理中无处不在。在关系数据库中，高阶查询出现在许多方面，包括查询重写和查询规范。这项工作研究的语言，结合联合收割机高阶转换与普通的关系数据库查询语言。我们研究了与这些查询语言相关的两个最基本的计算问题-评估问题和包容问题。我们在每一个顺序上隔离求值的复杂性，分析类似于标准类型lambda演算。我们表明，包含问题（因此，等价问题）是可判定的几个重要的子情况下，特别是在查询常量和变量的范围超过正关系运算符的情况下。主要的可判定性结果依赖于与经典查询包含中使用的技术不同的技术。我们还表明，高阶查询的分析是密切相关的非递归数据库的评估和包容问题。
Higher-order transformations are ubiquitous within data management. In relational databases, higher-order queries appear in numerous aspects including query rewriting and query specification. This work investigates languages that combine higher-order transformations with ordinary relational database query languages. We study the two most basic computational problems associated with these query languages – the evaluation problem and the containment problem. We isolate the complexity of evaluation at every order, in an analysis similar to that for that standard typed lambda calculus. We show that the containment problem (and hence, the equivalence problem) is decidable in several important subcases, particularly in the case where query constants and variables range over the positive relational operators. The main decidability result relies on techniques that differ from those used in classical query containment. We also show that the analysis of higher-order queries is closely connected to the evaluation and containment problems for non-recursive Datalog.
登录
查看更多内容
树上的联合查询包含
影响因子：
4.8
作者：
Henrik Björklund;W. Martens;T. Schwentick
通讯作者：
T. Schwentick
影响因子：
1.1
作者：
J. V. D. Bussche;D. V. Gucht;Stijn Vansummeren
通讯作者：
Stijn Vansummeren
函数式数据库查询语言作为固定顺序的类型化 lambda 演算（扩展抽象）
DOI：
--
发表时间：
1994
期刊：
ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems
影响因子：
--
作者：
Gerd G. Hillebrand;P. Kanellakis
通讯作者：
P. Kanellakis
高阶查询的复杂性
DOI：
--
发表时间：
2011
期刊：
International Conference on Database Theory
影响因子：
--
作者：
Huy Vu;Michael Benedikt
通讯作者：
Michael Benedikt
论简单类型和 let 多态 lambda 演算的表达能力
DOI：
--
发表时间：
1996
期刊：
Proceedings 11th Annual IEEE Symposium on Logic in Computer Science
影响因子：
--
作者：
Gerd G. Hillebrand;P. Kanellakis
通讯作者：
P. Kanellakis