2026-09-26T15:50:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25615 2026-09-23T23:44:56Z ddc:004 open_access

Query Decompositions and All That (Invited Talk) Deeds, Kyle Merkl, Timo Camillo Pichler, Reinhard Suciu, Dan Query evaluation Query decompositions Complexity The close relationship between Conjunctive Queries (CQs) and Constraint Satisfaction Problems (CSPs) has long been known. Nevertheless, apart from decomposition methods, research on efficient query evaluation or constraint solving algorithms has developed rather independently. In this article, we illustrate how search algorithms originating from the CSP community can be fruitfully applied to query evaluation - either by further developing the original search algorithms or by combining them with query decomposition methods. It turns out that the resulting approaches may indeed lead to lower time and/or space complexity than previous query evaluation methods. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kyle Deeds and Timo Camillo Merkl and Reinhard Pichler and Dan Suciu 2026 Is Part Of LIPIcs, Volume 365, 29th International Conference on Database Theory (ICDT 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2026.1 urn:nbn:de:0030-drops-256158 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2026.1 eng https://creativecommons.org/licenses/by/4.0/legalcode