We define and study the Functional Aggregate Query (FAQ) problem, which
encompasses many frequently asked questions in constraint satisfaction,
databases, matrix operations, probabilistic graphical models and logic. This is
our main conceptual contribution.
We then present a simple algorithm called "InsideOut" to solve this general
problem. InsideOut is a variation of the traditional dynamic programming
approach for constraint programming based on variable elimination. Our
variation adds a couple of simple twists to basic variable elimination in order
to deal with the generality of FAQ, to take full advantage of Grohe and Marx's
fractional edge cover framework, and of the analysis of recent worst-case
optimal relational join algorithms.
As is the case with constraint programming and graphical model inference, to
make InsideOut run efficiently we need to solve an optimization problem to
compute an appropriate 'variable ordering'. The main technical contribution of
this work is a precise characterization of when a variable ordering is
'semantically equivalent' to the variable ordering given by the input FAQ
expression. Then, we design an approximation algorithm to find an equivalent
variable ordering that has the best 'fractional FAQ-width'. Our results imply a
host of known and a few new results in graphical model inference, matrix
operations, relational joins, and logic.
We also briefly explain how recent algorithms on beyond worst-case analysis
for joins and those for solving SAT and #SAT can be viewed as variable
elimination to solve FAQ over compactly represented input functions.

研究和定义了 Functional Aggregate Query 问题，并提出了 InsideOut 算法解决该问题。算法使用了变量消除和 Grohe 和 Marx 的分数边缘覆盖框架，以及最近的最优关系连接算法的分析。精确描述了何时变量排序与输入 FAQ 表达式中的变量排序是 “语义等效的”，并设计了一种近似算法来找到具有最佳 “分数 FAQ 宽度” 的等效变量排序。结果涵盖了图形模型推断、矩阵运算、关系连接和逻辑等多个领域。