Umeå universitets logga

The Shapes Constraint Language (SHACL) is a recent W3C recommendation for validating RDF graphs against shape constraints to be checked on target nodes of the data graph. The standard also describes the notion of validation reports for data graphs that violate given constraints, which aims to provide feedback on how the data graph can be fixed to satisfy the constraints. Since the specification left it open to SHACL processors to define such explanations, a recent work proposed the use of explanations in the style of database repairs, where a repair is a set of additions to or deletions from the data graph so that the resulting graph validates against the constraints. In this paper, we study such repairs for non-recursive SHACL, the largest fragment of SHACL that is fully defined in the specification. We propose an algorithm to compute repairs by encoding the explanation problem – using Answer Set Programming (ASP) – into a logic program, the answer sets of which correspond to (minimal) repairs. We then study a scenario where it is not possible to simultaneously repair all the targets, which may be often the case due to overall unsatisfiability or conflicting constraints. We introduce a relaxed notion of validation, which allows to validate a (maximal) subset of the targets and adapt the ASP translation to take into account this relaxation. Our implementation in Clingo is – to the best of our knowledge – the first implementation of a repair generator for SHACL.

A key prerequisite for the successful adoption of the Shapes Constraint Language (SHACL)—the W3C standardized constraint language for RDF graphs—is the availability of automated tools that efficiently validate targeted constraints (known as shapes graphs) over possibly very large RDF graphs. There are already significant efforts to produce optimized engines for SHACL validation, but they focus on restricted fragments of SHACL. For unrestricted SHACL, that is SHACL with unrestricted recursion and negation, there is no validator beyond a proof-of-concept prototype, and existing techniques are inherently incompatible with the goal-driven approaches being pursued by existing validators. Instead they require a global computation on the entire data graph that is not only computationally very costly, but also brittle, and can easily result in validation failures due to conflicts that are irrelevant to the validation targets. To address these challenges, we present a ‘magic’ transformation— based on Magic Sets as known from Logic Programming—that transforms a SHACL shapes graph S into a new shapes graph S′ whose validation considers only the relevant neighbourhood of the targeted nodes. The new S′ is equivalent to S whenever there are no conflicts between the constraints and the data, and in case the validation of S fails due to conflicts that are irrelevant to the target, S′ may still admit a lazy, target-oriented validation. We implement the algorithm and run preliminary experiments, showing our approach can be a stepping stone towards validators for full SHACL, and that it can significantly improve the performance of the only prototype validator that currently supports full recursion and negation.

This extended abstract summarizes our recent work [1] on SHACL validation in the presence of OWL 2 QL ontologies. To overcome the challenge posed by the non-monotonic behavior of SHACL constraints, we propose a new intuitive validation semantics and a rewriting algorithm that embeds the effects of the ontological axioms into the SHACL constraints. We analyze the complexity of validation in this setting.

OWL and SHACL are two prominent W3C standards for managing RDF graphs, the data model of the Web. They are used for different purposes and make different assumptions about the completeness of data: SHACL is used for expressing integrity constraints on complete data, while OWL allows inferring implicit facts from incomplete data; SHACL reasoners perform validation, while OWL reasoners do logical inference. Integrating these two tasks into one uniform approach is a relevant but challenging problem. The SHACL standard envisions graph validation in combination with OWL entailment, but it does not provide technical guidance on how to realize this. To address this problem, we propose a new intuitive semantics for validating SHACL constraints with OWL 2 QL ontologies based on a suitable notion of the chase. We propose an algorithm that rewrites a set of recursive SHACL constraints (with stratified negation) and an OWL 2 QL ontology into a stand-alone set of SHACL constraints that preserves validation for every input graph, which can in turn be evaluated using an off-the-shelf SHACL validator. We show that validation in this setting is EXPTIME-complete in combined complexity, but only PTIME-complete in data complexity, i.e., if the constraints and the ontology are fixed.

Circumscription is a prominent approach to bring non-monotonicity to Description Logics (DLs), but unfortunately, it usually displays very high computational complexity of reasoning. Many works have studied circumscribed DLs, but most of them focus on expressive DLs containing ALC, and the results for low-complexity DLs are limited. This paper summarises some recent progress in characterizing the computational complexity of reasoning in circumscribed DL-Lite. We perform a two-dimensional analysis, considering different languages of the DL-Lite family, and varying how concepts and roles are treated. In addition to classical circumscription, we consider the recently studied pointwise circumscription, which shows better complexity, in some cases, and remains decidable in the presence of minimized roles.

