Recorrido de árbol de preorden modificado en Django

Este artículo es una extensión de un artículo anterior titulado Relaciones de modelos recursivos en Django, que demostró una forma de utilizar Django c...

Introducción

Este artículo es una extensión de un artículo anterior titulado, Relaciones de modelos recursivos en Django, que demostró una forma de utilizar las capacidades básicas de Django para definir la base de datos. Clases respaldadas que modelan un caso de uso común para una relación recursiva. El caso de uso que intento satisfacer es la relación común entre empleados y gerentes de empleados, que también son empleados.

Evaluación de la implementación anterior

El artículo anterior definió una clase Empleado que se traduce en una tabla de base de datos de la estructura "empleado(id, nombre, apellido, función, ID_gerente)" donde ID_gerente es una clave externa que hace referencia a la identificación del empleado que representa al gerente de la empleado actual. Este tipo de implementación de almacenar datos recursivos en una base de datos se conoce como método de lista adictiva.

Para aclarar esto, el conjunto de resultados a continuación enumera a los empleados de una empresa ficticia, que se enumeran en orden jerárquico desde el presidente en la parte superior, luego dos gerentes y los empleados que administran debajo de ellos.

1
SELECT id, first_name, last_name, role, manager_id FROM employee ORDER BY id;

Tabla de empleados

id nombre apellido rol manager_id


1 Jane Doe PRES 2 John Doe Director General 1 3 Joe Schmo STD 2 4 John Brown ETS 2 5 Adam Smith Director General 1 6 Milt Friedman STD 5

Al observar la tabla de empleados que se muestra arriba, puede identificar la naturaleza jerárquica de los datos. Por ejemplo, puede decir que Jane Doe es la presidenta (la parte superior de la jerarquía) porque su entrada manager_id está vacía y también puede decir que dos empleados le reportan a ella, John Doe y Adam Smith, porque sus entradas manager_id son iguales a Jane. ID de empleado de \ de 1.

A continuación, demuestro el uso de una instancia de la clase ‘Empleado’ del artículo anterior, que representa a Jane Doe, para recuperar los empleados que le reportan directamente.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
(venv) $ python manage.py shell
Python 3.6.2 (default, Jul 17 2017, 16:44:45)
>>> from hrmgmt.models import Employee
>>> jane_doe = Employee.objects.get(pk=1)
>>> managers = jane_doe.employee.all()
>>> for m in managers:
...     print(m.first_name, m.last_name, m.role, m.manager_id, m.manager_id)
... 
John Doe MGR 1
Adam Smith MGR 1
>>>

Bajo el capó, Django ORM emite una consulta similar a la siguiente para obtener a los empleados directamente bajo Jane Doe cuando se llama a la propiedad employee en una instancia de la clase Employee.

1
SELECT * FROM htmgmt_employee WHERE manager_id = 1  

id nombre apellido rol manager_id


1 John Doe Director General 1 5 Adam Smith Director General 1

De manera similar, para obtener los empleados que reportan a John Doe, debe llamar al campo de relación ’empleado’ en una instancia de clase ‘Empleado’ que representa a John Doe, y bajo el capó, el ORM emitirá una consulta similar a esta:

1
SELECT * FROM hrmgmt_employee WHERE manager_id = 2

id nombre apellido rol manager_id


3 Joe Schmo STD 2 4 John Brown ETS 2

De esta manera, podemos identificar la jerarquía de la empresa comenzando con la parte superior (Jane Doe) y avanzando hacia abajo en la cadena de informes. Sin embargo, para cada nuevo gerente que identifique, tendrá que volver a llamar a la propiedad de relación empleado y el ORM de Django emitirá otra consulta para recuperar el nuevo conjunto de empleados que reportan al gerente anterior.

Si bien este enfoque ciertamente funcionará, brindando la información que deseamos cuando queremos avanzar hacia abajo en la lista de empresas, existe una preocupación por el rendimiento. Cada nuevo nivel de administración que encontramos requiere un nuevo viaje a la base de datos, y estas consultas se acumulan, consumiendo más y más recursos, lo que genera tiempos de espera más prolongados para el cliente que llama al programa. Los usuarios se irritarán rápidamente mientras miran la rueca de la paciencia en la pestaña del navegador.

El mismo problema ocurre cuando tratamos de subir la lista de empleados desde un empleado regular hasta los niveles de gestión y terminando con el presidente. Por ejemplo, considere cuándo desea determinar la línea ascendente de gestión a partir de John Brown.

