🤖 AI

A General Sufficient Condition for Rewriting Horn-ALCHI Atomic Queries into GQL

本文通过采用状态分层（state stratification）来消除增加复杂性的循环依赖，引入了 DL 自动机，用以识别一类广泛的、可重写为合取双向正则路径查询并集（UC2RPQs）的 Horn-ALCHI 本体介导原子查询，而 UC2RPQs 是新 ISO 标准 GQL 的一个核心片段。

原作者： David Carral, Calixte Gruson, Quentin Manière

发布于 2026-08-06

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： David Carral, Calixte Gruson, Quentin Manière

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正试图在一座巨大且不断变化的城市中寻找一位特定的朋友。你有一张地图（数据库）显示着人们此时此刻的位置，但你还有一套“城市规则”（本体），这些规则告诉了你地图上没有直接显示的信息。例如，规则可能会说：“如果某人站在大门旁边，那么他也站在一个连接点旁边”；或者“如果你是一个受信任的用户，你必须连接到一个敏感节点”。在计算机科学领域，这被称为本体介导查询（Ontology-Mediated Querying）。这就像是不仅向图书管理员询问书架上的书，还要询问根据图书馆编目规则必须存在的书。

挑战在于当这些规则变得复杂时。有时，判断一个事实是否为真需要遵循一条漫长、曲折且可能自我循环的逻辑链，就像迷宫一样。传统的数据库工具擅长简单的查找，但在面对这种复杂的、循环的规则时，往往会陷入困境或崩溃。于是有了 GQL（图查询语言），这是一种用于询问网络问题的新型强大标准。它就像是从一张简单的纸质地图升级到了一个能够处理复杂路线和“假设”场景的 GPS。科学家们一直提出的核心问题是：我们能否将这些棘手的、具有循环性的规则翻译成 GQL，以便让标准的数据库工具来解决它们？

这篇题为《将 Horn-ALCHI 原子查询重写为 GQL 的通用充分条件》（A General Sufficient Condition for Rewriting Horn-ALCHI Atomic Queries into GQL）的论文，正是为了解决这个难题。作者 David Carral、Calixte Gruson 和 Quentin Manière 专注于一种特定且功能强大的规则系统，称为 Horn-ALCHI。你可以把这想象成一种非常丰富的语言，用于描述事物在网络中是如何相互关联的。虽然这种语言在描述复杂世界方面表现出色，但由于它允许传统工具无法处理的“无限逻辑循环”，因此将其翻译成标准数据库查询是非常困难的。

作者的主要发现是一把“魔法钥匙”，或者说是一个特定的条件，它能准确告诉我们何时可以将这些复杂的规则安全地翻译成 GQL。他们引入了一种新工具，称为 DL 自动机（DL automaton）。想象一下这是一个在你的数据中穿梭的小型数字机器人。它不是试图一次性解决整个谜题，而是遵循一套指令（转换）来观察自己是否能到达一个“获胜状态”。如果机器人能找到一条通往获胜者的路径，那么你查询的答案就是“是”。

这项工作的巧妙之处在于识别出了一种保证有效的特定类型的机器人。他们称之为分层自动机（stratified automata）。要理解“分层”，请想象一栋多层建筑。在普通建筑中，电梯可能会从 10 层去 1 层，然后再回到 10 层，从而产生混乱的循环。然而，“分层”建筑的设计确保你只能向上移动或停留在同一层；你永远不会以一种会产生混乱循环的方式回到已经访问过的楼层。作者证明，如果他们的机器人（自动机）构建得像这样一座“分层”建筑——这意味着其逻辑不会陷入某些特定类型的循环依赖——那么它就可以被完美地翻译成一个 GQL 查询。

他们展示了这一条件足够广泛，可以涵盖许多以往方法错过的现实场景。例如，他们演示了一个关于计算机网络中“受信任用户”的查询（这涉及检查与敏感节点和大门的连接）符合这种“分层”模式，并且可以被重写为 GQL。然而，他们也含蓄地排除了“所有 Horn-ALCHI 查询都能被重写”的可能性；如果逻辑创造了某种违反“分层”建筑规则的特定类型循环，翻译就会失败。

这篇论文并非凭空猜测；它提供了一个严密的数学证明。他们展示了如何一步步地将复杂的 Horn-ALCHI 规则集转化为 DL 自动机，检查其是否具有分层性，如果是，则将其转换为 GQL 查询。他们还证明了其方法比以往的研究覆盖范围更广，包括了一些曾被其他研究人员认为无法转换的复杂案例。虽然他们并未声称解决了所有可能的情况（有些循环仍然过于纠缠不清），但他们为一大类有用的问题提供了一种可靠且可证明的方法，为复杂的语义网查询在现代图数据库上运行开启了大门。

技术摘要：将 Horn-ALCHI 原子查询重写为 GQL 的通用充分条件

问题陈述
ISO 标准 GQL（图查询语言）的出现引入了一种强大的查询语言，它通过受控的正规递归扩展了首次阶逻辑（FO）。这引发了一个关键问题，即本体介导查询（OMQ）：定义在表达性描述逻辑（DL）之上的规则查询，哪些可以被重写为 GQL？

作者关注的是 Horn-ALCHI，这是一种支持逆向角色（inverse roles）和角色构造器的表达性描述逻辑。与 DL-Lite 系列不同，Horn-ALCHI 通常不具备首次阶可重写性，这意味着标准的基于 SQL 的评估技术并不适用。虽然 GQL 提供了必要的表达能力（具体而言是通过连结正则路径查询的并集，即 UC2RPQ），但目前尚不清楚哪些 Horn-ALCHI 查询可以有效地转换到这一片段中。本文旨在确定一类广泛且可判定的、可被此类重写的 Horn-ALCHI OMQ。

