论文标题
边境保护本体介导的查询的一阶重写能力
First-Order Rewritability of Frontier-Guarded Ontology-Mediated Queries
论文作者
论文摘要
我们专注于基于（边界）保护的存在规则和（工会）连接性查询的本体介导的查询（OMQ），我们研究了FO-剥夺性的问题，即是否可以将OMQ重写为一阶查询。我们采用两种不同的方法。第一种方法采用标准的双向交替平均树自动机。尽管它不会导致紧密的复杂性绑定，但它提供了基于广为人知的工具的透明解决方案。第二种方法依赖于复杂的自动机模型，称为COST AUTOMATA。这使我们能够证明我们的问题是2Exptime-Complete。在这两种方法中，我们都提供了具有独立利益的FO-剥夺性的语义特征。
We focus on ontology-mediated queries (OMQs) based on (frontier-)guarded existential rules and (unions of) conjunctive queries, and we investigate the problem of FO-rewritability, i.e., whether an OMQ can be rewritten as a first-order query. We adopt two different approaches. The first approach employs standard two-way alternating parity tree automata. Although it does not lead to a tight complexity bound, it provides a transparent solution based on widely known tools. The second approach relies on a sophisticated automata model, known as cost automata. This allows us to show that our problem is 2ExpTime-complete. In both approaches, we provide semantic characterizations of FO-rewritability that are of independent interest.
