Reasoning with the Core Chase - the Case of SHACL Validation over ELHI Knowledge Bases

Sep 15, 2026

Query answering in Description Logics often relies on certain-answer semantics, which suits languages without negation but becomes inadequate when negation is required. Core universal models provide a semantics for such queries. This paper studies evaluating SHACL expressions over the core universal model of an ℰℒℋℐ knowledge base, focusing on a fragment combining regular path navigation with semi-positive monadic Datalog. It builds a finite representation via a data-aware ℰℒℋℐ calculus and reduces SHACL validation with ontologies to plain SHACL validation, yielding tight complexity bounds matching consistency testing.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages11

Reading Time28 min

AccessFree to download

Abstract

1. Introduction

Certain answers and Horn DLs

Chase procedures and universal models

Negation and core universal models

Contributions and finite representation

Reasoning with the Core Chase: the Case of SHACL Validation over ELHI Knowledge Bases Anouk Oudshoorn1 , Magdalena Ortiz1 and Mantas Šimkus1 1 Institute of Logic and Computation, TU Wien, Austria Abstract Many approaches to query answering in Description Logics (DLs) adopt the certain answer semantics, which is natural for standard query languages without negation, but falls short when negation is involved. Since negation plays a crucial role in many applications, alternative semantics are needed. Core universal models are increasingly accepted as a means to give a semantics to queries with negation. In this paper, we consider the problem of evaluating (possibly recursive) SHACL expressions over the core universal model of an ℰℒℋℐ KB. SHACL, recently proposed as a standard constraint language for RDF data, is a natural and powerful query language, and the fragment we consider adds regular path navigation to semi-positive monadic Datalog with acyclic rule bodies. We first propose a construction of a finite representation of the core universal model, based on a novel calculus for ℰℒℋℐ that gives up the data-independence to avoid the best-case exponential behaviour of similar approaches, and which we believe can lead towards an efficient implementation. Then we leverage this finite representation to reduce validation in the presence of ontologies to plain SHACL validation, similarly to previous algorithms but avoiding their best-case exponential behaviour. Our algorithms yield tight data-and combined-complexity bounds for the studied SHACL validation problem, which coincide with plain consistency testing in ℰℒℋℐ. Keywords core chase, query rewriting, SHACL, ELHI, Horn DLs 1. Introduction Evaluating queries over description logic (DL) knowledge bases has been the subject of huge research efforts over almost two decades. Here, the certain answer semantics has played a prominent role inelegantly handling information incompleteness for large classes of queries: answering a query consists of computing the intersection of query answers over all models of the input knowledge base (KB) . This problem can easily become computationally very costly for expressive DLs, and it is provably more expensive than standard reasoning in most of the popular extensions of 􀁁ℒ􀁃 [1] . But fortunately, this computational hurdle can usually be avoided in the so-called Horn DLs, which disallow ontological statements that involve disjunction, leading in turn to the universal model property [2, 3] . This property guarantees that a consistent KB always has a model that represents all models (technically, that can be homomorphically mapped into any model) and is thus sufficient to compute the certain answers to all conjunctive queries. The universal model property is closely related to the notion of a chase procedure known from databases, originally studied for reasoning about integrity constraints [4] . There are several chase variants with different properties (e.g., oblivious, Skolem, core) [5, 6, 7], and all of them can be used to obtain a model that is universal in the sense above. Query answering is still far from trivial even when universal models exists. For standard DLs, the chase does not terminate in general and universal models can be infinite, so we need to reason about them without building them explicitly. Nevertheless, the universal model property of Horn DLs has enabled the development of several algorithms and practical implementations of query answering over large classes of positive queries, see e.g., [2, 3, 8, 9, 10, 11] and their references. DL 2024: 37th International Workshop on Description Logics, June 18 –21, 2024, Bergen, Norway $ [anouk.oudshoorn@tuwien.ac.at](anouk.oudshoorn@tuwien.ac.at) (A. Oudshoorn); [magdalena.ortiz@tuwien.ac.at](magdalena.ortiz@tuwien.ac.at) (M. Ortiz); [mantas.simkus@tuwien.ac.at](mantas.simkus@tuwien.ac.at) (M. Šimkus) 􀀚 0009-0006-4638-5948 (A. Oudshoorn); 0000-0002-2344-9658 (M.

FAQs

Why are certain-answer semantics insufficient when queries involve negation?

Because negation-as-failure allows querying about the absence of information, different universal models can yield different answers, so intersection over all models no longer provides an adequate semantics.

What role does the core universal model play in this work?

It serves as the intended semantics structure for queries with negation, representing the data and terminological axioms without superfluous elements, thereby supporting consistent evaluation.

How does the paper evaluate SHACL expressions in the studied setting?

It evaluates SHACL expressions over the core universal model of an ℰℒℋℐ knowledge base by first constructing a finite representation through a data-aware calculus and then reducing ontology-aware validation to plain SHACL validation.

Sep 15, 2026

Uploaded by Bill Black