Inproceedings3152: Unterschied zwischen den Versionen
Sru (Diskussion | Beiträge) (Die Seite wurde neu angelegt: „{{Publikation Erster Autor |ErsterAutorNachname=Jean-Francois |ErsterAutorVorname=Baget }} {{Publikation Author |Rank=2 |Author=Marie-Laure Mugnier }} {{Publikati…“) |
Sru (Diskussion | Beiträge) |
||
(2 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
Zeile 1: | Zeile 1: | ||
{{Publikation Erster Autor | {{Publikation Erster Autor | ||
− | |ErsterAutorNachname= | + | |ErsterAutorNachname=Baget |
− | |ErsterAutorVorname= | + | |ErsterAutorVorname=Jean-Francois |
}} | }} | ||
{{Publikation Author | {{Publikation Author | ||
Zeile 21: | Zeile 21: | ||
|Month=Juli | |Month=Juli | ||
|Booktitle=Proceedings of the 22nd International Joint Conference on Artificial Intelligence | |Booktitle=Proceedings of the 22nd International Joint Conference on Artificial Intelligence | ||
− | |Publisher=IJCAI | + | |Pages=712-717 |
− | | | + | |Publisher=IJCAI/AAAI |
+ | |Editor=Toby Walsh | ||
}} | }} | ||
{{Publikation Details | {{Publikation Details | ||
|Abstract=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. | |Abstract=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. | ||
+ | |Download=BMRT-IJCAI2011-walking.pdf, | ||
|Projekt=ExpresST | |Projekt=ExpresST | ||
|Forschungsgruppe=Wissensmanagement | |Forschungsgruppe=Wissensmanagement |
Aktuelle Version vom 12. August 2011, 16:36 Uhr
Walking the Complexity Lines for Generalized Guarded Existential Rules
Walking the Complexity Lines for Generalized Guarded Existential Rules
Published: 2011
Juli
Herausgeber: Toby Walsh
Buchtitel: Proceedings of the 22nd International Joint Conference on Artificial Intelligence
Seiten: 712-717
Verlag: IJCAI/AAAI
Referierte Veröffentlichung
BibTeX
Kurzfassung
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.
Download: Media:BMRT-IJCAI2011-walking.pdf
Komplexitätstheorie, Logik, Logikprogrammierung