Ontology-Mediated Queries Combined Complexity and Succinctness of Rewritings via Circuit Complexity
Ontology-Mediated Queries Combined Complexity and Succinctness of Rewritings via Circuit Complexity
复制标题
本体介导的查询通过电路复杂性结合了重写的复杂性和简洁性
DOI：
10.1145/3191832
复制
发表时间：
2018
影响因子：
2.5
通讯作者：
Bienvenu M
中科院分区：
文献类型：
--
作者：
Bienvenu M
我们给出了解决方案的两个基本的计算问题，基于本体的数据访问与W3C标准本体语言OWL 2 QL：简洁性问题的一阶重写的本体介导的查询（OMQ）和复杂性问题的OMQ回答。我们分类OMQs根据他们的合取查询的形状（树宽，叶子的数量）和存在的深度，他们的本体。对于这些类中的每一个，我们确定OMQ回答的组合复杂性，以及类中的所有OMQ是否具有多项式大小的一阶，正存在和非递归数据重写。我们得到简洁的结果，使用超图程序，一个新的计算模型的布尔函数，这使得它有可能连接的大小OMQ重写和电路的复杂性。
We give solutions to two fundamental computational problems in ontology-based data access with the W3C standard ontology languageOWL 2 QL: the succinctness problem for first-order rewritings of ontology-mediated queries (OMQs) and the complexity problem for OMQ answering. We classify OMQs according to the shape of their conjunctive queries (treewidth, the number of leaves) and the existential depth of their ontologies. For each of these classes, we determine the combined complexity of OMQ answering and whether all OMQs in the class have polynomial-size first-order, positive existential, and nonrecursive datalog rewritings. We obtain the succinctness results using hypergraph programs, a new computational model for Boolean functions, which makes it possible to connect the size of OMQ rewritings and circuit complexity.