On Impossibility of Decremental Recomputation of Recursive Queries in Relational Calculus and SQL
On Impossibility of Decremental Recomputation of Recursive Queries in Relational Calculus and SQL
复制标题
关系演算和SQL中递归查询不可能递减重新计算的问题
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
L. Wong
中科院分区：
文献类型：
--
作者：
Guozhu Dong;L. Libkin;L. Wong
我们研究了在没有递归机制的传统关系语言中维持递归DE（CID：12）NED观点的问题。特别是，我们表明，在边缘缺失下，连续闭合无法维持。我们使用新的证明技术来证明此结果。这些证明技术将其推广到其他语言，例如，嵌套关系的语言也包含许多聚合函数。本文将这种语言视为SQL的理论重建。我们的证明技术还推广到其他递归查询。因此，我们表明无法使用类似SQL的语言来维护许多递归查询。我们表明，在某些辅助关系的情况下，这仍然是正确的。我们还将更新及其更新的复杂性与更新同一生成查询的复杂性相关联，并表明后者严格比前者更难。然后，我们将此结果扩展到基于无上下文集的更新查询的结果。
We study the problem of maintaining recursively-de(cid:12)ned views, such as the transitive closure of a relation, in traditional relational languages that do not have recursion mechanisms. In particular, we show that the transitive closure cannot be maintained in relational calculus under deletion of edges. We use new proof techniques to show this result. These proof techniques generalize to other languages, for example, to the language for nested relations that also contains a number of aggregate functions. Such a language is considered in this paper as a theoretical reconstruction of SQL. Our proof techniques also generalize to other recursive queries. Consequently, we show that a number of recursive queries cannot be maintained in an SQL-like language. We show that this continues to be true in the presence of certain auxiliary relations. We also relate the complexity of updating transitive closure to that of updating the same-generation query and show that the latter is strictly harder than the former. Then we extend this result to that of updating queries based on context-free sets.