Umeå University's logo

umu.sePublications
Change search
Link to record
Permanent link

Direct link
Publications (10 of 14) 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
Di Stefano, F. & Šimkus, M. (2024). Stable model semantics for description logic terminologies. In: Michael Wooldridge; Jennifer Dy; Sriraam Natarajan (Ed.), Proceedings of the 38th AAAI conference on artificial intelligence: . Paper presented at 38th AAAI Conference on Artificial Intelligence, AAAI 2024, Vancouver, Canada, February 20-27, 2024 (pp. 10484-10492). Association for the Advancement of Artificial Intelligence, 38
Open this publication in new window or tab >>Stable model semantics for description logic terminologies
2024 (English)In: Proceedings of the 38th AAAI conference on artificial intelligence / [ed] Michael Wooldridge; Jennifer Dy; Sriraam Natarajan, Association for the Advancement of Artificial Intelligence , 2024, Vol. 38, p. 10484-10492Conference paper, Published paper (Refereed)
Abstract [en]

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

Place, publisher, year, edition, pages
Association for the Advancement of Artificial Intelligence, 2024
Series
Proceedings of the AAAI Conference on Artificial Intelligence, ISSN 2159-5399, E-ISSN 2374-3468 ; 38:9
National Category
Computer Sciences
Identifiers
urn:nbn:se:umu:diva-223237 (URN)10.1609/aaai.v38i9.28917 (DOI)2-s2.0-85189359529 (Scopus ID)1577358872 (ISBN)9781577358879 (ISBN)
Conference
38th AAAI Conference on Artificial Intelligence, AAAI 2024, Vancouver, Canada, February 20-27, 2024
Funder
Wallenberg AI, Autonomous Systems and Software Program (WASP)
Available from: 2024-04-19 Created: 2024-04-19 Last updated: 2024-04-19Bibliographically 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
Calvanese, D., Okulmus, C., Ortiz, M. & Šimkus, M. (2023). On the way to temporal OBDA systems. In: Proceedings of the 15th Alberto Mendelzon International Workshop on Foundations of Data Management (AMW 2023): . Paper presented at 15th Alberto Mendelzon International Workshop on Foundations of Data Management, AMW 2023, Santiago de Chile, Chile, May 22-26, 2023. CEUR-WS
Open this publication in new window or tab >>On the way to temporal OBDA systems
2023 (English)In: Proceedings of the 15th Alberto Mendelzon International Workshop on Foundations of Data Management (AMW 2023), CEUR-WS , 2023Conference paper, Published paper (Refereed)
Abstract [en]

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

Place, publisher, year, edition, pages
CEUR-WS, 2023
Series
CEUR Workshop proceedings, ISSN 1613-0073 ; 3409
Keywords
description logic, Ontology-based data access, temporal database
National Category
Computer Sciences
Identifiers
urn:nbn:se:umu:diva-211805 (URN)2-s2.0-85162909647 (Scopus ID)
Conference
15th Alberto Mendelzon International Workshop on Foundations of Data Management, AMW 2023, Santiago de Chile, Chile, May 22-26, 2023
Funder
Knut and Alice Wallenberg Foundation
Available from: 2023-07-11 Created: 2023-07-11 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
Ghosh, A., Šimkus, M. & Calvanese, D. (2023). Semantic querying of integrated raster and relational data: a virtual knowledge graph approach. In: Jan Vanthienen; Tomáš Kliegr; Paul Fodor; Davide Lanti; Dörthe Arndt; Egor V. Kostylev; Theodoros Mitsikas; Ahmet Soylu (Ed.), Proceedings of the 17th International Rule Challenge and 7th Doctoral Consortium @ RuleML+RR 2023 (RuleML+RR-Companion 2023), Oslo, Norway, 18 - 20 September, 2023: . Paper presented at 17th International Rule Challenge and 7th Doctoral Consortium @ RuleM+RR, RuleML+RR-Companion 2023, Oslo, September 18-20, 2023. CEUR-WS, Article ID 8240.
Open this publication in new window or tab >>Semantic querying of integrated raster and relational data: a virtual knowledge graph approach
2023 (English)In: Proceedings of the 17th International Rule Challenge and 7th Doctoral Consortium @ RuleML+RR 2023 (RuleML+RR-Companion 2023), Oslo, Norway, 18 - 20 September, 2023 / [ed] Jan Vanthienen; Tomáš Kliegr; Paul Fodor; Davide Lanti; Dörthe Arndt; Egor V. Kostylev; Theodoros Mitsikas; Ahmet Soylu, CEUR-WS , 2023, article id 8240Conference paper, Published paper (Refereed)
Abstract [en]

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

