为关系结构设计匹配的本体与约束，精确确定计算复杂度与构造方法。
Fitting Ontologies and Constraints to Relational Structures
- 基于正负例数据结构，研究本体与依赖规则的适配算法。
- 揭示了各类语言在适配时的计算复杂度与最小规模限制。
- 适用于知识图谱构建与逻辑推理，尤其关注可有限基的场景。
我们研究如何将本体与约束适配到由有限关系结构构成的正负样本上。采用描述逻辑$\ ext{EL}$和$\ ext{ELI}$，以及多种元组生成依赖（TGDs）：全、守护、前导守护、前导一元及无限制TGDs，还包括包含依赖。本文精确定位了各类语言的计算复杂性，设计了相应算法，并分析了适配本体与TGD的大小。同时探讨了为给定有限结构集构造概念蕴含或TGD的有限基问题。结果显示，$\ ext{EL}$、$\ ext{ELI}$、守护型TGDs和包含依赖存在有限基，而全、前导守护和前导一元型TGDs一般不存在有限基。
原文摘要 · Abstract (English)
We study the problem of fitting ontologies and constraints to positive and negative examples that take the form of a finite relational structure. As ontology and constraint languages, we consider the description logics $\mathcal{E\mkern-2mu L}$ and $\mathcal{E\mkern-2mu LI}$ as well as several classes of tuple-generating dependencies (TGDs): full, guarded, frontier-guarded, frontier-one, and unrestricted TGDs as well as inclusion dependencies. We pinpoint the exact computational complexity, design algorithms, and analyze the size of fitting ontologies and TGDs. We also investigate the related problem of constructing a finite basis of concept inclusions / TGDs for a given set of finite structures. While finite bases exist for $\mathcal{E\mkern-2mu L}$, $\mathcal{E\mkern-2mu LI}$, guarded TGDs, and inclusion dependencies, they in general do not exist for full, frontier-guarded and frontier-one TGDs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。