Mar, 2023

Datalog 查询的 Why-Provenance 复杂性

PDF
TL;DR本文旨在填补 why-provenance 计算复杂性方面的空白，我们确定了 Datalog 查询和其子类的 why-provenance 的数据复杂度，得出结论，由于其计算复杂性的特殊性质，递归查询的 why-provenance 是一个棘手的问题。
explainable aidatalogwhy-provenancecomputational complexityrecursive queries
发现论文，激发创造
  • 溯源作为依赖关系分析

    本论文提出依赖关系分析技术作为数据来源或历史的形式化基础，探讨了相应的数据溯源机制和静态 / 动态逼近方法。

    Aug, 2007

  • 可验证性的核心演算法

    本文介绍了一种形式化的 Provenance 安全框架，探讨在通用程序语言方面的有效性并提出了关于披露和混淆方面的正式定义。研究了针对追踪语义的生产力视角，使用了算法来解决披露和混淆问题。

    Oct, 2013

  • 描述逻辑 ELHr 的溯源

    本文章针对 ELHr 本体中的溯源信息问题，基于整环和扩展经典数据溯源的本体数据访问，对本体公理进行注释来生成溯源多项式，并分析了 ELHr 案例的语义，揭示如何处理省略符号所带来的种种困难，其中一些困难可以通过假定整环的乘法幂等性来缓解。在此基础上，研究了三个问题：使用溯源信息来生成完整的本体，计算得到与结论相关的公理集，并进行查询回答。

    Jan, 2020

  • 轻量级描述逻辑的半环来源

    我们研究了半环溯源，它是一个最初在关系数据库环境中定义的成功框架，用于描述逻辑。我们定义了一种在包含多个轻量级描述逻辑的语言上的溯源语义，并展示了它与具有特定类型注释的本体所定义的语义的关系。我们重点关注了众所周知的 why 溯源，对于每个可加且可乘幂等的交换半环，计算了半环溯源，并研究了与公理或连词查询答案溯源相关的问题的复杂性。最后，我们考虑了两种更加限制的情况，它们对应于数据库环境中的正 Boolean 溯源和谱系。对于这些情况，我们展示了与描述逻辑解释相关的众所周知概念的关系，并完成了复杂性分析。此外，我们还提供了 ELHI_bot 本体的一些条件以保证具有可处理的推理。

    Oct, 2023

  • Vadalog 系统：基于 Datalog 的知识图谱推理

    本文介绍了 Vadalog 系统，这是使用 Datalog 进行复杂逻辑推论任务的系统，采用侵略性终止控制策略实现了 Warded Datalog+/-，并提供了全面的实验评估。

    Jul, 2018

  • 查询答案和非答案的因果关系和责任的复杂性

    该论文研究了查询的答案和非答案的原因和责任的计算方法以及 P 和 NP 的情况和 LOGPACE 的完整性，并证明了某些查询中的因果关系可以通过关系查询在多项式时间内计算。

    Sep, 2010

  • 数据库查询结果的原因：Datalog 推理、视图更新和完整性约束

    本研究建立了 QA 因果关系与数据库诊断、维护完整性约束、视图定义更新的联系，研究了限制条件下的诊断算法工具的复杂性，并获得了新的算法工具。

    Nov, 2016

  • 树形和类树形实例的溯源电路（扩展版）

    该论文提出了一种基于单调二阶逻辑的查询可验证性框架，它利用树形自动机构造电路并连接到关系实例上，从而计算出查询输出的证明，并且应用于树形和树状实例中的计数和概率计算。

    Nov, 2015

  • 将本体查询重写成小型非递归 Datalog 程序

    本文研究本体数据库访问设置，其中 Abox 以关系数据库 D 的形式给出，而布尔连接查询 q 必须针对在 DL-Lite 或 Linear Datalog+/- 中制定的 Tbox T 模块进行求值。我们展示了如何将（T，q）转换为大小为多项式的等效递推 Datalog 程序 P。

    Jun, 2011

  • 面向基于流式架构的约束型和保护型 Datalog$+-$ 的本体推理（技术报告）

    利用 Datalog+/- 语言中的 Shy 和 Warded Datalog+/- 以及引入的新型推理技术 'chase variants'，在基于流式处理架构中实现了 Vadalog 引擎，从而在真实环境中高效解决本体推理任务。

    Nov, 2023