  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.
