一句话：提出带投影合取查询的枚举算法，通过交错预计算与连接处理，为星形和路径查询提供延迟保证并改进已知结果。
论文研究带投影的合取查询（CQ）结果枚举，聚焦星形和路径查询。目标是在预处理阶段后以延迟保证高效枚举。核心思想是把预计算输出与后续连接处理交错，以维持延迟保证。对星形查询，给出线性预处理时间、实例相关的延迟保证的组合算法，优于已知最佳结果；并利用快速矩阵乘法改进已有结果；对含投影的路径查询给出预处理时间与延迟保证之间的权衡。布尔矩阵乘法可表示为投影连接属性被投影掉的 CQ，因此结果也可视为带延迟保证的稀疏、输出敏感矩阵乘法。
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.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{abs-2101-03712,
title = {Enumeration Algorithms for Conjunctive Queries with Projection},
author = {Shaleen Deep and Xiao Hu and Paraschos Koutris},
journal = {Logical Methods in Computer Science},
volume = {Volume 21, Issue 3},
year = {2025},
doi = {10.46298/lmcs-21(3:27)2025}
}