arXiv:2511.07095cs.AI2025-11AAAI被引 1

提出加权描述逻辑查询的新复杂度分析,发现特定场景下可实现最低数据复杂度。

Data Complexity of Querying Description Logic Knowledge Bases under Cost-Based Semantics

  • 基于代价语义定义查询答案,通过最小化违反公理的代价来判断真值
  • 在固定代价约束下,DL-Lite^H_bool 的实例查询和合取查询可实现TC₀复杂度
  • 首次精确刻画最优代价确然答案的复杂度,突破原有不可计算困境

本文研究在新提出的基于代价的语义下,不一致加权描述逻辑知识库的查询数据复杂度。核心思想是根据违反公理和断言的权重为每个解释分配代价,通过考虑具有最优或有界代价的所有(或某些)解释来确定确然和可能的查询答案。尽管早期研究仅限于介于$$\mathcal{EL}_\bot$和$$\mathcal{ALCO}$之间的描述逻辑,本文扩展至包含逆关系和角色包含的描述逻辑,覆盖了重要的DL-Lite方言。我们的数据复杂度分析显著超越现有成果:强化了多个下界,并精确定位了最优代价确然答案语义的精确复杂度(此前无非平凡上界)。更关键的是,尽管已有结果普遍表明基于代价语义的不可计算性,但本文最令人惊讶的结果表明:当使用$$\text{DL-Lite}^\mathcal{H}_\mathsf{bool}$本体且固定代价上限时,实例查询的确实答案与合取查询的可能答案可通过一阶重写计算,因而达到最低可能的数据复杂度$$\mathsf{TC}_0$。

原文摘要 · Abstract (English)

In this paper, we study the data complexity of querying inconsistent weighted description logic (DL) knowledge bases under recently-introduced cost-based semantics. In a nutshell, the idea is to assign each interpretation a cost based upon the weights of the violated axioms and assertions, and certain and possible query answers are determined by considering all (resp. some) interpretations having optimal or bounded cost. Whereas the initial study of cost-based semantics focused on DLs between $\mathcal{EL}_\bot$ and $\mathcal{ALCO}$, we consider DLs that may contain inverse roles and role inclusions, thus covering prominent DL-Lite dialects. Our data complexity analysis goes significantly beyond existing results by sharpening several lower bounds and pinpointing the precise complexity of optimal-cost certain answer semantics (no non-trivial upper bound was known). Moreover, while all existing results show the intractability of cost-based semantics, our most challenging and surprising result establishes that if we consider $\text{DL-Lite}^\mathcal{H}_\mathsf{bool}$ ontologies and a fixed cost bound, certain answers for instance queries and possible answers for conjunctive queries can be computed using first-order rewriting and thus enjoy the lowest possible data complexity ($\mathsf{TC}_0$).

知识库描述逻辑复杂度分析代价语义

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。