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 nearly 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.
翻译:我们调查大量有预测的CQ的查询结果,即恒星和路径查询。任务是设计数据结构和算法,以便在预处理阶段后以延迟保证有效查点,我们的主要贡献是一系列基于以下想法的结果:将预考产出与进一步合并处理相结合,以保持延迟保证,这可能具有独立的兴趣。特别是,我们设计组合算法,在近线性预处理时间里提供具体实例的延迟保证。这些算法改进了目前已知的最佳结果。此外,我们展示了如何通过快速矩阵乘法改进现有结果。我们还介绍了预处理时间之间的交换结果,以及含有预测的路径查询的拖延保证。预测连接属性的预测值相当于布林矩阵乘法。因此,我们的结果也可以被解释为稀少的、对产出敏感的矩阵乘以延迟保证。