Umeå University's logo

umu.sePublications
Change search
Link to record
Permanent link

Direct link
Publications (9 of 9) Show all publications
Lukumbuzya, S., Ortiz, M. & Šimkus, M. (2024). Datalog rewritability and data complexity of ALCHOIQ with closed predicates. Artificial Intelligence, 330, Article ID 104099.
Open this publication in new window or tab >>Datalog rewritability and data complexity of ALCHOIQ with closed predicates
2024 (English)In: Artificial Intelligence, ISSN 0004-3702, E-ISSN 1872-7921, Vol. 330, article id 104099Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
Elsevier, 2024
Keywords
Closed predicates, Datalog, Description logics, Query rewriting
National Category
Computer Sciences Computer Systems
Identifiers
urn:nbn:se:umu:diva-222308 (URN)10.1016/j.artint.2024.104099 (DOI)2-s2.0-85186267714 (Scopus ID)
Funder
Wallenberg AI, Autonomous Systems and Software Program (WASP)Knut and Alice Wallenberg Foundation
Available from: 2024-03-14 Created: 2024-03-14 Last updated: 2024-03-14Bibliographically approved
Ortiz, M. (2023). A short introduction to SHACL for logicians. In: Helle Hvid Hansen; Andre Scedrov; Ruy J.G.B. de Queiroz (Ed.), Logic, language, information, and computation: 29th International Workshop, WoLLIC 2023, Halifax, NS, Canada, July 11–14, 2023, Proceedings. Paper presented at WoLLIC 2023, the 29th Workshop on Logic, Language, Information and Computation, Halifax, Canada, July 11-14, 2023 (pp. 19-32). Springer Nature
Open this publication in new window or tab >>A short introduction to SHACL for logicians
2023 (English)In: Logic, language, information, and computation: 29th International Workshop, WoLLIC 2023, Halifax, NS, Canada, July 11–14, 2023, Proceedings / [ed] Helle Hvid Hansen; Andre Scedrov; Ruy J.G.B. de Queiroz, Springer Nature, 2023, p. 19-32Conference paper, Published paper (Refereed)
Abstract [en]

The Shapes Constraint Language (SHACL) was recommended by the W3C in 2017 for describing constraints on web data (specifically, on the so-called RDF graphs) and validating them. At first glance, it may not seem to be a topic for logicians, but as it turns out, SHACL can be approached as a formal logic, and actually quite an interesting one. In this paper, we give a brief introduction to SHACL tailored towards logicians and frame key uses of SHACL as familiar logic reasoning tasks. We discuss how SHACL relates to description logics, which are the basis of the OWL Web Ontology Languages, a related yet orthogonal standard for web data. Finally, we summarize some of our recent work in the SHACL world, hoping that this may shed light on how ideas, results, and techniques from well-established areas of logic can advance the state of the art in this emerging field.

Place, publisher, year, edition, pages
Springer Nature, 2023
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 13923
Keywords
description logics, semantic web, SHACL
National Category
Computer Sciences
Identifiers
urn:nbn:se:umu:diva-215095 (URN)10.1007/978-3-031-39784-4_2 (DOI)2-s2.0-85172733098 (Scopus ID)978-3-031-39783-7 (ISBN)978-3-031-39784-4 (ISBN)
Conference
WoLLIC 2023, the 29th Workshop on Logic, Language, Information and Computation, Halifax, Canada, July 11-14, 2023
Funder
Wallenberg AI, Autonomous Systems and Software Program (WASP)
Available from: 2023-10-13 Created: 2023-10-13 Last updated: 2023-11-24Bibliographically approved
Bonatti, P., Di Stefano, F., Ortiz, M. & Šimkus, M. (2023). Circumscription in DL-Lite: progress report. In: Oliver Kutz; Carsten Lutz; Ana Ozaki (Ed.), Proceedings of the 36th international workshop on Description Logics (DL 2023): . Paper presented at 36th International Workshop on Description Logics, DL 2023, Rhodes, Greece, September 2-4, 2023. CEUR-WS
Open this publication in new window or tab >>Circumscription in DL-Lite: progress report
2023 (English)In: Proceedings of the 36th international workshop on Description Logics (DL 2023) / [ed] Oliver Kutz; Carsten Lutz; Ana Ozaki, CEUR-WS , 2023Conference paper, Published paper (Refereed)
Abstract [en]

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

