# FAQ: Questions Asked Frequently

arXiv: https://arxiv.org/abs/1504.04044 · HTML: https://mlsanity.com/paper/1504.04044/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Apr 2015.

## Built on by (most cited first, 14 of 14)

- [Expressiveness and Approximation Properties of Graph Neural Networks](https://mlsanity.com/paper/2204.04661/) (2022)
- [A Compositional Atlas for Algebraic Circuits](https://mlsanity.com/paper/2412.05481/) (2024)
- [Functional Collection Programming with Semi-Ring Dictionaries](https://mlsanity.com/paper/2103.06376/) (2021)
- [JoinBoost: Grow Trees Over Normalized Data Using Only SQL](https://mlsanity.com/paper/2307.00422/) (2023)
- [DPMS: An ADD-Based Symbolic Approach for Generalized MaxSAT Solving](https://mlsanity.com/paper/2205.03747/) (2022)
- [DPO: Dynamic-Programming Optimization on Hybrid Constraints](https://mlsanity.com/paper/2205.08632/) (2022)
- [Coresets for Relational Data and The Applications](https://mlsanity.com/paper/2210.04249/) (2022)
- [Tractable Responsibility Measures for Ontology-Mediated Query Answering](https://mlsanity.com/paper/2507.23191/) (2025)
- [Relational Boosted Regression Trees](https://mlsanity.com/paper/2107.12373/) (2021)
- [Fine-Tuning Data Structures for Analytical Query Processing](https://mlsanity.com/paper/2112.13099/) (2021)
- [DPER: Dynamic Programming for Exist-Random Stochastic SAT](https://mlsanity.com/paper/2205.09826/) (2022)
- [Graphical Join: A New Physical Join Algorithm for RDBMSs](https://mlsanity.com/paper/2206.10435/) (2022)
- [Incremental Updates of Generalized Hypertree Decompositions](https://mlsanity.com/paper/2209.10375/) (2022)
- [Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability](https://mlsanity.com/paper/2311.14579/) (2023)

## Abstract (arXiv)

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.