Complexity Boundaries for Generalized Guarded Existential Rules
Complexity Boundaries for Generalized Guarded Existential Rules
复制标题
广义保护存在规则的复杂性边界
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
M. Thomazo
中科院分区：
文献类型：
--
作者：
Jean;M. Mugnier;S. Rudolph;M. Thomazo
In this report, we establish complexities of the conjunctive query entailment problem for classes of existential rules (also called Tuple-Generating Dependencies or Datalog+/- rules). Our contribution is twofold. First, we introduce the class of \emph{greedy bounded treewidth sets} \emph{(gbts)} of rules, which covers guarded rules, and their known generalizations, namely (weakly) frontier-guarded rules. We provide a generic algorithm for query entailment with \emph{gbts}, which is worst-case optimal for combined complexity with bounded predicate arity, as well as for data complexity. Secondly, we classify several \emph{gbts} classes, whose complexity was unknown, namely frontier-one, frontier-guarded and weakly frontier-guarded rules, with respect to combined complexity (with both unbounded and bounded predicate arity) and data complexity.
查询受保护的片段
DOI：
10.2168/lmcs-10(2:3)2014
发表时间：
2014
期刊：
2010 25th Annual IEEE Symposium on Logic in Computer Science
影响因子：
--
作者：
V. Barany;G. Gottlob;M. Otto
通讯作者：
M. Otto