Place, publisher, year, edition, pages
CEUR-WS, 2023
Series
CEUR workshop proceedings, E-ISSN 1613-0073 ; 3515
Keywords
Circumscription, Computational Complexity, DL-Lite, Lightweight DLs, Non-monotonic reasoning
National Category
Computer Sciences
Identifiers
urn:nbn:se:umu:diva-217214 (URN)2-s2.0-85176437469 (Scopus ID)
Conference
36th International Workshop on Description Logics, DL 2023, Rhodes, Greece, September 2-4, 2023
Available from: 2023-12-01 Created: 2023-12-01 Last updated: 2023-12-01Bibliographically approved
Di Stefano, F., Ortiz, M. & Šimkus, M. (2023). Description logics with pointwise circumscription. In: Edith Elkind (Ed.), Proceedings of the thirty-second international joint conference on artificial intelligence: . Paper presented at 32nd International Joint Conference on Artificial Intelligence, IJCAI 2023, Macao, August 19-25, 2023 (pp. 3167-3175). International Joint Conferences on Artificial Intelligence
Open this publication in new window or tab >>Description logics with pointwise circumscription
2023 (English)In: Proceedings of the thirty-second international joint conference on artificial intelligence / [ed] Edith Elkind, International Joint Conferences on Artificial Intelligence , 2023, p. 3167-3175Conference paper, Published paper (Refereed)
Abstract [en]

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

Place, publisher, year, edition, pages
International Joint Conferences on Artificial Intelligence, 2023
Series
International Joint Conference on Artificial Intelligence, ISSN 1045-0823
National Category
Computer Sciences
Identifiers
urn:nbn:se:umu:diva-214549 (URN)10.24963/ijcai.2023/353 (DOI)2-s2.0-85170402945 (Scopus ID)9781956792034 (ISBN)
Conference
32nd International Joint Conference on Artificial Intelligence, IJCAI 2023, Macao, August 19-25, 2023
Funder
Wallenberg AI, Autonomous Systems and Software Program (WASP)
Available from: 2023-09-27 Created: 2023-09-27 Last updated: 2023-11-24Bibliographically approved
Lukumbuzya, S., Ortiz, M. & Šimkus, M. (2023). On the expressive power of ontology-mediated queries: capturing coNP. In: Oliver Kutz; Carsten Lutz; Ana Ozaki (Ed.), Proceedings of the 36th international workshop on Description Logics (DL 2023): . Paper presented at 36th International Workshop on Description Logics, DL 2023, Rhodes, Greece, September 2-4, 2023. CEUR-WS
Open this publication in new window or tab >>On the expressive power of ontology-mediated queries: capturing coNP
2023 (English)In: Proceedings of the 36th international workshop on Description Logics (DL 2023) / [ed] Oliver Kutz; Carsten Lutz; Ana Ozaki, CEUR-WS , 2023Conference paper, Published paper (Refereed)
Abstract [en]

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