Identificaría la identificación del gerente para John Brown, que es 2, luego haría una llamada a la base de datos para determinar el gerente del empleado con una identificación de 2.

1
2
/* Get John Brown and determine his associated manager_id */
SELECT * FROM htmgmt_employee WHERE first_name = 'John' AND last_name = 'Brown';

id nombre apellido rol manager_id


4 John Brown ETS 2

 

1
2
/* Get the employee with id of 2 */
SELECT * FROM htmgmt_employee WHERE id = 2;

id nombre apellido rol manager_id


2 John Doe Director General 1

Esto devuelve a John Doe, el gerente de John Brown, y vemos que su manager_id es 1, lo que indica que hay al menos un nivel de administración más por encima de él. Una vez más, emitimos otra consulta para determinar si el empleado con ID de 1 produce la parte superior de la jerarquía de gestión, o si hay otro nivel de gestión.

1
2
/* Get the employee with id of 1 */
SELECT * FROM htmgmt_employee WHERE id = 1;

id nombre apellido rol manager_id


1 Jane Doe PRES NULO

Solo ahora, después de realizar múltiples viajes a la base de datos, puede determinar la jerarquía de gestión. En una empresa mucho más grande, este método claramente tendrá algunos problemas de escala.

Recorrido de árbol de pedido anticipado modificado

Afortunadamente, existe otro método para almacenar y recuperar datos jerárquicos en una base de datos conocida como el Traversal de árbol de preorden modificado (MPTT). Esta segunda forma utiliza una estructura de datos similar a un árbol para modelar los datos, junto con un etiquetado intuitivo de los nodos asociados del árbol, lo que permite el recorrido basado en las etiquetas.

A continuación se muestra una representación en árbol de los datos de la tabla de listado de empleados anterior.

Employee MPTT Tree Structure{.img-responsive}

El esquema de etiquetado comienza colocando un 1 a la izquierda del nodo raíz, presidente Jane Doe en este ejemplo, luego baja un nodo a la izquierda de la raíz. En este nodo inmediatamente debajo ya la izquierda, incremente el conteo y etiquete este nuevo nodo con un 2. Este proceso continúa hasta el nodo secundario más bajo (hoja), Joe Schmo en este ejemplo. Luego, etiqueta el lado derecho del nodo secundario con el siguiente incremento y se mueve lateralmente a través de los hermanos hacia la derecha, etiquetando los lados izquierdo y derecho, incrementando a medida que avanza.

Una vez que llega al borde del subárbol, John Brown, atraviesa el árbol hasta llegar a un nivel que tiene hermanos, luego vuelve a moverse lateralmente y retrocede en el árbol, de manera similar al subárbol anterior encontrado hasta llegar a la raíz nuevamente.

Lo siguiente que debe hacer es traducir este árbol anidado en una estructura de tabla plana. Esto se logra definiendo dos columnas adicionales de valores "izquierda" y "derecha". Sin embargo, dado que left y right son palabras clave reservadas en el lenguaje SQL, las implementaciones reales usan abreviaturas, como "lft" y "rgt".

A continuación se muestra una tabla de ejemplo de una implementación mínima de una tabla estructurada MPTT para la lista de empleados.

empleado_mptt

id nombre apellido rol manager_id lft rgt


1 Jane Doe PRES 1 12 2 John Doe Gerente General 1 2 7 3 Joe Schmo STD 2 3 4 4 John Brown STD 2 5 6 5 Adam Smith Gerente General 1 8 11 6 Milt Friedman STD 5 9 10

Ahora que los datos están organizados y anotados con los valores en las columnas lft y rgt, hemos ganado más flexibilidad, control y eficiencia en la forma en que recuperamos los datos.

Usando la tabla estructurada MPTT anterior, puede enumerar los empleados que reportan al gerente John Doe usando la siguiente consulta SQL.

1
SELECT * FROM employee_mptt WHERE lft > 2 and rgt < 7 ORDER BY lft;

Sin embargo, para demostrar la eficiencia de la estructura del MPTT, rastrearé nuevamente la incorporación de la gerencia a partir de John Brown. Puedo lograr esto incluyendo algunos predicados en la sección WHERE de la consulta, especificando que lft sea menor a 6 y rgt mayor a 6 y luego ORDER por rgt listará la jerarquía de administración en orden ascendente, todo en un viaje a la base de datos.

1
SELECT * FROM employee_mptt WHERE lft < 5 AND rgt > 6 ORDER BY rgt;

id nombre apellido rol manager_id lft rgt


2 John Doe Gerente General 1 2 7 1 Jane Doe PRES 1 12

