ABSTRACT. Reasoning with minimal models has always been at the core of many knowledge representation techniques, but we still have only a limited understanding of this problem in Description Logics (DLs). Minimization of some selected predicates - letting the remaining predicates vary or be fixed, as proposed in circumscription - has been explored and exhibits high complexity. The case of `pure' minimal models, where the extension of all predicates must be minimal, has remained largely uncharted. In this extended abstract, we report on our recent contribution addressing this problem in popular lightweight DLs. Surprisingly we show that concept satisfiability in minimal models is undecidable already for EL. This undecidability also extends to a very restricted fragment of tuple-generating dependencies. To regain decidability, we impose acyclicity conditions on the TBox that bring the worst-case complexity below double exponential time. We conclude with a brief excursion to the DL-Lite family, establishing ExpSpace-hardness already for DL-Lite-horn.

ABSTRACT. Abduction is the task of computing a sufficient extension of a knowledge base (KB) that entails a conclusion not entailed by the original KB. It serves to compute explanations, or hypotheses, for such missing entailments. While this task has been intensively investigated for perfect data and under classical semantics, less is known about abduction when erroneous data results in inconsistent KBs. In this paper we define a suitable notion of abduction under repair semantics, and propose a set of properties and optimality criteria that guides abduction towards `useful' hypotheses. We provide initial complexity results on deciding existence of and verifying abductive solutions with these criteria, under different repair semantics and for the description logics DL-Lite and EL_bot.

ABSTRACT. In this extended abstract, we report on our recent contribution studying the data complexity of querying inconsistent weighted description logic (DL) knowledge bases under recently-introduced cost-based semantics. In a nutshell, the idea is to assign each interpretation a cost based upon the weights of the violated axioms and assertions, and certain and possible query answers are determined by considering all (resp. some) interpretations having optimal or bounded cost. Whereas the initial study of cost-based semantics focused on DLs between EL_\bot and ALCO, we consider DLs that may contain inverse roles and role inclusions, thus covering prominent DL-Lite dialects. Our data complexity analysis goes significantly beyond existing results by sharpening several lower bounds and pinpointing the precise complexity of optimal-cost certain answer semantics (no non-trivial upper bound was known). Moreover, while all existing results show the intractability of cost-based semantics, our most challenging and surprising result establishes that if we consider DL-Lite-bool-H ontologies and a fixed cost bound, certain answers for instance queries and possible answers for conjunctive queries can be computed using first-order rewriting and thus enjoy the lowest possible data complexity (AC^0).

ABSTRACT. Repair-based semantics have been extensively studied as a means of obtaining meaningful answers to queries posed over inconsistent knowledge bases (KBs). While several works have considered how to exploit a priority relation between facts to select optimal repairs, the question of how to specify such preferences remains largely unaddressed. In this extended abstract, we introduce a declarative rule-based framework for specifying and computing a priority relation between conflicting facts. As the expressed preferences may contain undesirable cycles, we consider the problem of determining when a set of preference rules always yields an acyclic relation, and we also explore a pragmatic approach that extracts an acyclic relation by applying various cycle removal techniques. As a step towards an end-to-end system for querying inconsistent KBs, we present a preliminary implementation and experimental evaluation of the framework, which employs answer set programming to evaluate the preference rules, apply the desired cycle resolution techniques to obtain a priority relation, and answer queries under prioritized-repair semantics.

ABSTRACT. Answering conjunctive queries (CQs) equipped with basic forms of negation is a challenging task, which happens to be undecidable even for lightweight Description Logic (DL) ontologies. Interestingly, the DL counterpart of RDFS seems to be partially unaffected by those negative results, even when equipped with disjointness axioms. This paper summarises our recent work on this subject, where we present a refined complexity analysis of answering CQs with inequality atoms and safe negation posed over such ontologies. We introduce a unified $\Pi_2^p$ algorithm for the general case, we prove that two inequality atoms already lead to $\Pi_2^p$-hardness, and we show similar results for the case of safe negation: answering CQs with one negated atom is in NP, but two negated atoms are enough to reach $\Pi_2^p$-hardness. These results close key gaps in the literature and refine the complexity analysis of the query containment problem.

ABSTRACT. This extended abstract summarises our recent investigation on RDFS-based Knowledge Graphs (RKGs). Inspired by previous work on equipping DLs with a semantics adequate for metamodeling, we provide a formal semantics for RKGs based on classical logic. We show that, surprisingly, under the newly defined semantics, RKGs do not admit, in general, a canonical model. Also, we introduce the notions of definite and indefinite RKGs and show that being definite is both a sufficient and necessary condition for an RKG to admit a canonical model, thus singling out the source of incompleteness that causes the lack of a canonical model for indefinite RKGs. Finally, we characterize the complexity of the query answering problem for both definite and indefinite RKGs.

