Equivalence-Invariant Algebraic Provenance for Hyperplane Update Queries
Equivalence-Invariant Algebraic Provenance for Hyperplane Update Queries
复制标题
超平面更新查询的等价不变代数起源
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Y. Moskovitch
中科院分区：
文献类型：
--
作者：
P. Bourhis;Daniel Deutch;Y. Moskovitch
起源自Green等人的半环模型的溯源代数方法已被证明是处理元数据的一种抽象方法。交换半环被证明是合取查询联合的“正确”代数结构，因为它的使用允许在某些预期的查询等价公理下来源是不变的。在本文中，我们提出了第一个（据我们所知的）更新查询片段的代数来源模型，该模型在集合等价下是不变的。我们关注的片段是超平面查询，以前在多个工作中研究过。我们的代数物源结构和相应的物源感知语义是基于Karabeg和Vianu的完备公理化。我们证明了我们的构造可以指导不同应用的具体来源模型实例的设计。我们进一步研究了超平面更新查询源的高效生成和存储。我们展示了一个朴素的算法可以导致一个指数级大的来源表达式，但是通过提出一个标准形式来补救这个问题，我们展示了一个可以与查询计算一起有效计算的形式。我们通过实验研究了我们的解决方案的性能，并证明了它的可扩展性和实用性，特别是我们的范式表示的有效性。
The algebraic approach for provenance tracking, originating in the semiring model of Green et. al, has proven useful as an abstract way of handling metadata. Commutative Semirings were shown to be the "correct" algebraic structure for Union of Conjunctive Queries, in the sense that its use allows provenance to be invariant under certain expected query equivalence axioms. In this paper we present the first (to our knowledge) algebraic provenance model, for a fragment of update queries, that is invariant under set equivalence. The fragment that we focus on is that of hyperplane queries, previously studied in multiple lines of work. Our algebraic provenance structure and corresponding provenance-aware semantics are based on the sound and complete axiomatization of Karabeg and Vianu. We demonstrate that our construction can guide the design of concrete provenance model instances for different applications. We further study the efficient generation and storage of provenance for hyperplane update queries. We show that a naive algorithm can lead to an exponentially large provenance expression, but remedy this by presenting a normal form which we show may be efficiently computed alongside query evaluation. We experimentally study the performance of our solution and demonstrate its scalability and usefulness, and in particular the effectiveness of our normal form representation.