Magdalena Ortiz

AIJ Journal 2026 Journal Article

SHACL validation in the presence of ontologies: Semantics and rewriting techniques

• Anouk Oudshoorn
• Magdalena Ortiz
• Mantas Šimkus

SHACL and OWL are two prominent W3C standards for managing RDF data. These languages share many features, but they have one fundamental difference: OWL, designed for inferring facts from incomplete data, makes the open-world assumption, whereas SHACL is a constraint language that treats the data as complete and must be validated under the closed-world assumption. The combination of both formalisms is very appealing and has been called for, but their semantic gap is a major challenge, semantically and computationally. In this paper, we advocate a semantics for SHACL validation in the presence of ontologies based on core universal models. We provide a technique for constructing these models for ontologies in the rich data-tractable description logic Horn-ALCHIQ. Furthermore, we use a finite representation of this model to develop a rewriting technique that reduces SHACL validation in the presence of ontologies to standard validation. Finally, we study the complexity of SHACL validation in the presence of ontologies, and show that even very simple ontologies make the problem EXPTIME-complete, and PTIME-complete in data complexity.

KR Conference 2025 Conference Paper

Expressive Description Logics with Rich Yet Affordable Numeric Constraints

• Federica Di Stefano
• Sanja Lukumbuzya
• Magdalena Ortiz
• Mantas Šimkus

Description Logics (DLs) excel at representing structured knowledge in several application domains, but fall very short when it comes to reasoning about their numeric aspects. We consider the expressive DL ALCHOIQ with closed predicates and extend it with features ranging over user-specified finite numeric intervals, feature assertions, and local additive constraints on feature values. We illustrate the power of this language for describing problems that involve ontological and numeric reasoning and study reasoning problems that go beyond satisfiability, such as finding models that minimize some costs. We show that these additional numeric modeling and reasoning capabilities can be accommodated by extending a standard reasoning technique for ALCHOIQ using linear inequalities, and the extension does not necessarily increase the worst-case computational cost.

KR Conference 2025 Conference Paper

Minimal Model Reasoning in Description Logics: Don’t Try This at Home!

• Federica Di Stefano
• Quentin Manière
• Magdalena Ortiz
• Mantas Šimkus

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. We address this problem in popular DLs and obtain surprisingly negative results: 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 and allow us to establish a connection with the recently studied pointwise circumscription; we also derive results in data complexity. We conclude with a brief excursion to the DL-Lite family, where a positive result was known for DL-Lite_core, but our investigation establishes ExpSpace-hardness already for its extension DL-Lite_horn.

AIJ Journal 2024 Journal Article

Datalog rewritability and data complexity of ALCHOIQ with closed predicates

• Sanja Lukumbuzya
• Magdalena Ortiz
• Mantas Šimkus

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.

IJCAI Conference 2023 Conference Paper

Description Logics with Pointwise Circumscription

• Federica Di Stefano
• Magdalena Ortiz
• Mantas Šimkus

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 ExpTime-complete, 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.

KR Conference 2021 Conference Paper

Closed- and Open-world Reasoning in DL-Lite for Cloud Infrastructure Security

• Claudia Cauli
• Magdalena Ortiz
• Nir Piterman

Infrastructure in the cloud is deployed through configuration files, which specify the resources to be created, their settings, and their connectivity. We aim to model infrastructure before deployment and reason about it so that potential vulnerabilities can be discovered and security best practices enforced. Description logics are a good match for such modeling efforts and allow for a succinct and natural description of cloud infrastructure. Their open-world assumption allows capturing the distributed nature of the cloud, where a newly deployed infrastructure could connect to pre-existing resources not necessarily owned by the same user. However, parts of the infrastructure that are fully known need closed-world reasoning, calling for the usage of expressive formalisms, which increase the computational complexity of reasoning. Here, we suggest an extension of DL-LiteF that is tailored for capturing such cloud infrastructure. Our logic allows combining a core part that is completely defined (closed-world) and interacts with a partially known environment (open-world). We show that this extension preserves the first-order rewritability of DL-LiteF for knowledge-base satisfiability and conjunctive query answering. Security properties combine universal and existential reasoning about infrastructure. Thus, we also consider the problem of conjunctive query satisfiability and show that it can be solved in logarithmic space in data complexity.

KR Conference 2021 Conference Paper

Reasoning about Explanations for Non-validation in SHACL

• Shqiponja Ahmetaj
• Robert David
• Magdalena Ortiz
• Axel Polleres
• Bojken Shehu
• Mantas Šimkus

