FWF Stand-alone Project: Ontology-mediated Queries for Graph Databases

Abstract
Modern software applications need to manage and access increasingly complex data, which often does not conform to rigid schemas used in traditional databases. Graph databases and Description Logics (DLs) provide complementary tools for managing such loosely-structured information. For example, an ontology written in a DL can be used to capture knowledge about a given application domain in a machine readable format. This knowledge can then be used for answering ontology-mediated queries (OMQs): a user query is evaluated not directly over the available data, but a reasoning engine is employed to incorporate the knowledge in the ontology, possibly inferring facts that are not explicitly present in the data.

OMQs and queries over graph databases have many similarities, but they also have major differences that we aim to reconcile in this project. In particular, when answering OMQs one makes the so-called open-world assumption (information is assumed to be incomplete), while the closed-world assumption is made in graph databases (information completeness is assumed). It is acknowledged however that both assumptions are too strong, and that the users should have the ability to specify which part of the data is to be assumed as complete and which as incomplete. Second, OMQs do not support navigational features that are very common in languages for querying graph databases and other representations of loosely- structured data (e.g., the path expressions in the XPath query language for XML documents, or the property paths in the SPARQL query language for RDF data). In this project, we will consider extensions of standard OMQs with features that overcome the above two drawbacks, i.e. we will study OMQs that allow to mix the open-world and the closed-world assumptions, and that simultaneously support navigational features. For such rich OMQs, we will study the following fundamental database-theoretic properties:

- The first major goal is to compare the expressive power of the considered OMQs with the expressive power of classic database query languages. To this end, we will mainly develop translations from OMQs into suitable variations of Datalog. This will also enable us to transfer existing results from the setting of Datalog to the setting of OMQs, e.g., to reuse existing efficient Datalog engines for answering OMQs.

- The second major goal is to study the computational complexity of reasoning tasks to support the design of OMQs. In particular, we will investigate the query containment and the query emptiness problems for the OMQs introduced in the project. These static analysis problems lie at the core of query design and optimization techniques.

Conference and Journal Publications

Shqiponja Ahmetaj, Bianca Loehnert, Magdalena Ortiz, Mantas Simkus
Magic Shapes for Validation in SHACL
Proceedings of the VLDB Endowment. Volume 15 Issue 10. 2022. PDF

Robert David, Shqiponja Ahmetaj, Axel Polleres, Mantas Simkus
Repairing SHACL Constraint Violations using Answer Set Programming
The 21th International Semantic Web Conference (ISWC 2022). 2022. PDF

Shqiponja Ahmetaj, Robert David, Magdalena Ortiz, Axel Polleres, Bojken Shehu, Mantas Simkus
Reasoning about Explanations for Non-validation in SHACL
Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning (KR 2021). 2021. PDF

Sanja Lukumbuzya, Mantas Simkus
Bounded Predicates in Description Logics with Counting
Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI 2021). 2021. PDF VIDEO

Shqiponja Ahmetaj, Magdalena Ortiz, Mantas Simkus
Polynomial rewritings from expressive Description Logics with closed predicates to variants of Datalog
Artificial Intelligence. 2020. PDF

Thomas Schneider, Mantas Simkus
Ontologies and Data Managament: A Brief Survery
German Journal of Artificial Intelligence. 2020. PDF

Sanja Lukumbuzya, Magdalena Ortiz, Mantas Simkus
Resilient Logic Programs: Answer Set Programs Challenged by Ontologies
Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI 2020). 2020. PDF

Medina Andresel, Magdalena Ortiz, Mantas Simkus
Query Rewriting for Ontology-mediated Conditional Answers
Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI 2020). 2020. PDF

Tomasz Gogacz, Victor Gutierrez Basulto, Yazmin A. Ibanez Garcia, Filip Murlak, Magdalena Ortiz, Mantas Simkus
Ontology Focusing: Knowledge-enriched Databases on Demand
Proceedings of the 24th European Conference on Artificial Intelligence (ECAI 2020). 2020. PDF VIDEO

Medina Andresel, Julien Corman, Magdalena Ortiz, Juan L. Reutter, Ognjen Savkovic, Mantas Simkus
Stable Model Semantics for Recursive SHACL
Proceedings of The Web Conference 2020 (WWW 2020). 2020. PDF VIDEO

Nadia Labai, Magdalena Ortiz, Mantas Simkus
An ExpTime Upper Bound for ALC with Integers
Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning (KR 2020). 2020. PDF VIDEO

Sanja Lukumbuzya, Magdalena Ortiz, Mantas Simkus
Datalog Rewritability and Data Complexity of ALCHOIF with Closed Predicates
Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning (KR 2020). 2020. PDF VIDEO

Medina Andresel, Yazmin A. Ibanez Garcia, Magdalena Ortiz, Mantas Simkus
Relaxing and Restraining Queries for OBDA
Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI 2019). 2019. PDF

Nadia Labai, Tomer Kotek, Magdalena Ortiz, Helmut Veith
Pebble-Intervals Automata and FO2 with Two Orders
Language and Automata Theory and Applications - 14th International Conference, LATA 2020 PDF

