Positive higher-order queries
Positive higher-order queries
复制标题
正向高阶查询
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Huy Vu
中科院分区：
文献类型：
--
作者：
Michael Benedikt;Gabriele Puppis;Huy Vu
我们调查了一种嵌入正相关代数的运算符的高阶查询语言，我们的语言使我们的语言简洁地定义了普通的正面关系代数查询（连接性查询，二阶查询功能，允许在通用的（即语法独立于语法）的方式中转换CQ和UCQ。对于每个可能的输入查询，如果输出查询是相等的，则类似地，对于封存和等效性的这些注释都取决于（普通的关系代数）查询。变量仅限于正相关代数，我们确定了问题的精确复杂性。
We investigate a higher-order query language that embeds operators of the positive relational algebra within the simply-typed λ-calculus. Our language allows one to succinctly define ordinary positive relational algebra queries (conjunctive queries and unions of conjunctive queries) and, in addition, second-order query functionals, which allow the transformation of CQs and UCQs in a generic (i.e., syntax-independent) way. We investigate the equivalence and containment problems for this calculus, which subsumes traditional CQ/UCQ containment. Query functionals are said to be equivalent if the output queries are equivalent, for each possible input query, and similarly for containment. These notions of containment and equivalence depend on the class of (ordinary relational algebra) queries considered. We show that containment and equivalence are decidable when query variables are restricted to positive relational algebra and we identify the precise complexity of the problem. We also identify classes of functionals where containment is tractable. Finally, we provide upper bounds to the complexity of the containment problem when functionals act over other classes.