AofA2022 – Keynote Lecture: Achieving Worst-Case-Optimal Multijoins on Databases through Geometric Data Structures

Abstract.

“El estado del arte en el procesamiento de consultas en bases de datos se ha visto recientemente sacudido por una nueva generación de algoritmos de procesamiento de multi-joins con fuertes garantías de optimalidad basadas en la cota AGM de las consultas: el tamaño máximo de la salida de la consulta sobre todas las relaciones posibles con las mismas cardinalidades. Con los años, se ha demostrado que esto se traduce en mejoras prácticas considerables por sobre las técnicas clásicas de join binario en uso desde los años sesenta. En esta charla presentaré primero la cota AGM, que resulta bastante interesante desde una perspectiva de análisis de algoritmos (aunque sea en el peor caso). Luego mostraré cómo se ha logrado típicamente siguiendo su fórmula, lo que ha dado lugar al conocido algoritmo Leapfrog TrieJoin. Finalmente, presentaré una nueva estructura de datos que considera las tablas de d columnas como puntos en un espacio d-dimensional y representa esas grillas usando, esencialmente, versiones d-dimensionales de quadtrees. El algoritmo de join se implementa entonces elevando (virtualmente) su dimensión para incluir los atributos faltantes del join, y luego recorriendo (virtualmente) su intersección, o equivalentemente el espacio de salida. Mostraré entonces cómo este enfoque geométrico extremadamente simple logra la optimalidad en el peor caso de una manera completamente distinta. Esta charla se basa en nuestro trabajo “Optimal Joins using Compressed Quadtrees”, que será publicado en ACM Transactions on Database Systems.”

Presenter

Gonzalo Navarro, DCC Universidad de Chile

When and where

23 de junio, 17:30–18:30 (UTC) / 13:30–14:30 en America/Santiago