Provenance Traces
Provenance Traces
复制标题
出处痕迹
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Amal Ahmed
中科院分区：
文献类型：
--
作者：
J. Cheney;Umut A. Acar;Amal Ahmed
出处是关于一个对象的起源、派生、所有权或历史的信息。由于它在帮助科学家判断数据的有效性、质量和完整性方面的重要性，它最近在科学数据库和其他环境中得到了广泛的研究。然而，大多数来源模型都是由诸如“来自”、“影响”、“产生”或“依赖”等非正式概念所激发的特别定义。这些模型缺乏清晰的形式化描述，说明定义在何种意义上捕获了这些直观的概念。这使得比较方法、评估它们的有效性或争论它们的有效性变得困难。我们介绍了来源痕迹，这是嵌套关系演算（NRC）的一种一般形式的来源，NRC是一种核心数据库查询语言。来源痕迹可以被认为是具体的数据结构，表示计算的操作语义推导；它们与自调整计算中的轨迹有关，但在重要方面有所不同。我们为NRC查询定义了一个跟踪操作语义，它既产生普通结果，也产生执行的跟踪。我们表明，可以从来源痕迹中提取出NRC的三种预先存在的来源形式。此外，跟踪满足两个语义保证：一致性，即跟踪描述执行期间实际发生的情况；保真度，即跟踪“解释”如果i输入发生变化，表达式将如何表现。这些保证比以前的来源方法所设想的要有力得多；因此，溯源痕迹为比较和统一数据库中的溯源模型提供了一个通用的语义基础。
Provenance is information about the origin, derivation, ow nership, or history of an object. It has recently been studied extensi v ly in scientific databases and other settings due to its importa nce in helping scientists judge data validity, quality and integr ity. However, most models of provenance have been stated as ad hoc defi nitions motivated by informal concepts such as “comes from”, “ influences”, “produces”, or “depends on”. These models lack clea r formalizations describing in what sense the definitions captur e these intuitive concepts. This makes it difficult to compare appro aches, evaluate their effectiveness, or argue about their validit y. We introduceprovenance traces , a general form of provenance for the nested relational calculus(NRC), a core database query language. Provenance traces can be thought of as concrete da ta structures representing the operational semantics deriva tion of a computation; they are related to the traces that have been us d in self-adjusting computation, but differ in important res p cts. We define a tracing operational semantics for NRC queries that p roduces both an ordinary result and a trace of the execution. We show that three pre-existing forms of provenance for the NRC can b e extracted from provenance traces. Moreover, traces satisf y two semantic guarantees: consistency , meaning that the traces describe what actually happened during execution, and fidelity, meaning that the traces “explain” how the expression would behave if the i nput were changed. These guarantees are much stronger than those contemplated for previous approaches to provenance; thus, pro venance traces provide a general semantic foundation for comparing and unifying models of provenance in databases.