The Shapes Constraint Language (SHACL) is a recently standardized language for describing and validating constraints over RDF graphs. The SHACL specification describes the so-called validation reports, which are meant to explain to the users the outcome of validating an RDF graph against a collection of constraints. Specifically, explaining the reasons why the input graph does not satisfy the constraints is challenging. In fact, the current SHACL standard leaves it open on how such explanations can be provided to the users. In this paper, inspired by works on logic-based abduction and database repairs, we study the problem of explaining non-validation of SHACL constraints. In particular, in our framework non-validation is explained using the notion of a repair, i. e. , a collection of additions and deletions whose application on an input graph results in a repaired graph that does satisfy the given SHACL constraints. We define a collection of decision problems for reasoning about explanations, possibly restricting to explanations that are minimal with respect to cardinality or set inclusion. We provide a detailed characterization of the computational complexity of those reasoning tasks, including the combined and the data complexity.

KR Conference 2020 Conference Paper

An ExpTime Upper Bound for ALC with Integers

• Nadia Labai
• Magdalena Ortiz
• Mantas Šimkus

Concrete domains, especially those that allow to compare features with numeric values, have long been recognized as a very desirable extension of description logics (DLs), and significant efforts have been invested into adding them to usual DLs while keeping the complexity of reasoning in check. For expressive DLs and in the presence of general TBoxes, for standard reasoning tasks like consistency, the most general decidability results are for the so-called ω-admissible domains, which are required to be dense. Supporting non-dense domains for features that range over integers or natural numbers remained largely open, despite often being singled out as a highly desirable extension. The decidability of some extensions of ALC with non-dense domains has been shown, but existing results rely on powerful machinery that does not allow to infer any elementary bounds on the complexity of the problem. In this paper, we study an extension of ALC with a rich integer domain that allows for comparisons (between features, and between features and constants coded in unary), and prove that consistency can be solved using automata-theoretic techniques in single exponential time, and thus has no higher worst-case complexity than standard ALC. Our upper bounds apply to some extensions of DLs with concrete domains known from the literature, support general TBoxes, and allow for comparing values along paths of ordinary (not necessarily functional) roles.

KR Conference 2020 Conference Paper

Datalog Rewritability and Data Complexity of ALCHOIF with Closed Predicates

• Tomasz Gogacz
• Sanja Lukumbuzya
• Magdalena Ortiz
• Mantas Šimkus

We study the relative expressiveness of ontology-mediated queries (OMQs) formulated in the expressive Description Logic ALCHOIF 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 role functionality. 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.

AIJ Journal 2020 Journal Article

Polynomial rewritings from expressive Description Logics with closed predicates to variants of Datalog

• Shqiponja Ahmetaj
• Magdalena Ortiz
• Mantas Šimkus

In many scenarios, complete and incomplete information coexist. For this reason, the knowledge representation and database communities have long shown interest in simultaneously supporting the closed- and the open-world views when reasoning about logic theories. Here we consider the setting of querying possibly incomplete data using logic theories, formalized as the evaluation of an ontology-mediated query (OMQ) that pairs a query with a theory, sometimes called an ontology, expressing background knowledge. This can be further enriched by specifying a set of closed predicates from the theory that are to be interpreted under the closed-world assumption, while the rest are interpreted with the open-world view. In this way we can retrieve more precise answers to queries by leveraging the partial completeness of the data. The central goal of this paper is to understand the relative expressiveness of ontology-mediated query languages in which the ontology part is written in the expressive Description Logic (DL) ALCHOI and includes a set of closed predicates. We consider a restricted class of conjunctive queries. Our main result is to show that every query in this non-monotonic query language can be translated in polynomial time into Datalog with negation as failure under the stable model semantics. To overcome the challenge that Datalog has no direct means to express the existential quantification present in ALCHOI, we define a two-player game that characterizes the satisfaction of the ontology, and design a Datalog query that can decide the existence of a winning strategy for the game. If there are no closed predicates—in the case of querying an ALCHOI knowledge base—our translation yields a positive disjunctive Datalog program of polynomial size. To the best of our knowledge, unlike previous translations for related fragments with expressive (non-Horn) DLs, these are the first polynomial time translations.

AAAI Conference 2020 Conference Paper

Query Rewriting for Ontology-Mediated Conditional Answers

• Medina Andresel
• Magdalena Ortiz
• Mantas Simkus