ABSTRACT. The framework of ontology-mediated data access (OBDA) has enjoyed great success in the setting of relational databases. But while querying graph data has always been seen as a key motivation of OBDA, current technologies lack support for standard graph database systems. In recent years, graph databases using the labeled property graph data model have seen increasing popularity, and two ISO standards for querying property graphs were made public in 2023: GQL and SQL-PGQ. Leveraging this momentum, we take a big step toward ontology-mediated querying of property graphs. We propose DL-Lite_PG, a DL-Lite variant tailored for property graphs that uses property values to define concepts and roles in the ontology, and present a practical rewriting algorithm for rewriting navigational queries with DL-Lite_PG ontologies. We consider nested two-way regular path queries (N2RPQs) and a large class of conjunctive N2RPQs. Our queries can access property values within path expressions and capture a substantial portion of the GQL and SQL-PGQ standards. This is the first algorithm to fully support full 2RPQs in the presence of ontologies by leveraging nested regular paths. We present our algorithm and a proof-of-concept implementation and conclude with a set of preliminary experiments that showcase the practicality of our approach.

ABSTRACT. Since the introduction of the SHACL standard, understanding its computational features and formal foundations has become essential. Some research has focused on the semantics of recursive constraints and the complexity of validation, but the satisfiability of SHACL constraints remains largely unexplored. The most significant previous work in this direction is rather coarse, obtaining very few positive results for finite satisfiability and for fragments with counting. In this paper, we build on description logics to paint a comprehensive and fine-grained boundary for SHACL fragments with a decidable satisfiability problem under the supported semantics, both for unrestricted and finite models.

ABSTRACT. We present a probably approximately correct algorithm for learning the termino- logical part of a description-logic knowledge base via subsumption queries. The axioms we learn are concept inclusions between conjunctions of concepts from a specified set of concept descriptions. By varying the distribution of queries posed to the oracle, we adapt the algorithm to improve the recall when using the resulting TBox for ontology-mediated query answering. Experimental eval- uation on OWL 2 EL ontologies suggests that our approach helps significantly improve recall while maintaining a high precision of query answering.

ABSTRACT. We introduce EL-clustering, a type of conceptual clustering in which each cluster is described by an EL concept. The cluster then contains all instances of that concept. This contribution can be seen as a form of unsupervised learning of EL concepts from data, useful for analyzing graph-based data as well as for ontology engineering. Towards a practical method for EL-clustering, we introduce complete simulation graphs, a structure from which all possible EL-clusterings of the given data can be extracted. From this structure, a good EL-clustering is then selected based on a utility function. We evaluate a first prototypical implementation of this idea on ABoxes of ontologies from a known benchmark, and show that bounded simulation graphs and EL-clusterings can often be computed in practice.

ABSTRACT. We investigate the problem of computing small conjunctive queries that separate positive from negative examples in ontology-enriched systems. This work builds upon prior research on the query-by-example paradigm, which focused on the existence of separating queries. Here, we go beyond mere existence and study how to construct separating queries that are both correct and compact. Specifically, we define a new recursive notion of homomorphism based on Trémaux trees (normal spanning trees), show that it allows us to extract small separating conjunctive queries from the chase (universal model), and provide an algorithm for this query construction process. Our results offer both theoretical insights and practical tools for making ontology-based query-by-example more usable for end-users.

ABSTRACT. Within the Ontology Based Data Access (OBDA) framework, users can query relational data sources using an ontology to which the source is linked via declarative mappings. In a world where data sharing is widespread, ensuring privacy while managing data poses a significant challenge. Controlled Query Evaluation (CQE) is a privacy preserving query answering framework in the presence of ontologies, where policies representing confidential information are used to devise suitable censors that enforce data protection. The integration of CQE within OBDA was recently proposed through the Policy-Protected OBDA (PPOBDA) framework, which is based on embedding policies into mappings. Such framework is essentially theoretical, and the effectiveness with which PPOBDA policies are able to capture real-world privacy requirements has not been assessed so far. In this work, we carry out such an evaluation, utilizing the well-known MIMIC-III hospital dataset, which recently has been mapped, by adopting the OBDA framework, to the Fast Healthcare Interoperability Resources (FHIR) ontology. We identify relevant privacy requirements by analyzing the legal regulations on data sharing expressed in HIPAA of US Federal Law and GDPR of the EU, show how they can be expressed via PPOBA policies, and analyze the impact of these policies on the answers to a set of representative queries. Our analysis exposes both strengths and weaknesses of the PPOBA framework in relation to these practically relevant privacy regulations. Furthermore, we perform a performance evaluation of the OBDA framework implemented over the MIMIC-III dataset via the FHIR ontology, assessing the overhead introduced by the PPOBDA policies and its implications on such real-world use case.

