Mantas Simkus

ECAI Conference 2023 Conference Paper

Reconciling SHACL and Ontologies: Semantics and Validation via Rewriting

• Shqiponja Ahmetaj
• Magdalena Ortiz 0001
• Anouk Oudshoorn
• Mantas Simkus

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.

IJCAI Conference 2021 Conference Paper

Bounded Predicates in Description Logics with Counting

• Sanja Lukumbuzya
• Mantas Simkus

Description Logics (DLs) support so-called anonymous objects, which significantly contribute to the expressiveness of these KR languages, but also cause substantial computational challenges. This paper investigates reasoning about upper bounds on predicate sizes for ontologies written in the expressive DL ALCHOIQ extended with closed predicates. We describe a procedure based on integer programming that allows us to decide the existence of upper bounds on the cardinality of some predicate in the models of a given ontology in a data-independent way. Our results yield a promising supporting tool for constructing higher quality ontologies, and provide a new way to push the decidability frontiers. To wit, we define a new safety condition for Datalog-based queries over DL ontologies, while retaining decidability of query entailment.

ECAI Conference 2020 Conference Paper

Ontology Focusing: Knowledge-Enriched Databases on Demand

• Tomasz Gogacz
• Víctor Gutiérrez-Basulto
• Yazmín Ibáñez-García
• Filip Murlak
• Magdalena Ortiz 0001
• Mantas Simkus

We propose a novel use of ontologies to aid the on-demand design of data-centric systems. By means of a process that we call focusing, a schema for a (possibly knowledge-enriched) database can be obtained semi-automatically from an existing ontology and a specification of the scope of the desired system. We formalize the inputs and outputs of focusing, and identify relevant computational problems: finding a schema via focusing, testing its consistency, and answering queries in the knowledge-enriched databases it produces. These definitions are independent from the ontology language. We then study focusing for selected description logics as ontology languages, and popular classes of queries for specifying the scope of the system. For several representative combinations, we study the decidability and complexity of the identified computational problems. As a by-product, we isolate (and solve) mixed variants of the classical satisfiability and entailment problems, where selected predicates are required to have finite extension, as well as the nullability problem, which is closely related to query emptiness.

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.

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.

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.

LPAR Conference 2018 Conference Paper

The Triguarded Fragment of First-Order Logic

• Sebastian Rudolph
• Mantas Simkus

Past research into decidable fragments of first-order logic (FO) has produced two very prominent fragments: the guarded fragment GF, and the two-variable fragment FO2. These fragments are of crucial importance because they provide significant insights into decidabil- ity and expressiveness of other (computational) logics like Modal Logics (MLs) and various Description Logics (DLs), which play a central role in Verification, Knowledge Represen- tation, and other areas. In this paper, we take a closer look at GF and FO2, and present a new fragment that subsumes them both. This fragment, called the triguarded fragment (denoted TGF), is obtained by relaxing the standard definition of GF: quantification is required to be guarded only for subformulae with three or more free variables. We show that, in the absence of equality, satisfiability in TGF is N2ExpTime-complete, but becomes NExpTime-complete if we bound the arity of predicates by a constant (a natural assumption in the context of MLs and DLs). Finally, we observe that many natural extensions of TGF, including the addition of equality, lead to undecidability.

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.

AAAI Conference 2014 Conference Paper

Capturing Relational Schemas and Functional Dependencies in RDFS

• Diego Calvanese
• Wolfgang Fischl
• Reinhard Pichler
• Emanuel Sallinger
• Mantas Simkus

Mapping relational data to RDF is an important task for the development of the Semantic Web. To this end, the W3C has recently released a Recommendation for the so-called direct mapping of relational data to RDF. In this work, we propose an enrichment of the direct mapping to make it more faithful by transferring also semantic information present in the relational schema from the relational world to the RDF world. We thus introduce expressive identification constraints to capture functional dependencies and define an RDF Normal Form, which precisely captures the classical Boyce-Codd Normal Form of relational schemas.

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

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

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

• 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.

IJCAI Conference 2009 Conference Paper

• Thomas Eiter
• Mantas Simkus

Current Answer Set Programming (ASP) solvers largely build on logic programming without function symbols. This limitation makes ASP decidable, but greatly complicates the modeling of indefinite time, recursive data structures (e. g. , lists), and infinite processes and objects in general. Recent research thus aims at finding decidable fragments of ASP with function symbols and studying their complexity. We identify bidirectional ASP programs as an expressive such fragment that is useful, e. g. , for reasoning about actions involving both the future and the past. We tightly characterize the computational complexity of bidirectional programs and of some of their subclasses, addressing the main reasoning tasks. Our results also imply that the recently introduced FDNC programs can be extended by inverse predicates while retaining decidability, but computational costs are unavoidably higher.

JELIA Conference 2008 Conference Paper

Query Answering in the Description Logic Horn-

• Thomas Eiter
• Georg Gottlob
• Magdalena Ortiz 0001
• Mantas Simkus

Abstract We provide an ExpTime algorithm for answering conjunctive queries (CQs) in Horn - \(\mathcal{SHIQ}\), a Horn fragment of the well-known Description Logic \(\mathcal{SHIQ}\) underlying the OWL-Lite standard. The algorithm employs a domino system for model representation, which is constructed via a worst-case optimal tableau algorithm for Horn - \(\mathcal{SHIQ}\); the queries are answered by reasoning over the domino system. Our algorithm not only shows that CQ answering in Horn - \(\mathcal{SHIQ}\) is not harder than satisfiability testing, but also that it is polynomial in data complexity, making Horn - \(\mathcal{SHIQ}\) an attractive expressive Description Logic.

LPAR Conference 2008 Invited Paper

Reasoning Using Knots

• Thomas Eiter
• Magdalena Ortiz 0001
• Mantas Simkus

Abstract The deployment of Description Logics (DLs) and Answer Set Programming (ASP), which are well-known knowledge representation and reasoning formalisms, to a growing range of applications has created the need for novel reasoning algorithms and methods. Recently, knots have been introduced as a tool to facilitate reasoning tasks in extensions of ASP with functions symbols. They were then also fruitfully applied for query answering in Description Logics, hinging on the forest-shaped model property of knowledge bases. This paper briefly reviews the knot idea at a generic level and recalls some of the results obtained with them. It also discusses features of knots and relations to other reasoning techniques, and presents issues for further research.

LPAR Conference 2007 Conference Paper

\mathbb FDNC: Decidable Non-monotonic Disjunctive Logic Programs with Function Symbols

• Mantas Simkus
• Thomas Eiter

Abstract Current Answer Set Programming systems are built on non-monotonic logic programs without function symbols; as well-known, they lead to high undecidability in general. However, function symbols are highly desirable for various applications, which challenges to find meaningful and decidable fragments of this setting. We present the class \(\mathbb{FDNC}\) of logic programs which allows for function symbols, disjunction, non-monotonic negation under answer set semantics, and constraints, while still retaining the decidability of the standard reasoning tasks. Thanks to these features, they are a powerful formalism for rule-based modeling of applications with potentially infinite processes and objects, which allows also for common-sense reasoning. We show that consistency checking and brave reasoning are ExpTime -complete in general, but have lower complexity for restricted fragments, and outline worst-case optimal reasoning procedures for these tasks. Furthermore, we present a finite representation of the possibly infinitely many infinite stable models of an \(\mathbb{FDNC}\) program, which may be exploited for knowledge compilation purposes.