Among many solutions for extracting useful answers from incomplete data, ontology-mediated queries (OMQs) use domain knowledge to infer missing facts. We propose an extension of OMQs that allows us to make certain assumptions— for example, about parts of the data that may be unavailable at query time, or costly to query—and retrieve conditional answers, that is, tuples that become certain query answers when the assumptions hold. We show that querying in this powerful formalism often has no higher worst-case complexity than in plain OMQs, and that these queries are first-order rewritable for DL-LiteR. Rewritability is preserved even if we allow some use of closed predicates to combine the (partial) closed- and open-world assumptions. This is remarkable, as closed predicates are a very useful extension of OMQs, but they usually make query answering intractable in data complexity, even in very restricted settings.

AAAI Conference 2020 Conference Paper

Resilient Logic Programs: Answer Set Programs Challenged by Ontologies

• Sanja Lukumbuzya
• Magdalena Ortiz
• Mantas Šimkus

We introduce resilient logic programs (RLPs) that couple a non-monotonic logic program and a first-order (FO) theory or description logic (DL) ontology. Unlike previous hybrid languages, where the interaction between the program and the theory is limited to consistency or query entailment tests, in RLPs answer sets must be ‘resilient’ to the models of the theory, allowing non-output predicates of the program to respond differently to different models. RLPs can elegantly express ∃∀∃-QBFs, disjunctive ASP, and configuration problems under incompleteness of information. RLPs are decidable when a couple of natural assumptions are made: (i) satisfiability of FO theories in the presence of closed predicates is decidable, and (ii) rules are safe in the style of the well-known DL-safeness. We further show that a large fragment of such RLPs can be translated into standard (disjunctive) ASP, for which efficient implementations exist. For RLPs with theories expressed in DLs, we use a novel relaxation of safeness that safeguards rules via predicates whose extensions can be inferred to have a finite bound. We present several complexity results for the case where ontologies are written in some standard DLs.

AAAI Conference 2019 Conference Paper

Relaxing and Restraining Queries for OBDA

• Medina Andreşel
• Yazmín Ibáñez-García
• Magdalena Ortiz
• Mantas Šimkus

We advocate the use of ontologies for relaxing and restraining queries, so that they retrieve either more or less answers, enabling the exploration of a given dataset. We propose a set of rewriting rules to relax and restrain conjunctive queries (CQs) over datasets mediated by an ontology written in a dialect of DL-Lite with complex role inclusions (CRIs). The addition of CRI enables the representation of knowledge about data involving ordered hierarchies of categories, in the style of multi-dimensional data models. Although CRIs in general destroy the first-order rewritability of CQs, we identify settings in which CQs remain rewritable.

AAAI Conference 2018 Conference Paper

Combining Rules and Ontologies into Clopen Knowledge Bases

• Labinot Bajraktari
• Magdalena Ortiz
• Mantas Šimkus

We propose Clopen Knowledge Bases (CKBs) as a new formalism combining Answer Set Programming (ASP) with ontology languages based on first-order logic. CKBs generalize the prominent r-hybrid and DL+LOG languages of Rosati, and are more flexible for specification of problems that combine open-world and closed-world reasoning. We argue that the guarded negation fragment of first-order logic (GNFO)—a very expressive fragment that subsumes many prominent ontology languages like Description Logics (DLs) and the guarded fragment—is an ontology language that can be used in CKBs while enjoying decidability for basic reasoning problems. We further show how CKBs can be used with expressive DLs of the ALC family, and obtain worst-case optimal complexity results in this setting. For DL-based CKBs, we define a fragment called separable CKBs (which still strictly subsumes r-hybrid and DL+LOG knowledge bases), and show that they can be rather efficiently translated into standard ASP programs. This approach allows us to perform basic inference from separable CKBs by reusing existing ef- ficient ASP solvers. We have implemented the approach for separable CKBs containing ontologies in the DL ALCH, and present in this paper some promising empirical results for real-life data. They show that our approach provides a dramatic improvement over a naive implementation based on a translation of such CKBs into dl-programs.

IJCAI Conference 2018 Conference Paper

Compiling Model Representations for Querying Large ABoxes in Expressive DLs

• Labinot Bajraktari
• Magdalena Ortiz
• Mantas Simkus