Anotar los registros de los empleados con las columnas lft y rgt de acuerdo con la estructura MPTT nos brinda una forma mejorada de recorrer los datos y obtener información útil con menos interacciones con la base de datos y de manera más eficiente. Por ejemplo, si quisiéramos saber cuántos empleados hay bajo John Doe en la estructura, asumiendo que ya tenemos la información de John, podemos aplicar esta sencilla fórmula:

1
abs((rgt - lft - 1)) / 2 = # of managed employees

Conectando los valores rgt y lft de John, obtenemos:

1
abs((2 - 7 - 1)) / 2 = 2

Esto nos proporciona la respuesta y no requirió ninguna interacción adicional con la base de datos.

django-mptt

La impresionante comunidad que utiliza y desarrolla el marco web de Django ha producido el proyecto Django-MPTT que amplía las funcionalidades básicas de Django e implementa MPTT. El proyecto Django-MPTT ofrece una serie de comodidades que hacen que la interacción con datos jerárquicos en la estructura MPTT sea muy conveniente al mismo tiempo que se logran las eficiencias asociadas con la recuperación de datos MPTT.

Implementar nuestra lista de empleados de datos jerárquicos usando Django-MPTT es bastante simple. Para demostrar esto, usaré el código existente de la discusión del artículo anterior sobre el uso de Django para modelar relaciones de empleados recursivas.

Si quieres seguir, puedes descargar el código desde mi cuenta de GitHub aquí comenzando en la etiqueta para el comienzo de este tutorial llamado "mptt-start".

Open up your command terminal, create a new ambiente virtual, and install the following requirements:

1
(venv) $ pip install django django-mptt

Después de ejecutar las migraciones iniciales como se describe en el artículo anterior, cargue el proyecto en su entorno de desarrollo integrado o editor de texto favorito y abra la secuencia de comandos de Python del modelo en el directorio "hrmgmt" y agregue el siguiente código.

 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
# hrmgmt/models.py

from django.db import models

from mptt.models import MPTTModel, TreeForeignKey

class EmployeeMptt(MPTTModel):
   STANDARD = 'STD'
   MANAGER = 'MGR'
   SR_MANAGER = 'SRMGR'
   PRESIDENT = 'PRES'

   EMPLOYEE_TYPES = (
       (STANDARD, 'base employee'),
       (MANAGER, 'manager'),
       (SR_MANAGER, 'senior manager'),
       (PRESIDENT, 'president'))

   role = models.CharField(max_length=25, choices=EMPLOYEE_TYPES)
   first_name = models.CharField(max_length=100)
   last_name = models.CharField(max_length=100)
   parent = TreeForeignKey('self', null=True, related_name='employee')

   def __str__(self):
       return "<EmployeeMptt: {} {}>".format(self.first_name, self.last_name)

   def __repr__(self):
       return self.__str__()

La primera declaración nueva agrega importaciones para las clases MPTTModel y TreeForeignKey desde la biblioteca django-mptt. Luego se define la clase EmployeeMptt.

La clase EmployeeMptt hereda del MPTTModel que agrega los campos de clase lft, rght, level y tree_id a la subclase (EmployeeMptt). Los campos funcionan de la siguiente manera:

  • lft: un campo entero como se describe en la sección anterior
  • rght: un campo entero como se describe en la sección anterior
  • level: un campo entero que indica el nivel de jerarquía para cada instancia
  • tree_id: un campo entero similar al campo de clase Empleado del artículo anterior manager_id

Sin embargo, una característica más útil que resulta de heredar de MPTTModel son los métodos que lo acompañan, que abstraen la implementación de los campos antes mencionados y brindan las funcionalidades preferidas para trabajar con la estructura de árbol.

  • get_ancestors(ascendente=Falso, include_self=Falso)
  • obtener_niños()
  • get_descendants(include_self=Falso)
  • get_descendant_count()
  • obtener_familia()
  • obtener_siguiente_hermano()
  • get_anterior_hermano()
  • get_root()
  • get_siblings(include_self=Falso)
  • insert_at(objetivo, posición='primer hijo', guardar=Falso)
  • es_niño_nodo()
  • es_nodo_hoja()
  • es_nodo_raíz()
  • move_to(objetivo, posición='primer hijo')

El campo TreeForeignKey se comporta esencialmente igual que django.db.models.ForeignKey normal, pero también muestra las opciones de la jerarquía de un árbol anidado en formularios de Django.

