Jun, 2023

带或存在规则和映射查询重写

PDF
TL;DR本文研究了使用拼接查询组成的联合响应（UCQs）答案问题，有 “或型存在规则和映射”。本文首先提出了一个完整的查询重写操作符，并使用广度优先查询重写算法来输出最小的 UCQ 重写副本。其次，我们证明，在任何真正的 “分离” 递归规则中，存在一种联合查询，不需要 UCQ 重写。最后，本文研究了通过 “或型映射” 决定 UCQ 是否有 UCQ 重写的问题，结果是不可判定的。
发现论文，激发创造
  • 存在规则下的元组删除语义一致的查询答案

    研究使用存在规则表示的知识库中的一致查询回答。具体地，建立了一般类别的消解存在规则和多个子类（无环、线性、全面、守卫、粘滞）下的一致查询回答和修复检查的数据复杂性（元组删除语义）。特别是，鉴定了几种情况下问题可处理或甚至是一阶可重写的，并提出了新的查询重写技术，可作为实际的容忍不一致查询回答系统的基础。

    Jan, 2024

  • 存在规则的有限团宽集：朝着决定性、高表达性查询的通用准则迈进

    该研究通过引入 “有限团宽集合”（FCS）来寻求可决定本体论查询的一般性标准，FCS 是一种模型理论定义的规则集类，受到图论中团宽的启发，这一类规则集确保了一类子句共有查询（DaMSOQs）的蕴涵可决定性，它们吸收了合取查询（CQs）并且限制于元数为 2 的符号。

    Sep, 2022

  • ALC 本体上有限封装的 UCRPQs

    研究了基于本体的查询的有限包含问题，考虑了扩展了联合的连通查询类的表达性查询语言 UCRPQs，并通过介绍确定性有限自动机来决定解释的分层结构，证明了 ALC 下 UCRPQs 的紧 2EXPTIME 上界。

    Apr, 2022

  • 结合存在规则和传递性：下一步

    本文探讨存在规则作为本体规范的形式化方法，重点研究了如何将传递性与可判定类的存在规则组合，并给出了能够安全添加传递性的情况和相应的查询重写算法。

    Apr, 2015

  • 本体查询：重写与优化 (扩展版)

    本文研究了本体查询中的查询重写和查询优化问题，其中查询重写包括将本体查询编译为与底层关系型数据库等效的查询，查询优化旨在改善此过程以生成成本效益高的 UCQ 重写，提出了一种有效的新方法以支持基于线性 Datalog+/- 的规则。

    Dec, 2011

  • 存在规则的无环概念及其在本体查询回答中的应用

    本文探讨了如何使用 chase 算法在存在规则的事实集上回答联合查询，介绍了两种新的不将模型扩展到不可数状态的无环性概念，展示了如何基于这些概念构造 OWl2 本体推理器，从而提供了在实践中如何实现这些系统的基本理论解释。

    Feb, 2014

  • 联结查询反向工程问题的复杂性

    本文研究了解决共识查询相关反向工程问题的复杂性，并提出了基于量子比较的松弛方法来降低复杂度。最终得出了基于共识查询树宽度的 QBE 的可行性和闭合性条件，并将其应用于图数据库的查询问题。

    Jun, 2016

  • SHIQ 描述逻辑的联合查询回答

    本文研究 DL 中具有传递性角色的联接查询的可决定性和复杂度问题，并证明了在 SHIQ 中允许传递性角色的联接查询有一个完美的单指数时间算法及共 NP 复杂性。

    Oct, 2011

  • 联结查询：独特特征和精确可学性

    研究了如何构造多项式多个正负示例唯一确定的不变式查询，提出了前沿算法并讨论其在描述逻辑和模式映射中的应用。

    Aug, 2020

  • 存在规则的保守扩展

    研究基于元组生成依赖（TGDs）的存在性规则，确定给定的 T1，T2 元素集是否为 T1 的保守扩展，结果表明当 TGDs 是线性的时，对于两种自然的保守扩展概念，问题是不可判定的；对于保护 TGDs，即使 T1 是空的，问题也是不可判定的；对于 frontier-one TGDs，问题是可判定的。

    Feb, 2022