Place, publisher, year, edition, pages
CEUR-WS, 2023
Series
CEUR Workshop Proceedings, ISSN 1613-0073 ; 3485
Keywords
Artificial Intelligence (AI), Knowledge Representation, Multi-Dimensional Arrays, Ontology-Based Data Access (OBDA), Raster Data, Relational Data, Spatial-temporal reasoning, Vector Data, Virtual Knowledge Graph (VKG)
National Category
Computer Sciences
Identifiers
urn:nbn:se:umu:diva-215876 (URN)2-s2.0-85174146079 (Scopus ID)
Conference
17th International Rule Challenge and 7th Doctoral Consortium @ RuleM+RR, RuleML+RR-Companion 2023, Oslo, September 18-20, 2023
Funder
Wallenberg AI, Autonomous Systems and Software Program (WASP)
Available from: 2023-11-06 Created: 2023-11-06 Last updated: 2023-11-06Bibliographically approved
Wandji, R. E., Šimkus, M. & Calvanese, D. (2023). Towards techniques for updating virtual knowledge graphs. In: Jan Vanthienen; Tomáš Kliegr; Paul Fodor; Davide Lanti; Dörthe Arndt; Egor V. Kostylev; Theodoros Mitsikas; Ahmet Soylu (Ed.), Proceedings of the 17th International Rule Challenge and 7th Doctoral Consortium @ RuleML+RR 2023 (RuleML+RR-Companion 2023), Oslo, Norway, 18 - 20 September, 2023: . Paper presented at 17th International Rule Challenge and 7th Doctoral Consortium @ RuleM+RR, RuleML+RR-Companion 2023, Oslo, September 18-20, 2023. CEUR-WS, Article ID 9284.
Open this publication in new window or tab >>Towards techniques for updating virtual knowledge graphs
2023 (English)In: Proceedings of the 17th International Rule Challenge and 7th Doctoral Consortium @ RuleML+RR 2023 (RuleML+RR-Companion 2023), Oslo, Norway, 18 - 20 September, 2023 / [ed] Jan Vanthienen; Tomáš Kliegr; Paul Fodor; Davide Lanti; Dörthe Arndt; Egor V. Kostylev; Theodoros Mitsikas; Ahmet Soylu, CEUR-WS , 2023, article id 9284Conference paper, Published paper (Refereed)
Abstract [en]

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

Place, publisher, year, edition, pages
CEUR-WS, 2023
Series
CEUR Workshop Proceedings, ISSN 1613-0073 ; 3485
Keywords
Knowledge Representation, Ontology-based Data Access, View Updates, Virtual Knowledge Graph (VKG)
National Category
Computer Sciences Computer Systems
Identifiers
urn:nbn:se:umu:diva-215832 (URN)2-s2.0-85174215075 (Scopus ID)
Conference
17th International Rule Challenge and 7th Doctoral Consortium @ RuleM+RR, RuleML+RR-Companion 2023, Oslo, September 18-20, 2023
Funder
Wallenberg AI, Autonomous Systems and Software Program (WASP)
Available from: 2023-11-06 Created: 2023-11-06 Last updated: 2023-11-06Bibliographically approved
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0003-0632-0294

Search in DiVA

Show all publications