ML Anthology

First Order-Rewritability and Containment of Conjunctive Queries in Horn Description Logics

Meghyn Bienvenu, Peter Hansen, Carsten Lutz, Frank Wolter
IJCAI 2016 pp. 965-971
/ijcai/2016/bienvenu2016ijcai-first/

Abstract

We study FO-rewritability of conjunctive queries in the presence of ontologies formulated in a description logic between EL and Horn-SHIF, along with related query containment problems. Apart from providing characterizations, we establish complexity results ranging from ExpTime via NExpTime to 2ExpTime, pointing out several interesting effects. In particular, FO-rewriting is more complex for conjunctive queries than for atomic queries when inverse roles are present, but not otherwise. PDF

PDF IJCAI Semantic Scholar

Cite

Text

Bienvenu et al. "First Order-Rewritability and Containment of Conjunctive Queries in Horn Description Logics." International Joint Conference on Artificial Intelligence, 2016.

Markdown

[Bienvenu et al. "First Order-Rewritability and Containment of Conjunctive Queries in Horn Description Logics." International Joint Conference on Artificial Intelligence, 2016.](https://mlanthology.org/ijcai/2016/bienvenu2016ijcai-first/)

BibTeX

@inproceedings{bienvenu2016ijcai-first,
  title     = {{First Order-Rewritability and Containment of Conjunctive Queries in Horn Description Logics}},
  author    = {Bienvenu, Meghyn and Hansen, Peter and Lutz, Carsten and Wolter, Frank},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2016},
  pages     = {965-971},
  url       = {https://mlanthology.org/ijcai/2016/bienvenu2016ijcai-first/}
}