方法论
作者提出了一个多阶段、保持等价性的转换流水线：

归一化为 Horn-ALC $\not\exists$ ：
该过程始于将 Horn-ALCHI 查询转换为等价的 Horn-ALC $\not\exists$ 查询。这包括：
- 消除角色包含公理（例如 $R \sqsubseteq S$ ）和逆向角色公理，通过在角色包含的反射-传递闭包中传播约束来实现。
- 通过将存在量词在规则头中的存在（例如 $A \sqsubseteq \exists R.B$ ）转化为 Datalog 规则来消除它们，遵循针对 Horn-SHIQ 的既定技术。这一步可能会导致规则集规模的指数级膨胀，但能保持语义等价。
转换为 DL 自动机：
归一化后的 Horn-ALC $\not\exists$ 查询随后被映射到一个 DL 自动机，这是一种新型的有限状态设备。
- 结构： 该自动机由对应于概念名称的状态和一个特殊的接受状态（ $q_{acc}$ ）组成。转移要么是二元的（由类或角色表达式标记，从一个状态移动到另一个状态），要么是多元的（由 $\varepsilon$ 标记，将一个状态拆分为一组状态）。
- 语义： 一个接受运行（accepting run）被定义为一个由“状态-常量对”标记节点的有限根树。该树结构镜像了通过“追逐”（chase）程序进行的事实推导。如果存在一个从初始状态和常量开始，并以所有叶节点都标记为接受状态结束的运行，则该自动机接受一个事实集。
分层化与重写为 PQ：
核心贡献在于确定了一个重写的充分条件：分层化（Stratification）。
- 分层化： 作者根据自动机的转移函数定义了状态之间的依赖关系（ $\succ_A$ ）。如果一条路径涉及一个二元转移（角色）并最终导致一个多元转移，则存在依赖关系。如果该依赖关系是无环的，则称该自动机是分层化的。
- 重写算法： 对于分层化的自动机，作者构造了一个等价的正向二向正则路径查询（Positive Two-Way Regular Path Query, PQ）。这是通过层级递进完成的：
  - 对于最低层级（无依赖）的状态，直接使用由二元转移（建模为非确定有限状态自动机）导出的正则表达式构建查询。
  - 对于更高层级的状态，递归地合并依赖的低层级 PQ，并通过引入存在量词来处理由多元转移引起的 branching（分支）。
- 这种构造保证了生成的 PQ 是有限的，因为分层化的无环特性防止了无限递归。
映射到 GQL：
最后，生成的 PQ 被转换为连结二向正则路径查询的并集（UC2RPQ）。由于 UC2RPQ 是 GQL 的核心片段，这建立了最终的重写。

主要贡献

DL 自动机形式化： 引入 DL 自动机作为连接 Horn-ALCHI 语义与路径查询语言的桥梁。
分层化条件： 确定了分层化作为 GQL 可重写性的通用充分条件。该条件排除了已知会增加复杂性的特定循环依赖，但允许比以往方法更广泛的查询类。
通用重写程序： 一个完整的、构造性的算法，通过归一化、自动机构建和分层 PQ 生成等中间步骤，将一类 Horn-ALCHI 查询转换为 GQL 公式。
对前人工作的涵盖： 作者证明其类别严格涵盖了：
- DL-Lite： DL-Lite 中的查询平凡地产生分层化自动机（仅含单个层级）。
- 无害的 Harmless Linear ELHI： 所提类别覆盖了此前 ELHI 重写工作中属于“非无害”限制之外的查询。
- $\text{ELH}^{ql}_i$ ： 该类别包含了类似于文中提到的涉及 Crit 和 Acc 的例子，这些例子在 $\text{ELH}^{ql}_i$ 意义下不是局部的，但仍是分层化的，因此是可重写的。

结果与意义
本文确立了很大一部分具有实际意义的 Horn-ALCHI OMQ 子类可以被重写为 GQL。

表达能力： 该方法处理了此前被认为无法重写为 GQL 片段的查询，例如涉及逆向角色与规则体中合取之间复杂交互的查询（例如 $Sens(x) \land Onl(x) \to Crit(x)$ 与 $Crit(x) \land Acc(x, y) \to Trust(y)$ 的结合）。
完备性： 作者承认该条件是充分而非必要的。存在一些 Horn-ALCHI 查询（例如需要嵌套正则路径查询的查询）是 GQL 可重写的，但并不满足分层化条件。
实用性： 作者指出，尽管归一化步骤可能导致指数级膨胀，但最终的分层化检查是可判定的。他们建议，在真实世界仓库（如 Manchester OWL Repository）上进行经验性评估是下一步必要的步骤，以确定有多少实际查询属于此类。

结论
本文为利用 GQL 评估表达性 DL 之上的本体介导查询提供了理论基础。通过引入 DL 自动机和分层化概念，作者提供了一种稳健的方法来确定可重写性，将 GQL 的适用范围从简单的 DL-Lite 场景扩展到了更复杂的表达性知识库。这项工作将 GQL 定位为更广泛 OMQ 谱系的可行目标语言，弥合了表达性本体推理与现代图查询处理之间的鸿沟。

技术摘要：将 Horn-ALCHI 原子查询重写为 GQL 的通用充分条件

类似论文