Answering ontology mediated queries (OMQs) has received much attention in the last decade, but the big gap between practicable algorithms for lightweight ontologies, that are supported by implemented reasoners, and purely theoretical algorithms for expressive ontologies that are not amenable to implementation, has only increased. Towards narrowing the gap, we propose an algorithm to compile a representation of sets of models for ALCHI ontologies, which is sufficient for answering any monotone OMQ. Rather than reasoning for specific ABoxes, or being fully data-independent, we use generic descriptions of families of ABoxes, given by what we call profiles. Our model compilation algorithm runs on TBoxes and sets of profiles, and supports the incremental addition of new profiles. To illustrate the potential of our approach for OMQ answering, we implement a rewriting into an extension of Datalog for OMQs comprising reachability queries, and provide some promising evaluation results.

IJCAI Conference 2018 Conference Paper

Improving Data Management using Domain Knowledge

• Magdalena Ortiz

The development of tools and techniques for flexible and reliable data management is a long-standing challenge, ever more pressing in today’s data-rich world. We advocate using domain knowledge expressed in ontologies to tackle it, and summarize some research efforts to this aim that follow two directions. First, we consider the problem of ontology-mediated query answering (OMQA), where queries in a standard database query language are enriched with an ontology expressing background knowledge about the domain of interest, used to retrieve more complete answers when querying incomplete data. We discuss some of our contributions to OMQA, focusing on (i) expressive languages for OMQA, with emphasis on combining the open- and closed-world assumptions to reason about partially complete data; and (ii) OMQA algorithms based on rewriting techniques. The second direction we discuss proposes to use ontologies to manage evolving data. In particular, we use ontologies to model and reason about constraints on datasets, effects of operations that modify data, and the integrity of the data as it evolves.

KR Conference 2018 Short Paper

Relaxing and Restraining Queries for OBDA

• Medina Andresel
• Magdalena Ortiz
• Yazmin Ibanez-Garcia
• Mantas Simkus

(S1) if A1 v A2 ∈ T and A2 (x) ∈ q, then θ = [A2 (x)/A1 (x)]; We investigate query reformulation rules in OBDA to obtain either more or less answers. We extend DL-Lite with complex role inclusions and define rules that produce query relaxations/restrictions over any dataset. We also introduce a set of data-driven rules to get more fine-grained reformulations.

KR Conference 2016 Conference Paper

Closed Predicates in Description Logics: Results on Combined Complexity

• Nhung Ngo
• Magdalena Ortiz
• Mantas Simkus

In many applications of Description Logic (DL) ontologies, complete information—e. g., stemming from relational databases—interacts with incomplete knowledge. Closed predicates allow to leverage information completeness within the standard open-world semantics of DLs. In this paper we study the (combined) complexity of query answering in the presence of closed predicates, establishing tight complexity results for a range of DLs and query languages. Our results show that consistency testing and instance query answering in the presence of closed predicates is NP-complete even for rich dialects of the DL-Lite family. For EL, in contrast, they are E XPTIME-complete, thus as hard as for ALC and some of its extensions. If (unions of) conjunctive queries (UCQs) are considered, the picture is rather bleak, as 2E XPTIMEhardness holds even for DL-LiteR and EL. Our results also imply 2E XPTIME-hardness of query answering in ALCO for the standard open-world setting. Despite these negative results, we can still identify several useful classes of queries for which the increase in complexity is not so drastic.

IJCAI Conference 2016 Conference Paper

Polynomial Datalog Rewritings for Expressive Description Logics with Closed Predicates

• Shqiponja Ahmetaj
• Magdalena Ortiz
• Mantas Simkus

We consider instance queries mediated by an ontology expressed in the expressive DL ALCHIO with closed predicates. We observe that such queries are nonmonotonic and cannot be expressed in monotonic variants of Datalog, but a polynomial time translation into disjunctive Datalog extended with negation as failure is feasible. If no closed predicates are present - in the case of classical instance checking in ALCHIO - our translation yields a positive disjunctive Datalog program of polynomial size. To the best of our knowledge, this is the first polynomial time translation of an expressive (non-Horn) DL into disjunctive Datalog.

JAIR Journal 2015 Journal Article

Regular Path Queries in Lightweight Description Logics: Complexity and Algorithms

• Meghyn Bienvenu
• Magdalena Ortiz
• Mantas Simkus