Ahora que hemos escrito el código para definir EmployeeMptt, traduzcamos el código modelo a tablas de base de datos de acuerdo con la estructura MPTT. En su terminal, realice y ejecute una migración para la clase EmployeeMptt:

1
2
3
4
(venv) $ python manage.py makemigrations
Migrations for 'hrmgmt':
  hrmgmt/migrations/0002_employeemptt.py
    - Create model EmployeeMptt

Inspeccione el DDL SQL que se emitirá:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
(venv) $ python manage.py sqlmigrate hrmgmt 0002
BEGIN;
--
-- Create model EmployeeMptt
--
CREATE TABLE "hrmgmt_employeemptt" ("id" integer NOT NULL PRIMARY KEY AUTOINCREMENT, "role" varchar(25) NOT NULL, "first_name" varchar(100) NOT NULL, "last_name" varchar(100) NOT NULL, "lft" integer unsigned NOT NULL, "rght" integer unsigned NOT NULL, "tree_id" integer unsigned NOT NULL, "level" integer unsigned NOT NULL, "parent_id" integer NULL REFERENCES "hrmgmt_employeemptt" ("id"));
CREATE INDEX "hrmgmt_employeemptt_lft_c82902c3" ON "hrmgmt_employeemptt" ("lft");
CREATE INDEX "hrmgmt_employeemptt_rght_c6110254" ON "hrmgmt_employeemptt" ("rght");
CREATE INDEX "hrmgmt_employeemptt_tree_id_7abd1eb2" ON "hrmgmt_employeemptt" ("tree_id");
CREATE INDEX "hrmgmt_employeemptt_level_687f7b49" ON "hrmgmt_employeemptt" ("level");
CREATE INDEX "hrmgmt_employeemptt_parent_id_88909826" ON "hrmgmt_employeemptt" ("parent_id");
COMMIT;

Ejecute la migración:

1
2
3
4
5
(venv) $ python manage.py migrate
Operations to perform:
  Apply all migrations: admin, auth, contenttypes, hrmgmt, sessions
Running migrations:
  Applying hrmgmt.0002_employeemptt... OK

Ahora utilice el shell de Django para llenar la nueva tabla "hrmgmt_employeemptt" mientras se familiariza simultáneamente con la API de Django-MPTT:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
(venv) $ python manage.py shell
Python 3.6.2 (default, Jul 17 2017, 16:44:45) 
(InteractiveConsole)
>>> from hrmgmt.models import EmployeeMptt
>>> jane_doe = EmployeeMptt.objects.create(first_name='Jane', last_name='Doe', role=EmployeeMptt.PRESIDENT)
>>> john_doe = EmployeeMptt.objects.create(first_name='John', last_name='Doe', role=EmployeeMptt.MANAGER, parent=jane_doe)
>>> joe_schmo = EmployeeMptt.objects.create(first_name='Joe', last_name='Schmo', role=EmployeeMptt.STANDARD, parent=john_doe)
>>> john_brown = EmployeeMptt.objects.create(first_name='John', last_name='Brown', role=EmployeeMptt.STANDARD, parent=john_doe)
>>> adam_smith = EmployeeMptt.objects.create(first_name='Adam', last_name='Smith', role=EmployeeMptt.MANAGER, parent=jane_doe)
>>> milt_friedman = EmployeeMptt.objects.create(first_name='Milt', last_name='Friedman', role=EmployeeMptt.STANDARD, parent=adam_smith)

No es demasiado complicado, ¿verdad? Hasta ahora, lo único que es relevante para la API de Django-MPTT es el uso del campo padre. Esto es necesario para que la biblioteca Django-MPTT anote los registros con los campos apropiados lft, rght, tree_id y level, lo que conduce a una tabla denominada "hrmgmt_employeemptt", que se completa de la siguiente manera.

htmgmt_employeemptt

id nombre apellido rol lft rght tree_id level parent_id


1 Jane Doe PRES 1 12 1 0 NULO 2 John Doe Gerente General 2 7 1 1 1 3 Joe Schmo STD 3 4 1 2 2 4 John Brown STD 5 6 1 2 2 5 Adam Smith Gerente General 8 11 1 1 1 6 Milt Friedman STD 9 10 1 2 5

Ahora apreciemos un poco esta excelente biblioteca jugando con los métodos de gran utilidad que Django-MPTT tiene para ofrecer.

Digamos que queremos obtener una lista de los empleados que reportan directamente a la presidenta Jane Doe (es decir, John Doe y Adam Smith), el nodo raíz del árbol MPTT.

