Functional Aggregate Queries Asked Frequently

Tuesday, May 3, 2016 - 4:00pm
CS 1257

Speaker Name: 

Hung Ngo

Speaker Institution: 





Description of the talk: We define and study the {\bf F}unctional {\bf A}ggregate {\bf Q}uery
(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.

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 {\em variable
ordering}. The main technical contribution of this work is a precise
characterization of when a variable ordering is `semantically
equivalent' to the variable ordering given by the input FAQ
expression. Then, we design an approximation algorithm to find an
equivalent variable ordering that has the best `fractional FAQ-width'.
Our results imply a host of known and a few new results in graphical
model inference, matrix operations, 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 also briefly explain how
recent algorithms on beyond worst-case analysis for joins and those
for solving SAT and #SAT can be viewed as variable elimination to
solve FAQ over compactly represented input functions.

This is joint work with Mahmoud Abo Khamis (LogicBlox) and Atri Rudra (SUNY Buffalo)

Brief Bio: Hung Ngo is currently a Computer Scientist at LogicBlox. From 2001 to 2016, he was a (assistant, associate, full) professor at SUNY Buffalo, department of Computer Science and Engineering. He works on the design and implementation of algorithms for the LogicBlox engine.