Conjunctive regular path queries are an expressive extension of the well-known class of conjunctive queries. Such queries have been extensively studied in the (graph) database community, since they support a controlled form of recursion and enable sophisticated path navigation. Somewhat surprisingly, there has been little work aimed at using such queries in the context of description logic (DL) knowledge bases, particularly for the lightweight DLs that are considered best suited for data-intensive applications. This paper aims to bridge this gap by providing algorithms and tight complexity bounds for answering two-way conjunctive regular path queries over DL knowledge bases formulated in lightweight DLs of the DL-Lite and EL families. Our results demonstrate that in data complexity, the cost of moving to this richer query language is as low as one could wish for: the problem is NL-complete for DL-Lite and P-complete for EL. The combined complexity of query answering increases from NP- to PSpace-complete, but for two-way regular path queries (without conjunction), we show that query answering is tractable even with respect to combined complexity. Our results reveal two-way conjunctive regular path queries as a promising language for querying data enriched by ontologies formulated in DLs of the DL-Lite and EL families or the corresponding OWL 2 QL and EL profiles.

I&C Journal 2014 Journal Article

Answering regular path queries in expressive Description Logics via alternating tree-automata

• Diego Calvanese
• Thomas Eiter
• Magdalena Ortiz

Expressive Description Logics (DLs) have been advocated as formalisms for modeling the domain of interest in various application areas, including the Semantic Web, data and information integration, peer-to-peer data management, and ontology-based data access. An important requirement there is the ability to answer complex queries beyond instance retrieval, taking into account constraints expressed in a knowledge base. We consider this task for positive 2-way regular path queries (P2RPQs) over knowledge bases in the expressive DL ZIQ. P2RPQs are more general than conjunctive queries, union of conjunctive queries, and regular path queries from the literature. They allow regular expressions over roles and data joins that require inverse paths. The DL ZIQ extends the core DL ALC with qualified number restrictions, inverse roles, safe Boolean role expressions, regular expressions over roles, and concepts of the form ∃ S. Self in the style of the DL SRIQ. Using techniques based on two-way tree-automata, we first provide as a stepping stone an elegant characterization of TBox and ABox satisfiability testing which gives us a tight ExpTime bound for this problem (under unary number encoding). We then establish a double exponential upper bound for answering P2RPQs over ZIQ knowledge bases; this bound is tight. Our result significantly pushes the frontier of 2ExpTime decidability of query answering in expressive DLs, both with respect to the query language and the considered DL. Furthermore, by reducing the well known DL SRIQ to ZIQ (with an exponential blow-up in the size of the knowledge base), we also provide a tight 2ExpTime upper bound for knowledge base satisfiability in SRIQ and establish the decidability of query answering for this significant fragment of the new OWL 2 standard.

AAAI Conference 2014 Conference Paper

Managing Change in Graph-Structured Data Using Description Logics

• Shqiponja Ahmetaj
• Diego Calvanese
• Magdalena Ortiz
• Mantas Simkus

In this paper, we consider the setting of graph-structured data that evolves as a result of operations carried out by users or applications. We study different reasoning problems, which range from ensuring the satisfaction of a given set of integrity constraints after a given sequence of updates, to deciding the (non-)existence of a sequence of actions that would take the data to an (un)desirable state, starting either from a specific data instance or from an incomplete description of it. We consider an action language in which actions are finite sequences of conditional insertions and deletions of nodes and labels, and use Description Logics for describing integrity constraints and (partial) states of the data. We then formalize the above data management problems as a static verification problem and several planning problems. We provide algorithms and tight complexity bounds for the formalized problems, both for an expressive DL and for a variant of DL-Lite.

KR Conference 2014 Conference Paper

Nested Regular Path Queries in Description Logics

• Meghyn Bienvenu
• Diego Calvanese
• Magdalena Ortiz
• Mantas Simkus

