Stage-oe-small.jpg

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…“)
 
 
(2 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 1: Zeile 1:
 
{{Publikation Erster Autor
 
{{Publikation Erster Autor
|ErsterAutorNachname=Jean-Francois
+
|ErsterAutorNachname=Baget
|ErsterAutorVorname=Baget
+
|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 2011
+
|Pages=712-717
|Note=to appear
+
|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

Projekt

ExpresST



Forschungsgruppe

Wissensmanagement


Forschungsgebiet

Komplexitätstheorie, Logik, Logikprogrammierung