Cost-Based Semantics for Querying Inconsistent Weighted Knowledge Bases

技术摘要：针对不一致加权知识库的基于成本的语义研究

问题陈述
本体介导查询回答（OMQA）依赖于由 TBox（本体）和 ABox（数据）组成的描述逻辑（DL）知识库（KB）。经典的 OMQA 语义基于一阶逻辑，当知识库出现不一致时，由于矛盾会导致所有命题皆为真，因此无法提供有意义的回答。虽然现有的处理方法通过修复（如 AR 和 brave 语义）来处理不一致性，但这些方法通常假设 TBox 是可靠的，仅对 ABox 进行修改。此外，标准的修复语义通常将所有断言视为同等可靠，或者依赖于基于基数的极大性，缺乏一种根据不同信任程度来优先处理冲突信息的细致方法。

本文通过引入一个定量框架来解决查询不一致 DL 知识库的挑战。核心问题在于，当 TBox 公理和 ABox 断言都可能被违反，且违反行为根据分配的权重受到惩罚时，如何定义有意义的确定性答案（certain answers）和可能答案（possible answers）。

方法论与框架
作者提出了一个**加权知识库（Weighted Knowledge Base, WKB）**框架，记作 $K_\omega = (\langle \mathcal{T}, \mathcal{A} \rangle, \omega)$。

• 权重： 成本函数 $\omega$ 为 $\mathcal{T}$ 中的每个公理和 $\mathcal{A}$ 中的每个断言分配一个值 $\mathbb{N}_{>0} \cup \{+\infty\}$。无穷大权重代表必须满足的“硬”约束，而有限权重代表“软”约束，其中较高的值表示更高的可靠性。
• 解释的成本： 解释 $I$ 的成本定义为所有被违反的公理和断言的权重之和。具体而言，对于概念包含关系 $\tau$，其成本包括 $\omega_\tau \times |vio_\tau(I)|$，其中 $vio_\tau(I)$ 是违反该包含关系的领域元素集合。断言最多只能被违反一次。
• 语义： 文中根据解释的成本定义了四种查询蕴含语义：
  1. $k$-成本限制确定性 ($K_\omega \models^k_c q$)： $q$ 在所有成本 $\le k$ 的解释中均成立。
  2. $k$-成本限制可能性 ($K_\omega \models^k_p q$)： $q$ 在至少一个成本 $\le k$ 的解释中成立。
  3. 最优成本确定性 ($K_\omega \models^{opt}_c q$)： $q$ 在所有最小成本（$optc(K_\omega)$）的解释中均成立。
  4. 最优成本可能性 ($K_\omega \models^{opt}_p q$)： $q$ 在至少一个最小成本的解释中成立。

该框架泛化了现有的修复语义。具体而言，当 TBox 公理具有无穷大权重时，最优成本确定性语义与 $\le_\omega$-AR 语义（Bienvenu, Bourgaux, and Goasdoué 2014）一致，后者选择最大化保留断言权重之和的修复。

主要贡献
本文的主要贡献是对该设定下主要决策问题的**结合复杂度（combined complexity）和数据复杂度（data complexity）**进行了全面分析：

1. 有界成本可满足性（Bounded Cost Satisfiability, BCS）： 判定是否存在一个成本 $\le k$ 的解释。
2. 确定性与可能性的答案识别： 在上述四种语义下判定蕴含关系。

研究涵盖了一系列从轻量级 $\mathcal{EL}^\bot$ 到表达能力较强的 $\mathcal{ALCO}$（以及用于上界证明的 $\mathcal{ALCO}^\mathcal{Q}$）的描述逻辑，同时处理实例查询（IQs）和连接查询（CQs）。

复杂度结果
本文确立了紧凑的复杂度界限，总结如下：

• 结合复杂度：

  • 大多数问题是 EXPTIME-complete。
  • 连接查询（CQs）的确定性答案识别（无论是 bounded 还是 opt-cost）是 2EXPTIME-complete。这种高复杂度源于需要在特定成本的所有模型中验证蕴含关系，这与环绕（circumscribed）知识库相关。
  • 即使权重和成本界限 $k$ 以二进制编码，上述界限依然成立。

• 数据复杂度：

  • 有界成本可满足性 (BCS)： NP-complete。
  • 有界成本回答 (IQs/CQs)： 可能回答（possible）为 NP-complete；确定回答（certain）为 coNP-complete。
  • 最优成本回答： 复杂度高度依赖于权重的编码方式：
    • 如果权重以**一进制（unary）**编码或相对于 ABox 大小独立受限，则问题为 $\Theta^p_2$-complete（可通过对 NP Oracle 进行对数次调用在多项式时间内解决）。
    • 如果权重以**二进制（binary）**编码且相对于 ABox 大小可以呈指数级增长，则问题为 $\Delta^p_2$-complete（可通过访问 NP Oracle 在多项式时间内解决）。
  • 文中指出，对于具有二进制权重的最优成本确定性语义，其上界仍是一个开放问题，但其下界为 $\Delta^p_2$-hard。

意义与主张
作者声称提供了一个关于基于成本语义的查询不一致知识库复杂度的“几乎完整的图景”。这项工作的意义在于：

1. 定量灵活性： 超越了二元一致性的限制，转向一种分级的处理方式，使得答案可以根据其“鲁棒性”（即是否在接近最优成本的解释中成立）进行排序或过滤。
2. 泛化性： 统一了数据库中的软约束（Carmeli et al. 2021）与本体中的加权修复，表明最优成本语义自然地泛化了优选修复语义。
3. 技术深度： 复杂度证明利用并改进了 DL 推理的高级技术，包括：
   • 利用过滤（Filtration）和有界模型属性来建立上界。
   • 通过来自基数查询回答和环绕知识库的归约来建立下界。
   • 适配了计数查询文献（Manière 2022）中的“交织”（interlacing）和“商”（quotient）构造，以处理特定权重的违反约束。

最后，本文指出了未来的研究方向，特别是将这些结果扩展到具有逆角色、角色包含和函数式角色的 DL（例如 DL-Lite 系列），并指出目前的上界技术无法直接迁移到这些构造中。同时，文章也强调了开发实用算法以进行实现的挑战。