Inproceedings3152: Unterschied zwischen den Versionen

Aus Aifbportal
Wechseln zu:Navigation, Suche
(Die Seite wurde neu angelegt: „{{Publikation Erster Autor |ErsterAutorNachname=Jean-Francois |ErsterAutorVorname=Baget }} {{Publikation Author |Rank=2 |Author=Marie-Laure Mugnier }} {{Publikati…“)
Zeile 1: Zeile 1:
{{Publikation Erster Autor
{{Publikation Erster Autor
{{Publikation Author
{{Publikation Author

Version vom 31. März 2011, 18:56 Uhr

Walking the Complexity Lines for Generalized Guarded Existential Rules

Walking the Complexity Lines for Generalized Guarded Existential Rules

Published: 2011 Juli

Buchtitel: Proceedings of the 22nd International Joint Conference on Artificial Intelligence
Verlag: IJCAI 2011

Referierte Veröffentlichung
Note: to appear


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 greedy bounded treewidth sets (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 gbts, which is worst-case optimal for combined complexity with bounded predicate arity, as well as for data complexity. Secondly, we classify several 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.






Komplexitätstheorie, Logik, Logikprogrammierung