Shaleen Deep ; Xiao Hu ; Paraschos Koutris - Enumeration Algorithms for Conjunctive Queries with Projection

lmcs:8639 - Logical Methods in Computer Science, September 12, 2025, Volume 21, Issue 3 - https://doi.org/10.46298/lmcs-21(3:27)2025
Enumeration Algorithms for Conjunctive Queries with ProjectionArticle

Authors: Shaleen Deep ; Xiao Hu ; Paraschos Koutris

    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, for star queries, 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. Boolean matrix multiplication is an important query that can be expressed as a CQ with projection where the join attribute is projected away. Our results can therefore also be interpreted as sparse, output-sensitive matrix multiplication with delay guarantees.


    Volume: Volume 21, Issue 3
    Published on: September 12, 2025
    Accepted on: May 9, 2025
    Submitted on: November 2, 2021
    Keywords: Databases, Data Structures and Algorithms

    Consultation statistics

    This page has been seen 700 times.
    This article's PDF has been downloaded 137 times.