On the Limitations of Provenance for Queries with Difference
On the Limitations of Provenance for Queries with Difference
复制标题
关于差异查询来源的限制
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
V. Tannen
中科院分区：
文献类型：
--
作者：
Yael Amsterdamer;Daniel Deutch;V. Tannen
对数据库转换结果的注释被证明对于各种应用程序非常有效。直到最近，这方面的大部分工作都集中在正向查询语言上。起源半环是一种被证明对这些语言有效的方法，当用半环传播起源时，满足了相应查询语言的期望等价公理。已经有几次尝试扩展该框架以说明具有差异的关系代数查询。我们在这里表明，这些建议未能满足某些预期的等价公理(尤其适用于对“标准”集合和包数据库的查询)。有趣的是，我们表明这不是这些特定尝试的陷阱，而是每一个这样的尝试在满足这些公理方面都注定会失败，对于某些半环来说。最后，我们证明了支持差的扩张是(Im)可能的。
The annotation of the results of database transformations was shown to be very effective for various applications. Until recently, most works in this context focused on positive query languages. The provenance semirings is a particular approach that was proven effective for these languages, and it was shown that when propagating provenance with semirings, the expected equivalence axioms of the corresponding query languages are satisfied. There have been several attempts to extend the framework to account for relational algebra queries with difference. We show here that these suggestions fail to satisfy some expected equivalence axioms (that in particular hold for queries on “standard” set and bag databases). Interestingly, we show that this is not a pitfall of these particular attempts, but rather every such attempt is bound to fail in satisfying these axioms, for some semirings. Finally, we show particular semirings for which an extension for supporting difference is (im)possible.