LFCS Seminar: Tuesday, 28 March - Dan Suciu

 

Speaker:     Dan Suciu 

 

Title:             Optimizing Recursive Queries

 

Abstract:

Modern data analytics requires iteration, yet relational database

engines are mostly optimized for non-recursive queries. SQL supports

only a limited form of recursion. A better formalism for recursive

queries is datalog, which has some elegant properties (recursion

always terminates), and led to the development of two powerful

optimizations techniques: semi-naive evaluation, and magic set

rewriting. But standard datalog is restricted to monotone queries

over sets and does not support aggregates, which has limited its

adoption.

 

 

In this talk I will describe a new approach to recursive queries and

their optimization. First, we extend datalog to semirings, while

preserving some of the elegant properties of datalog, and also

supporting aggregates naturally. Then, I will describe a simple, yet

very powerful optimization rule, called the FGH rule, that rewrites a

recursive program into a different recursive program. The rule

captures many optimizations discussed in the literature, such as

magic set optimization, the PreM rule, and semi-naive evaluation, and

as well as new semantics optimizations. Our implementation of the FGH

rule is based on the egg term rewriting engine, and the Rosette program

synthesizer.

 

 

Joint work with: Yisu Remy Wang, Mahmoud Abo Khamis, Hung Q. Ngo,

Reinhard Pichler

 

 

Dan Suciu is a Microsoft Endowed Professor in the Paul G. Allen School of

Computer Science and Engineering at the University of Washington.

Suciu is conducting research in data management, on topics such as

query optimization, probabilistic data, data pricing, parallel data

processing, data security. He is a co-author of two books Data on the

Web: from Relations to Semistructured Data and XML, 1999, and

Probabilistic Databases, 2011. He received the ACM SIGMOD Codd

Innovation Award, received several best paper awards and test of time

awards, and is a Fellow of the ACM. Suciu is currently an associate

editor for the Journal of the ACM. Suciu's PhD students Gerome Miklau,

Christopher Re and Paris Koutris received the ACM SIGMOD Best

Dissertation Award in 2006, 2010, and 2016 respectively, and Nilesh

Dalvi was a runner up in 2008.