# Computing FO-Rewritings in EL in Practice: from Atomic to Conjunctive Queries

arXiv: https://arxiv.org/abs/1804.06907 · HTML: https://mlsanity.com/paper/1804.06907/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Apr 2018.

## Built on by (most cited first, 1 of 1)

- [Tractable Responsibility Measures for Ontology-Mediated Query Answering](https://mlsanity.com/paper/2507.23191/) (2025)

## Abstract (arXiv)

A prominent approach to implementing ontology-mediated queries (OMQs) is to rewrite into a first-order query, which is then executed using a conventional SQL database system. We consider the case where the ontology is formulated in the description logic EL and the actual query is a conjunctive query and show that rewritings of such OMQs can be efficiently computed in practice, in a sound and complete way. Our approach combines a reduction with a decomposed backwards chaining algorithm for OMQs that are based on the simpler atomic queries, also illuminating the relationship between first-order rewritings of OMQs based on conjunctive and on atomic queries. Experiments with real-world ontologies show promising results.