@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{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}}, } @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}}, }