Consulta de ruta regular

En las bases de datos , y específicamente en las bases de datos de grafos , una consulta de ruta regular ^{[ 1 ]} o RPQ es una consulta que solicita pares de puntos finales en la base de datos que están conectados por una ruta que satisface una determinada expresión regular . Una característica similar existe en el lenguaje de consulta SPARQL como "rutas de propiedades".

Una base de datos de grafos consiste en un grafo dirigido cuyos bordes llevan una etiqueta. Una consulta de ruta regular es simplemente una expresión regular sobre el conjunto de etiquetas. Por ejemplo, en una base de datos de grafos donde los vértices representan usuarios y hay una etiqueta de borde "padre" para los bordes de un padre a un hijo, la consulta de ruta regular${\displaystyle {\text{padre}}{\text{padre}}^{*}}$seleccionaría pares de un nodo x y un descendiente y de x , con un camino de x a y de aristas "padre" que tengan una longitud de 1 o más.

Las respuestas a las consultas de relaciones regulares (RPQ) pueden consistir en pares de puntos finales , es decir, pares de nodos x e y conectados por una ruta que satisface la expresión regular; o bien, pueden consistir en la lista de todas las rutas que satisfacen dicha expresión. Sin embargo, este conjunto de rutas suele ser infinito.

Para asegurar que el número de resultados no sea infinito, la semántica de las RPQ a veces se define para devolver solo los caminos simples , es decir, los caminos que no pasan dos veces por el mismo vértice; o los senderos , es decir, los caminos que no pasan dos veces por la misma arista. ^{[ 2 ]}

La evaluación de consultas de ruta regulares (RPQ), en el sentido de devolver todos los pares de puntos finales, se puede realizar en tiempo polinomial . Para ello, para cada par de puntos finales, podemos considerar la base de datos de grafos como un autómata finito , representar también la consulta de ruta regular como un autómata finito y comprobar si existe una ruta adecuada verificando que la intersección de ambos lenguajes no sea vacía (es decir, resolviendo el problema de la vacuidad ), por ejemplo, mediante la construcción de un autómata producto .

Se han estudiado varios problemas clásicos sobre consultas para consultas de ruta regulares, como la contención de consultas ^{[ 3 ]} y la reescritura de consultas . ^{[ 4 ]}

La investigación en teoría de bases de datos ha estudiado variantes más expresivas de las RPQ:

• Las RPQ bidireccionales , también conocidas como 2RPQ , pueden recorrer aristas en la dirección inversa. Más precisamente, una 2RPQ es una expresión regular que utiliza las etiquetas del grafo junto con etiquetas que corresponden a aristas inversas. Por ejemplo, la RPQ${\displaystyle {\text{padre}}^{-}{\text{padre}}}$Selecciona pares de nodos x e y con un camino de x a y que va primero hacia atrás en una arista padre, luego hacia adelante en una arista padre, es decir, x e y son hermanos.
• Las consultas de ruta regulares conjuntivas, también conocidas como CRPQ , son consultas conjuntivas cuyos átomos son RPQ. Estas consultas permiten probar patrones más complejos que simples rutas, pero su evaluación resulta intratable.
• Una extensión adicional que permite tanto disyunciones (como la unión de consultas conjuntivas ) como expresiones bidireccionales son las UC2RPQ . ^{[ 5 ]}