FAQ: Questions asked frequently
Abo Khamis, Mahmoud
MetadataShow full item record
We define and study the FAQ ( F unctional A ggregate Q uery) 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, as well as to take full advantage of the (relatively) recent fractional edge cover framework of Grohe and Marx, 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 ordering given by the input FAQ expression. Then, we design an approximation algorithm to find an equivalent ordering that has the best "fractional FAQ-width". Our results imply a host of known and a few new results in graphical model inference, relational joins, and logic. FAQ can be thought of as a declarative language over functions. We examine how the input and output function representations affect the tractability of the problem. We show that the dynamic programming approach is still powerful in some cases where the input functions are compactly represented; in particular, we briefly explain how recent algorithms on beyond worst-case analysis for joins and for solving SAT and #SAT can be viewed as variable elimination to solve FAQ over compactly represented input functions. While InsideOut relies on worst-case optimal relational join processing, those optimality guarantees break down in the presence of functional dependencies (FDs). Recently, Gottlob, Lee, Valiant, and Valiant (GLVV) introduced an information-theoretic bound for queries with FDs. We present the first algorithm that meets GLVV bound. We show that our algorithm, called CSMA, can also handle general degree bounds while maintaining the same information-theoretic guarantees as GLVV.