Cem Okulmus

Postdoctoral Researcher at Paderborn University

DBLP Google Scholar GitHub ORCID LinkedIn Email

I currently work as a PostDoc in the Knowledge Representation group at Paderborn University led by Anni-Yasmin Turhan. My recent work has focused on exploring learnability of constraints over graph-structured data in the context of RDF and SHACL.

Previously I was a postdoctoral fellow at Umeå University where I worked with (then) WASP guest professor Diego Calvanese on the topic of temporal ontology-based data-access (OBDA).

I completed my PhD at TU Wien, where my thesis focused on exploring the practical computation of structural decomposition methods for relational queries.

Topics I am interested in include

• Learnability/Separability in various languages over graph-structured data
• Temporal Ontology-Based Data Access
• Ontology-Mediated Query Answering for Graph Queries
• Shape Constraint Languages
• Structural Width Measures over Hypergraphs

CV

Publications

2026

Rewriting Ontology-Mediated Property Graph Queries into GQL Accepted

To be presented at the 35th International ACM Conference on Information and Knowledge Management (CIKM 2026)

Bianca Löhnert, Nikolaus Augsten, Cem Okulmus and Magdalena Ortiz

Will be presented in Rome, Italy, on 7–11 November 2026.

Conference Graph queries Ontology-mediated querying Query rewriting Description logics

PDF arXiv Source Code More Info

This is our latest published work on the topic of bringing Ontology-Based Data-Access to the world of graph data bases. Compared to our previous paper (see ESWC 2025), we consider a much richer set of navigational queries as the input of rewriting, and in the output language we fully exploit the expressive power of GQL, the recently standardised graph query language.

sheval: An RDF data shapes evaluation tool and test-suite for recursive shapes Accepted

To be presented at the 2nd International Workshop on Data Management for Knowledge Graphs (DMKG26)Co-located with the 25th International Semantic Web Conference (ISWC 2026)

Shqiponja Ahmetaj, Iovka Boneva, Jan Hidders, Maxime Jakubowski, José Emilio Labra Gayo, Wim Martens, Filip Murlak, Cem Okulmus, Ognjen Savković, Mantas Šimkus and Dominik Tomaszuk

Will be presented in Bari, Italy, on 25 October 2026.

Workshop SHACL ShEx Graph schemas

PDF arXiv Source Code

Shapes from Examples: Foundations of Shape Learning in Recursive SHACL Accepted

To be presented at the 25th International Semantic Web Conference (ISWC 2026)

Bente Gortworst, Cem Okulmus, Magdalena Ortiz and Anni-Yasmin Turhan

Will be presented in Bari, Italy, on 25–29 October 2026.

Conference SHACL Graph schemas Learnability Description logics

PDF arXiv More Info

Shape Learning refers to the process of generating parts of a SHACL schema (the so-called shapes), in this case from labelled examples. The goal is to find a fitting shape, in the sense that it includes all positively-labelled examples and none of the negatively-labelled ones.
In this work, we provide the first algorithm for learning such fitting shapes for a given fragment of SHACL, computing not only arbitrary fittings, but also the most specific fittings.
This is the start of a larger project, where the ultimate aim is to have systems that can automatically generate entire SHACL schemas, with formal guarantees on its correctness w.r.t. the examples the shapes were learned from.

Querying Interval-Based Temporal Data with SPARQL

