Diseño e implementación de un lenguaje de consulta para bases de datos de grafos

Abstract

Las bases de datos de grafos son un modelo que ha ganado terreno en los últimos años, dada la necesidad de modelar situaciones complejas en donde el modelo relacional no es suficiente. En este trabajo introducimos el tema haciendo una revisión del estado del arte de las bases de datos de grafos, explicando algunas de sus aplicaciones reales, definiendo algunos de los diferentes modelos teóricos y analizando las implementaciones más importantes que existen en la realidad. De nuestro análisis concluimos que la gran falencia en el tema es la ausencia de un lenguaje de consulta formal, con una sintaxis y semántica clara, y que tenga un buen equilibrio entre expresividad y complejidad. Nuestra propuesta para solucionar este problema es utilizar Converse-PDL como lenguaje de consulta de bases de datos de grafos, definiéndolo formalmente, y demostrando que su complejidad teórica es óptima. Además, mostramos que la expresividad de este lenguaje es suficiente para una gran cantidad de aplicaciones. Una vez definido nuestro lenguaje, procedemos a diseñar una implementación eficiente, definiendo los algoritmos y las estructuras de datos necesarias, cuidando de cumplir todas las restricciones que están presentes en nuestro modelo computacional. Luego, procedemos a realizar la implementación en sí, describiendo en detalle las representaciones internas de los distintos elementos, respaldando con resultados experimentales las decisiones tomadas. Además, explicamos las distintas mejoras y optimizaciones que realizamos, con el fin de obtener la mayor eficiencia posible. Una vez terminada la implementación, procedemos a explicar todos los archivos programados y la interfaz de usuario implementada, con el fin de facilitar los futuros desarrollos. Con el fin de validar nuestra implementación, procedemos a diseñar un experimento para evaluar cuantitativamente el desempeño de nuestra implementación. El experimento diseñado se ejecuta en nuestra implementación, así como en otras tres implementaciones existentes, escogiendo los proyectos más competitivos, para así realizar una comparación objetiva. Finalizamos nuestro trabajo con las conclusiones obtenidas a partir de los experimentos, destacando los aspectos más importantes de nuestra implementación, y exponiendo algunas ideas a desarrollar en el futuro.