Implementación de interfaz para consultas SQL sobre algoritmos recursivos para grafos en sistemas de bases de datos relacionales

Abstract

SQL es un lenguaje de consulta basada en el uso de álgebra relacional. Si bien el álgebra relacional no permite la expresión de consultas recursivas, existen distintas funcionalidades implementadas en este lenguaje para poder realizarlas. La codificación de este tipo de consultas no siempre resulta del todo intuitiva para un programador que desea implementarlas, debido a que la lógica de la recursión en SQL hace que la tabla temporal generada por la consulta recursiva crezca de manera iterativa e incremental, hasta que su tamaño no varía, complejizando la codificación de problemas recursivos en SQL. Para abordar este problema se propone una codificación genérica para consultas recursivas en bases de datos relacionales que facilite la implementación de estas consultas para un desarrollador. Para probar esta codificación genérica se implementarán consultas recursivas en SQL para los siguientes problemas clásicos de grafos que corren en tiempo polinomial: Topological Sorting, Connected Components, Eulerian Circuit, Minimum Spanning Tree, Eulerian Circuit y Planarity Testing. Se evaluará la factibilidad de la implementación de la propuesta de recursión generalizada para la simplificación de consultas recursivas para el caso de un motor de bases de datos SQL, mediante la entrega de un orden que permita a una consulta recursiva llegar a un punto fijo. En este trabajo se realizó la implementación una codificación genérica para consultas recursivas. Junto con esta codificación se implementó una interfaz gráfica que permite la creación de datasets que representan grafos y la codificación de las consultas recursivas sobre los datos generados. Esta interfaz permite la codificación de estas consultas siguiendo el formato de la consulta genérica implementada. También se implementaron consultas recursivas para los 6 problemas propuestos anteriormente sobre la base de la codificación genérica propuesta. Se obtuvo como resultado que es posible implementar una codificación genérica para consultas recursivas en SQL para bases de datos relacionales. Por otro lado, en el contexto de la evaluación sobre el motor de bases de datos relacionales PostgreSQL, se obtiene el resultado de que es posible entregar un orden dentro de la sub-consulta recursiva, la que se reduce a entregar la profundidad máxima que puede tener la recursión. Además, se concluye que implementación actual de recursión en el contexto de bases de datos relacionales no es idónea para resolver de manera eficiente los problemas propuestos, debiendo requerir de recursos externos para desarrollar ciertos algoritmos y de estar bajo diversas limitaciones respecto a las instrucciones que se pueden entregar en la sub consulta recursiva.