33rd International Symposium on Temporal Representation and Reasoning (TIME 2026)Co-located with the 37th International Conference on Principles of Diagnosis and Resilient Systems (DX'26)

Julien Corman, Roman Kontchakov and Cem Okulmus

Presented in Cork, Ireland, on 1–3 September 2026.

Conference Temporal OBDA Query languages

PDF Talk Slides More Info

We present a syntactic extension of SPARQL—built ontop of SPARQL 1.2—that has

1. interval temporal variables as first-class objects,
2. allows simple joining over these temporal variables, and
3. can easily describe user-defined predicate over temporal variables.

This language will serve as the front-end language of a temporal extension of the Ontology-Based Data-Access system ONTOP, which is part of our on-going work.

Common Foundations for Recursive Shape Languages

23rd International Conference on Principles of Knowledge Representation and Reasoning (KR 2026)Co-located with the other conferences of the Federated Logic Conference (FLoC 2026)

Shqiponja Ahmetaj, Iovka Boneva, Jan Hidders, Maxime Jakubowski, José Emilio Labra Gayo, Wim Martens, Fabio Mogavero, Filip Murlak, Cem Okulmus, Ognjen Savković, Mantas Šimkus and Dominik Tomaszuk

Presented in Lisbon, Portugal, on 20–23 July 2026.

Conference SHACL ShEx Graph schemas

PDF arXiv Talk Slides

Reaching for the stars in ${ℰℒ}^{\ast }$ concept learning

39th International Workshop on Description Logics (DL 2026)Co-located with the 23rd International Conference on Principles of Knowledge Representation and Reasoning (KR 2026), as part of the Federated Logic Conference (FLoC 2026)

Bente Gortworst, Cem Okulmus, Magdalena Ortiz and Anni-Yasmin Turhan

Presented in Lisbon, Portugal, on 17–19 July 2026.

Workshop Learnability Description logics

PDF

Selective Use of Yannakakis’ Algorithm for Consistent Performance Gains

28th International Workshop on Design, Optimization, Languages and Analytical Processing of Big Data (DOLAP 2026)Co-located with the 29th International Conference on Extending Database Technology and the 28th International Conference on Database Theory (EDBT/ICDT 2026)

Daniela Böhm, Georg Gottlob, Matthias Lanzinger, Davide Mario Longo, Cem Okulmus, Reinhard Pichler and Alexander Selzer

Won the 🖼Best Paper Award for DOLAP 2026.

Presented in Tampere, Finland, on 24 March 2026.

Workshop Query optimisation

PDF arXiv Source Code

2025

Query Rewriting for Nested Navigational Queries over Property Graphs

38th International Workshop on Description Logics (DL 2025)

Bianca Löhnert, Nikolaus Augsten, Cem Okulmus and Magdalena Ortiz

Presented in Opole, Poland, on 3–6 September 2025.

Workshop Graph queries Ontology-mediated querying Query rewriting Description logics

PDF

Soft and Constrained Hypertree Width

44th Symposium on Principles of Database Systems (PODS 25)Co-located with the 2025 ACM SIGMOD International Conference on Management of Data (SIGMOD 2025)

Volume 3, Proceedings of the ACM on Management of Data

Matthias Lanzinger, Cem Okulmus, Reinhard Pichler, Alexander Selzer and Georg Gottlob

Presented in Berlin, Germany, on 22–27 June 2025. Published on 9 June 2025.

Conference Journal Hypergraph decompositions Query optimisation

PDF arXiv

Towards Practicable Algorithms for Rewriting Graph Queries Beyond DL-Lite

22nd European Semantic Web Conference (ESWC 2025)

Bianca Löhnert, Nikolaus Augsten, Cem Okulmus and Magdalena Ortiz

Presented in Portorož, Slovenia, on 1–5 June 2025.

Conference Graph queries Ontology-mediated querying Query rewriting Description logics

PDF arXiv

Common Foundations for SHACL, ShEx, and PG-Schema

The Web Conference 2025 (WWW '25)

Shqiponja Ahmetaj, Iovka Boneva, Jan Hidders, Katja Hose, Maxime Jakubowski, José Emilio Labra Gayo, Wim Martens, Fabio Mogavero, Filip Murlak, Cem Okulmus, Axel Polleres, Ognjen Savković, Mantas Šimkus and Dominik Tomaszuk

Presented in Sydney, Australia, on 28 April – 2 May 2025.

Conference SHACL ShEx Graph schemas

PDF arXiv Talk Slides

2024

SHACL Validation under the Well-founded Semantics

21st International Conference on Principles of Knowledge Representation and Reasoning (KR 2024)

Cem Okulmus and Mantas Šimkus

Presented in Hanoi, Vietnam, on 2–8 November 2024.

Conference SHACL Graph schemas Well-founded semantics

PDF Source Code Talk Slides

One Language to Rule Them All: Behavioural Querying of Process Data Using SQL

9th International Workshop on Process Querying, Manipulation, and Intelligence (PQMI 2024)Co-located with the 6th International Conference on Process Mining (ICPM 2024)

Jakob Brand, Timotheus Kampik, Cem Okulmus and Matthias Weidlich

Presented in Kongens Lyngby, Denmark, on 14 October 2024.

Workshop Process querying Query languages

PDF

Expressive Power and Complexity Results for SIGNAL, an Industry-scale Process Query Language

22nd International Conference on Business Process Management (BPM 2024) - Forum paper

Timotheus Kampik and Cem Okulmus

Presented in Kraków, Poland, on 1–6 September 2024.

Conference Process querying Query languages Complexity

PDF arXiv

Towards Practicable Algorithms for Rewriting Graph Queries Beyond DL-Lite (Extended Abstract)

37th International Workshop on Description Logics (DL 2024)

Bianca Löhnert, Nikolaus Augsten, Cem Okulmus and Magdalena Ortiz

Presented in Bergen, Norway, on 18–21 June 2024.

Workshop Graph queries Ontology-mediated querying Query rewriting Description logics

PDF

Fast Parallel Hypertree Decompositions in Logarithmic Recursion Depth (Journal article)

Volume 49, ACM Transactions on Database Systems (TODS)

Georg Gottlob, Matthias Lanzinger, Cem Okulmus and Reinhard Pichler

Published on 28 February 2024.

Journal Hypergraph decompositions Parallel algorithms

PDF

2023

Rewriting Ontology-Mediated Navigational Queries into Cypher

36th International Workshop on Description Logics (DL 2023)Co-located with the 20th International Conference on Principles of Knowledge Representation and Reasoning (KR 2023) and the 21st International Workshop on Non-Monotonic Reasoning (NMR 2023)

Nikola Dragovic, Cem Okulmus and Magdalena Ortiz

Presented in Rhodes, Greece, on 2–4 September 2023.

Workshop Graph queries Ontology-mediated querying Query rewriting Description logics

PDF Talk Slides

On the Way to Temporal OBDA Systems (short paper)

15th Alberto Mendelzon International Workshop on Foundations of Data Management (AMW 2023)

Diego Calvanese, Cem Okulmus, Magdalena Ortiz and Mantas Šimkus

Presented in Santiago, Chile, on 22–26 May 2023.

Workshop Temporal OBDA

PDF Talk Slides

Reaching Back to Move Forward: Using Old Ideas to Achieve a New Level of Query Optimization (short paper)

15th Alberto Mendelzon International Workshop on Foundations of Data Management (AMW 2023)

Georg Gottlob, Matthias Lanzinger, Davide Mario Longo, Cem Okulmus, Reinhard Pichler and Alexander Selzer

Presented in Santiago, Chile, on 22–26 May 2023.

Workshop Query optimisation

PDF

Structure-Guided Query Evaluation: Towards Bridging the Gap from Theory to Practice.

Preprint

Georg Gottlob, Matthias Lanzinger, Davide Mario Longo, Cem Okulmus, Reinhard Pichler and Alexander Selzer

First published online on 5 March 2023.

Preprint Hypergraph decompositions Query optimisation

PDF arXiv

Incremental Updates of Generalized Hypertree Decompositions

Volume 27, ACM Journal of Experimental Algorithmics (JEA)

Georg Gottlob, Matthias Lanzinger, Davide Mario Longo and Cem Okulmus

Published on 3 March 2023.

Journal Hypergraph decompositions Incremental algorithms

PDF arXiv

2022

Parallel Computation of Structural Decompositions

PhD Thesis, Technische Universität Wien

Cem Okulmus

Submitted on 19 October 2022. Defended on 29 November 2022.

Thesis Hypergraph decompositions Parallel algorithms

PDF

Fast Parallel Hypertree Decompositions in Logarithmic Recursion Depth.

41st Symposium on Principles of Database Systems (PODS 22)Co-located with the 2022 ACM SIGMOD International Conference on Management of Data (SIGMOD 2022)

Georg Gottlob, Matthias Lanzinger, Cem Okulmus and Reinhard Pichler

Presented in Philadelphia, USA, on 12–17 June 2022.

Conference Hypergraph decompositions Parallel algorithms

PDF arXiv Source Code Talk Slides

Fast and parallel decomposition of constraint satisfaction problems (Journal article)

Volume 27, Constraints - An International Journal

Georg Gottlob, Cem Okulmus and Reinhard Pichler

Published on 3 June 2022.

Journal Hypergraph decompositions Constraint satisfaction Parallel algorithms

PDF

2020

Fast and Parallel Decomposition of Constraint Satisfaction Problems.

29th International Joint Conference on Artificial Intelligence (IJCAI-20)

Georg Gottlob, Cem Okulmus and Reinhard Pichler

Presented online, on 7–15 January 2021.

Conference Hypergraph decompositions Constraint satisfaction Parallel algorithms

PDF Source Code Talk Slides

The Hypertrac Project: Recent progress and future research directions on hypergraph decompositions

Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 17th International Conference (CPAIOR 2020)

Georg Gottlob, Matthias Lanzinger, Davide Mario Longo, Cem Okulmus and Reinhard Pichler

Presented online, on 21–24 September 2020.

Conference Hypergraph decompositions Constraint satisfaction

PDF arXiv

2019

Parallel Computation of Generalized Hypertree Decompositions (short paper)

13th Alberto Mendelzon International Workshop on Foundations of Data Management (AMW 2019)

Georg Gottlob, Cem Okulmus and Reinhard Pichler

Presented in Asunción, Paraguay, on 3–7 June 2019.

Workshop Hypergraph decompositions Parallel algorithms

PDF Talk Slides

Teaching

• University Assistant at DBAI group at Faculty of Informatics, TU Wien.
  Helped with organising the following courses:

  • Database Systems
    • Winter Terms 2018 - 2022
  • Semi-structured Data
    • Summer Terms 2019 - 2022
  • Advanced Database Systems
    • Summer Terms 2020 - 2022

• Teaching Duties as part of the Knowledge Representation group, Paderborn University.
  Helped with organising the following courses:

  • Programming 2
    • Summer Term 2025
  • Modelling
    • Winter Term 2025
  • Proseminar: Gems of Theoretical Computer Science
  • Project Group: Ontology-mediated Validation of Knowledge Graphs

• Thesis Supervision

  • "Multimedia Processing: Real-Time Colour Grading with JIT using the MLT Framework", Pina Kolling, Master Thesis, Umeå University, Supervised by Cem Okulmus and Urban Söderberg, 2024
  • "Comparative Study of Solution-Conflict and Query-Conflict Hypergraphs under Tree Decomposition", Chen Cheng, Bachelor Thesis, Paderborn University, Supervised by Yasir Mahmood and Cem Okulmus, 2026
  • "A Dynamic Programming-Based Implementation for Consistent Query Answering", Wenghao Bi, Bachelor Thesis, Paderborn University, Supervised by Yasir Mahmood and Cem Okulmus, 2026

Scientific Engagement

• Member of the Programme Committee for the following conferences

  • JELIA 2023 — 18th edition of the European Conference on Logics in Artificial Intelligence
  • KR 2024 — 21st International Conference on Principles of Knowledge Representation and Reasoning
  • JELIA 2025 — 19th edition of the European Conference on Logics in Artificial Intelligence
  • ECAI 2025 — 28th European Conference on Artificial Intelligence
  • KR 2026 — 23rd International Conference on Principles of Knowledge Representation and Reasoning
  • CIKM 2026 — 35th International ACM Conference on Information and Knowledge Management

• Member of the Programme Committee for the following workshops

  • XLoKR-25 — 6th Workshop on Explainable Logic-Based Knowledge Representation
  • DL 2026 — 39th International Workshop on Description Logics
  • XLoKR-26 — 7th Workshop on Explainable Logic-Based Knowledge Representation

Etc

• Presentation Of Interactive Normalform Transformations (point)
  Tool I developed as part of teaching a database course to come up with functional dependencies in various normal forms. The source code can be found here.
• shaWell
  A SHACL validator that I wrote which supports the 1.0 SHACL Core standard, and has support for recursive shapes. It follows the well-founded semantics for SHACL, as proposed in our paper.