Complexity of higher-order queries
Complexity of higher-order queries
复制标题
高阶查询的复杂性
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Michael Benedikt
中科院分区：
文献类型：
--
作者：
Huy Vu;Michael Benedikt
虽然关系代数和计算是经典数据库查询语言的良好基础，但尚不清楚模拟函数的模拟是什么，例如查询转换。语言通过将数据库查询运算符添加到λ-calculus作为常数。重点：在此工作中只允许积极的关系运算符作为常数，我们对查询函数的遏制和等价问题。 。查询迭代运算符； λ-calculus评估。
While relational algebra and calculus are a well-established foundation for classical database query languages, it is less clear what the analog is for higher-order functions, such as query transformations. Here we study a natural way to add higher-order functionality to query languages, by adding database query operators to the λ-calculus as constants. This framework, which we refer to as λ-embedded query languages, was introduced in [BPV10]. That work had a restricted focus: the containment and equivalence problems for query-to-query functions, in the case where only positive relational operators are allowed as constants. In this work we take an in-depth look at the most basic issue for such languages: the evaluation problem. We give a full picture of the complexity of evaluation for λ-embedded query languages, looking at a number of variations: with negation and without; with only relational algebra operators, and also with a recursion mechanism in the form of a query iteration operator; in a strongly-typed calculus as well as a weakly-typed one. We give tight bounds on both the combined complexity and the query complexity of evaluation in all these settings, in the process explaining connections with Datalog and prior work on λ-calculus evaluation.