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

Download

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

Details
Bibtex

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}
}