---
_id: '60496'
abstract:
- lang: eng
  text: <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>
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. <i>Proceedings of the ACM on Management of Data</i>. 2025;3(2):1-25.
    doi:<a href="https://doi.org/10.1145/3725251">10.1145/3725251</a>
  apa: Lanzinger, M., Okulmus, C., Pichler, R., Selzer, A., &#38; Gottlob, G. (2025).
    Soft and Constrained Hypertree Width. <i>Proceedings of the ACM on Management
    of Data</i>, <i>3</i>(2), 1–25. <a href="https://doi.org/10.1145/3725251">https://doi.org/10.1145/3725251</a>
  bibtex: '@article{Lanzinger_Okulmus_Pichler_Selzer_Gottlob_2025, title={Soft and
    Constrained Hypertree Width}, volume={3}, DOI={<a href="https://doi.org/10.1145/3725251">10.1145/3725251</a>},
    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.” <i>Proceedings of the
    ACM on Management of Data</i> 3, no. 2 (2025): 1–25. <a href="https://doi.org/10.1145/3725251">https://doi.org/10.1145/3725251</a>.'
  ieee: 'M. Lanzinger, C. Okulmus, R. Pichler, A. Selzer, and G. Gottlob, “Soft and
    Constrained Hypertree Width,” <i>Proceedings of the ACM on Management of Data</i>,
    vol. 3, no. 2, pp. 1–25, 2025, doi: <a href="https://doi.org/10.1145/3725251">10.1145/3725251</a>.'
  mla: Lanzinger, Matthias, et al. “Soft and Constrained Hypertree Width.” <i>Proceedings
    of the ACM on Management of Data</i>, vol. 3, no. 2, Association for Computing
    Machinery (ACM), 2025, pp. 1–25, doi:<a href="https://doi.org/10.1145/3725251">10.1145/3725251</a>.
  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'
...