Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part I
Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part I
复制标题
计算机科学数学基础 2014 - 第 39 届国际研讨会，MFCS 2014，匈牙利布达佩斯，2014 年 8 月 25-29 日。论文集，第一部分
DOI：
10.1007/978-3-662-44522-8_9
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Bourhis P
中科院分区：
文献类型：
--
作者：
Bourhis P
在主要的基于保护的析取存在规则类别下回答连接查询（的并集）的复杂性的完整情况最近已经解决。事实证明，这个问题非常困难，即 2ExpTime-complete，即使对于以轻量级形式表示的固定规则集也是如此。这就产生了一个问题：是否可以通过限制查询语言来降低其复杂性。为了降低诸如查询评估和查询包含之类的经典数据库问题的复杂性，已经提出了联合查询的几个子类。这种类型中最突出的三个子类是有界超树宽度的查询、有界树宽度的查询和非循环查询。本文的中心目标是了解上述查询语言是否对主要基于保护的析取存在规则类别下的查询回答复杂性产生积极影响。我们表明，有界超树宽度和有界树宽度的合取查询（并集）不会降低问题的复杂性，即使我们关注有界元数谓词或固定的析取存在规则集。关于非循环查询，虽然我们的问题总体上仍然是2ExpTime-complete，但在一些相关设置中复杂度降低到ExpTime-complete；事实上，这需要限制谓词的数量，并且对于某些基于保护的表达形式主义，需要确定规则集。
The complete picture of the complexity of answering (unions of) conjunctive queries under the main guarded-based classes of disjunctive existential rules has been recently settled. It has been shown that the problem is very hard, namely 2ExpTime-complete, even for fixed sets of rules expressed in lightweight formalisms. This gives rise to the question whether its complexity can be reduced by restricting the query language. Several subclasses of conjunctive queries have been proposed with the aim of reducing the complexity of classical database problems such as query evaluation and query containment. Three of the most prominent subclasses of this kind are queries of bounded hypertree-width, queries of bounded treewidth and acyclic queries. The central objective of the present paper is to understand whether the above query languages have a positive impact on the complexity of query answering under the main guarded-based classes of disjunctive existential rules.We show that (unions of) conjunctive queries of bounded hypertree-width and of bounded treewidth do not reduce the complexity of our problem, even if we focus on predicates of bounded arity, or on fixed sets of disjunctive existential rules. Regarding acyclic queries, although our problem remains 2ExpTime-complete in general, in some relevant settings the complexity reduces toExpTime-complete; in fact, this requires to bound the arity of the predicates, and for some expressive guarded-based formalisms, to fix the set of rules.