根据正负例自动学习满足条件的本体，解决知识库查询匹配问题。
Fitting Description Logic Ontologies to ABox and Query Examples
- 基于正负示例构建满足查询条件的本体，使用ALC和ALCI逻辑语言。
- 原子查询和全合取查询下问题为CO-NP，合取与并查询下为2E-EXPTIME完全。
- 适用于知识图谱补全、语义推理等需要精确查询匹配的场景。
我们研究了一个受本体媒介查询启发的拟合问题：给定一组形式为$(\mathcal{A},q)$的正负示例，其中$\mathcal{A}$是一个ABox，$q$是布尔查询，目标是寻找一个本体$\mathcal{O}$，使得对所有正例有$\mathcal{A} \cup \mathcal{O} \vDash q$，对所有负例有$\mathcal{A} \cup \mathcal{O} \not\vDash q$。我们考虑以描述逻辑$\mathcal{ALC}$和$\mathcal{ALCI}$作为本体语言，并涵盖原子查询（AQ）、合取查询（CQ）及其并集（UCQ）在内的多种查询语言。针对所有组合，我们提供了有效的刻画，并确定了判断是否存在拟合本体的计算复杂度。结果表明，对于原子查询和全合取查询，该问题是CO-NP；而对于合取查询和并查询，其复杂度为2E-EXPTIME完全。这些结论在$\mathcal{ALC}$和$\mathcal{ALCI}$下均成立。
原文摘要 · Abstract (English)
We study a fitting problem inspired by ontology-mediated querying: given a collection of positive and negative examples of the form $(\mathcal{A},q)$ with $\mathcal{A}$ an ABox and $q$ a Boolean query, we seek an ontology $\mathcal{O}$ that satisfies $\mathcal{A} \cup \mathcal{O} \vDash q$ for all positive examples and $\mathcal{A} \cup \mathcal{O}\not\vDash q$ for all negative examples. We consider the description logics $\mathcal{ALC}$ and $\mathcal{ALCI}$ as ontology languages and a range of query languages that includes atomic queries (AQs), conjunctive queries (CQs), and unions thereof (UCQs). For all of the resulting fitting problems, we provide effective characterizations and determine the computational complexity of deciding whether a fitting ontology exists. This problem turns out to be ${\scriptsize CO}NP$ for AQs and full CQs and $2E{\scriptsize XP}T{\scriptsize IME}$-complete for CQs and UCQs. These results hold for both $\mathcal{ALC}$ and $\mathcal{ALCI}$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。