Skip to content

Functional Aggregate Query (FAQ): Questions Asked Frequently

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 (opens in a new tab)

Get Started!

Start your journey with RelationalAI today! Sign up to receive our newsletter, invitations to exclusive events, and customer case studies.

The information you provide will be used in accordance with the terms of our Privacy Policy. By submitting this form, you consent to allow RelationalAI to store and process the personal information submitted above to provide you the content requested.