Place, publisher, year, edition, pages
CEUR-WS, 2023
Series
CEUR workshop proceedings, E-ISSN 1613-0073 ; 3515
Keywords
Description Logics, Descriptive Complexity, Expressive Power, Ontology-mediated Query Answering
National Category
Computer Sciences
Identifiers
urn:nbn:se:umu:diva-217412 (URN)2-s2.0-85176404570 (Scopus ID)
Conference
36th International Workshop on Description Logics, DL 2023, Rhodes, Greece, September 2-4, 2023
Available from: 2023-12-04 Created: 2023-12-04 Last updated: 2023-12-04Bibliographically approved
Ortiz, M., Gaggl, S. & Martinez, M. V. (2023). Preface. In: Sarah Gaggl; Maria Vanina Martinez; Magdalena Ortiz (Ed.), Logics in Artificial Intelligence: 18th European Conference, JELIA 2023, Dresden, Germany, September 20–22, 2023, Proceedings (pp. V-VI). Cham: Springer Nature
Open this publication in new window or tab >>Preface
2023 (English)In: Logics in Artificial Intelligence: 18th European Conference, JELIA 2023, Dresden, Germany, September 20–22, 2023, Proceedings / [ed] Sarah Gaggl; Maria Vanina Martinez; Magdalena Ortiz, Cham: Springer Nature, 2023, p. V-VIChapter in book (Other academic)
Place, publisher, year, edition, pages
Cham: Springer Nature, 2023
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 14281
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:umu:diva-215962 (URN)2-s2.0-85174526435 (Scopus ID)978-3-031-43618-5 (ISBN)978-3-031-43619-2 (ISBN)
Available from: 2023-10-30 Created: 2023-10-30 Last updated: 2023-11-24Bibliographically approved
Ahmetaj, S., Ortiz, M., Oudshoorn, A. & Šimkus, M. (2023). Reconciling SHACL and ontologies: semantics and validation via rewriting. In: Kobi Gal; Ann Nowé; Grzegorz J. Nalepa; Roy Fairstein; Roxana Rădulescu (Ed.), ECAI 2023: . Paper presented at 26th European Conference on Artificial Intelligence, ECAI 2023, Krakow, September 30-October 4, 2023 (pp. 27-35). IOS Press
Open this publication in new window or tab >>Reconciling SHACL and ontologies: semantics and validation via rewriting
2023 (English)In: ECAI 2023 / [ed] Kobi Gal; Ann Nowé; Grzegorz J. Nalepa; Roy Fairstein; Roxana Rădulescu, IOS Press, 2023, p. 27-35Conference paper, Published paper (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
IOS Press, 2023
Series
Frontiers in Artificial Intelligence and Applications, ISSN 0922-6389, E-ISSN 1879-8314 ; 372
National Category
Computer Sciences Computer Systems
Identifiers
urn:nbn:se:umu:diva-216798 (URN)10.3233/FAIA230250 (DOI)2-s2.0-85175828692 (Scopus ID)9781643684376 (ISBN)9781643684369 (ISBN)
Conference
26th European Conference on Artificial Intelligence, ECAI 2023, Krakow, September 30-October 4, 2023
Funder
EU, Horizon 2020, 101034440Wallenberg AI, Autonomous Systems and Software Program (WASP)
Available from: 2023-11-24 Created: 2023-11-24 Last updated: 2023-11-24Bibliographically approved
Ahmetaj, S., Ortiz, M., Oudshoorn, A. M. & Šimkus, M. (2023). Reconciling SHACL and ontologies: semantics and validation via rewriting. In: Oliver Kutz; Carsten Lutz; Ana Ozaki (Ed.), Proceedings of the 36th international workshop on Description Logics (DL 2023): . Paper presented at 36th International Workshop on Description Logics, DL 2023, Rhodes, Greece, September 2-4, 2023. CEUR-WS
Open this publication in new window or tab >>Reconciling SHACL and ontologies: semantics and validation via rewriting
2023 (English)In: Proceedings of the 36th international workshop on Description Logics (DL 2023) / [ed] Oliver Kutz; Carsten Lutz; Ana Ozaki, CEUR-WS , 2023Conference paper, Oral presentation with published abstract (Refereed)
Abstract [en]

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

Place, publisher, year, edition, pages
CEUR-WS, 2023
Series
CEUR Workshop Proceedings, E-ISSN 1613-0073 ; 3515
Keywords
complexity, OWL 2 QL, rewriting, SHACL, validation
National Category
Computer Sciences
Identifiers
urn:nbn:se:umu:diva-217414 (URN)2-s2.0-85176443534 (Scopus ID)
Conference
36th International Workshop on Description Logics, DL 2023, Rhodes, Greece, September 2-4, 2023
Note

Extended abstract.

Available from: 2023-12-04 Created: 2023-12-04 Last updated: 2023-12-04Bibliographically approved
Dragovic, N., Okulmus, C. & Ortiz, M. (2023). Rewriting ontology-mediated navigational queries into cypher. In: Oliver Kutz; Carsten Lutz; Ana Ozaki (Ed.), Proceedings of the 36th international workshop on Description Logics (DL 2023): . Paper presented at 36th International Workshop on Description Logics, DL 2023, Rhodes, Greece, September 2-4, 2023. CEUR-WS
Open this publication in new window or tab >>Rewriting ontology-mediated navigational queries into cypher
2023 (English)In: Proceedings of the 36th international workshop on Description Logics (DL 2023) / [ed] Oliver Kutz; Carsten Lutz; Ana Ozaki, CEUR-WS , 2023Conference paper, Published paper (Refereed)
Abstract [en]

The ontology-based data access (OBDA) paradigm has successfully grown over the last decade as a powerful means to access data from possibly diverse and incomplete sources, using a domain ontology as a mediator. The ability to query generic graph-structured data is often highlighted as an advantage of OBDA, but in practice, existing solutions do not allow to access data in popular graph database management systems (DBMS) (e.g., Neo4j) that adopt the so-called 'property graph' data model and support dedicated query languages such as Cypher. Towards overcoming this major limitation, we propose a technique for ontology-mediated querying (OMQ) of property graphs. We tailor a suitable query language that supports path navigation in a form that can be naturally expressed in Cypher and other important graph query languages. It keeps the data complexity of query evaluation tractable even under trail semantics and is sufficient for our motivating use case in the autonomous driving domain. We address the semantic gap between the traditional path semantics adopted by most works on graph databases, and the trail semantics used in Cypher, and identify cases where both semantics coincide. To our knowledge, OMQs with trail semantics had not been addressed before. We develop a rewriting algorithm for queries mediated by DL-Lite ontologies that enables query answering using plain Cypher. The experimental evaluation of our proof-of-concept prototype on a sample set of use case queries reveals that the approach is promising, and can be a stepping stone to making OBDA applicable to data stored in graph DBMS.

Place, publisher, year, edition, pages
CEUR-WS, 2023
Series
CEUR workshop proceedings., E-ISSN 1613-0073 ; 3515
Keywords
Graph databases, Ontology-based data access, Property graphs, Query rewriting
National Category
Computer Sciences Computer Systems
Identifiers
urn:nbn:se:umu:diva-217217 (URN)2-s2.0-85176468627 (Scopus ID)
Conference
36th International Workshop on Description Logics, DL 2023, Rhodes, Greece, September 2-4, 2023
Available from: 2023-12-01 Created: 2023-12-01 Last updated: 2024-07-02Bibliographically approved
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0002-2344-9658

Search in DiVA

Show all publications