Implementación de un lenguaje de consultas para bases de datos de grafos utilizando estructuras de datos comprimidas

Abstract

En la actualidad existe una clara tendencia por buscar nuevos modelos de bases de datos que se adecuen de mejor manera a las necesidades modernas. Dentro de las alternativas que cuentan con popularidad se encuentran las denominadas bases de datos de grafos, que han adquirido fuerza en conjunto a la reciente revolución de la Web y sus tecnologías asociadas. La adopción de este modelo aún requiere de un amplio estudio, pues los grafos suponen una complejidad intrínseca que debe ser considerada al momento de diseñar una implementación. Dos desafíos fundamentales que se presentan son los volúmenes de información que deben ser manejados, junto con la elección de un buen lenguaje de consultas que equilibre el nivel de expresividad con su complejidad de evaluación. En este trabajo se considera un lenguaje de consultas ampliamente estudiado que permite realizar consultas de navegación a partir de expresiones regulares. Así mismo, se presenta un algoritmo de evaluación práctico para resolver estas consultas de manera eficiente. Adicionalmente se utiliza una representación para bases de datos de grafos que explota las características de las estructuras de datos sucintas para mantener grandes volúmenes de información en memoria principal. El trabajo presenta además una implementación de la propuesta considerando la extensibilidad y orden del código, con el fin de proveer una herramienta de utilidad para nuevas investigaciones. El desarrollo está dividido en dos componentes. Por un lado se proporciona una biblioteca con la implementación de las estructuras sucintas involucradas y por otro un sistema simple de gestión de base de datos que permite la evaluación de consultas del lenguaje escogido. Adicionalmente, y con el objetivo de comprobar el desempeño de la propuesta, se presenta una evaluación experimental de la implementación, realizando una comparación con algunas alternativas actuales para bases de datos de grafos y obteniendo resultados favorables. Finalmente se termina el trabajo señalando las conclusiones obtenidas del análisis experimental realizado.