Investigadores de la Universidad de Chile, la Pontificia Universidad Católica de Chile (PUC) y la Universidad Técnica Federico Santa María (UFTSM) obtuvieron el Best Paper Award en GRADES-NDA 2026, workshop satélite de SIGMOD/PODS, la conferencia de mayor relevancia internacional en el área de bases de datos. El reconocimiento fue otorgado al artículo "Boosting Graph Joins and Matrix Multiplications in Little Space", desarrollado por Gonzalo Navarro, académico del Departamento de Ciencias de la Computación (DCC) de la U. de Chile; Diego Arroyuelo, académico del DCC de la PUC; y José M. Cazorla, doctorando de la UTFSM. Los autores también integran el Instituto Milenio Fundamentos de los Datos (IMFD).

El artículo retoma los Qdags, un índice que los investigadores publicaron en 2020 caracterizado por poder resolver consultas en bases de datos de grafos usando muy poco espacio. “De hecho, comprimen los datos significativamente, y dentro de ese espacio pueden resolver las consultas en forma eficiente”, afirmó el profesor Navarro.

Explicó que los Qdags se enfocan en las consultas más importantes, en las que el usuario muestra un subgrafo donde los nodos pueden tener valores indefinidos, y resolverla significa encontrar todas las formas de darles valores a esos nodos de modo que el subgrafo aparezca en el grafo. “Por ejemplo, en un grafo de información sobre personas podríamos buscar personas x e y que estudiaron en la misma universidad y ahora una es jefa de la otra con un subgrafo como (x estudió-en z), (y estudió-en z), (x jefe-de y)”, complementó.

Los Qdags demostraron que era posible resolver estas consultas con garantías de optimalidad que antes sólo se habían logrado usando mucho más espacio –“¡al menos 100 veces más que los Qdags!”, enfatizó el académico del DCC. Además, su implementación demostró que eran prácticos, compitiendo en tiempo contra los sistemas establecidos. “Sin embargo -dijo- eso era así con consultas de pocas variables (hasta 3, como en el ejemplo). A partir de 4 variables, los tiempos explotaban y los Qdags se volvían muy poco competitivos”.

En este paper los investigadores diseñaron una estrategia que llamaron "pre-joining", en la cual preprocesaron la consulta eligiendo unas pocas variables relevantes y realizaron una primera subconsulta sólo con ellas. El resultado de esa subconsulta se agrega entonces a la consulta final, como un filtro más. 

“Mostramos que este filtro adicional, a pesar de parecer aumentar el trabajo a realizar, cuesta poco al Qdag por hacerse sobre pocas variables, y luego puede reducir mucho los tiempos de la consulta final porque ayuda a evitar muchos caminos innecesarios que se recorren, y que son muy costosos para el Qdag cuando hay muchas variables. La clave es que el pre-join precalcula qué combinaciones de valores de las variables elegidas tienen chance de producir resultados y cuáles no es necesario revisar”, explicó el profesor Navarro.

De este modo, usando distintas estrategias de pre-joining, los investigadres mostraron que los Qdags pueden ser sumamente rápidos también en consultas de más de 3 variables, de hecho ganando en todos los casos probados, donde los Qdags originales tenían resultados desastrosos. El académico afirmó que la nueva versión resulta útil en un espectro mucho más amplio de consultas reales, convirtiéndose en una herramienta muy útil para resolver consultas sobre grafos usando muy poco espacio.

Cabe destacar que este trabajo se gestó a partir de una colaboración académica entre las tres instituciones. José Cazorla realiza su doctorado en la Universidad Técnica Federico Santa María bajo la dirección de Diego Arroyuelo y desarrolló una pasantía de investigación en el DCC de la Universidad de Chile junto a Gonzalo Navarro. Fue en ese contexto donde surgió la idea que dio origen a esta investigación, que hoy es reconocida por la comunidad internacional.

--
Comunicaciones DCC