Es muy probable que se haya encontrado con problemas con búsquedas jerárquicas o navegación por grafos en tu aplicación como desarrollador que maneja casos de uso del mundo real. Y, por razones obvias, prefieres resolverlos en el base de datos y no en el cliente.
¿Qué son las búsquedas jerárquicas?
La búsqueda jerárquica hace referencia al proceso de búsqueda y recuperación de datos de una estructura jerárquica, como una árbol o una relación padre-hijo. Implica navegar por los niveles o capas de la jerarquía para localizar elementos de datos específicos o información relacionada, por ejemplo, organigramas, sistemas de archivos y árboles de categorías.
Los grafos son básicamente árboles que pueden tener ciclos, por lo que, además, también podríamos cubrir casos de uso como la búsqueda de rutas, etc. siempre que dispongamos de configuraciones adicionales para tratar los ciclos.
Considere un ejemplo en el que se utiliza una colección de empleados con una estructura jerárquica. Los empleados están organizados en una relación gerente-subordinado. Vamos a realizar operaciones en esta jerarquía de empleados usando Couchbase y JavaScript UDFs para demostrar la solución.
Pasando de la Recogida de empleados que podemos recuperar:
i) nivel genérico de empleado:
ii) jerarquía para cada empleado:
De qué trata este blog
Realmente te gusta el flexibilidad de bases de datos NoSQL, y su modelo de datos subyacente es JSON, por eso ha elegido Couchbase para sus necesidades de base de datos (gran elección, por cierto :-) ).
Ahora que tienes Couchbase como base de datos, quieres resolver el problema mencionado. Después de investigar un poco en SQL Documentos de referencia lingüística ha llegado a la conclusión de que no hay Declaración o Función en SQL++ para resolver nuestro problema, como el graphLookup API en MongoDB o CTE recursivo en bases de datos SQL.
Pero con la infraestructura existente, los usuarios pueden emular CTE recursivos utilizando UDF de JavaScript. En las secciones siguientes se explica cómo hacerlo y mucho más.
Solución a las consultas recursivas
Para implementar esta solución, necesitamos crear un UDF de JavaScript que utilice un algoritmo de búsqueda breadth-first para recorrer la jerarquía de empleados. La UDF toma un consulta de anclaje, a consulta recursivay opciones de configuración como parámetros. La consulta de anclaje recupera el conjunto inicial de empleados, mientras que la consulta recursiva hace referencia a los resultados de la iteración anterior utilizando la función $1 parámetro. Las opciones de configuración permiten la personalización, incluidos los criterios de salida anticipada, los argumentos para las consultas internas, la detección de ciclos, el modo de explicación para la planificación de consultas y las opciones de registro.
Cómo utilizar las consultas internas
La consulta de anclaje obtiene el documentos de nivel raíz de la colección de destino.
La consulta recursiva puede utilizar un ÚNASE A con un lado como $1 y la otra como colección de destino, para explotar la relación padre-hijo y realizar el recorrido de un nivel a otro.
En nuestra función, $1 hace lo mismo que el alias CTE en CTE recursivo.
Para comprender mejor cómo utilizamos SQL++ (N1QL) en las UDF de JavaScript, eche un vistazo a De N1QL a JavaScript y viceversa.
Veamos ahora el proceso paso a paso. En primer lugar, ¿es realmente necesario que el procesamiento recursivo de consultas sea una función recursiva?
No, esta sería una mala elección teniendo en cuenta la complejidad temporal (la misma funcionalidad en recursivo podría ser exponencial, pero lineal en un enfoque iterativo) y todas las demás cuestiones como marcos, etc., que vienen junto con la recursividad. Si estás interesado, echa un vistazo a esto artículo sobre la conversión de funciones de recursividad de cola a iterativas. Además, las UDF de JS tienen un preajuste profundidad de recursión máxima de 128; esto no es preferible para lo que intentamos hacer.
En pocas palabras, cualquier tarea iterativa hace lo siguiente:
Nos gustaría agradecer este artículo por su planteamiento.
Puntos de reflexión
¿Cómo mantenemos la expresión de estado y pasarlo como parámetro a la consulta (parte recursiva aquí)?
-
- Utilizamos la capacidad de SQL++ para pasar parámetros de consulta dinámicos y utilizar consultas parametrizadas para mantener el valor del estado en todos los niveles.
- Utilizamos $1 en la cláusula recursiva para referirse a los resultados de iteraciones anteriores, es decir, la expresión de estado
¿Cómo podemos optimizar?
-
- Preparar inicialmente tanto las consultas ancla como las recursivas para poder reutilizar los planes de consulta en el momento de la ejecución.
- Encontrar una manera de mirar el plan de consulta( similar a un EXPLICAR ) para que podamos generar índices apropiados para las sentencias internas (ancla y recursivas).
El resumen de alto nivel de la aplicación es el siguiente:
Código para CTE recursivo utilizando JS UDFs
Se trata de una implementación muy ingenua para empezar a funcionar. Configuramos el Búsqueda exhaustiva estableciendo el flujo de órdenes según el resumen anterior. Aquí está el código, de este Gist enlace:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 |
función recursive_cte(ancla , recursivo, config) { deje isLog = falso; deje anchorArgs=[]; deje recursiveArgs=[]; deje cycleFields=[]; deje hash; deje levelLimit = -1; deje isExplain = falso; deje res = {"res":[], "log":[]} si(config!=indefinido) { si(config.registro!=indefinido && config.registro==verdadero) { isLog = verdadero; } si(config.anchorArgs!=indefinido) { anchorArgs = config.anchorArgs; } si(config.recursiveArgs!=indefinido) { recursiveArgs = config.recursiveArgs; } si(config.levelLimit!=indefinido && config.levelLimit>0) { levelLimit = config.levelLimit; } si(config.cycleFields!=indefinido && config.cycleFields.longitud>0) { res['log'].pulse("Got cycle fields"+ config.cycleFields) // for(const campo de config.cicloCampos) { // cycleFields.push(campo); // } cycleFields = config.cycleFields; res['log'].pulse(cycleFields); // init hash hash = createhash(); } si(config.explique!=indefinido) { isExplain = verdadero; } } // estado inicial recursiveArgs.pulse(0); // Preparar la declaración de anclaje deje anchorPname; deje anchorPlan; pruebe{ const anchor_prep = N1QL("PREPARAR LA FUERZA"+ancla); para(const ap de anchor_prep) { anchorPname = ap["nombre"]; anchorPlan = ap["operador"]; } res['log'].pulse("ancla preparada"); } captura(err) { res['log'].pulse("no podía preparar el ancla"); tirar err; } // preparar declaración recursiva deje recursivePname; deje recursivePlan; pruebe{ const prep_recursivo = N1QL("PREPARAR LA FUERZA"+recursivo); para(const rp de prep_recursivo) { recursivePname = rp["nombre"]; recursivePlan = rp["operador"]; } res['log'].pulse("preparado recursivo"); } captura(err) { res['log'].pulse("no se pudo preparar recursivo"); tirar err; } // expresión de estado deje workSet = [] // ejecutar anclaje pruebe{ const anclaExec = N1QL("EJECUTAR `"+anchorPname+"`",anchorArgs); para(const doc de anclaExec) { workSet.pulse(doc); } } captura(err) { res['log'].pulse("falló la ejecución del ancla"); tirar err; } // comprobación del ciclo si(cycleFields.longitud>0) { res['log'].pulse("comprobación cíclica de los campos"+cycleFields) workSet = cycleCheck(cycleFields, hash, workSet); } // rellenar nivel raíz( nivel 0 ) res['res'].pulse(...workSet); deje nivel = 0; mientras que(workSet.longitud!=0) { // salir en condición de nivel si(levelLimit>0 && nivel>=levelLimit) { res['log'].pulse("Salir en condición de nivel: levelLimit="+levelLimit.toString()) romper; } // ejecutar consulta recursiva deje newWorkSet = [] // establecer estado $1 recursiveArgs[0] = workSet; pruebe{ const recursiveExec = N1QL("EJECUTAR `"+recursivePname+"`", recursiveArgs) // workSet vacío para rellenar de nuevo para(const doc de recursiveExec) { newWorkSet.pulse(doc) } } captura(err){ res['log'].pulse("fallo en la ejecución recursiva"); tirar err; } // comprobación del ciclo si(cycleFields.longitud>0) { newWorkSet = cycleCheck(cycleFields, hash, newWorkSet); } si(newWorkSet.longitud==0) romper; res["res"].pulse(...newWorkSet); // actualizar expresión de estado workSet = newWorkSet; nivel++; } si(isExplain){ res['log'].pulse("Plan de anclaje:"); res['log'].pulse(anchorPlan); res['log'].pulse("Plan Recursivo"); res["log"].pulse(recursivePlan); devolver res; } devolver isLog?res:res['res']; } función createhash() { deje h = {}; const getVal = función(clave) { devolver h[clave]==indefinido?falso:verdadero; } const setVal = función(clave) { h[clave] = verdadero; } devolver {setVal, getVal}; } función cycleCheck(cycleFields, hash, workSet) { deje cycleTrim = []; para(const doc de workSet) { deje clave = []; para(const campo de cycleFields) { si(doc[campo]!=indefinido){ clave.pulse(Cadena(doc[campo])); } } // crear hashKey hashKey = clave.únase a(Cadena.fromCódigoCar(30)); si(hash.getVal(hashKey)==verdadero){ continuar; } si no{ hash.setVal(hashKey); cycleTrim.pulse(doc); } } devolver cycleTrim; } |
Cómo añadir la función
He aquí una enlace para añadirlo a una biblioteca JavaScript (por ejemplo "mi biblioteca") dentro de su servicio de consulta, y un enlace para crear la UDF a partir de la biblioteca añadida.
Cree la UDF desde la biblioteca utilizando SQL++:
|
1 2 |
CREAR FUNCIÓN recursiveCte(ancla, recursivo, config) IDIOMA JAVASCRIPT como "recursive_cte" EN "mi biblioteca"; |
Utilización
Argumento 1: Ancla consulta, cadena
Argumento 2: Recursivo consulta, cadena (usos $1(expresión del estado) para referirse a los resultados de la iteración anterior )
Argumento 3: Config opcionesobjeto
Todos son obligatoriopero puede pasar un objeto vacíoes decir, {} si no está utilizando ninguna opción de configuración.
Opciones de configuración
Salida anticipada
levelLimit(1 a N) - Especifica el nivel en el que podemos parar. El recuento de niveles comienza en 0 para obtener resultados de anclaje, 1 para la primera iteración/nivel, 2 para el segundo, etc.
Argumentos de la consulta interna
anchorArgs - como se nombra, por ejemplo,{"arg:1} o argumentos posicionales, por ejemplo [1] para utilizar en la consulta de anclaje.
recursiveArgs - sólo pueden ser argumentos posicionales, y 0 debe reservarse para la expresión de estado. Por ejemplo: [0, 1] - fijar siempre el índice 0 ($1 arg) a 0por lo que podemos utilizarla en la cláusula recursiva como expresión de estado.
Detección de ciclo
cycleFields - Matriz de nombres de campo, por ejemplo, ["_de", "_a"]
Explique
explique - Comprobar el plan de consulta en los registros (conjuntos registro por defecto)
Registros
registro - Visualizar registros que ayudan cuando se quiere registrar mientras se desarrolla
Ejemplos de consultas
1. Contar números del 1 al N - ejemplo más sencillo de una consulta que muestra cómo funciona la CTE recursiva.
Haz una breve pausa para pensar cómo podrías hacer esto en N1QL sin la función utilidad que desarrollamos ahora. ¿Es posible? (¿O acabamos de hacer N1QL ¡Turing completo!)
2. Ejemplo de empleados - se refieren a la colección de empleados que vimos antes.
A. Encontrar el nivel organizativo de un empleado
B. Por empleado depende de la jerarquía
Consulta de anclaje:
|
1 2 3 |
SELECCIONE e1.*, 0 como hlevel DESDE `empleados` e1 DONDE e1.manager_id=" || to_str(e.empleado_id) |
Esto puede parecer demasiado verboso cuando se añade un DONDE predicado de la consulta externa. We puede utilizar el anchorArgs opción ¡para mitigarlo!
Argumentos (anchorArgs/recursiveArgs)
Explique
Proporcione {"explain": true} - puede ver el plan de consulta en el campo de registro
Salida anticipada
Establecer levelLimit como {"levelLimit":2} - si sólo desea 2 niveles de recursividad
Detección del ciclo
Sin detección de ciclo la consulta para encontrar la jerarquía de nivel de empleado irá a un bucle infinito y se bloquean al agotarse el tiempo de espera de la función, desperdiciando recursos de la CPU.
Teniendo en cuenta que cuando trabajamos con datos gráficos es muy probable que tengamos ciclos presentes y es el responsabilidad de la persona que llama a la función para establecer la detección de ciclo de los campos apropiados.
Aquí, el "employee_id", "manager_id" es suficiente para salir en ciclo.
Gracias por seguirnos en este desafiante tema, ¡esperamos que te revele más opciones para algunos de tus retos de consulta recursiva!
Referencias
-
- Convertir funciones recursivas en iterativas (Baeldung)
- Documentación de referencia del lenguaje SQL
- Referencia de MongoDB graphLookup
- Referencia CTE recursiva Snowflake
- Blog: De N1QL a JavaScript y viceversa - Parte 1
- Referencia de consulta PostgreSQL, cláusula WITH
- Documentación sobre consultas y resultados en SQL
- Creación de una biblioteca JavaScript docs
- Creación de funciones definidas por el usuario (UDF) en Couchbase