Institute of Information Systems Vienna Univ. of Technology, Austria it is typically assumed that the data is incomplete and additional domain knowledge is provided by the DL ontology (or TBox). Hence query answering amounts to the more complex task of computing certain answers, i. e., those answers that are obtained from all databases that both contain the explicit facts in the ABox and satisfy the TBox constraints. This difference has driven research in different directions. In databases, expressive query languages for querying graph-structured data have been studied, which are based on the requirement of relating objects by flexibly navigating the data. The main querying mechanism that has been considered for this purpose is that of one-way and two-way regular path queries (RPQs and 2RPQs) (Cruz, Mendelzon, and Wood 1987; Calvanese et al. 2003), which are queries returning pairs of objects related by a path whose sequence of edge labels belongs to a regular language over the (binary) database relations and their inverses. Conjunctive 2RPQs (C2RPQs) (Calvanese et al. 2000) are a significant extension of such queries that add to the navigational ability the possibility of expressing arbitrary selections, projections, and joins over objects related by 2RPQs, in line with conjunctive queries (CQs) over relational databases. Two-way RPQs are present in the property paths in SPARQL 1. 1 (Harris and Seaborne 2013), the new standard RDF query language, and in the XML query language XPath (Berglund and others 2010). An additional construct that is present in XPath is the possibility of using existential test operators, also known as nesting, to express sophisticated conditions along navigation paths. When an existential test hEi is used in a 2RPQ E 0, there will be objects along the main navigation path for E 0 that match positions of E 0 where hEi appears; such objects are required to be the origin of a path conforming to the (nested) 2RPQ E. It is important to notice that existential tests in general cannot be captured even by C2RPQs, e. g., when tests appear within a transitive closure of an RPQ. Hence, adding nesting effectively increases the expressive power of 2RPQs and of C2RPQs. In the DL community, query answering has been investigated extensively for a wide range of DLs, with much of the work devoted to CQs. With regards to the complexity of query answering, attention has been paid on the one hand to combined complexity, i. e., the complexity measured considering as input both the query and the DL knowledge base (constituted by TBox and ABox), and on the other Two-way regular path queries (2RPQs) have received increased attention recently due to their ability to relate pairs of objects by flexibly navigating graph-structured data. They are present in property paths in SPARQL 1. 1, the new standard RDF query language, and in the XML query language XPath. In line with XPath, we consider the extension of 2RPQs with nesting, which allows one to require that objects along a path satisfy complex conditions, in turn expressed through (nested) 2RPQs. We study the computational complexity of answering nested 2RPQs and conjunctions thereof (CN2RPQs) in the presence of domain knowledge expressed in description logics (DLs). We establish tight complexity bounds in data and combined complexity for a variety of DLs, ranging from lightweight DLs (DL-Lite, EL) up to highly expressive ones. Interestingly, we are able to show that adding nesting to (C)2RPQs does not affect worst-case data complexity of query answering for any of the considered DLs. However, in the case of lightweight DLs, adding nesting to 2RPQs leads to a surprising jump in combined complexity, from P-complete to E XP-complete. 1 Magdalena Ortiz Mantas Šimkus

IJCAI Conference 2013 Conference Paper

Conjunctive Regular Path Queries in Lightweight Description Logics

• Meghyn Bienvenu
• Magdalena Ortiz
• Mantas Šimkus

Conjunctive regular path queries are an expressive extension of the well-known class of conjunctive queries and have been extensively studied in the database community. Somewhat surprisingly, there has been little work aimed at using such queries in the context of description logic (DL) knowledge bases, and all existing results target expressive DLs, even though lightweight DLs are considered better-suited for data-intensive applications. This paper aims to bridge this gap by providing algorithms and tight complexity bounds for answering two-way conjunctive regular path queries over DL knowledge bases formulated in lightweight DLs of the DL-Lite and EL families.

IJCAI Conference 2013 Conference Paper

Tractable Queries for Lightweight Description Logics

• Meghyn Bienvenu
• Magdalena Ortiz
• Mantas Šimkus
• Guohui Xiao

It is a classic result in database theory that conjunctive query (CQ) answering, which is NP-complete in general, is feasible in polynomial time when restricted to acyclic queries. Subsequent results identified more general structural properties of CQs (like bounded treewidth) which ensure tractable query evaluation. In this paper, we lift these tractability results to knowledge bases formulated in the lightweight description logics DL-Lite and ELH. The proof exploits known properties of query matches in these logics and involves a querydependent modification of the data. To obtain a more practical approach, we propose a concrete polynomial-time algorithm for answering acyclic CQs based on rewriting queries into datalog programs. A preliminary evaluation suggests the interest of our approach for handling large acyclic CQs.

AAAI Conference 2012 Conference Paper

Query Rewriting for Horn-SHIQ Plus Rules

• Thomas Eiter
• Magdalena Ortiz
• Mantas Simkus
• Trung-Kien Tran
• Guohui Xiao

