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)
Related Posts
Design and Implementation of the LogicBlox System
The LogicBlox system aims to reduce the complexity of software development for modern applications which enhance and automate decision-making and enable their users to evolve their capabilities via a “self-service” model.
Join Processing for Graph Patterns: An Old Dog with New Tricks
Join optimization has been dominated by Selinger-style, pairwise optimizers for decades. But, Selinger-style algorithms are asymptotically suboptimal for applications in graphic analytics. This suboptimality is one of the reasons that many have advocated supplementing relational engines with specialized graph processing engines.