A Generic Querying Algorithm for Greedy Sets of Existential Rules

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche

Toggle side column

A Generic Querying Algorithm for Greedy Sets of Existential Rules

Michaël ThomazoMichaël Thomazo,  Jean-François BagetJean-François Baget,  Marie-Laure MugnierMarie-Laure Mugnier,  Sebastian RudolphSebastian Rudolph
Michaël Thomazo, Jean-François Baget, Marie-Laure Mugnier, Sebastian Rudolph
A Generic Querying Algorithm for Greedy Sets of Existential Rules
Proceedings of the 13th International Conference on the Principles of Knowledge Representation and Reasoning (KR'12), 2012. AAAI
  • KurzfassungAbstract
    Answering queries in information systems that allow for ex- pressive inferencing is currently a field of intense research. This problem is often referred to as ontology-based data ac- cess (OBDA). We focus on conjunctive query entailment un- der logical rules known as tuple-generating dependencies, existential rules or Datalog+/-. One of the most expressive decidable classes of existential rules known today is that of greedy bounded treewidth sets (gbts). We propose an algo- rithm for this class, which is worst-case optimal for data and combined complexities, with or without bound on the pred- icate arity. A beneficial feature of this algorithm is that it allows for separation between offline and online processing steps: the knowledge base can be compiled independently from queries, which are evaluated against the compiled form. Moreover, very simple adaptations of the algorithm lead to worst-case-optimal complexities for specific subclasses of gbts which have lower complexities, such as guarded rules.
  • Forschungsgruppe:Research Group: Computational LogicComputational Logic
@inproceedings{TBMR2012,
  author    = {Micha{\"{e}}l Thomazo and Jean-Fran{\c{c}}ois Baget and
               Marie-Laure Mugnier and Sebastian Rudolph},
  title     = {A Generic Querying Algorithm for Greedy Sets of Existential Rules},
  booktitle = {Proceedings of the 13th International Conference on the
               Principles of Knowledge Representation and Reasoning (KR'12)},
  publisher = {AAAI},
  year      = {2012}
}