Travesía de árbol de preorden modificada en Django

    Introducción

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

    Evaluación de la implementación previa

    El artículo anterior definió una Employeeclase que se traduce en una tabla de base de datos de la estructura “employee (id, first_name, last_name, role, manager_id)” donde manager_id es una clave externa que hace referencia a la identificación del empleado que representa al gerente del empleado actual. Este tipo de implementación de almacenamiento de datos recursivos en una base de datos se conoce como método de lista adyacente .

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

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

    Tabla de empleados

    idfirst_namelast_namerolemanager_id

    1JaneHacerPRES
    2JohnHacerMONSEÑOR1
    3JoeSchmoHORAS2
    4JohnmarrónHORAS2
    5AdánHerreroMONSEÑOR1
    6LechaFriedmanHORAS5

    Si observa la tabla de empleados que se muestra arriba, puede identificar la naturaleza jerárquica de los datos. Por ejemplo, puede saber 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 saber que dos empleados le reportan, John Doe y Adam Smith, porque sus entradas manager_id son iguales a las de Jane ID de empleado de 1.

    A continuación, demuestro el uso de una instancia de la Employeeclase del artículo anterior, que representa a Jane Doe, para recuperar a los empleados que dependen directamente de ella.

    (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 debajo de Jane Doe cuando employeese llama a la propiedad en una instancia de la Employeeclase.

    SELECT * FROM htmgmt_employee WHERE manager_id = 1  
    

    idfirst_namelast_namerolemanager_id

    1JohnHacerMONSEÑOR1
    5AdánHerreroMONSEÑOR1

    De manera similar, para obtener los empleados que informan a John Doe, llamaría al employeecampo de relación en una Employeeinstancia de clase que representa a John Doe, y bajo el capó, el ORM emitiría una consulta similar a esta:

    SELECT * FROM hrmgmt_employee WHERE manager_id = 2
    

    idfirst_namelast_namerolemanager_id

    3JoeSchmoHORAS2
    4JohnmarrónHORAS2

    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, por cada nuevo gerente que identifique, tendrá que volver a llamar a la employeepropiedad de relación y el ORM de Django emitirá otra consulta para recuperar el nuevo conjunto de empleados que informan al gerente anterior.

    Si bien este enfoque ciertamente funcionará, proporcionando la información que deseamos cuando queremos caminar hacia abajo en la lista de la empresa, existe una preocupación por el rendimiento. Cada nuevo nivel de gestión que encontramos requiere un viaje más a la base de datos, y estas consultas se acumulan, consumiendo cada vez más recursos, lo que lleva a tiempos de espera más largos para el cliente que llama al programa. Los usuarios se enojarán rápidamente mientras miran la rueda giratoria de la paciencia en la pestaña del navegador.

    El mismo problema ocurre cuando intentamos subir la lista de empleados desde un empleado regular hasta los niveles de administració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 el ID de gerente de John Brown, que es 2, luego realizaría una llamada a la base de datos para determinar el gerente del empleado con un ID de 2.

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

    idfirst_namelast_namerolemanager_id

    4JohnmarrónHORAS2
    /* Get the employee with id of 2 */
    SELECT * FROM htmgmt_employee WHERE id = 2;
    

    idfirst_namelast_namerolemanager_id

    2JohnHacerMONSEÑOR1

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

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

    idfirst_namelast_namerolemanager_id

    1JaneHacerPRESNULO

    Solo ahora, después de realizar varios 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.

    Desplazamiento del árbol de pedidos anticipados modificado

    Afortunadamente, existe otro método para almacenar y recuperar datos jerárquicos en una base de datos conocido como Modified Preorder Tree Traversal (MPTT). Esta segunda forma utiliza una estructura de datos similar a un árbol para modelar los datos, junto con un etiquetado intuitivo de los nodes asociados del árbol, lo que permite el desplazamiento 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.

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

    Una vez que llegas al borde del subárbol, John Brown, atraviesas el árbol hasta llegar a un nivel que tiene hermanos, luego te mueves de nuevo lateralmente y retrocedes por el árbol, 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 mediante la definición de dos columnas adicionales de valores “izquierda” y “derecha”. Sin embargo, dado que izquierda y derecha son palabras clave reservadas en el lenguaje SQL, las implementaciones reales utilizan 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

    idfirst_namelast_namerolemanager_idlftrgt

    1JaneHacerPRES112
    2JohnHacerMONSEÑOR127
    3JoeSchmoHORAS234
    4JohnmarrónHORAS256
    5AdánHerreroMONSEÑOR1811
    6LechaFriedmanHORAS5910

    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.

    Con la tabla estructurada de MPTT anterior, puede enumerar los empleados que dependen del gerente John Doe mediante la siguiente consulta SQL.

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

    Sin embargo, para demostrar la eficiencia de la estructura MPTT, volveré a rastrear la adhesión de la administración a partir de John Brown. Puedo lograr esto incluyendo algunos predicados en la sección DONDE de la consulta, especificando que lft sea menor que 6 y rgt sea mayor que 6 y luego ORDER-ing by rgt enumerará la jerarquía de administración en orden ascendente, todo en un viaje a la base de datos.

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

    idfirst_namelast_namerolemanager_idlftrgt

    2JohnHacerMONSEÑOR127
    1JaneHacerPRES112

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

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

    Conectando los valores rgt y lft de John, obtenemos:

    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 increíble comunidad que usa y desarrolla el marco web 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 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 recursivas entre empleados.

    Si desea seguir adelante, puede descargar el código de mi cuenta de GitHub aquí, comenzando por la etiqueta del comienzo de este tutorial llamado “mptt-start”.

    Abra su terminal de comando, cree un nuevo entorno virtual e instale los siguientes requisitos:

    (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 favorito o editor de texto y abra el script Python del modelo en el directorio “hrmgmt” y agregue el siguiente código.

    # 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 MPTTModely TreeForeignKeyde la biblioteca django-mptt. Entonces EmployeeMpttse define la clase.

    Los EmployeeMptthereda de la clase de la MPTTModelque añade los campos de clase lft, rght, level, y tree_ida 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 de cada instancia
    • tree_id: un campo entero similar al Employeecampo de clase del artículo anterior manager_id

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

    • get_ancestors (ascendente = Falso, include_self = False)
    • get_children ()
    • get_descendants (include_self = False)
    • get_descendant_count ()
    • get_family ()
    • get_next_sibling ()
    • get_previous_sibling ()
    • get_root ()
    • get_siblings (include_self = False)
    • insert_at (objetivo, posición = ‘primer hijo’, guardar = Falso)
    • is_child_node ()
    • is_leaf_node ()
    • is_root_node ()
    • move_to (objetivo, posición = ‘primer hijo’)

    El TreeForeignKeycampo se comporta esencialmente de la misma manera que el normal, django.db.models.ForeignKeypero también muestra las opciones de la jerarquía de un árbol con anidación en formas Django.

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

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

    Inspeccione el SQL DDL que se emitirá:

    (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:

    (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 completar la nueva tabla “hrmgmt_employeemptt” mientras se familiariza simultáneamente con la API de Django-MPTT:

    (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 Django-MPTT es el uso del parentcampo. Esto es necesario para que la biblioteca Django-MPTT anote los registros con los campos lft, rght, tree_id y level apropiados, lo que lleva a una tabla llamada “hrmgmt_employeemptt”, que se completa de la siguiente manera.

    htmgmt_employeemptt

    idfirst_namelast_namerolelftrghttree_idlevelparent_id

    1JaneHacerPRES11210NULO
    2JohnHacerMONSEÑOR27111
    3JoeSchmoHORAS34122
    4JohnmarrónHORAS56122
    5AdánHerreroMONSEÑOR811111
    6LechaFriedmanHORAS910125

    Ahora ganemos un poco de apreciación por esta excelente biblioteca jugando con los excelentes métodos de utilidad que Django-MPTT tiene para ofrecer.

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

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

    Ok, hasta ahora no es muy especial, ¿verdad? Esto básicamente nos dio el mismo resultado que el anterior jane_doe.employee.all()y ya establecimos que 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:

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

    Bueno, eso fue bastante hábil, 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:

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

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

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

    Bastante simple, ¿verdad? Y nuevamente, 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 .

    Compensación entre la lista adyacente y MPTT

    Como es el caso de 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 demuestra aquí, ¿cuál debería elegir?

    El método de lista adyacente es relativamente sencillo para razonar e interactuar desde una perspectiva de codificación con Django, así como también mediante el uso de SQL sin formato y programación de procedimientos. Sin embargo, mirando críticamente al nivel de la base de datos ( SELECTconsultas 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 para liberarnos de la necesidad de pensar en términos de estructuras de datos de árbol. Hemos visto claramente que recuperar 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 SELECTdeclaraciones.

    Actualizar las entradas en una tabla estructurada MPTT es caro 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 métodos agradables que se encargan de la complejidad, pero esto no alivia el problema de tener que actualizar los valores de nivel, derecho e izquierdo de casi todas las entradas.

    Para resumir, sugiero implementar la lista adyacente en los casos en los que espere que los datos se actualicen con frecuencia o más y sacar 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 haya disfrutado del artículo y, como siempre, no dude en comentar o criticar cuando sea necesario.

     

    Etiquetas:

    Deja una respuesta

    Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *