---
_id: '65178'
abstract:
- lang: eng
text: "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.\r\nIn 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:
- first_name: Daniela
full_name: Böhm, Daniela
last_name: Böhm
- first_name: Georg
full_name: Gottlob, Georg
last_name: Gottlob
- first_name: Matthias
full_name: Lanzinger, Matthias
last_name: Lanzinger
- first_name: Davide Mario
full_name: Longo, Davide Mario
last_name: Longo
- first_name: Cem
full_name: Okulmus, Cem
id: '114410'
last_name: Okulmus
orcid: 0000-0002-7742-0439
- first_name: Reinhard
full_name: Pichler, Reinhard
last_name: Pichler
- first_name: Alexander
full_name: Selzer, Alexander
last_name: Selzer
citation:
ama: 'Böhm D, Gottlob G, Lanzinger M, et al. Selective Use of Yannakakis’ Algorithm
for Consistent Performance Gains. In: Proceedings of the 28th International
Workshop on Design, Optimization, Languages and Analytical Processing of Big Data
(DOLAP 2026). ; 2026.'
apa: Böhm, D., Gottlob, G., Lanzinger, M., Longo, D. M., Okulmus, C., Pichler, R.,
& Selzer, A. (2026). Selective Use of Yannakakis’ Algorithm for Consistent
Performance Gains. Proceedings of the 28th International Workshop on Design,
Optimization, Languages and Analytical Processing of Big Data (DOLAP 2026).
bibtex: '@inproceedings{Böhm_Gottlob_Lanzinger_Longo_Okulmus_Pichler_Selzer_2026,
place={Tampere, Finland}, title={Selective Use of Yannakakis’ Algorithm for Consistent
Performance Gains}, booktitle={Proceedings of the 28th International Workshop
on Design, Optimization, Languages and Analytical Processing of Big Data (DOLAP
2026)}, author={Böhm, Daniela and Gottlob, Georg and Lanzinger, Matthias and Longo,
Davide Mario and Okulmus, Cem and Pichler, Reinhard and Selzer, Alexander}, year={2026}
}'
chicago: Böhm, Daniela, Georg Gottlob, Matthias Lanzinger, Davide Mario Longo, Cem
Okulmus, Reinhard Pichler, and Alexander Selzer. “Selective Use of Yannakakis’
Algorithm for Consistent Performance Gains.” In Proceedings of the 28th International
Workshop on Design, Optimization, Languages and Analytical Processing of Big Data
(DOLAP 2026). Tampere, Finland, 2026.
ieee: D. Böhm et al., “Selective Use of Yannakakis’ Algorithm for Consistent
Performance Gains,” 2026.
mla: Böhm, Daniela, et al. “Selective Use of Yannakakis’ Algorithm for Consistent
Performance Gains.” Proceedings of the 28th International Workshop on Design,
Optimization, Languages and Analytical Processing of Big Data (DOLAP 2026),
2026.
short: 'D. Böhm, G. Gottlob, M. Lanzinger, D.M. Longo, C. Okulmus, R. Pichler, A.
Selzer, in: Proceedings of the 28th International Workshop on Design, Optimization,
Languages and Analytical Processing of Big Data (DOLAP 2026), Tampere, Finland,
2026.'
date_created: 2026-03-27T15:20:54Z
date_updated: 2026-03-27T15:22:01Z
department:
- _id: '888'
keyword:
- Join Queries
- Acyclic Queries
- Query Processing
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://ceur-ws.org/Vol-4186/paper2.pdf
oa: '1'
place: Tampere, Finland
publication: Proceedings of the 28th International Workshop on Design, Optimization,
Languages and Analytical Processing of Big Data (DOLAP 2026)
status: public
title: Selective Use of Yannakakis’ Algorithm for Consistent Performance Gains
type: conference
user_id: '114410'
year: '2026'
...
---
_id: '59840'
abstract:
- lang: eng
text: "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.\r\n"
author:
- first_name: Shqiponja
full_name: Ahmetaj, Shqiponja
last_name: Ahmetaj
- first_name: Iovka
full_name: Boneva, Iovka
last_name: Boneva
- first_name: Jan
full_name: Hidders, Jan
last_name: Hidders
- first_name: Katja
full_name: Hose, Katja
last_name: Hose
- first_name: Maxime
full_name: Jakubowski, Maxime
last_name: Jakubowski
- first_name: Jose Emilio
full_name: Labra Gayo, Jose Emilio
last_name: Labra Gayo
- first_name: Wim
full_name: Martens, Wim
last_name: Martens
- first_name: Fabio
full_name: Mogavero, Fabio
last_name: Mogavero
- first_name: Filip
full_name: Murlak, Filip
last_name: Murlak
- first_name: Cem
full_name: Okulmus, Cem
id: '114410'
last_name: Okulmus
orcid: 0000-0002-7742-0439
- first_name: Axel
full_name: Polleres, Axel
last_name: Polleres
- first_name: Ognjen
full_name: Savković, Ognjen
last_name: Savković
- first_name: Mantas
full_name: Šimkus, Mantas
last_name: Šimkus
- first_name: Dominik
full_name: Tomaszuk, Dominik
last_name: Tomaszuk
citation:
ama: 'Ahmetaj S, Boneva I, Hidders J, et al. Common Foundations for SHACL, ShEx,
and PG-Schema. In: Proceedings of the ACM on Web Conference 2025. ACM;
2025:8-12. doi:10.1145/3696410.3714694'
apa: Ahmetaj, S., Boneva, I., Hidders, J., Hose, K., Jakubowski, M., Labra Gayo,
J. E., Martens, W., Mogavero, F., Murlak, F., Okulmus, C., Polleres, A., Savković,
O., Šimkus, M., & Tomaszuk, D. (2025). Common Foundations for SHACL, ShEx,
and PG-Schema. Proceedings of the ACM on Web Conference 2025, 8–12. https://doi.org/10.1145/3696410.3714694
bibtex: '@inproceedings{Ahmetaj_Boneva_Hidders_Hose_Jakubowski_Labra Gayo_Martens_Mogavero_Murlak_Okulmus_et
al._2025, title={Common Foundations for SHACL, ShEx, and PG-Schema}, DOI={10.1145/3696410.3714694},
booktitle={Proceedings of the ACM on Web Conference 2025}, publisher={ACM}, 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 et al.}, year={2025}, pages={8–12} }'
chicago: Ahmetaj, Shqiponja, Iovka Boneva, Jan Hidders, Katja Hose, Maxime Jakubowski,
Jose Emilio Labra Gayo, Wim Martens, et al. “Common Foundations for SHACL, ShEx,
and PG-Schema.” In Proceedings of the ACM on Web Conference 2025, 8–12.
ACM, 2025. https://doi.org/10.1145/3696410.3714694.
ieee: 'S. Ahmetaj et al., “Common Foundations for SHACL, ShEx, and PG-Schema,”
in Proceedings of the ACM on Web Conference 2025, Sidney, Australia, 2025,
pp. 8–12, doi: 10.1145/3696410.3714694.'
mla: Ahmetaj, Shqiponja, et al. “Common Foundations for SHACL, ShEx, and PG-Schema.”
Proceedings of the ACM on Web Conference 2025, ACM, 2025, pp. 8–12, doi:10.1145/3696410.3714694.
short: 'S. Ahmetaj, I. Boneva, J. Hidders, K. Hose, M. Jakubowski, J.E. Labra Gayo,
W. Martens, F. Mogavero, F. Murlak, C. Okulmus, A. Polleres, O. Savković, M. Šimkus,
D. Tomaszuk, in: Proceedings of the ACM on Web Conference 2025, ACM, 2025, pp.
8–12.'
conference:
end_date: 2025-05-02
location: Sidney, Australia
name: 'ACM Web Conference 2025 '
start_date: 2025-04-28
date_created: 2025-05-07T11:46:03Z
date_updated: 2025-05-07T11:51:17Z
department:
- _id: '888'
doi: 10.1145/3696410.3714694
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2502.01295
oa: '1'
page: 8-12
publication: Proceedings of the ACM on Web Conference 2025
publication_status: published
publisher: ACM
status: public
title: Common Foundations for SHACL, ShEx, and PG-Schema
type: conference
user_id: '114410'
year: '2025'
...
---
_id: '63786'
author:
- first_name: Bianca
full_name: Löhnert, Bianca
last_name: Löhnert
- first_name: Nikolaus
full_name: Augsten, Nikolaus
last_name: Augsten
- first_name: Cem
full_name: Okulmus, Cem
id: '114410'
last_name: Okulmus
orcid: 0000-0002-7742-0439
- first_name: Magdalena
full_name: Ortiz, Magdalena
last_name: Ortiz
citation:
ama: 'Löhnert B, Augsten N, Okulmus C, Ortiz M. Query Rewriting for Nested Navigational
Queries over Property Graphs. In: Tendera L, Ibanez Garcia Y, Koopmann P, eds.
Proceedings of the 38th International Workshop on Description Logics (DL 2025),
Opole, Poland, September 3-6, 2025. Vol 4091. CEUR Workshop Proceedings. ;
2025.'
apa: Löhnert, B., Augsten, N., Okulmus, C., & Ortiz, M. (2025). Query Rewriting
for Nested Navigational Queries over Property Graphs. In L. Tendera, Y. Ibanez
Garcia, & P. Koopmann (Eds.), Proceedings of the 38th International Workshop
on Description Logics (DL 2025), Opole, Poland, September 3-6, 2025. (Vol.
4091).
bibtex: '@inproceedings{Löhnert_Augsten_Okulmus_Ortiz_2025, place={Opole, Poland},
series={CEUR Workshop Proceedings}, title={Query Rewriting for Nested Navigational
Queries over Property Graphs}, volume={4091}, booktitle={Proceedings of the 38th
International Workshop on Description Logics (DL 2025), Opole, Poland, September
3-6, 2025.}, author={Löhnert, Bianca and Augsten, Nikolaus and Okulmus, Cem and
Ortiz, Magdalena}, editor={Tendera, Lidia and Ibanez Garcia, Yazmin and Koopmann,
Patrick}, year={2025}, collection={CEUR Workshop Proceedings} }'
chicago: Löhnert, Bianca, Nikolaus Augsten, Cem Okulmus, and Magdalena Ortiz. “Query
Rewriting for Nested Navigational Queries over Property Graphs.” In Proceedings
of the 38th International Workshop on Description Logics (DL 2025), Opole, Poland,
September 3-6, 2025., edited by Lidia Tendera, Yazmin Ibanez Garcia, and Patrick
Koopmann, Vol. 4091. CEUR Workshop Proceedings. Opole, Poland, 2025.
ieee: B. Löhnert, N. Augsten, C. Okulmus, and M. Ortiz, “Query Rewriting for Nested
Navigational Queries over Property Graphs,” in Proceedings of the 38th International
Workshop on Description Logics (DL 2025), Opole, Poland, September 3-6, 2025.,
2025, vol. 4091.
mla: Löhnert, Bianca, et al. “Query Rewriting for Nested Navigational Queries over
Property Graphs.” Proceedings of the 38th International Workshop on Description
Logics (DL 2025), Opole, Poland, September 3-6, 2025., edited by Lidia Tendera
et al., vol. 4091, 2025.
short: 'B. Löhnert, N. Augsten, C. Okulmus, M. Ortiz, in: L. Tendera, Y. Ibanez
Garcia, P. Koopmann (Eds.), Proceedings of the 38th International Workshop on
Description Logics (DL 2025), Opole, Poland, September 3-6, 2025., Opole, Poland,
2025.'
date_created: 2026-01-28T10:37:05Z
date_updated: 2026-01-28T10:38:17Z
department:
- _id: '888'
editor:
- first_name: Lidia
full_name: Tendera, Lidia
last_name: Tendera
- first_name: Yazmin
full_name: Ibanez Garcia, Yazmin
last_name: Ibanez Garcia
- first_name: Patrick
full_name: Koopmann, Patrick
last_name: Koopmann
intvolume: ' 4091'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://ceur-ws.org/Vol-4091/paper40.pdf
oa: '1'
place: Opole, Poland
publication: Proceedings of the 38th International Workshop on Description Logics
(DL 2025), Opole, Poland, September 3-6, 2025.
publication_status: published
series_title: CEUR Workshop Proceedings
status: public
title: Query Rewriting for Nested Navigational Queries over Property Graphs
type: conference
user_id: '114410'
volume: 4091
year: '2025'
...
---
_id: '60496'
abstract:
- lang: eng
text: 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:
- first_name: Matthias
full_name: Lanzinger, Matthias
last_name: Lanzinger
- first_name: Cem
full_name: Okulmus, Cem
id: '114410'
last_name: Okulmus
orcid: 0000-0002-7742-0439
- first_name: Reinhard
full_name: Pichler, Reinhard
last_name: Pichler
- first_name: Alexander
full_name: Selzer, Alexander
last_name: Selzer
- first_name: Georg
full_name: Gottlob, Georg
last_name: Gottlob
citation:
ama: Lanzinger M, Okulmus C, Pichler R, Selzer A, Gottlob G. Soft and Constrained
Hypertree Width. Proceedings of the ACM on Management of Data. 2025;3(2):1-25.
doi:10.1145/3725251
apa: Lanzinger, M., Okulmus, C., Pichler, R., Selzer, A., & Gottlob, G. (2025).
Soft and Constrained Hypertree Width. Proceedings of the ACM on Management
of Data, 3(2), 1–25. https://doi.org/10.1145/3725251
bibtex: '@article{Lanzinger_Okulmus_Pichler_Selzer_Gottlob_2025, title={Soft and
Constrained Hypertree Width}, volume={3}, DOI={10.1145/3725251},
number={2}, journal={Proceedings of the ACM on Management of Data}, publisher={Association
for Computing Machinery (ACM)}, author={Lanzinger, Matthias and Okulmus, Cem and
Pichler, Reinhard and Selzer, Alexander and Gottlob, Georg}, year={2025}, pages={1–25}
}'
chicago: 'Lanzinger, Matthias, Cem Okulmus, Reinhard Pichler, Alexander Selzer,
and Georg Gottlob. “Soft and Constrained Hypertree Width.” Proceedings of the
ACM on Management of Data 3, no. 2 (2025): 1–25. https://doi.org/10.1145/3725251.'
ieee: 'M. Lanzinger, C. Okulmus, R. Pichler, A. Selzer, and G. Gottlob, “Soft and
Constrained Hypertree Width,” Proceedings of the ACM on Management of Data,
vol. 3, no. 2, pp. 1–25, 2025, doi: 10.1145/3725251.'
mla: Lanzinger, Matthias, et al. “Soft and Constrained Hypertree Width.” Proceedings
of the ACM on Management of Data, vol. 3, no. 2, Association for Computing
Machinery (ACM), 2025, pp. 1–25, doi:10.1145/3725251.
short: M. Lanzinger, C. Okulmus, R. Pichler, A. Selzer, G. Gottlob, Proceedings
of the ACM on Management of Data 3 (2025) 1–25.
conference:
end_date: 2025-06-27
location: Berlin
name: 44th ACM Symposium on Principles of Database Systems (PODS) 2025
start_date: 2025-06-22
date_created: 2025-07-02T11:41:00Z
date_updated: 2025-07-02T11:45:18Z
department:
- _id: '888'
doi: 10.1145/3725251
intvolume: ' 3'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2412.11669
oa: '1'
page: 1-25
publication: Proceedings of the ACM on Management of Data
publication_identifier:
issn:
- 2836-6573
publication_status: published
publisher: Association for Computing Machinery (ACM)
status: public
title: Soft and Constrained Hypertree Width
type: journal_article
user_id: '114410'
volume: 3
year: '2025'
...
---
_id: '60497'
abstract:
- lang: eng
text: 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:
- first_name: Bianca
full_name: Löhnert, Bianca
last_name: Löhnert
- first_name: Nikolaus
full_name: Augsten, Nikolaus
last_name: Augsten
- first_name: Cem
full_name: Okulmus, Cem
id: '114410'
last_name: Okulmus
orcid: 0000-0002-7742-0439
- first_name: Magdalena
full_name: Ortiz, Magdalena
last_name: Ortiz
citation:
ama: 'Löhnert B, Augsten N, Okulmus C, Ortiz M. Towards Practicable Algorithms for Rewriting
Graph Queries Beyond DL-Lite. In: The Semantic Web - 22nd European Semantic
Web Conference, {ESWC} 2025, Portoroz, Slovenia, June 1-5, 2025, Proceedings,
Part {I}. Vol 15718. Lecture Notes in Computer Science. Springer Nature Switzerland;
2025:342--361. doi:10.1007/978-3-031-94575-5_19'
apa: Löhnert, B., Augsten, N., Okulmus, C., & Ortiz, M. (2025). Towards Practicable
Algorithms for Rewriting Graph Queries Beyond DL-Lite. The Semantic Web - 22nd
European Semantic Web Conference, {ESWC} 2025, Portoroz, Slovenia, June 1-5, 2025,
Proceedings, Part {I}, 15718, 342--361. https://doi.org/10.1007/978-3-031-94575-5_19
bibtex: '@inproceedings{Löhnert_Augsten_Okulmus_Ortiz_2025, series={Lecture Notes
in Computer Science}, title={Towards Practicable Algorithms for Rewriting Graph
Queries Beyond DL-Lite}, volume={15718}, DOI={10.1007/978-3-031-94575-5_19},
booktitle={The Semantic Web - 22nd European Semantic Web Conference, {ESWC} 2025,
Portoroz, Slovenia, June 1-5, 2025, Proceedings, Part {I}}, publisher={Springer
Nature Switzerland}, author={Löhnert, Bianca and Augsten, Nikolaus and Okulmus,
Cem and Ortiz, Magdalena}, year={2025}, pages={342--361}, collection={Lecture
Notes in Computer Science} }'
chicago: Löhnert, Bianca, Nikolaus Augsten, Cem Okulmus, and Magdalena Ortiz. “Towards
Practicable Algorithms for Rewriting Graph Queries Beyond DL-Lite.” In The
Semantic Web - 22nd European Semantic Web Conference, {ESWC} 2025, Portoroz, Slovenia,
June 1-5, 2025, Proceedings, Part {I}, 15718:342--361. Lecture Notes in Computer
Science. Springer Nature Switzerland, 2025. https://doi.org/10.1007/978-3-031-94575-5_19.
ieee: 'B. Löhnert, N. Augsten, C. Okulmus, and M. Ortiz, “Towards Practicable Algorithms
for Rewriting Graph Queries Beyond DL-Lite,” in The Semantic Web - 22nd European
Semantic Web Conference, {ESWC} 2025, Portoroz, Slovenia, June 1-5, 2025, Proceedings,
Part {I}, Portorož, Slovenia, 2025, vol. 15718, pp. 342--361, doi: 10.1007/978-3-031-94575-5_19.'
mla: Löhnert, Bianca, et al. “Towards Practicable Algorithms for Rewriting Graph
Queries Beyond DL-Lite.” The Semantic Web - 22nd European Semantic Web Conference,
{ESWC} 2025, Portoroz, Slovenia, June 1-5, 2025, Proceedings, Part {I}, vol.
15718, Springer Nature Switzerland, 2025, pp. 342--361, doi:10.1007/978-3-031-94575-5_19.
short: 'B. Löhnert, N. Augsten, C. Okulmus, M. Ortiz, in: The Semantic Web - 22nd
European Semantic Web Conference, {ESWC} 2025, Portoroz, Slovenia, June 1-5, 2025,
Proceedings, Part {I}, Springer Nature Switzerland, 2025, pp. 342--361.'
conference:
end_date: 2025-06-05
location: Portorož, Slovenia
name: 22th European Semantic Web Conference (ESWC 2025)
start_date: 2025-06-01
date_created: 2025-07-02T11:46:06Z
date_updated: 2025-07-02T11:55:19Z
department:
- _id: '888'
doi: 10.1007/978-3-031-94575-5_19
intvolume: ' 15718'
keyword:
- Ontology-based Data Access
- Property Graphs
- Navigational Queries
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2405.18181
oa: '1'
page: 342--361
publication: The Semantic Web - 22nd European Semantic Web Conference, {ESWC} 2025,
Portoroz, Slovenia, June 1-5, 2025, Proceedings, Part {I}
publication_identifier:
isbn:
- '9783031945748'
- '9783031945755'
issn:
- 0302-9743
- 1611-3349
publication_status: published
publisher: Springer Nature Switzerland
quality_controlled: '1'
series_title: Lecture Notes in Computer Science
status: public
title: Towards Practicable Algorithms for Rewriting Graph Queries Beyond DL-Lite
type: conference
user_id: '114410'
volume: 15718
year: '2025'
...