Query answering over Description Logic (DL) ontologies has become a vibrant field of research. Efficient realizations often exploit database technology and rewrite a given query to an equivalent SQL or Datalog query over a database associated with the ontology. This approach has been intensively studied for conjunctive query answering in the DL-Lite and EL families, but is much less explored for more expressive DLs and queries. We present a rewriting-based algorithm for conjunctive query answering over Horn-SHIQ ontologies, possibly extended with recursive rules under limited recursion as in DL+log. This setting not only subsumes both DL-Lite and EL, but also yields an algorithm for answering (limited) recursive queries over Horn-SHIQ ontologies (an undecidable problem for full recursive queries). A prototype implementation shows its potential for applications, as experiments exhibit efficient query answering over full Horn-SHIQ ontologies and benign downscaling to DL-Lite, where it is competitive with comparable state of the art systems.

KR Conference 2012 Short Paper

The Complexity of Explaining Negative Query Answers in DL-Lite

• Diego Calvanese
• Magdalena Ortiz
• Mantas Simkus
• Giorgio Stefanoni

In order to meet usability requirements, most logic-based applications provide explanation facilities for reasoning services. This holds also for DLs, where research has focused on the explanation of both TBox reasoning and, more recently, query answering. Besides explaining the presence of a tuple in a query answer, it is important to explain also why a given tuple is missing. We address the latter problem for (conjunctive) query answering over DL-Lite ontologies, by adopting abductive reasoning, that is, we look for additions to the ABox that force a given tuple to be in the result. As reasoning tasks we consider existence and recognition of an explanation, and relevance and necessity of a certain assertion for an explanation. We characterize the computational complexity of these problems for subset minimal and cardinality minimal explanations. For this reason, we formalize the problem of explaining the absence of a tuple in the context of query answering over DL ontologies. We adopt abductive reasoning [Eiter and Gottlob, 1995; Klarman, Endriss, and Schlobach, 2011], that is, we consider which additions need to be made to the ABox to force the given tuple to be in the result. More precisely, given a TBox T, an ABox A, and a query q, an explanation for a given tuple ~c is a new ABox E such that the answer to q over hT, A ∪ Ei contains ~c. An important aspect in explanations is to provide users with explanations that are simple to understand and free of redundancy, hence as small as possible. To address this requirement, we study various restrictions on explanations, in particular, we focus on subset minimal and cardinality minimal ones. We consider standard decision problems associated to logic-based abduction: (i) existence of an explanation; (ii) recognition of a given ABox as being an explanation; (iii) relevance and (iv) necessity of an ABox assertion, i. e., whether it occurs in some or all explanations. Additionally, it is important to allow one to restrict the signature of explanations. This can be used to consider only solutions that do not extend the ABox vocabulary: an important property in the context of accessing relational databases through ontologies, where database instances are defined over a small, fixed, vocabulary, and the terminological component is used to enrich that vocabulary. The idea of restricting the explanation signature is an adaptation of a concept introduced in [Baader et al., 2010], which studies among others the CQ-emptiness problem. That is, given a query q

IJCAI Conference 2011 Conference Paper

A Practical Automata-Based Technique for Reasoning in Expressive Description Logics

• Diego Calvanese
• Domenico Carbotta
• Magdalena Ortiz

In this work we describe the theoretical foundations and the implementation of a new automata-based technique for reasoning over expressive Description Logics that is worst-case optimal and lends itself to an efficient implementation. In order to show the feasibility of the approach, we have realized a working prototype of a reasoner based upon these techniques. An experimental evaluation of this prototype shows encouraging results.

IJCAI Conference 2011 Conference Paper

Containment of Regular Path Queries under Description Logic Constraints

• Diego Calvanese
• Magdalena Ortiz
• Mantas Simkus

Query containment has been studied extensively in KR and databases, for different kinds of query languages and domain constraints. We address the longstanding open problem of containment under expressive description logic (DL) constraints for two-way regular path queries (2RPQs) and their conjunctions, which generalize conjunctive queries with the ability to express regular navigation. We show that, surprisingly, functionality constraints alone make containment of 2RPQs already ExpTime-hard. By employing automata-theoretic techniques, we also provide a matching upper bound that extends to very expressive DL constraints. For conjunctive 2RPQs we prove a further exponential jump in complexity, and provide again a matching upper bound for expressive DLs. Our techniques provide also a solution to the problem of query entailment over DL knowledge bases in which individuals in the ABox may be related through regular role-paths.

KR Conference 2010 Conference Paper

Worst-case Optimal Reasoning for the Horn-DL Fragments of OWL 1 and 2

• Magdalena Ortiz
• Sebastian Rudolph
• Mantas Simkus

