  We define and study the Functional Aggregate Query (FAQ) problem, which
captures common computational tasks across a very wide range of domains
including relational databases, logic, matrix and tensor computation,
probabilistic graphical models, constraint satisfaction, and signal processing.
Simply put, an FAQ is a declarative way of defining a new function from a
database of input functions.
  We present "InsideOut", a dynamic programming algorithm, to evaluate an FAQ.
The algorithm rewrites the input query into a set of easier-to-compute FAQ
sub-queries. Each sub-query is then evaluated using a worst-case optimal
relational join algorithm. The topic of designing algorithms to optimally
evaluate the classic multiway join problem has seen exciting developments in
the past few years. Our framework tightly connects these new ideas in database
theory with a vast number of application areas in a coherent manner, showing
potentially that a good database engine can be a general-purpose constraint
solver, relational data store, graphical model inference engine, and
matrix/tensor computation processor all at once.
  The InsideOut algorithm is very simple, as shall be described in this paper.
Yet, in spite of solving an extremely general problem, its runtime either is as
good as or improves upon the best known algorithm for the applications that FAQ
specializes to. These corollaries include computational tasks in graphical
model inference, matrix/tensor operations, relational joins, and logic. Better
yet, InsideOut can be used within any database engine, because it is basically
a principled way of rewriting queries. Indeed, it is already part of the
LogicBlox database engine, helping efficiently answer traditional database
queries, graphical model inference queries, and train a large class of machine
learning models inside the database itself.
