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

Bienvenu, Meghyn; Hansen, Peter; Lutz, Carsten; Wolter, Frank

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

Meghyn Bienvenu, Peter Hansen, Carsten Lutz, Frank Wolter

Download BibTeX Cite

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 965-970.

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.

Meghyn Bienvenu, Peter Hansen, Carsten Lutz, and Frank Wolter. 2016. First Order-Rewritability and Containment of Conjunctive Queries in Horn Description Logics. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16. IJCAI, 965–970. https://ijcai.org/proceedings/2016/141

@inproceedings{ijcai2016p141,
  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 = {Proceedings of the Twenty-Fifth International Joint Conference on
               Artificial Intelligence, {IJCAI-16}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Subbarao Kambhampati},
  pages     = {965--970},
  year      = {2016},
  month     = {7},
  url       = {https://ijcai.org/proceedings/2016/141},
}

TY  - CPAPER
TI  - First Order-Rewritability and Containment of Conjunctive Queries in Horn Description Logics
AU  - Bienvenu, Meghyn
AU  - Hansen, Peter
AU  - Lutz, Carsten
AU  - Wolter, Frank
T2  - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2016
SP  - 965
EP  - 970
UR  - https://ijcai.org/proceedings/2016/141
ER  -