{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T23:40:08Z","timestamp":1755906008647,"version":"3.44.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"DOI":"10.13039\/501100006374","name":"Vienna Science and Technology Fund","doi-asserted-by":"publisher","award":["10.47379\/ICT2201,10.47379\/VRG18013"],"award-info":[{"award-number":["10.47379\/ICT2201,10.47379\/VRG18013"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006374","name":"Knut och Alice Wallenbergs Stiftelse","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006374","name":"Ministero dell'Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["PE00000013"],"award-info":[{"award-number":["PE00000013"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,9]]},"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>","DOI":"10.1145\/3725251","type":"journal-article","created":{"date-parts":[[2025,6,9]],"date-time":"2025-06-09T15:20:31Z","timestamp":1749482431000},"page":"1-25","source":"Crossref","is-referenced-by-count":0,"title":["Soft and Constrained Hypertree Width"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7601-3727","authenticated-orcid":false,"given":"Matthias","family":"Lanzinger","sequence":"first","affiliation":[{"name":"Institute of Logic and Computation, TU Wien, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7742-0439","authenticated-orcid":false,"given":"Cem","family":"Okulmus","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, Paderborn University, Paderborn, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1760-122X","authenticated-orcid":false,"given":"Reinhard","family":"Pichler","sequence":"additional","affiliation":[{"name":"Institute of Logic and Computation, TU Wien, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6867-5448","authenticated-orcid":false,"given":"Alexander","family":"Selzer","sequence":"additional","affiliation":[{"name":"Institute of Logic and Computation, TU Wien, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2353-5230","authenticated-orcid":false,"given":"Georg","family":"Gottlob","sequence":"additional","affiliation":[{"name":"Dipartimento di Matematica e Informatica, University of Calabria, Calabria, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20025"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2007.04.013"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/0608024"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/3681954.3681995"},{"key":"e_1_2_1_5_1","volume-title":"Technische Universit\u00e4t Wien","author":"B\u00f6hm D.","year":"2024","unstructured":"B\u00f6hm, D. To rewrite or not to rewrite: Decision making in query optimization of sql queries. Master's thesis, Technische Universit\u00e4t Wien, 2024."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-68530-8_29"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-49116-3_18"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46541-3_42"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799359683"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00007-X"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3604437.3604458"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3440015"},{"key":"e_1_2_1_13_1","volume-title":"Structure-guided query evaluation: Towards bridging the gap from theory to practice. CoRR abs\/2303.02723","author":"Gottlob G.","year":"2023","unstructured":"Gottlob, G., Lanzinger, M., Longo, D. M., Okulmus, C., Pichler, R., and Selzer, A. Structure-guided query evaluation: Towards bridging the gap from theory to practice. CoRR abs\/2303.02723 (2023)."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3638758"},{"key":"e_1_2_1_15_1","series-title":"LIPIcs","first-page":"1","volume-title":"Proc. MFCS","author":"Gottlob G.","year":"2020","unstructured":"Gottlob, G., Lanzinger, M., Pichler, R., and Razgon, I. Fractional covers of hypergraphs with bounded multi-intersection. In Proc. MFCS (2020), vol. 170 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, pp. 41:1--41:14."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3457374"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1809"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1568318.1568320"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10601-022-09332-1"},{"key":"e_1_2_1_20_1","first-page":"13","article-title":"A backtracking-based algorithm for hypertree decomposition","author":"Gottlob G.","year":"2008","unstructured":"Gottlob, G., and Samer, M. A backtracking-based algorithm for hypertree decomposition. ACM J. Exp. Algorithmics 13 (2008).","journal-title":"ACM J. Exp. Algorithmics"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(02)00182-0"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2636918"},{"key":"e_1_2_1_23_1","volume-title":"Systematic integration of biomedical knowledge prioritizes drugs for repurposing. eLife 6 (sep","author":"Himmelstein D. S.","year":"2017","unstructured":"Himmelstein, D. S., Lizee, A., Hessler, C., Brueggeman, L., Chen, S. L., Hadley, D., Green, A., Khankhanian, P., and Baranzini, S. E. Systematic integration of biomedical knowledge prioritizes drugs for repurposing. eLife 6 (sep 2017), e26726."},{"key":"e_1_2_1_24_1","volume-title":"Soft and constrained hypertree width. CoRR abs\/2412.11669","author":"Lanzinger M.","year":"2024","unstructured":"Lanzinger, M., Okulmus, C., Pichler, R., Selzer, A., and Gottlob, G. Soft and constrained hypertree width. CoRR abs\/2412.11669 (2024)."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3461837.3464516"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564759"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319678"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.10.010"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976007.1"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2023.104015"},{"key":"e_1_2_1_31_1","first-page":"82","volume-title":"Proc. VLDB","author":"Yannakakis M.","year":"1981","unstructured":"Yannakakis, M. Algorithms for acyclic database schemes. In Proc. VLDB (1981), IEEE Computer Society, pp. 82--94. graphy"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725251","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T23:18:51Z","timestamp":1755904731000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725251"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,9]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,9]]}},"alternative-id":["10.1145\/3725251"],"URL":"https:\/\/doi.org\/10.1145\/3725251","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2025,6,9]]}}}