庞悦关于利用物化视图以加速图上正则路径查询的论文被SIGMOD 2024录用。

给定一张数据图，正则路径查询（Regular path query, RPQ）返回以具有满足给定正则表达式的边标签序列的路径所连接的节点对。如果给定若干RPQ构成的集合作为查询负载，那么选择这些RPQ共有的子查询作为离线预计算的物化视图可以加速在线查询。由于可用内存有限，论文将RPQ的物化视图选择（Materialized view selection, MVS）问题定义为如下的优化问题：在给定的内存预算下，最小化RPQ负载的总查询时间。论文证明此问题是NP难的，并给出了一种高效的启发式MVS算法。为避免选择冗余的物化视图，论文创新性地提出了一种多RPQ的查询计划表示以编码子查询间的关系，称为AND-OR DAG with Closure（AODC）。除了检测冗余视图外，AODC还会随着视图选择过程增量化更新自身，使得视图选择完成后同时也得到了基于视图优化的查询计划。为支持查询计划选择，论文针对RPQ给出了一个具有良好可扩展性的查询代价与基数估计模型，这是首个能够支持包括Kleene闭包在内的任意RPQ的查询代价与基数估计模型。本方法在应用于Wikidata查询日志时，相较于不使用物化视图的方法，能够取得高达9.73倍的总查询时间加速比。