This paper has been accepted for publication in the proceedings of the 22nd Int. Conf. on Modeling Decisions for Artificial Intelligence (MDAI 2025).

ABSTRACT. This work summarizes our paper currently under review at the 24th International Semantic Web Conference focusing on Controlled Query Evaluation over Description Logics ontologies. We express the data protection policy using epistemic dependencies (EDs), and use optimal ground atom (GA) censors as tools for exposing the facts entailed by the ontology in a maximal, policy-compliant way. We study the complexity of answering Boolean unions of conjunctive queries with respect to the intersection of all optimal GA censors. We identify a class of EDs for which this entailment problem is first-order rewritable for DL-LiteR ontologies, and we empirically validate the efficiency of our method.

ABSTRACT. We propose a method for generating evaluation datasets for ABox abduction algorithms, using diverse real-world knowledge bases, logical consequences as observations to ensure meaningfulness, justifications to guarantee explanations exist, and ontology modules to constrain the search space.

ABSTRACT. The state-of-the-art complete algorithms to solve ABox abduction in DL include the original Reiter's algorithm for minimal hitting sets alongside its more recent updates: Wotawa's HST and Pill and Quaritch's RC-Tree. On the other hand, incomplete methods that quickly find some but not all solutions include Junker's QuickXplain and MergeXplain by Shchekotykhin et al. We present CATS, a new modular ABox abduction solver. It implements all the said algorithms together with the hybrid MHS-MXP, recently introduced by Homola et al., and two new analogous variants: HST-MXP and RCT-MXP, based on HST and RC-Tree, respectively. The user can choose any of the eight algorithms. The solver uses the JFact reasoner as a black box and thus allows any DL expressivity up to SROIQ. The modular implementation served as a test bed for an evaluation and comparison of the implemented algorithms, which we conducted over the LUBM ontology. Out of the complete algorithms, the hybrid ones were proven to find explanations faster, and they were also more memory-efficient.

ABSTRACT. The web application Evonne explains Description Logic (DL) entailments through interactive visualization. We discuss an extension of Evonne to DLs with concrete domains, which are needed for formalizing concepts whose definitions involve quantitative information. Specifically, we focus on two extensions of the DL EL_\bot: one with constraints formulated as linear equations and the other with difference constraints. First, we have extended Evonne to enable the generation and presentation of proofs involving these concrete domains. Then, leveraging the unique properties of each domain, we have designed and incorporated alternative visual explanations for the numerical parts of the proofs. Finally, we have assessed the effectiveness of these visual explanations through qualitative user studies and a performance benchmark. While opinions on one of these explanations varied, the other was widely recognized for its clarity and ease of understanding.

This is an extended abstract of a paper submitted to the 15th International Symposium on Frontiers of Combining Systems (FroCoS 2025) and currently under review.

ABSTRACT. Extending a set of facts with every fact that can be derived based on a set of rules is called materialization. Incremental approaches, like Delete/Rederive (DRed) and Backward/Forward (B/F), allow for efficient adaptations of materialized datasets whenever the original set of facts changes due to an update. To effectively deal with streams of updates, we previously extended DRed with marking, where we directly take a look at the next available update in the stream and utilize this insight to prevent repeated rule applications. In this work, we apply this idea on B/F by using marks to indicate and find facts that are deleted by the next update, which enables us to determine facts that need to be checked for derivation proofs without considering rules for that. An evaluation with both synthetic and real test data demonstrates the marking approach's potential to reduce processing time compared to classical B/F.

ABSTRACT. Reasoning with rules that allow for exceptions has been a longstanding challenge in knowledge representation. The KLM paradigm has been successful for defeasible reasoning in propositional logics, but its application to Description Logics (DLs) has been challenging. Many approaches to terminological reasoning with defeasible inclusions have been proposed, but reasoning about ABoxes is still largely unexplored. In this paper, we consider defeasible inclusions in the expressive DL ALCI with closed predicates, but restrict the inclusions in a way that circumvents some of the challenges faced by related approaches. We also consider the data complexity of defeasible reasoning, which, to our knowledge, had not yet been analysed. Unfortunately, our approach is hard for the second level of the polynomial hierarchy, but we identify a restricted fragment that enables tractable reasoning.

ABSTRACT. Standard automated planning employs first-order formulas under closed-world semantics to achieve a goal with a given set of actions from an initial state. We follow a line of research that aims to incorporate background knowledge into automated planning problems, for example by means of ontologies, which are usually interpreted under open-world semantics. We present a new approach for planning with DL-Lite ontologies that combines the advantages of ontology-based action conditions provided by explicit-input knowledge and action bases (eKABs) and ontology-aware action effects under the coherence update semantics. We show that the complexity of the resulting formalism is not higher than that of previous approaches, and provide an implementation via a polynomial compilation into classical planning. An evaluation on existing and new benchmarks examines the performance of a planning system on different variants of our compilation.