Soft and Constrained Hypertree Width
M. Lanzinger, C. Okulmus, R. Pichler, A. Selzer, G. Gottlob, Proceedings of the ACM on Management of Data 3 (2025) 1–25.
Download (ext.)
DOI
Journal Article
| Published
| English
Author
Lanzinger, Matthias;
Okulmus, CemLibreCat
;
Pichler, Reinhard;
Selzer, Alexander;
Gottlob, Georg

Department
Abstract
<jats:p>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.</jats:p>
Publishing Year
Journal Title
Proceedings of the ACM on Management of Data
Volume
3
Issue
2
Page
1-25
Conference
44th ACM Symposium on Principles of Database Systems (PODS) 2025
Conference Location
Berlin
Conference Date
2025-06-22 – 2025-06-27
ISSN
LibreCat-ID
Cite this
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
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
@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} }
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.
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.
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.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