1
2
>>> jane_doe.get_children()
<TreeQuerySet [<EmployeeMptt: John Doe>, <EmployeeMptt: Adam Smith>]>

Ok, hasta ahora no es demasiado especial, ¿verdad? Esto básicamente nos dio el mismo resultado que nuestro jane\_doe.employee.all() anterior y ya establecimos que esto tiene básicamente el mismo rendimiento que la implementación de la lista adyacente. Sin embargo, digamos que quería que todos los empleados fueran más bajos en la empresa, en relación con Jane Doe:

1
2
>>> jane_doe.get_descendants()
<TreeQuerySet [<EmployeeMptt: John Doe>, <EmployeeMptt: Joe Schmo>, <EmployeeMptt: John Brown>, <EmployeeMptt: Adam Smith>, <EmployeeMptt: Milt Friedman>]>

Bueno, eso fue bastante ingenioso, ya que obtuvimos todo eso en un solo viaje a la base de datos.

Otra cosa que podría ser interesante sería ver a todos los empleados en el mismo nivel que otro, dice John Brown:

1
2
>>> john_brown.get_siblings()
<TreeQuerySet [<EmployeeMptt: Joe Schmo>]>

Ahora vamos a echar un vistazo a algo un poco más interesante. Veamos si podemos enumerar a los empleados que están por encima de John Brown, por lo que básicamente estamos ascendiendo en la jerarquía gerencial, que ya describí antes como algo que es costoso (en términos de viajes a la base de datos) pero también inevitablemente requeriría algún tipo de construcción de bucle.

1
2
>>> john_brown.get_ancestors()
<TreeQuerySet [<EmployeeMptt: Jane Doe>, <EmployeeMptt: John Doe>]>

Bastante simple, ¿verdad? Y de nuevo, solo un viaje a la base de datos.

Los otros métodos de utilidad proporcionados por Django-MPTT son bastante sencillos con nombres intuitivos. Los invito a investigar más a fondo los otros métodos de utilidad en la documentación oficial.

Compensaciones entre la lista adyacente y MPTT {#compensaciones entre la lista adyacente y el mptt}

Como es el caso con muchas tareas que enfrentan los desarrolladores de software, a menudo necesitamos tomar decisiones importantes con respecto a la estrategia de implementación. En el primer artículo sobre relaciones recursivas con Django demostré un método de implementación conocido como "lista adyacente". Mientras que en este artículo de seguimiento presenté otro método de implementación, conocido como "Modified Preorder Tree Traversal (MPTT)". Ambos satisfacen los requisitos básicos para nuestro caso de uso. Entonces, cuando se enfrenta a una tarea de programación que es inherentemente recursiva, como en el caso de uso que se muestra aquí, ¿cuál debe elegir?

El método de la lista adyacente es relativamente sencillo de razonar e interactuar desde una perspectiva de codificación con Django, así como el uso de SQL sin procesar y programación de procedimientos. Sin embargo, mirando críticamente el nivel de la base de datos (consultas SELECT regulares), esto tiende a ser un poco repetitivo y costoso con muchos viajes a la base de datos.

Por otro lado, MPTT es una implementación un poco más elaborada en su perspectiva teórica, pero gracias a Django-MPTT tenemos una buena capa de abstracción que nos libera de la necesidad de pensar en términos de estructuras de datos de árbol. Hemos visto claramente que la recuperación de datos de una tabla de base de datos que implementa la estructura MPTT tiene un rendimiento significativamente mayor que el método de lista adyacente.

Sin embargo, hay un problema importante que debe tener en cuenta y considerar antes de continuar implementando MPTT en todas sus aplicaciones de Django:

MPTT es más adecuado para casos de uso en los que tiene datos jerárquicos relativamente estáticos a los que se accede con frecuencia a través de instrucciones SELECT.

Actualizar las entradas en una tabla estructurada MPTT es costoso porque tiene que cambiar los valores izquierdo y derecho de casi todas las entradas, pero también es un proceso bastante complejo. Afortunadamente, Django-MPTT viene con algunos buenos métodos que se encargan de la complejidad, pero esto no alivia el problema de tener que actualizar los valores izquierdo, derecho y de nivel de casi todas las entradas.

Para resumir, sugiero implementar la lista adyacente en los casos en los que espera que los datos se actualicen con una frecuencia parcial o más y extraiga Django-MPTT cuando se espera que los datos permanezcan bastante estáticos para que pueda disfrutar de los grandes aumentos de rendimiento de recuperación.

Espero que hayas disfrutado el artículo y, como siempre, no dudes en comentar o criticar cuando sea necesario. o.