@inproceedings{65178,
abstract = {{Large intermediate results can cause join queries to run unexpectedly long. This problem is particularly common for analytical queries, which aggregate data over many tables to produce a comparatively small final output, and queries on graph data, where intermediate results blow up quickly. Recent work inspired by Yannakakis’ algorithm approaches this by modifying the query engine to avoid materializing unnecessary tuples. However, this requires significant changes to the core of the system, which is not feasible in many situations such as cloud environments or proprietary systems.
In this work, we propose a flexible approach for optimizing long-running join queries from the outside of the DBMS. Rewriting-based realizations of Yannakakis’ algorithm suffer from inherent overhead due to the creation of intermediate tables. Thus, we present an approach for detecting and targeting queries which would benefit from a Yannakakis-style optimization. We introduce a new benchmark combining 5 standard benchmarks and augmenting them with additional instances, which provides a sufficient size and diversity for a machine learning based solution. On PostgreSQL, DuckDB and SparkSQL, slowdowns on queries where the rewriting is counterproductive are mostly avoided, as opposed to a naïve application of the rewriting, and we observe significant improvements in end-to-end runtimes over standard query execution and unconditional rewriting.}},
author = {{Böhm, Daniela and Gottlob, Georg and Lanzinger, Matthias and Longo, Davide Mario and Okulmus, Cem and Pichler, Reinhard and Selzer, Alexander}},
booktitle = {{Proceedings of the 28th International Workshop on Design, Optimization, Languages and Analytical Processing of Big Data (DOLAP 2026)}},
keywords = {{Join Queries, Acyclic Queries, Query Processing}},
title = {{{Selective Use of Yannakakis’ Algorithm for Consistent Performance Gains}}},
year = {{2026}},
}
@inproceedings{65489,
author = {{Okulmus, Cem and Ahmetaj, Shqiponja and Boneva, Iovka and Hidders, Jan and Jakubowski, Maxime and Labra Gayo, José Emilio and Martens, Wim and Mogavero, Fabio and Murlak, Filip and Savković, Ognjen and Šimkus, Mantas and Tomaszuk, Dominik }},
booktitle = {{Proceedings of the 23rd International Conference on Principles of Knowledge Representation and Reasoning (KR 2026)}},
location = {{Lisbon, Portugal}},
title = {{{Common Foundations for Recursive Shape Languages}}},
year = {{2026}},
}
@inproceedings{59840,
abstract = {{The Semantic Web and Graph Database communities have developed three distinct schema languages for RDF and graph-structured data: SHACL, ShEx, and PG-Schema. Each language has its unique approach to defining constraints and validating graph data. In this work, we provide formal, concise definitions of the core components of each of these schema languages. We employ a uniform framework to facilitate a comprehensive comparison between the languages and identify a common set of functionalities, shedding light on both overlapping and distinctive features of the three languages.
}},
author = {{Ahmetaj, Shqiponja and Boneva, Iovka and Hidders, Jan and Hose, Katja and Jakubowski, Maxime and Labra Gayo, Jose Emilio and Martens, Wim and Mogavero, Fabio and Murlak, Filip and Okulmus, Cem and Polleres, Axel and Savković, Ognjen and Šimkus, Mantas and Tomaszuk, Dominik}},
booktitle = {{Proceedings of the ACM on Web Conference 2025}},
location = {{Sidney, Australia}},
pages = {{8--12}},
publisher = {{ACM}},
title = {{{Common Foundations for SHACL, ShEx, and PG-Schema}}},
doi = {{10.1145/3696410.3714694}},
year = {{2025}},
}
@inproceedings{63786,
author = {{Löhnert, Bianca and Augsten, Nikolaus and Okulmus, Cem and Ortiz, Magdalena}},
booktitle = {{Proceedings of the 38th International Workshop on Description Logics (DL 2025), Opole, Poland, September 3-6, 2025.}},
editor = {{Tendera, Lidia and Ibanez Garcia, Yazmin and Koopmann, Patrick}},
title = {{{Query Rewriting for Nested Navigational Queries over Property Graphs}}},
volume = {{4091}},
year = {{2025}},
}
@unpublished{61065,
abstract = {{Abduction is the task of computing a sufficient extension of a knowledge base (KB) that entails a conclusion not entailed by the original KB. It serves to compute explanations, or hypotheses, for such missing entailments. While this task has been intensively investigated for perfect data and under classical semantics, less is known about abduction when erroneous data results in inconsistent KBs. In this paper we define a suitable notion of abduction under repair semantics and propose a set of minimality criteria that guides abduction towards `useful' hypotheses. We provide initial complexity results on deciding existence of and verifying abductive solutions with these criteria, under different repair semantics and for the description logics DL-Lite and EL_bot.}},
author = {{Haak, Anselm and Koopmann, Patrick and Mahmood, Yasir and Turhan, Anni-Yasmin}},
booktitle = {{arXiv:2507.21955}},
title = {{{Why not? Developing ABox Abduction beyond Repairs}}},
year = {{2025}},
}
@inproceedings{63888,
author = {{Haak, Anselm and Koopmann, Patrick and Mahmood, Yasir and Turhan, Anni-Yasmin}},
booktitle = {{Proceedings of the 38th International Workshop on Description Logics - DL 2025}},
editor = {{Tendera, Lidia and Ibanez Garcia, Yazmin and Koopmann, Patrick}},
location = {{Opole, Poland}},
title = {{{Why not? Developing ABox Abduction beyond Repairs}}},
year = {{2025}},
}
@article{60496,
abstract = {{Hypertree decompositions provide a way to evaluate Conjunctive Queries (CQs) in polynomial time, where the exponent of this polynomial is determined by the width of the decomposition. In theory, the goal of efficient CQ evaluation therefore has to be a minimisation of the width. However, in practical settings, it turns out that there are also other properties of a decomposition that influence the performance of query evaluation. It is therefore of interest to restrict the computation of decompositions by constraints and to guide this computation by preferences. To this end, we propose a novel framework based on candidate tree decompositions, which allows us to introduce soft hypertree width (shw). This width measure is a relaxation of hypertree width (hw); it is never greater than hw and, in some cases, shw may actually be lower than hw. Most importantly, shw preserves the tractability of deciding if a given CQ is below some fixed bound, while offering more algorithmic flexibility. In particular, it provides a natural way to incorporate preferences and constraints into the computation of decompositions. A prototype implementation and preliminary experiments confirm that this novel framework can indeed have a practical impact on query evaluation.}},
author = {{Lanzinger, Matthias and Okulmus, Cem and Pichler, Reinhard and Selzer, Alexander and Gottlob, Georg}},
issn = {{2836-6573}},
journal = {{Proceedings of the ACM on Management of Data}},
location = {{Berlin}},
number = {{2}},
pages = {{1--25}},
publisher = {{Association for Computing Machinery (ACM)}},
title = {{{Soft and Constrained Hypertree Width}}},
doi = {{10.1145/3725251}},
volume = {{3}},
year = {{2025}},
}
@inproceedings{60497,
abstract = {{Despite the advantages that the virtual knowledge graph paradigm has brought to many application domains, state-of-the-art systems still do not support popular graph database management systems like Neo4j. Their query rewriting algorithms focus on languages like conjunctive queries and their unions, which were developed for relational data and are poorly suited for graph data. Moreover, they also limit the expressiveness of the ontology languages that admit rewritings, restricting them to those that enjoy the so-called FO-rewritability property. Rewritings have thus focused on the DL-Lite family of Description Logics. In this paper, we propose a technique for rewriting a family of navigational queries for a suitably tailored fragment of ELHI. Leveraging navigational features in the target query language, we can include some widely-used axiom shapes not supported by DL-Lite. We implemented a proof-of-concept prototype that rewrites into Cypher queries, and tested it on a real-world cognitive neuroscience use case with promising results.}},
author = {{Löhnert, Bianca and Augsten, Nikolaus and Okulmus, Cem and Ortiz, Magdalena}},
booktitle = {{The Semantic Web - 22nd European Semantic Web Conference, {ESWC} 2025, Portoroz, Slovenia, June 1-5, 2025, Proceedings, Part {I}}},
isbn = {{9783031945748}},
issn = {{0302-9743}},
keywords = {{Ontology-based Data Access, Property Graphs, Navigational Queries}},
location = {{Portorož, Slovenia}},
pages = {{342----361}},
publisher = {{Springer Nature Switzerland}},
title = {{{Towards Practicable Algorithms for Rewriting Graph Queries Beyond DL-Lite}}},
doi = {{10.1007/978-3-031-94575-5_19}},
volume = {{15718}},
year = {{2025}},
}
@article{61471,
author = {{Governatori, Guido and Turhan, Anni-Yasmin}},
journal = {{Theory Pract. Log. Program.}},
number = {{2}},
pages = {{132–133}},
title = {{{Introduction to the Special Issue on Logic Rules and Reasoning: Selected Papers From the 6th International Joint Conference on Rules and Reasoning (RuleML+RR 2022)}}},
doi = {{10.1017/S1471068425000079}},
volume = {{25}},
year = {{2025}},
}
@article{61874,
abstract = {{
We study descriptive complexity of counting complexity classes in the range from #P to
\({\text{#}\!\cdot\!\text{NP}}\)
. The proof of Fagin’s characterization of NP by existential second-order logic generalizes to the counting setting in the following sense: The class #P can be logically described as the class of functions counting satisfying assignments to free relation variables in first-order formulae. This was first observed by Saluja et al. (1995). In this paper we extend this study to classes beyond #P and extensions of first-order logic with team semantics. These team-based logics are closely related to existential second-order logic and its fragments, hence our results also shed light on the complexity of counting for extensions of first-order logic in Tarski’s semantics. Our results show that the class
\({\text{#}\!\cdot\!\text{NP}}\)
can be logically characterized by independence logic and existential second-order logic, whereas dependence logic and inclusion logic give rise to subclasses of
\({\text{#}\!\cdot\!\text{NP}}\)
and #P , respectively. We further relate the class obtained from inclusion logic to the complexity class
\({\text{TotP}} \subseteq{\text{#P}}\)
.
}},
author = {{Haak, Anselm and Kontinen, Juha and Müller, Fabian and Vollmer, Heribert and Yang, Fan}},
issn = {{1529-3785}},
journal = {{ACM Transactions on Computational Logic}},
publisher = {{Association for Computing Machinery (ACM)}},
title = {{{Counting of Teams in First-Order Team Logics}}},
doi = {{10.1145/3771721}},
year = {{2025}},
}
@inproceedings{55479,
author = {{Peñaloza, Rafael and Turhan, Anni-Yasmin}},
booktitle = {{Rules and Reasoning - Eighth International Joint Conference, RuleML+RR 2024, Proceedings}},
editor = {{Kirrane, Sabrina and Simkus, Mantas and Soylu, Ahmet and Roman, Dumitru}},
publisher = {{Springer}},
title = {{{Reasoning in Rough Description Logics with Multiple Indiscernibility Relations}}},
doi = {{10.1007/978-3-031-72407-7\_11}},
year = {{2024}},
}
@inproceedings{56158,
author = {{Gil, Oliver Fernández and Patrizi, Fabio and Perelli, Giuseppe and Turhan, Anni-Yasmin}},
booktitle = {{Proceedings of the 37th International Workshop on Description Logics (DL 2024), Bergen, Norway, June 18-21, 2024}},
editor = {{Giordano, Laura and Jung, Jean Christoph and Ozaki, Ana}},
publisher = {{CEUR-WS.org}},
title = {{{Optimal Alignment of Temporal Knowledge Bases (Extended Abstract)}}},
volume = {{3739}},
year = {{2024}},
}
@inproceedings{56159,
author = {{Peñaloza, Rafael and Turhan, Anni-Yasmin}},
booktitle = {{Proceedings of the 37th International Workshop on Description Logics (DL 2024), Bergen, Norway, June 18-21, 2024}},
editor = {{Giordano, Laura and Jung, Jean Christoph and Ozaki, Ana}},
publisher = {{CEUR-WS.org}},
title = {{{Rough, Rougher, Roughest: Extending EL with a Hierarchy of Indiscernibility Relations}}},
volume = {{3739}},
year = {{2024}},
}
@article{52861,
author = {{Gil, Oliver Fernández and Patrizi, Fabio and Perelli, Giuseppe and Turhan, Anni-Yasmin}},
journal = {{CoRR}},
title = {{{Optimal Alignment of Temporal Knowledge Bases}}},
doi = {{10.48550/ARXIV.2307.15439}},
volume = {{abs/2307.15439}},
year = {{2023}},
}
@inproceedings{52913,
author = {{Turhan, Anni-Yasmin}},
booktitle = {{Proceedings of the 36th International Workshop on Description Logics {(DL} 2023) co-located with the 20th International Conference on Principles of Knowledge Representation and Reasoning and the 21st International Workshop on Non-Monotonic Reasoning {(KR} 2023 and NMR 2023)., Rhodes, Greece, September 2-4, 2023}},
editor = {{Kutz, Oliver and Lutz, Carsten and Ozaki, Ana}},
publisher = {{CEUR-WS.org}},
title = {{{Brushing-up DLs to Cope with Imperfect Data (Abstract of Joint DL+NMR Invited Talk)}}},
volume = {{3515}},
year = {{2023}},
}
@inproceedings{54997,
author = {{Turhan, Anni-Yasmin}},
booktitle = {{Proceedings of the 36th International Workshop on Description Logics {(DL} 2023) co-located with the 20th International Conference on Principles of Knowledge Representation and Reasoning and the 21st International Workshop on Non-Monotonic Reasoning {(KR} 2023 and NMR 2023)., Rhodes, Greece, September 2-4, 2023}},
editor = {{Kutz, Oliver and Lutz, Carsten and Ozaki, Ana}},
publisher = {{CEUR-WS.org}},
title = {{{Brushing-up DLs to Cope with Imperfect Data (Abstract of Joint DL+NMR Invited Talk)}}},
volume = {{3515}},
year = {{2023}},
}
@inproceedings{56096,
author = {{Gil, Oliver Fernández and Patrizi, Fabio and Perelli, Giuseppe and Turhan, Anni-Yasmin}},
booktitle = {{ECAI 2023 - 26th European Conference on Artificial Intelligence, September 30 - October 4, 2023, Kraków, Poland - Including 12th Conference on Prestigious Applications of Intelligent Systems (PAIS 2023)}},
editor = {{Gal, Kobi and Nowé, Ann and Nalepa, Grzegorz J. and Fairstein, Roy and Radulescu, Roxana}},
pages = {{708–715}},
publisher = {{IOS Press}},
title = {{{Optimal Alignment of Temporal Knowledge Bases}}},
doi = {{10.3233/FAIA230335}},
volume = {{372}},
year = {{2023}},
}
@inbook{52859,
author = {{de Camargo e Souza Câmara, Igor and Turhan, Anni-Yasmin}},
booktitle = {{Logics in Artificial Intelligence}},
isbn = {{9783031436185}},
issn = {{0302-9743}},
publisher = {{Springer Nature Switzerland}},
title = {{{Deciding Subsumption in Defeasible 𝓔𝓛𝓘⊥ with Typicality Models}}},
doi = {{10.1007/978-3-031-43619-2_36}},
year = {{2023}},
}
@article{52862,
author = {{Turhan, Anni-Yasmin}},
issn = {{0933-1875}},
journal = {{KI - Künstliche Intelligenz}},
keywords = {{Artificial Intelligence}},
number = {{1}},
pages = {{1--4}},
publisher = {{Springer Science and Business Media LLC}},
title = {{{A Double Take at Conferences: The Hybrid Format}}},
doi = {{10.1007/s13218-022-00758-6}},
volume = {{36}},
year = {{2022}},
}
@inproceedings{52923,
author = {{de Camargo e Souza Câmara, Igor and Turhan, Anni-Yasmin}},
booktitle = {{Proceedings of the 20th International Workshop on Non-Monotonic Reasoning, NMR 2022, Part of the Federated Logic Conference (FLoC 2022), Haifa, Israel, August 7-9, 2022}},
editor = {{Arieli, Ofer and Casini, Giovanni and Giordano, Laura}},
pages = {{159–162}},
publisher = {{CEUR-WS.org}},
title = {{{Rational Defeasible Subsumption in DLs with Nested Quantifiers: the Case of ELI\(\perp\)}}},
volume = {{3197}},
year = {{2022}},
}