A SQL-Middleware Unifying Why and Why-Not Provenance for First-Order Queries
A SQL-Middleware Unifying Why and Why-Not Provenance for First-Order Queries
复制标题
统一一阶查询的“为什么”和“为什么不”来源的 SQL 中间件
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Boris Glavic
中科院分区：
文献类型：
--
作者：
Seok;Sven Köhler;Bertram Ludäscher;Boris Glavic
解释为什么要查询的结果或结果为什么缺少答案对于许多应用程序很重要，包括审核，调试数据和查询以及回答有关数据的假设问题。两种类型的问题，即为什么和为什么不出处，都已进行了广泛的研究。在这项工作中，我们提出了第一种实用方法来回答有关否定的查询（第一阶查询）的问题。我们的方法是基于对Datalog规则（称为射击规则）的重写，该规则捕获了在Datalog查询的上下文中捕获成功的规则推导。我们扩展此重写以支持否定并捕获解释缺失答案的失败推导。给出一个（为什么或为什么）出处问题，我们计算一个解释，即与回答问题相关的出处部分。我们引入优化，以便在早期的出处图表中修剪部分，以确定它们将不合同给给定问题的解释的一部分。我们提出了一种实现，该实现使用SQL在关系数据库之上运行，以计算说明。我们的实验表明，我们的方法扩展到很大的实例，并显着优于早期的方法，该方法实例化了完整的出处以计算解释。
Explaining why an answer is in the result of a query or why it is missing from the result is important for many applications including auditing, debugging data and queries, and answering hypothetical questions about data. Both types of questions, i.e., why and why-not provenance, have been studied extensively. In this work, we present the first practical approach for answering such questions for queries with negation (firstorder queries). Our approach is based on a rewriting of Datalog rules (called firing rules) that captures successful rule derivations within the context of a Datalog query. We extend this rewriting to support negation and to capture failed derivations that explain missing answers. Given a (why or why-not) provenance question, we compute an explanation, i.e., the part of the provenance that is relevant to answer the question. We introduce optimizations that prune parts of a provenance graph early on if we can determine that they will not be part of the explanation for a given question. We present an implementation that runs on top of a relational database using SQL to compute explanations. Our experiments demonstrate that our approach scales to large instances and significantly outperforms an earlier approach which instantiates the full provenance to compute explanations.
影响因子：
2.5
作者：
Melanie Herschel;Mauricio A. Hernández
通讯作者：
Melanie Herschel;Mauricio A. Hernández