Extending the OBDA approach - where multiple data sources are exposed to users via a unified conceptual schema based on description logics - to also cover temporal reasoning has been a long standing goal, with many proposals over the last decades. To the best of our knowledge, these have yet to yield results in the form of systems or prototypes. As part of our ongoing work towards practical applicability, we identify here a number of key problems, which we believe have not been addressed suitably by previous works. Among these is the ability to deal with heterogeneous representations of time, the ability to deal with temporal inconsistencies, either due to missing value samples or conflicting values for a given time point and finally we also seek a suitable query language, where we in particular want compositionality - the ability to use the output of queries to form new temporal views on the data. We present here our initial ideas on how to meet these challenges.

W3C has recently introduced SHACL as a new standard for integrity constraints on RDF graphs. Unfortunately, the standard defines the semantics of non-recursive constraints only, which has spurred recent research efforts into finding a suitable, mathematically crisp semantics for constraints with cyclic dependencies. To this end, Corman et al. [1] introduced a semantics related to supported models known in logic programming, while Andresel et al. [2] presented a semantics based on stable models known in Answer Set Programming (ASP). In this paper, we argue that recursive SHACL can be naturally equipped with a semantics inspired in the well-founded semantics for (recursive) DATALOG queries with default negation. This semantics is not only intuitive, but it is also computationally tractable, unlike the previous proposals. To draw a connection with the classic definition of well-founded semantics in logic programming, we provide a simple translation of recursive SHACL under the well-founded semantics into propositional logic programs under the well-founded semantics. This translation is not only of theoretical interest: It can be efficiently implemented using the functionality of standard RDF triple stores (specifically, by issuing a small number of SPARQL queries), followed by an efficient evaluation using an existing engine for computing the well-founded model of a propositional logic program.

Circumscription is one of the most powerful ways to extend Description Logics (DLs) with non-monotonic reasoning features, albeit with huge computational costs and undecidability in many cases. In this paper, we introduce pointwise circumscription for DLs, which is not only intuitive in terms of knowledge representation, but also provides a sound approximation of classic circumscription and has reduced computational complexity. Our main idea is to replace the second-order quantification step of classic circumscription with a series of (pointwise) local checks on all domain elements and their immediate neighbourhood. Our main positive results are for ontologies in DLs ALCIO and ALCI: we prove that for TBoxes of modal depth 1 (i.e. without nesting of existential or universal quantifiers) standard reasoning problems under pointwise circumscription are (co)NEXPTIME-complete and EXPTIMEcomplete, respectively. The restriction of modal depth still yields a large class of ontologies useful in practice, and it is further justified by a strong undecidability result for pointwise circumscription with general TBoxes in ALCIO.

Circumscription is one of the major approaches to bring non-monotonic (common-sense) reasoning features to first-order logic and related formalisms, and it has already received attention in Description Logics (DLs), with the focus on understanding the computational complexity of reasoning. Those studies revealed that circumscription causes a dramatic increase in computational complexity in a broad range of DLs. In this paper, we consider a new notion of circumscription in DLs, aiming to preserve the key ideas and advantages of classical circumscription while mitigating its impact on the computational complexity of reasoning. Our main idea is to replace the second-order quantification step with a series of (pointwise) local checks on all domain elements and their immediate neighborhood. This approach provides a sound approximation of classical circumscription and is closely related to the notion of pointwise circumscription proposed by Lifschitz for first-order logic. Our main achievement is to show that, under certain syntactic restrictions, standard reasoning problems like subsumption testing or concept satisfiability for AℒCℐO KBs with pointwise circumscription are (co)NExpTime-complete.

This paper studies a stable model semantics for Description Logic (DL) knowledge bases (KBs) and for (possibly cyclic) terminologies, ultimately showing that terminologies under the proposed semantics can be equipped with effective reasoning algorithms. The semantics is derived using Quantified Equilibrium Logic, and-in contrast to the usual semantics of DLs based on classical logic-supports default negation and allows to combine the open-world and the closed-world assumptions in a natural way. Towards understanding the computational properties of this and related formalisms, we show a strong undecidability result that applies not only to KBs under the stable model semantics, but also to the more basic setting of minimal model reasoning. Specifically, we show that concept satisfiability in minimal models of an ALCIO KB is undecidable. We then turn our attention to (possibly cyclic) DL terminologies, where ontological axioms are limited to definitions of concept names in terms of complex concepts. This restriction still yields a very rich setting. We show that standard reasoning problems, like concept satisfiability and subsumption, are EXPTIME-complete for terminologies expressed in ALCI under the stable model semantics.

