A general approach to recursion in G-Core

Abstract

G-CORE es un lenguaje de consulta de bases de datos de grafos. Una de sus características más novedosas es que es un lenguaje cerrado, pues se consultan grafos y se retorna grafos. Además, tiene la capacidad de expresar caminos como ciudadanos de primera clase, es decir, se puede manipular, operar y retornar caminos. Como muchos otros lenguajes de consulta, G-CORE no tiene recursión. Aunque las funcionalidades de caminos ayudan, todavía no son suficientes para expresar una amplia variedad de consultas, particularmente algoritmos de grafos clásicos como orden topológico, búsqueda en anchura (BFS), circuito Euleriano, árbol recubridor mínimo, etc. Para abordar este problema en esta tesis se extiende G-CORE con funcionalidades recursivas. Esto se ha hecho en otros lenguajes de consulta, por ejemplo en SQL y SPARQL, donde se han obtenido buenos resultados al aumentar su poder expresivo de forma amigable.

Con ese objetivo, comenzamos por introducir una sintaxis y semántica para el nuevo operador recursivo. Dado que el modelo de datos de G-CORE es el de Path Property Graph, no es posible traducir directamente la recursión de SPARQL o de SQL. Lo anterior se debe a que la recursión de SQL y SPARQL está basada en la semántica de punto fijo, usando para ello la convergencia de una tabla auxiliar temporal que va creciendo hasta estabilizarse.

En el caso de The Path Property Graph, el avance del proceso recursivo no siempre se corresponde con un crecimiento de algún grafo. Luego no se puede saber de manera precisa cual métrica seguir para evaluar la convergencia del grafo temporal a un punto fijo. Para abordar esto, proponemos una recursión general a través de una estructura externa que pudiera definir distintas métricas para medir el crecimiento y convergencia del grafo temporal.

También mostramos cómo pueden ser codificadas las consultas clásicas de grafos añadiendo este nuevo operador recursivo. Finalmente repasamos las dificultades de implementar este nuevo operador en G-CORE y que otros operadores necesitan ser añadidos al lenguaje.