论文标题
有效列举本体介导的查询的答案
Efficiently Enumerating Answers to Ontology-Mediated Queries
论文作者
论文摘要
我们研究了本体介导的查询（OMQ）的答案，其中本体是一组受保护的TGD或描述逻辑ELI中的配方，查询是一个连接的查询（CQ）。除了传统的答案概念外，我们还提出并研究了两个新的部分答案的新概念，这些概念可以考虑到本体中存在量化词产生的零。我们的主要结果是，通过线性时间预处理和持续延迟的OMQ，既有无环和自由连续性cacyclic的OMQ，则可以列举传统的完整答案和两种部分答案。我们还提供部分匹配的下限。对于在线性时间内测试单个答案的相关问题以及在线性时间预处理后恒定时间测试多个答案的相关问题也获得了类似的结果。在这两种情况下，障碍性和顽固性之间的边界的特征都具有相似但略有不同的无环特性。
We study the enumeration of answers to ontology-mediated queries (OMQs) where the ontology is a set of guarded TGDs or formulated in the description logic ELI and the query is a conjunctive query (CQ). In addition to the traditional notion of an answer, we propose and study two novel notions of partial answers that can take into account nulls generated by existential quantifiers in the ontology. Our main result is that enumeration of the traditional complete answers and of both kinds of partial answers is possible with linear-time preprocessing and constant delay for OMQs that are both acyclic and free-connex acyclic. We also provide partially matching lower bounds. Similar results are obtained for the related problems of testing a single answer in linear time and of testing multiple answers in constant time after linear time preprocessing. In both cases, the border between tractability and intractability is characterized by similar, but slightly different acyclicity properties.
