A Horn extension of DL-Lite with NL data complexity

Ontology-mediated query answering (OMQA) has been dominated by two key results: first-order rewritability for DL-Lite, and PTime-hardness of data complexity for essentially every description logic beyond it. This AC0 vs. PTime dichotomy has 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. However, OMQA increasingly targets graph-structured data, and standard graph query languages—including the recent ISO standards GQL and SQL/PGQ—are typically NL-complete. This mismatch motivates the need for a richer Horn DL that can be rewritten into graph query languages while still expressing many ELI and DL-Lite ontologies. The authors address this gap by introducing a stratification mechanism for ELI that controls the interaction between conjunction and recursion, yielding ELbotpreceq, a description logic that strictly extends core DL-Lite, supports reachability axioms and restricted conjunction, and allows for reasoning in NL.

The main result is that ELbotpreceq enjoys NL data complexity for query answering. This is established by a rewriting into nested two-way regular path queries, which are evaluated in NL. The authors show that ELbotpreceq strictly extends DL-Lite, meaning that every DL-Lite ontology can be expressed in ELbotpreceq, but not vice versa. Furthermore, ELbotpreceq supports reachability axioms and restricted conjunction, which are not expressible in DL-Lite. The rewriting is constructive and can be implemented using standard graph query engines. The paper also demonstrates that ELbotpreceq can express many ELI ontologies, thus providing a rich formalism that bridges the gap between DL-Lite and more expressive DLs. The NL upper bound is proven by a reduction from query answering in ELbotpreceq to the evaluation of n2RPQs, which is in NL. The authors also show that the lower bound is NL-hard, making the complexity tight.