# A General Sufficient Condition for Rewriting Horn-ALCHI Atomic Queries into GQL

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 21 references that are in the map.
- First posted on arXiv 5 Aug 2026.

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

- [Graph Pattern Matching in GQL and SQL/PGQ](https://mlsanity.com/paper/2112.06217/) (2021)
- [GPC: A Pattern Calculus for Property Graphs](https://mlsanity.com/paper/2210.16580/) (2022)
- [A Complete Classification of the Complexity and Rewritability of Ontology-Mediated Queries based on the Description Logic EL](https://mlsanity.com/paper/1904.12533/) (2019)
- [Towards Practicable Algorithms for Rewriting Graph Queries beyond DL-Lite](https://mlsanity.com/paper/2405.18181/) (2024)
- [A Horn extension of DL-Lite with NL data complexity](https://mlsanity.com/paper/2605.13367/) (2026)

## Abstract (arXiv)

The emergence of the ISO standard GQL introduces a powerful query language extending first-order logic with controlled recursion, raising the question of its applicability to evaluation of ontology-mediated queries (OMQs). We focus on OMQs consisting of atomic queries over ontologies expressed in Horn-ALCHI, an expressive Description Logic that is not, in general, first-order rewritable. To address this, we introduce DL automata, a novel formalism that captures the semantics of such OMQs via runs over fact sets. We then identify a large class of DL automata that can be rewritten into unions of conjunctive two-way regular path queries (UC2RPQs), a central fragment of GQL. Our class of automata relies on a stratification of their states, ruling out specific forms of cyclic dependencies known to raise the complexity. This yields a broad class of Horn-ALCHI OMQs that are GQL-rewritable.