Ontology-based data access (OBDA) facilitates access to heterogeneous data sources through the mediation of an ontology (e.g. OWL), which captures the domain of interest and is connected to data sources through a declarative mapping. In our study, large, heterogeneous earth observational (EO) data, known as raster data, and geometrical data, known as vector data, are considered as (heterogeneous) data sources. Raster data represent, e.g., Earth's natural phenomena, such as surface temperature, elevation, or air pollution, as multidimensional arrays. In contrast, vector data depict, e.g., locations, networks, or regions on Earth, using geometries. Domain experts, such as earth scientists and GIS practitioners, still struggle to undertake advanced studies by querying large raster and vector data in an integrated way because, unlike relational data, they come in diverse formats and different data structures. In our approach to integration, we use a geospatial extension of an RDBMS to represent vector data as relational data, and a domain-agnostic array DBMS to handle raster data. Our aim is to extend the OBDA paradigm to effectively deal with relational, vector, and raster data in a combined way, while leveraging the built-in capabilities of data management tools relevant to each type of data. We also plan to develop techniques to calculate on the fly for each user query posed over the ontology an optimal query plan that exploits, at best, the query processing capabilities of each tool, while limiting costly data transfer operations between tools.

We study the relative expressiveness of ontology-mediated queries (OMQs) formulated in the expressive Description Logic ALCHOIQ extended with closed predicates. In particular, we present a polynomial time translation from OMQs into Datalog with negation under the stable model semantics, the formalism that underlies Answer Set Programming. This is a novel and non-trivial result: the considered OMQs are not only non-monotonic, but also feature a tricky combination of nominals, inverse roles, and counting. We start with atomic queries and then lift our approach to a large class of first-order queries where quantification is “guarded” by closed predicates. Our translation is based on a characterization of the query answering problem via integer programming, and a specially crafted program in Datalog with negation that finds solutions to dynamically generated systems of integer inequalities. As an important by-product of our translation we get that the query answering problem is co-NP-complete in data complexity for the considered class of OMQs. Thus, answering these OMQs in the presence of closed predicates is not harder than answering them in the standard setting. This is not obvious as closed predicates are known to increase data complexity for some existing ontology languages.

The complexity and relative expressiveness of Ontology-mediated Queries (OMQs) is quite well understood by now. In this paper, we study the expressive power of OMQs from a descriptive complexity perspective, where the central question is to understand whether a given OMQ language is powerful enough to express all queries that can be computed within some bound on time or space. We show that the OMQ language that pairs instance queries with ontologies in the very expressive DL ALCHOI with closed predicates cannot express all coNP-computable Boolean queries, despite being coNP-complete in data complexity. We, then, propose an extension of this OMQ language that is expressive enough to precisely capture the class of all Boolean queries computable in coNP. This involves adding functionality as well as path expressions and nominal schemata, which are restricted in a way that allows us to carefully incorporate them into the existing mosaic technique for the DL ALCHOIF with closed predicates without affecting the coNP upper bound in data complexity.

This paper is an extended abstract of our recent work on proposing a stable model semantics for Description Logic terminologies. Our semantics is based on Quantified Equilibrium Logic and overcomes some limitations of previous approaches. We prove that standard reasoning problems w.r.t. terminologies in AℒCℐ under the stable model semantics are decidable in deterministic single exponential time. In contrast, we show that concept satisfiability w.r.t. general KBs in AℒCℐ under the stable model semantics is undecidable.

The field of Virtual Knowledge Graphs (VKGs) continues to grow in both academic and applied contexts. Yet, the issue of updates in VKG systems has not yet received adequate attention, although it is crucial to manage data modifications at the data source level through the lens of an ontology. In this paper, we focus on VKGs whose ontology is specified in the lightweight ontology language DL-LiteA, and we propose diverse settings and research directions we intend to explore to address the challenge of translating ontology-based updates into updates at the level of data sources. We also pay attention to the important problem of automated analysis of mappings, which plays a major role when it comes to reformulating ontology-based update requests into update requests over the data sources.