Tractable Query Answering for Expressive Ontologies and Existential Rules

David CarralDavid Carral, Irina DragosteIrina Dragoste, Markus KrötzschMarkus Krötzsch

David Carral, Irina Dragoste, Markus Krötzsch
Tractable Query Answering for Expressive Ontologies and Existential Rules
In Claudia d'Amato, Miriam Fernández, Valentina A. M. Tamma, Freddy Lécué, Philippe Cudré-Mauroux, Juan F. Sequeda, Christoph Lange, Jeff Heflin, eds., Proceedings of the 16th International Semantic Web Conference (ISWC'17), volume 10587 of LNCS, 2017. Springer

Details
Bibtex

KurzfassungAbstract
The disjunctive skolem chase is a sound and complete (albeit non-terminating) algorithm that can be used to solve conjunctive query answering over DL ontologies and programs with disjunctive existential rules. Even though acyclicity notions can be used to ensure chase termination for a large subset of real-world knowledge bases, the complexity of reasoning over acyclic theories still remains high. Hence, we study several restrictions which not only guarantee chase termination but also ensure polynomiality. We include an evaluation that shows that almost all acyclic DL ontologies do indeed satisfy these general restrictions.
Bemerkung: Note: This paper has been nominated for the Best Research Paper Award at ISWC 2017.
Projekt:Project: DIAMOND, HAEC B08, Cfaed
Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-68288-4_10.

@inproceedings{CDK2017,
  author    = {David Carral and Irina Dragoste and Markus Kr{\"{o}}tzsch},
  title     = {Tractable Query Answering for Expressive Ontologies and
               Existential Rules},
  editor    = {Claudia {d'Amato} and Miriam Fern{\'{a}}ndez and Valentina A. M.
               Tamma and Freddy L{\'{e}}cu{\'{e}} and Philippe
               Cudr{\'{e}}-Mauroux and Juan F. Sequeda and Christoph Lange and
               Jeff Heflin},
  booktitle = {Proceedings of the 16th International Semantic Web Conference
               (ISWC'17)},
  series    = {LNCS},
  volume    = {10587},
  publisher = {Springer},
  year      = {2017},
  doi       = {10.1007/978-3-319-68288-4_10}
}