Magdalena Ortiz
Ontology-Mediated Queries from Examples: a Glimpse at the DL-Lite Case
GCAI 2019. Proceedings of the 5th Global Conference on Artificial Intelligence. PDF

Shqiponja Ahmetaj, Magdalena Ortiz, Mantas Simkus
Rewriting Guarded Existential Rules into Small Datalog Programs
Proceedings of the 21st International Conference on Database Theory (ICDT 2018). 2018. PDF

Labinot Bajraktari, Magdalena Ortiz, Mantas Simkus
Combining Rules and Ontologies into Clopen Knowledge Bases
Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI 2018). 2018. PDF

Sebastian Rudolph, Mantas Simkus
The Triguarded Fragment of First-order Logic
Proceedings of the 22nd International Conference on Logic for Programming, Artificial Intelligence and Reasoning (LPAR-22). 2018. PDF

Labinot Bajraktari, Magdalena Ortiz, Mantas Simkus
Compiling Model Representations for Querying Large ABoxes in Expressive DLs
Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI 2018). 2018. PDF

Medina Andresel, Yazmin A. Ibanez Garcia, Magdalena Ortiz, Mantas Simkus
Relaxing and Restraining Queries for OBDA - Extended Abstract
Proceedings of the 16th International Conference on Principles of Knowledge Representation and Reasoning (KR 2018). 2018. PDF

Víctor Gutiérrez-Basulto, Yazmín Angélica Ibáñez-García, Jean Christoph Jung
Answering Regular Path Queries over SQ Ontologies
Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18) PDF

Magdalena Ortiz
Improving Data Management Using Domain Knowledge
Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18) PDF

Workshops

Adrian Chmurovic, Mantas Simkus
Well-founded Semantics for Recursive SHACL. Datalog 2022: 2-13
Proceedings of the 4th International Workshop on the Resurgence of Datalog in Academia and Industry (Datalog-2.0 2022) PDF

Federica Di Stefano, Magdalena Ortiz, Mantas Simkus
Pointwise Circumscription in Description Logics
Proceedings of the 34th International Workshop on Description Logics (DL 2022). PDF

Shqiponja Ahmetaj, Bianca Loehnert, Magdalena Ortiz, Mantas Simkus
Magic Shapes for Validation in SHACL
Proceedings of the ISWC 2021 Posters, Demos and Industry Tracks. 2021. PDF

Shqiponja Ahmetaj, Robert David, Magdalena Ortiz, Axel Polleres, Bojken Shehu, Mantas Simkus
Explanations for Non-validation in SHACL
Proceedings of the ISWC 2021 Posters, Demos and Industry Tracks. 2021. PDF

Shqiponja Ahmetaj, Robert David, Magdalena Ortiz, Axel Polleres, Bojken Shehu, Mantas Simkus
Reasoning about Explanations for Non-validation in SHACL (Extended Abstract)
Proceedings of the 34th International Workshop on Description Logics (DL 2021). 2021. PDF

Magdalena Ortiz
Rewritability Results for OMQs with Closed Predicates
Proceedings of the 33rd International Workshop on Description Logics (DL 2020). PDF

Medina Andresel, Yazmín Ibáñez-García, Magdalena Ortiz
A Framework for Exploratory Query Answering with Ontologies
Proceedings of the 33rd International Workshop on Description Logics (DL 2020). PDF

Magdalena Ortiz, Sanja Pavlovic, Mantas Simkus
Answer Set Programs Challenged by Ontologies
Proceedings of the 32nd International Workshop on Description Logics (DL 2019). 2019. PDF

Mantas Simkus, Sebestian Rudolph
Satisfiability in the Triguarded Fragment of First-Order Logic
Proceedings of the 31st International Workshop on Description Logics (DL 2018). 2018. PDF

Medina Andresel, Yazmin A. Ibanez Garcia, Magdalena Ortiz, Mantas Simkus
Taming Complex Role Inclusions for DL-Lite
Proceedings of the 31st International Workshop on Description Logics (DL 2018). 2018. PDF

Edited Volumes

Mantas Simkus, Ivan Varzinczak
Reasoning Web. Declarative Artificial Intelligence - 17th International Summer School 2021
Leuven, Belgium, September 8-15, 2021, Tutorial Lectures. 2022. PDF

Thomas Schneider, Mantas Simkus
Special Issue on Ontologies and Data Management: Part I
German Journal of Artificial Intelligence. 2020. PDF

Thomas Schneider, Mantas Simkus
Special Issue on Ontologies and Data Management: Part II
German Journal of Artificial Intelligence. 2020. PDF

Mantas Simkus, Grant Weddell
Proceedings of the 32nd International Workshop on Description Logics
Oslo, Norway, June 18-21. 2019. PDF

Ahmet Soylu, Sotiris Moschoyiannis, Guido Governatori, Mantas Simkus, Petros Stefaneas, Alexander Steen, Adrian Giurca
Proceedings of RuleML+RR 2019 Doctoral Consortium and Rule Challenge
Bolzano, Italy, September 16-24, 2019. 2019. PDF