# A Horn extension of DL-Lite with NL data complexity

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 27 references that are in the map.
- First posted on arXiv 13 May 2026.

## Builds on (most cited first, 3 of 3)

- [Nested Regular Path Queries in Description Logics](https://mlsanity.com/paper/1402.7122/) (2014)
- [GPC: A Pattern Calculus for Property Graphs](https://mlsanity.com/paper/2210.16580/) (2022)
- [Towards Practicable Algorithms for Rewriting Graph Queries beyond DL-Lite](https://mlsanity.com/paper/2405.18181/) (2024)

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

- [A General Sufficient Condition for Rewriting Horn-ALCHI Atomic Queries into GQL](https://mlsanity.com/paper/2608.04945/) (2026)

## Abstract (arXiv)

The literature on ontology-mediated query answering (OMQA) has been shaped by two key results: first-order rewritability for DL-Lite, and PTime-hardness of data complexity for essentially every description logic beyond it. This has effectively positioned DL-Lite as the only practical choice for query rewriting, restricting OMQA solutions to first-order queries and ontologies that can be rewritten into them. This AC0 vs. PTime dichotomy is especially limiting if we consider that OMQA targets graph-structured data, and that standard graph query languages (including the recent ISO standards GQL and SQL/PGQ) are typically NL-complete. Towards identifying a rich Horn DL that can be rewritten into graph query languages and that can still express many ELI and DL-Lite ontologies, we introduce a stratification mechanism for ELI that controls the interaction between conjunction and recursion. In this way, we obtain ELbotpreceq, a description logic that strictly extends the core DL-Lite, supports reachability axioms and restricted conjunction, and allows for reasoning in NL. We establish the NL upper bound via a rewriting into nested two-way regular path queries, a fragment of GQL, providing initial evidence that our ontology language is a promising candidate for extending OMQA to graph query languages.