---
title: "First Order-Rewritability and Containment of Conjunctive Queries in Horn Description Logics"
authors:
  - "Meghyn Bienvenu"
  - "Peter Hansen"
  - "Carsten Lutz"
  - "Frank Wolter"
doi: ""
url: "https://ijcai.org/proceedings/2016/141"
pdf: "https://ijcai.org/proceedings/2016/0141.pdf"
venue: "Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence"
year: 2016
pages: "965-970"
track: ""
keywords:
---

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

Meghyn Bienvenu, Peter Hansen, Carsten Lutz, Frank Wolter

*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.