Horn fragments of Description Logics (DLs) have gained popularity because they provide a beneficial trade-off between expressive power and computational complexity and, more specifically, are usually tractable w. r. t. data complexity. Despite their potential, and partly due to the intricate interaction of nominals (O), inverses (I) and counting (Q), such fragments had not been studied so far for the DLs SHOIQ and SROIQ that underly OWL 1 and 2. In this paper, we present a polynomial and modular translation from HornSHOIQ knowledge bases into DATALOG, which shows that standard reasoning tasks are feasible in deterministic single exponential time. This improves over the previously known upper bounds, and contrasts the known NE XP T IME completeness of full SHOIQ. Thereby, Horn-SHOIQ stands out as the first E XP T IME complete DL that allows simultaneously for O, I, and Q. In addition, we show that standard reasoning in Horn-SROIQ is 2-E XP T IME complete. Despite their high expressiveness, both Horn-SHOIQ and HornSROIQ have polynomial data complexity. This makes them particularly attractive for reasoning in semantically enriched systems with large data sets. A promising first step in this direction could be achieved exploiting existing DATALOG engines, along the lines of our translation.

IJCAI Conference 2009 Conference Paper

• Diego Calvanese
• Thomas Eiter
• Magdalena Ortiz

Reasoning over complex queries in the DLs underlying OWL 2 is of importance in several application domains. We provide decidability and (tight) upper bounds for the problem of checking entailment and containment of positive regular path queries under various combinations of constructs used in such expressive DLs; specifically: regular expressions and (safe) Booleans over roles, and allowing for the combination of any two constructs among inverse roles, qualified number restrictions, and nominals. Our results carry over also to the DLs of the SR family, and thus have a direct impact on OWL 2.

IJCAI Conference 2009 Conference Paper

• Thomas Eiter
• Carsten Lutz
• Magdalena Ortiz
• Mantas Simkus

We study the computational complexity of conjunctive query answering w. r. t. ontologies formulated in fragments of the description logic SHIQ. Our main result is the identification of two new sources of complexity: the combination of transitive roles and role hierarchies which results in 2-EXPTIMEhardness, and transitive roles alone which result in CO-NEXPTIME-hardness. These bounds complement the existing result that inverse roles make query answering in SHIQ 2-EXPTIME-hard. We also show that conjunctive query answering with transitive roles, but without inverse roles and role hierarchies, remains in EXPTIME if the ABox is tree-shaped.

AAAI Conference 2008 Conference Paper

Worst-case Optimal Conjunctive Query Answering for an Expressive Description Logic without Inverses

• Magdalena Ortiz

Answering conjunctive queries (CQs) has been recognized as a key task for the usage of Description Logics (DLs) in a number of applications, and has thus been studied by many authors. In this paper, we present an algorithm for this problem in the DL ALCH which works in exponential time. It improves over previous algorithms which require double exponential time and is worst-case optimal, as already satisfiability testing in ALC is EXPTIME-complete. Furthermore, it shows that inverse roles cause an exponential jump in complexity; as recently shown, the problem is 2EXPTIMEcomplete for ALCI. The algorithm is based on a technique that compiles knowledge bases into sets of trees of depth 1. It is in CONP under data complexity (i. e. , if the taxonomy part and the query are fixed), thus worst-case optimal. An extension from ALCH to DLs with further constructs is possible.

AAAI Conference 2006 Conference Paper

Characterizing Data Complexity for Conjunctive Query Answering in Expressive Description Logics

• Magdalena Ortiz

Description Logics (DLs) are the formal foundations of the standard web ontology languages OWL-DL and OWL-Lite. In the Semantic Web and other domains, ontologies are increasingly seen also as a mechanism to access and query data repositories. This novel context poses an original combination of challenges that has not been addressed before: (i) sufficient expressive power of the DL to capture common data modeling constructs; (ii) well established and flexible query mechanisms such as Conjunctive Queries (CQs); (iii) optimization of inference techniques with respect to data size, which typically dominates the size of ontologies. This calls for investigating data complexity of query answering in expressive DLs. While the complexity of DLs has been studied extensively, data complexity has been characterized only for answering atomic queries, and was still open for answering CQs in expressive DLs. We tackle this issue and prove a tight CONP upper bound for the problem in SHIQ, as long as no transitive roles occur in the query. We thus establish that for a whole range of DLs from AL to SHIQ, answering CQs with no transitive roles has CONP-complete data complexity. We obtain our result by a novel tableaux-based algorithm for checking query entailment, inspired by the one in [19], but which manages the technical challenges of simultaneous inverse roles and number restrictions (which leads to a DL lacking the finite model property).