Implementación dinámica del Ring

Abstract

Las bases de datos de grafos permiten almacenar informaci´on utilizando representaciones de nodos y aristas. En este contexto, es posible realizar consultas utilizando basic graph patterns, equivalentes en t´erminos generales a joins naturales. No obstante, esta consulta requiere ser resuelta en tiempos accesibles. Considerando esto, el Ring es una base de datos compacta que logra tiempos bajos para consultas join implementando una variante del algoritmo Leapfrog Triejoin, la que cumple con ser Worst Case Optimal. Sin embargo, las estructuras sobre las que se basa el Ring no soportan operaciones de actualizaci´on, impidiendo la modificaci´on del grafo. Adicionalmente, debido a que los grafos ocupan valores en los nodos y etiquetas, representados como strings, en este ´ındice se debe traducir previamente el alfabeto del grafo al universo de identificadores utilizado por la base de datos. Esto excluye al Ring de varios casos de uso. Por este motivo, esta memoria plantea y valida el dise˜no de un nuevo Ring din´amico, el cual permite inserciones y eliminaciones de elementos. Para hacer esto posible, se modificaron y adaptaron estructuras existentes como B-Trees para formar bitvectors y wavelet matrices, con el fin de tener un formato din´amico y que soporte las operaciones necesarias para el funcionamiento del Ring. Adem´as, se cre´o un diccionario compacto a base de Plain Front Coding y ´arboles binarios, cuyo prop´osito es servir de traductor entre el alfabeto del usuario y los identificadores del ´ındice. La soluci´on fue implementada en C++ y logr´o ser funcional, siendo validada con el dataset de Wikidata Graph Pattern Benchmark frente a distintos ´ındices del estado del arte, para el cual se a˜nadieron experimentos de actualizaci´on. El Ring din´amico, incluyendo su diccionario, obtuvo buenos resultados en cuanto a compresi´on, logrando reducir en un 79 % el espacio ocupado frente a los datos en texto plano. En cuanto a los tiempos de consultas, el ´ındice creado fue mucho m´as lento que su versi´on est´atica, sin embargo, result´o ser superior que algunos sistemas, en particular Blazegraph, motor que soporta Wikidata en la actualidad. Adicionalmente, los resultados obtenidos son, en t´erminos generales, comparables con el resto de bases de datos, a excepci´on del caso particular en el que los patrones presentan ciclos. Para las operaciones de actualizaci´on, el Ring din´amico obtuvo resultados mejores que las bases de datos alternativas, siendo ´unicamente superado por Virtuoso para el caso espec´ıfico del borrado de nodos. Se concluye que la soluci´on planteada permite lograr dinamismo, preservando un espacio ocupado cercano al que necesita el Ring est´atico y siendo superado en tiempo ´unicamente por ´ındices que requieren de mucho m´as espacio para funcionar. Incluso se obtienen mejores resultados que algunas implementaciones populares para bases de datos para grafos.