Size bounds and algorithms for conjunctive regular path queries
Loading...
Date
2022
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Las conjuctive regular path queries (CRPQs) son una de las principales clases de consultas que se realizan sobre bases de datos de grafos. Su estructura se deriva de la estructura de consultas relacionales de joins, pero además permiten caminos de largo arbitrario para conectar puntos que deben ser considerados en dichos joins. Sin embargo y pese a su popularidad, hasta este momento se conoce poco acerca de cuales son los mejores algoritmos para procesar CRPQs. En este trabajo nos enfocamos en algoritmos óptimos en el peor caso, esto es, algoritmos cuyo tiempo de ejecución esta acotado por la cota superior del tamaño de las consultas que procesan. Aplicaciones recientes de este tipo de algoritmos se han llevado a cabo para consultas simples en grafos con resultados promisorios. En esta tesis, mostramos que la famosa cota sobre el número de resultados de una consulta propuesta por Atserias, Grohe y Marx puede ser extendida para CRPQs, pero que para obtener cotas ajustadas, se debe trabajar con un perfil de cardinalidad ligeramente mayor. Además de establecer dicha cota, discutimos acerca de los algoritmos que provienen de esta: si se procesa y materializa previamente todas las consultas del grafo (lo que demanda memoria cuadrática en términos de los vértices del grafo), entonces las técnicas desarrolladas para consultas conjuntivas pueden ser aplicadas. Por otro lado, si se impone una restricción en la memoria de trabajo de los algoritmos, entonces estos deben ser adaptados con cuidado: el orden de variables con el cual se procesa las consultas puede tener un gran impacto sobre su tiempo de ejecución.
Description
Tesis (Magíster en Ciencias de la Ingeniería)--Pontificia Universidad Católica de Chile, 2022