Feb, 2022

使用传递性和线性排序数据进行查询回答

PDF
TL;DR本研究研究了涉及强约束语言的蕴涵问题，如前沿守卫存在规则，并对一组特殊的关系施加额外的语义限制。我们考虑将关系限制为传递性、将一个关系的传递闭包限制为另一个关系、将关系限制为线性顺序。我们提出了一些自然的守卫性变体，以使推理在每种情况下具有可决定性，并确定了相应决策问题的复杂度。最后，我们证明了这些条件的轻微变化会导致不可决定性问题。
entailment problemsfrontier-guarded existential rulessemantic restrictionsinferencedecidability
发现论文，激发创造
  • 结合存在规则和传递性：下一步

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

    Apr, 2015

  • 存在规则的保守扩展

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

    Feb, 2022

  • 有限和无限制查询蕴涵：超越带有传递性角色数字限制的 SQ

    研究了具有数字限制的 SQ 描述逻辑，该逻辑适用于传递性角色，并扩展为名词或反向角色。为 nominals 的正存在查询和为 inverses 的实例查询建立了上界。

    Oct, 2020

  • 本体基于查询回答的存在规则语言表达完备性

    本文证明了分离嵌入式依赖可以精确捕捉基于本体的连词查询应答中的可递归枚举本体类，而关于 “元组生成依赖” 的复杂性类和嵌入式依赖的复杂性类都不能完全表达可递归枚举的 “基于本体的连词查询应答” 本体。

    Apr, 2016

  • 存在规则下的元组删除语义一致的查询答案

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

    Jan, 2024

  • 存在规则语言的模型论描述

    本研究旨在模型理论中建立存在规则语言的模型论特性，如嵌入依赖项，元组生成依赖项和线性依赖项，并确定它们的复杂度限制。

    Jan, 2020

  • 存在规则的规范化：不是那么无害！

    该研究系统研究了存在性规则对于不同的追踪变体以及基于一阶逻辑的重写的 (chase (non-) termination and FO-rewritability) 影响，从而探讨了相关的开放性问题。

    Jun, 2022

  • 具有传递性的一元否定片段的有限可满足性

    研究发现：在包含任意数量的传递关系的一元否定分段中，有限可满足性问题是可判定和 2-ExpTime 完全问题。此外，我们探讨了我们的基本逻辑的各种扩展的有限可满足性，特别是描述逻辑中已知的名称和角色层次概念的表达。

    Sep, 2018

  • 驯服无限追踪：在表达完整性约束下进行查询回答

    提出了大类元组生成依赖和相等生成依赖的追赶算法思想，并以受限语言的形式表现，证明了这种情况下查询的可决策性。给出了一些具体的限制模型，并将其应用于较常见的问题，并在问题求解的复杂度方面给出了确切的界限。

    Dec, 2012

  • 知识图谱上存在性一阶查询的推理

    这篇论文通过系统检视问题之前的范围并提出一个新的数据集，讨论了同时出现的新挑战，并提出了一种模糊逻辑理论的新搜索算法，以解决新的公式并在现有公式中胜过以前的方法。

    Apr, 2023