May, 2022

基于本体的有界团宽数据库查询

PDF
TL;DR本研究从参数复杂性角度研究了在有界团宽度的数据库上对本体中介查询 (OMQ) 的评估，研究了原子查询 (AQ)、连通查询 (CQ) 和连通查询的联合，发现所有 OMQ 问题都是固定参数线性 (FPL) 的，其参数是 OMQ 大小加上团宽度，我们的主要贡献是详细分析了运行时间对参数的依赖，展示了几个有趣的影响。
ontology-mediated queriesparameterized complexity theorydescription logicsconjunctive queriescliquewidth
发现论文，激发创造
  • 具有传递角色的表达能力描述逻辑中的有限查询回答

    该研究探讨了有限本体中介查询应答的问题，使用 DLs 描述逻辑中的联合，当仅考虑本体的有限模型时，研究 FOMQA 是相关的，本研究显示了 SOIF 的三个适当片段的 FOMQA 具有可决定性，这是基于模型的特定规律，开发了自动机决策程序。

    Aug, 2018

  • 线性时态逻辑中本体导向查询的一阶重写性

    本研究探索基于本体的时间数据访问，并通过证明重写为具有内置线性顺序的一阶逻辑或关系原始递归机制保证其电路复杂度，建立了包括正 LTL 公式、单调 MFO（<）公式和任意 MFO（<）公式在内的 OM ​​问题一系列查询的层次结构，从而为基于本体的访问提供了基础。

    Apr, 2020

  • 面向易处理本体中介查询应答的通用语言

    本文研究了三类 OMQA 语言，并提出了一种新的性质，locality，用于近似一阶重写。证明了对于每一类 OMQA 语言并不存在通用的语言，但是存在一种包含离散嵌入依赖的语言可以表示 OMQA 语言簇。

    Nov, 2019

  • ALC 本体上有限封装的 UCRPQs

    研究了基于本体的查询的有限包含问题，考虑了扩展了联合的连通查询类的表达性查询语言 UCRPQs，并通过介绍确定性有限自动机来决定解释的分层结构，证明了 ALC 下 UCRPQs 的紧 2EXPTIME 上界。

    Apr, 2022

  • 基于本体的数据访问：通过 Disjunctive Datalog、CSP 和 MMSNP 的研究

    本文研究了本体基础数据查询的各种类别，包括关系数据库查询与本体、描述逻辑或其他相关一阶逻辑和联结查询。研究结果包括三个方面，首先用不相交的 Datalog 片段来表达了本体中介查询的表达能力。其次，本体中介查询与约束满足问题（CSP）及其逻辑泛化 MMSNP 公式有密切联系。最后，利用这些联系得出了有关本体中介查询的新结果，如 i）本体中介查询的一阶重写和 Datalog 重写，ii）本体中介查询的 P / NP 二分法，以及 iii）本体中介查询的查询包容性问题。

    Jan, 2013

  • 查询约简描述逻辑知识库

    本文证明了在围绕述及 DL 知识库上进行的 (U) CQ 评估的可决定性，并获得了从 ALCHIO 通过 EL 到各种版本的 DL-Lite 等各种 DL 的组合复杂性和数据复杂性的相当完整的图片。

    Jun, 2023

  • 本体查询：重写与优化 (扩展版)

    本文研究了本体查询中的查询重写和查询优化问题，其中查询重写包括将本体查询编译为与底层关系型数据库等效的查询，查询优化旨在改善此过程以生成成本效益高的 UCQ 重写，提出了一种有效的新方法以支持基于线性 Datalog+/- 的规则。

    Dec, 2011

  • 在模糊 DL-Lite 本体上回答模糊查询

    研究了在模糊 DL-Lite 本体中，如何回答 CNF 查询和阈值查询的问题，并通过重写方法表明阈值查询回答在数据复杂度上始终保持在 AC0 中，但是组合查询回答高度依赖于所选的三角范数，这对基础语义产生影响。

    Nov, 2021

  • 轻量级描述逻辑本体的精确学习

    该论文研究了使用 Angluin 等人的准确查询学习框架来学习描述逻辑本体的问题，证明了可以用多项式大小的多项式查询来学习用 DL-Lite 描述逻辑和某些和 OWL 2 RL 相关的 EL 片段描述的本体，但即使只允许非循环本体，也不能用多项式大小的查询来学习用 EL 描述逻辑描述的本体。

    Sep, 2017

  • 联结查询反向工程问题的复杂性

    本文研究了解决共识查询相关反向工程问题的复杂性，并提出了基于量子比较的松弛方法来降低复杂度。最终得出了基于共识查询树宽度的 QBE 的可行性和闭合性条件，并将其应用于图数据库的查询问题。

    Jun, 2016