PANDAExpress: A Simpler and Faster PANDA Algorithm

doi:10.1145/3801910

PANDAExpress: A Simpler and Faster PANDA Algorithm

2026-05-01

0

PRE

AI

K

Khamis, Mahmoud Abo *

DOI：10.1145/3801910

原文求助

摘要

En 中文

PANDA是一种强大的通用算法，用于在给定输入度约束的情况下回答合取查询和析取Datalog规则。在仅含基数约束的布尔查询这一特殊情况下，PANDA的运行时间为O(N_w)，其中N是输入规模，w是查询的亚模宽度，这一概念由Daniel Marx（JACM 2013）在约束满足问题的背景下引入。当专门应用于某些子图模式查找问题时，O(N_w)的运行时间与可能的最佳运行时间相匹配，条件是满足一些精细复杂度中的猜想（Bringmann和Gorbachev（STOC 25））。PANDA框架更为通用，因为它处理任意的输入度约束，这些约束捕获了关系数据库管理系统中的常见统计和完整性约束，适用于带自由变量的查询，以及合取查询和析取Datalog规则。PANDA的主要缺点是O(·)符号中隐藏的大polylog(N)因子，使其完全不实用，并且不及专用算法所能达到的效果。本文通过两个新思想解决了这一缺点。首先，我们证明了一个新的概率不等式，该不等式在任意度约束下对析取Datalog规则的输出规模进行了上界估计。其次，该不等式的证明直接导致了一种新算法PANDAExpress的出现，该算法比PANDA更简单且更快。PANDAExpress的一个新颖特性是采用了使用任意超平面切割的新分区方案，而非PANDA中使用的轴平行超平面。这些超平面根据算法执行过程中仔细跟踪的数据偏斜统计量动态构建。结果，PANDAExpress从PANDA的运行时间中消除了polylog(N)因子，匹配了复杂专用算法的运行时间，同时保留了其所有通用性和强大功能。此外，我们还展示了PANDAExpress如何处理fp-范数约束，该约束是度约束的推广。

Keyword:

PANDA

conjunctive queries

disjunctive datalog rules

submodular width

proof sequences

Shannon inequalities

PANDAExpress: A Simpler and Faster PANDA Algorithm

摘要

期刊

机构

引用论文