Incremental computation of nested relational query expressions
Incremental computation of nested relational query expressions
复制标题
嵌套关系查询表达式的增量计算
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
L. Mark
中科院分区：
文献类型：
--
作者：
Lars Bækgaard;L. Mark
不存在用于递增地计算嵌套查询表达式的有效算法。嵌套查询表达式是其中选择/连接谓词包含子查询的查询表达式。为了解决这个问题，我们提出了一个两步的增量计算嵌套查询表达式的策略。在步骤（1）中，查询表达式被转换成等效的非嵌套平面查询表达式。在步骤（2）中，递增地计算平面查询表达式。为了支持步骤（1），我们已经开发了一个非常简洁的代数到代数的转换算法，并且我们已经正式证明了它的正确性。由转换产生的平面查询表达式大量使用了关系集差运算符。为了支持第（2）步，我们提出并分析了一个基于视图指针缓存的增量式计算集合差异的有效算法。当结合现有的增量算法SPJ查询，我们的增量集差算法可以用来计算非嵌套的平面查询表达式有效。重要的是要注意，如果没有我们的增量集差算法，现有的SPJ查询增量算法对于任何涉及集差运算符的查询都是无用的，包括不是非嵌套嵌套查询的结果的查询。
Efficient algorithms for incrementally computing nested query expressions do not exist. Nested query expressions are query expressions in which selection/join predicates contain subqueries. In order to respond to this problem, we propose a two-step strategy for incrementaly computing nested query expressions. In step (1), the query expression is transformed into an equivalent unnested flat query expression. In step (2), the flat query expression is incrementally computed. To support step (1), we have developed a very concise algebra-to-algebra transformation algorithm, and we have formally proved its correctness. The flat query expressions resulting from the transformation make intensive use of the relational set-difference operator. To support step (2), we present and analyze an efficient algorithm for incrementally computing set differences based on view pointer caches. When combined with existing incremental algorithms for SPJ queries, our incremental set-difference algorithm can be used to compute the unnested flat query expressions efficiently. It is important to notice that without our incremental set-difference algorithm the existing incremental algorithms for SPJ queries are useless for any query involving the set-difference operator, including queries that are not the result of unnesting nested queries.