2026-08-17T20:51:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13722 2024-03-06T10:52:31Z ddc:004 open_access

Enumeration Algorithms for Conjunctive Queries with Projection Deep, Shaleen Hu, Xiao Koutris, Paraschos Query result enumeration joins ranking We investigate the enumeration of query results for an important subset of CQs with projections, namely star and path queries. The task is to design data structures and algorithms that allow for efficient enumeration with delay guarantees after a preprocessing phase. Our main contribution is a series of results based on the idea of interleaving precomputed output with further join processing to maintain delay guarantees, which maybe of independent interest. In particular, we design combinatorial algorithms that provide instance-specific delay guarantees in linear preprocessing time. These algorithms improve upon the currently best known results. Further, we show how existing results can be improved upon by using fast matrix multiplication. We also present {new} results involving tradeoff between preprocessing time and delay guarantees for enumeration of path queries that contain projections. CQs with projection where the join attribute is projected away is equivalent to boolean matrix multiplication. Our results can therefore be also interpreted as sparse, output-sensitive matrix multiplication with delay guarantees. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shaleen Deep and Xiao Hu and Paraschos Koutris 2021 Is Part Of LIPIcs, Volume 186, 24th International Conference on Database Theory (ICDT 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2021.14 urn:nbn:de:0030-drops-137229 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2021.14 eng https://creativecommons.org/licenses/by/4.0/legalcode