Functional Aggregate Query (FAQ): Questions Asked Frequently

This paper developed theory and algorithms for semantic query optimization for queries expressible in the "functional aggregate queries" format, which includes a vast number of query classes from database, constraint satisfaction, to machine learning and AI.

Authors: Mahmoud Abo Khamis, Hung Q. Ngo, Atri Rudra. 2016.

In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS ‘16). (Best Paper Award, Invited to the Journal of the ACM)

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.

Read the PDF: Functional Aggregate Query (FAQ): Questions Asked Frequently