ALGORITMO PARA LA REDUCCIÓN DE BASES DE DATOS ORIENTADAS A GRAFOS

Resumen

En Internet, las consultas o queries se las realizan en bases de datos orientadas a grafos de gran tamaño. La optimización de consultas en este tipo de bases de datos es un campo importante de investigación, ya que estas pueden llegar a tardar mucho dependiendo del tamaño del grafo. Una de las soluciones es realizar la consulta en un grafo equivalente, pero de menor tamaño.

En este artículo planteamos una extensión a dicha solución que consiste en implementar algoritmos de equivalencias de procesos para poder “reducir” el grafo adicionando la semántica de la equivalencia débil, la cual nos permite comparar grafos con un cierto grado de equivalencia. Esta extensión a los algoritmos tradicionales nos permite hacer una comparación más “flexible” entre dos grafos, el resultado es que podemos eliminar ciertos parámetros que el usuario no usara´ comúnmente en sus consultas. Implementando este tipo de comparaciones entre grafos podemos reducir aún más las bases de datos que utilizando los algoritmos tradicionales de equivalencias.