Uno de los elementos fundamentales en casi todos los lenguajes de consultas en bases de datos de grafos son las llamadas Regular Path Queries (RPQs). “Estas permiten consultar por caminos en el grafo que tengan ciertas propiedades, por ejemplo ¿puedo llegar de mi casa al aeropuerto usando sólo un bus, varias conexiones de metro, y luego sólo un bus? o ¿tengo algún amigo, o amigo de amigo, que conozca un buen abogado?”, señaló el académico del DCC, Gonzalo Navarro.

Agregó que estas RPQs son muy flexibles y poderosas como herramienta de consulta, pero también muy costosas de calcular, “especialmente cuando buscamos caminos entre cualquier par de nodos posibles”, afirmó. Tomando este problema, junto con los académicos Diego Arroyuelo (DCC PUC) y Adrián Gómez-Brandón (Universidade de A Coruña) -todos investigadores del Instituto Milenio Fundamentos de los Datos (IMFD)- desarrollaron “Evaluating Regular Path Queries on Compressed Adjacency Matrices” trabajo que fue recientemente aceptado por la revista The Very Large Databases Journal (VLDBJ), una de las mejores en el área de bases de datos.

El profesor Navarro comentó que en esta investigación exploran cómo resolver RPQs mediante traducir la consulta al lenguaje del álgebra de matrices booleanas: “Cada matriz indica qué pares de nodos están conectados por una determinada propiedad, como estar conectados por bus, o ser amigos. Aunque el mapeo de RPQs al álgebra de matrices es natural, no se ha usado mucho porque las matrices resultantes suelen ser muy grandes. Pero por otro lado están mayormente vacías, lo que permite representarlas eficientemente. Nosotros utilizamos una representación que habíamos desarrollado antes para comprimir grafos Web, y la dotamos de los algoritmos necesarios para operar el álgebra de matrices (sumas, multiplicaciones, clausuras transitivas), de modo que además de usar poco espacio, la compresión agiliza las operaciones del álgebra de matrices”.

Como resultado los investigadores obtuvieron una representación que usa un orden de magnitud menos de la memoria que necesitan otros sistemas que resuelven RPQs, “y que es competitiva en velocidad para las RPQs más difíciles (cuando se buscan todos los pares de nodos conectados por la RPQ). Más en general, mostramos que este tipo de soluciones, vía matrices, es competitiva contra los enfoques usados más típicamente”, destacó el académico del DCC.

--
Comunicaciones DCC