Mixing Materialization and Query Rewriting for Existential Rules

Michaël ThomazoMichaël Thomazo, Sebastian RudolphSebastian Rudolph

Michaël Thomazo, Sebastian Rudolph
Mixing Materialization and Query Rewriting for Existential Rules
Proceedings of the 21st European Conference on Artificial Intelligence (ECAI'14), 897-902, 2014. IOS Press

Details
Bibtex

KurzfassungAbstract
Ontology-Based Data Access (OBDA) is a recent paradigm aiming at enhancing data access by taking ontological knowledge into account. When using existential rules as ontological language, query answering is an undecidable problem, whence numerous decidable classes of ontologies have been defined, ranging from classes with very good computational complexities (AC0 in data complexity) to classes with much larger expressivity. However, actually implementable algorithms have been proposed only for very restricted classes (typically those coinciding with lightweight description logics). The aim of this paper is to show how to deal with more expressive ontologies by proposing an algorithm that performs both materialization and rewriting and is applicable for a significant generalization of lightweight description logics. To this end, we first modify an existing algorithm previously proposed for a very generic class of rules, namely greedy bounded treewidth sets of rules. We then exhibit a special case, called pattern oblivious rule sets, which significantly generalizes the ELHdr description logic, which underlies the OWL 2 EL ontology standard, while keeping the beneficial worst-case computational complexity. We last define a subclass of pattern oblivious rules that is recognizable in polynomial time.
Forschungsgruppe:Research Group: Computational LogicComputational Logic

@inproceedings{TR2014,
  author    = {Micha{\"{e}}l Thomazo and Sebastian Rudolph},
  title     = {Mixing Materialization and Query Rewriting for Existential Rules},
  booktitle = {Proceedings of the 21st European Conference on Artificial
               Intelligence (ECAI'14)},
  publisher = {IOS Press},
  year      = {2014},
  pages     = {897-902},
  doi       = {10.3233/978-1-61499-419-0-897}
}