技术摘要：查询与修复不一致的优先级知识库

1. 问题陈述

本文解决了本体中介查询（OMQA）中处理不一致性的挑战，特别是当底层知识库（KB）包含优先级事实时。虽然标准的不一致性容忍语义（如 AR、IAR 和 brave）依赖于“修复”（即数据中包含最大的一致性子集）的概念，但它们通常无法根据特定事实的可靠性或偏好来区分不同的修复。

在数据库设置中，Staworko、Chomicki 和 Marcinkowski（2012）基于冲突事实之间的优先级关系，引入了三种“最优修复”（Pareto、全局和完成）的概念。本文研究了将这些概念转移到 OMQA 设置中，特别是针对轻量级描述逻辑（DL-Lite）的情况。本文分析的核心问题包括：

1. 查询蕴含：确定查询是否在基于最优修复的不一致性容忍语义（AR、IAR 和 brave 变体）下成立。
2. 唯一性：判断是否存在唯一的最优修复。
3. 枚举：枚举所有最优修复。
4. 论证链接：建立这些修复与抽象论证框架中扩展之间的形式对应关系。

2. 方法论

作者采用了一种结合复杂度分析与抽象论证理论的双重方法论。

2.1 复杂度分析

本研究聚焦于数据复杂度，即本体（$T$）和查询（$q$）固定，复杂度相对于 ABox（$A$）的大小进行衡量。分析涵盖：

• DL-Lite 方言：主要是 $DL\text{-}Lite_{core}$ 和 $DL\text{-}Lite_{H_{horn}}$。
• 修复类型：标准修复（$SRep$）、Pareto 最优（$PRep$）、全局最优（$GRep$）和完成最优（$CRep$）。
• 语义：AR（从所有修复中蕴含）、IAR（从交集蕴含）和 brave（从至少一个修复蕴含）的变体。
• 优先级关系：一般无环关系、传递关系以及结构化分数关系（其中优先级源自优先级级别）。

2.2 论证框架映射

本文提出了一种从优先级知识库到**基于偏好的集合论证框架（PSETAFs）**的新颖转换。

• 论证：ABox 断言。
• 攻击：源自冲突（最小不一致子集）。如果 $S \cup \{\alpha\}$ 不一致，则发生攻击 $S \to \alpha$。
• 偏好：事实上的优先级关系 $\succ$ 被映射为论证上的偏好关系。
• 归约：作者定义了从 PSETAFs 到标准 SETAFs 的归约，从而允许应用既定的论证语义（稳定、优选、基）来定义修复。

3. 主要贡献与结果

3.1 推理任务的复杂度

本文提供了 DL-Lite 中基于最优修复进行推理的数据复杂度的近乎完整的图景。

• 修复检查：
  • Pareto 和完成：在 P（多项式时间）内。
  • 全局：coNP 完全。
• 查询蕴含：
  • Pareto/完成（AR/IAR）：coNP 完全。
  • Pareto/完成（Brave）：NP 完全。
  • 全局（AR/IAR）：$\Pi^p_2$ 完全。
  • 全局（Brave）：$\Sigma^p_2$ 完全。
  • 注：与标准修复不同（在标准修复中 IAR 和 brave 语义是可处理的，属于 $AC^0$），引入最优性准则通常会将全局修复的复杂度提升至多项式层次结构的第二层。
• 唯一性与枚举：
  • Pareto 唯一性：coNP 完全。
  • 全局唯一性：$\Pi^p_2$ 完全。
  • 枚举：对于 $DL\text{-}Lite_{core}$，Pareto 和全局修复的枚举不在 TOTALP 中（无法在多项式总时间内完成）。然而，对于完成最优修复，在二元冲突的情况下，枚举属于 DELAYP（多项式延迟）。
• 传递性：如果优先级关系是传递的，则全局修复的唯一性变为可处理（P），尽管其他下界保持不变。

3.2 与论证的联系

一个核心的理论贡献是最优修复与论证扩展之间的精确映射：

• Pareto 最优修复：精确对应于相关 PSETAF 的稳定扩展。
• 优选扩展：在合理的假设下（具体而言，如果优先级关系是传递的或冲突是二元的），Pareto 最优修复也与优选扩展重合。
• 全局和完成修复：这些对应于稳定扩展的真子集，但目前缺乏标准论证文献中的直接类比。

3.3 基语义

受论证中基扩展的启发，作者提出了一种针对优先级知识库的新语义：

• 定义：如果查询在相关 PSETAF 的基扩展中成立，则该查询在基语义下被蕴含。
• 性质：
  • 基扩展是每一个 Pareto 最优修复的子集（即 P-IAR 的下近似）。
  • 它比最近提出的Elect语义更具生产性（包含更多断言）。
  • 复杂度：对于 $DL\text{-}Lite_{H_{horn}}$，基语义下的查询蕴含在数据复杂度中是 P 完全的。
• 实现：基扩展可以通过正规逻辑程序的良基语义来计算，或者对于固定的迭代深度，通过一阶查询（SQL）进行近似。

4. 意义与主张

本文在三个主要领域主张其重要性：

1. 复杂度格局：它阐明了虽然最优修复提供了更细致的一致性处理，但与标准修复相比，它们带来了显著的计算成本，通常将问题推向多项式层次结构的第二层。然而，它确定了具体的可处理情况（Pareto/完成蕴含、基语义）。
2. 论证桥梁：它在优先级数据库修复与抽象论证之间建立了严格的联系。通过表明 Pareto 最优修复是稳定扩展，本文将 OMQA 置于更广泛的理论背景中，允许引入论证的结果（例如，对称框架的一致性属性）。
3. 实用语义：提出基语义提供了一种可处理的不一致性处理替代方案。它提供了一种多项式时间可计算的 P-IAR 语义近似，比现有的Elect等替代方案包含更多信息。本文证明了该语义可以使用标准的逻辑编程或关系数据库系统来实现。

作者指出，虽然他们并未最终回答三种最优修复概念（Pareto、全局、完成）中哪一种“最自然”，但 Pareto 修复与稳定扩展和优选扩展的对应关系表明，采用它们具有强有力的理论依据。这项工作也为论证社区贡献了新的技术成果，例如具有传递偏好的强对称 PSETAF 的一致性。