php - topologico - para que sirven los grafos

Cómo desarrollar un esquema de base de datos para una estructura de árbol(gráfico acíclico dirigido) (7)

La única biblioteca de PHP que encontré para manipular gráficos es el paquete PEAR "Structures_Graph" ( http://pear.php.net/manual/en/package.structures.structures-graph.php ). Actualmente no se está manteniendo, las funciones importantes (por ejemplo, la eliminación de un nodo) no están implementadas y los errores graves están abiertos (por ejemplo, no se puede instalar en Windows 7). No parece que ese paquete, en su forma actual, sería útil.

Las operaciones básicas que se necesitan para manipular su gráfico se pueden dividir en aquellas que cambian el gráfico (mutación) y aquellas que lo consultan (no mutante).

Operaciones mutantes

CreateNode ($ nodeName), devuelve un $ nodeID. Tenga en cuenta que cuando se crean nodos, no tienen bordes que los conecten a otros nodos en el gráfico.
DeleteNode ($ nodeID): para imponer la integridad referencial, esto solo debe permitirse si todos los bordes que se conectan al nodo se han eliminado anteriormente, y de lo contrario se produce una excepción.
UpdateNodeName ($ nodeID, $ newNodeName): si se le permite cambiar el nombre de un nodo existente.
CreateHorizontalEdge ($ souceNodeID, $ destinationNodeID): este es un borde dirigido. Lanza excepciones si el borde ya existe, o si agregar una herida de borde crea un ciclo.
DeleteHorizontalEdge ($ sourceNodeID, $ destinationNodeID)
CreateVerticalEdge ($ firstNodeID, $ secondNodeID): este es un borde bidireccional, la primera y la segunda identificación de los nodos se pueden cambiar y el efecto en el gráfico será el mismo. Lanza una excepción si el borde ya existe o si los dos nodos no tienen el mismo padre horizontal.
DeleteVerticalEdge ($ firstNodeID, $ secondNodeID) - Como el borde no está dirigido, eliminará el borde incluso si los argumentos estaban en el orden opuesto para la creación.

Ejemplos: para construir la sección de su gráfico que tiene nombres de nodo que comienzan con "B" manualmente, el código sería:

$nodeID_B = CreateNode(“B”); $nodeID_B1 = CreateNode(“B1”); $nodeID_B2 = CreateNode(“B2”); $nodeID_B3 = CreateNode(“B3”); CreateHorizontalEdge($nodeID_B, $nodeID_B1); CreateHorizontalEdge($nodeID_B, $nodeID_B2); CreateHorizontalEdge($nodeID_B, $nodeID_B3); CreateVerticalEdge($nodeID_B1, $nodeID_B2); CreateVerticalEdge($nodeID_B2, $nodeID_B3);

Código para eliminar manualmente el nodo con el nombre "B3":

// Must remove all edges that connect to node first DeleteVerticalEdge($nodeID_B2, $nodeID_B3); DeleteHorizontalEdge($nodeID_B, $nodeID_B3); // Now no edges connect to the node, so it can be safely deleted DeleteNode($nodeID_B3);

Operaciones no mutantes

NodeExists ($ nodeID) - Devuelve true / false
GetNodeIDByName ($ nodeName) - Devuelve $ nodeID
GetNodeName ($ nodeID)
HorizontalEdgeExists ($ sourceNodeID, $ destinationNodeID) - Devuelve verdadero / falso
VerticalEdgeExists ($ firstNodeID, $ secondNodeID): devuelve verdadero / falso, el mismo resultado independientemente del orden de los argumentos.
HorizontalConnectionExists ($ startNodeID, $ endNodeID) - Devuelve true / false - Siguiendo las flechas horizontales, ¿hay una ruta desde el nodo de inicio hasta el nodo final? Para probar si la creación de un nuevo borde horizontal desde $ nodeID1 a $ nodeID2 creará un ciclo, llame a HorizontalConnectionExists ($ nodeID2, $ nodeID1).
GetHorizontalAncestorNodes ($ nodeID): devuelve una matriz de todos los nodos que tienen rutas horizontales que llevan desde ellos al nodo de argumento.
GetHorizontalDescendentNodes ($ nodeID): devuelve una matriz de todos los nodos que tienen rutas horizontales que van desde el nodo de argumento al nodo de argumento.
GetVerticalSiblingNodes ($ nodeID): devuelve una matriz de todos los nodos que tienen conexiones verticales con el nodo de argumento. Dado que (según su respuesta a mi pregunta de aclaración), las relaciones verticales no son transitivas, la función VerticalEdgeExists (arriba) es la única necesaria para consultar las relaciones verticales.

Ejemplo: Para obtener una lista de nodos que se incluirán en el subárbol que describe en su pregunta, combine los resultados de GetHorizontalAncestorNodes ($ nodeID) y GetVerticalSiblingNodes ($ nodeID).

Estructuras de datos

Siempre necesitará una tabla de "Nodos" para mantener nodeID y nodeName. Esta tabla se puede ampliar para contener otra información asociada con los nodos.

Dado que los bordes verticales no son transitivos, la información sobre ellos se puede colocar simplemente en una tabla de "VerticalEdges" con columnas vEdgeID, firstNodeID, secondNodeID.

Hay varias opciones para almacenar la información del borde horizontal. Por un lado, las estructuras de datos y las operaciones de mutación pueden ser simples, pero al costo de hacer que algunas de las operaciones de consulta sean más lentas y más complejas. Por otro lado, las estructuras de datos pueden ser un poco más complejas pero posiblemente mucho más grandes (creciendo exponencialmente con el número de nodos en el peor de los casos), con operaciones de mutación más complejas, pero consultas más simples y más rápidas. Decidir qué implementación es la mejor para usted dependerá del tamaño de sus gráficos y de la frecuencia con la que cambian en comparación con el número de veces que se consultan.

Describiré tres estructuras de datos posibles para representar el gráfico, pasando de lo simple a lo complejo. Entraré en detalles sobre los algoritmos para las operaciones enumeradas anteriormente solo para el último conjunto de estructuras de datos. Creo que el conjunto de estructuras es mejor para los gráficos más pequeños que tienen una alta proporción de consultas a cambios.

Tenga en cuenta que todas las estructuras de datos tienen las tablas "Nodos" y "Bordes verticales" que mencioné anteriormente.

Estructura de datos mínima

La primera estructura de datos tiene una tabla "HorizontalEdges" con columnas hEdgeID, sourceNodeID y destinationNodeID. Las funciones de mutación son simples, y la mayoría del código será un código de comprobación de errores que genera excepciones. Las funciones no mutantes HorizontalConnectionExists, GetHorizontalAncestorNodes y GetHorizontalDescendentNodes serán complejas y potencialmente lentas. Cada vez que se llaman, recursivamente recorren la tabla HorizontalEdges y recopilan los ID de nodo. Esas colecciones se devuelven directamente para las dos funciones posteriores, mientras que HorizontalConnectionExists puede terminar y devolver verdadero si encuentra el nodo final mientras busca a los descendientes del nodo inicial. Volverá falso si la búsqueda finaliza sin encontrar el nodo final.

Tabla de cierre transitivo

La segunda estructura de datos también tiene una tabla HorizontalEdges idéntica a la descrita anteriormente, pero también tiene una segunda tabla "HorizontalTransitiveClosures" con las columnas hTCID, startNodeID y endNodeID. Hay una fila en esta tabla para cada par de nodo de inicio y nodo final, de manera que una ruta que usa bordes horizontales puede rastrearse desde el nodo de inicio hasta el nodo final.

Ejemplo: Para el gráfico en la pregunta, las filas en esta tabla que incluyen el nodo A (para simplificar la notación, usaré los nombres, en lugar de los ID de nodo enteros para identificar los nodos, y omitir la columna hTCID) son:

A, A2 A, A2B1 A, A2B1B2 A, X A, Y A, Z

Las filas que incluyen el nodo A2B1 (el primero también se encuentra en el conjunto anterior) son:

A, A2B1 A2, A2B1 B, A2B1 B1, A2B1 A2B1, A2B1B2 A2B1, X A2B1, Y A2B1, Z

En el peor de los casos, esta tabla se escala como el cuadrado del número de nodos.

Con esta estructura de datos, HorizontalConnectionExists, GetHorizontalAncestorNodes y GetHorizontalDescendentNodes se pueden implementar como búsquedas simples de la tabla HorizontalTransitiveClosures. La complejidad se mueve a las funciones CreateHorizontalEdge y DeleteHorizontalEdge. DeleteHorizontalEdge es particularmente complejo y requiere una buena explicación de por qué funciona el algoritmo.

Cierre transitivo con caminos

La estructura de datos final que analizaré almacena la información del borde horizontal en dos tablas. El primero, "HorizontalTransitiveClosurePaths" tiene las columnas hTCPathID, startNodeID, endNodeID, pathLength. La segunda tabla "PathLinks" tiene columnas PathLinkID, hTCPathID, sourceNodeID, destinationNodeID.

La tabla HorizontalTransitiveClosurePaths es similar a la tabla HorizontalTransitiveClosures en la estructura de datos descrita anteriormente, pero tiene una fila para cada ruta posible que puede lograr un cierre transitivo, en lugar de una fila por cierre transitivo. Por ejemplo, en la gráfica que se muestra en la pregunta, la tabla HorizontalTransitiveClosures tendría una fila (B, A2B1B2) (notación abreviada como la anterior) para el cierre que comenzó en B y terminó A2B1B2. La tabla HorizontalTransitiveClosurePaths tendría dos filas: (10, B, A2B1B2, 3) y (11, B, A2B1B2, 2), ya que hay dos formas de ir de B a A2B1B2. La tabla PathLinks describe cada una de esas rutas con una fila por borde que forma la ruta. Para las dos rutas de B a A2B1B2, las filas son:

101, 10, B, B1 102, 10, B1, A2B1 103, 10, A2B1, A2B1B2 104, 11, B, B2 105, 11, B2, A2B1B2

No hay necesidad de una tabla HorizonalEdges, ya que los bordes se pueden encontrar seleccionando las filas en la tabla HorizontalTransitiveClosurePaths con una longitud de 1.

Las funciones de consulta se implementan de la misma manera que en la estructura de datos de cierre transitivo descrita anteriormente. Dado que pueden existir varias rutas para un cierre, deberá utilizarse el operador GROUP BY. Por ejemplo, la consulta SQL que devuelve todos los nodos que son ancestros del nodo con ID: nodeid es: SELECT startNodeID from HorizontalTransitiveClosurePaths WHERE endNodeID =: nodeid GROUP BY startNodeID

Para implementar DeleteHorizontalEdge, busque en los PathLinks el hTCPathID de todas las rutas que contienen el borde. Luego elimine esas rutas de la tabla HorizontalTransitiveClosurePaths y todos los bordes asociados con las rutas de la tabla PathLinks.

Para implementar CreateHorizontalEdge ($ souceNodeID, $ destinationNodeID), primero busque en la tabla HorizontalTransitiveClosurePaths las rutas que terminan en $ souceNodeID, este es el "conjunto de rutas de antecesor". Busque en las rutas de acceso horizontales / transitorias las rutas que comienzan en destinationNodeID: este es el "conjunto de rutas descendientes". Ahora inserte nuevas rutas de los siguientes 4 grupos (algunos de los cuales pueden estar vacíos) en la tabla HorizontalTransitiveClosurePaths e inserte los enlaces para esas rutas en la tabla PathLinks.

La ruta de longitud 1 desde $ souceNodeID a $ destinationNodeID
Para cada ruta en el conjunto de rutas del antepasado, una nueva ruta que extiende el final de la ruta en un enlace adicional desde $ souceNodeID a $ destinationNodeID
Para cada ruta en el conjunto de rutas descendientes, una nueva ruta que extiende el inicio de la ruta en un enlace adicional de $ souceNodeID a $ destinationNodeID
Para cada combinación de una ruta desde el conjunto de rutas del antepasado y una ruta desde el conjunto de la ruta del descendiente, una ruta creada al cortar la ruta del antepasado, al enlace de $ souceNodeID a $ destinationNodeID, a la ruta del descendiente.

Ejemplo: Una gráfica consta de 6 nodos: A1, A2, B, C, D1 y D2. Tiene 4 bordes, (A1, B), (A2, B), (C, D1), (C, D2). La tabla HorizontalTransitiveClosurePaths (usando el nombre de nodo en lugar de un número) es:

1, A1, B, 1 2, A2, B, 1 3, C, D1, 1 4, C, D2, 1

La tabla de PathLinks es:

1, 1, A1, B 2, 2, A2, B 3, 3, C, D1 4, 4, C, D2

Ahora agregamos el borde de B a C. El conjunto de la ruta del antepasado es (1, 2) y el conjunto de la ruta del descendiente es (3, 4) Las rutas agregadas en cada uno de los 4 grupos son:

El nuevo borde en sí mismo: HorizontalTransitiveClosurePaths: (5, B, C, 1); PathLinks (5, 5, B, C)
Extienda cada ruta de antepasado por un enlace al final:
HorizontalTransitiveClosurePaths: 6, A1, C, 2 7, A2, C, 2 PathLinks: 6, 6, A1, B 7, 6, B, C 8, 7, A2, B 9, 7, B, C
Extienda cada ruta descendente por un enlace al comienzo:
HorizontalTransitiveClosurePaths: 8, B, D1, 2 9, B, D2, 2 PathLinks: 10, 8, B, C 11, 8, C, D1 12, 9, B, C 13, 9, C, D2
Empalme todas las combinaciones que contengan una ruta ancestral y una ruta descendiente:
HorizontalTransitiveClosurePaths: 10, A1, D1, 3 11, A1, D2, 3 12, A2, D1, 3 13, A2, D2, 3 PathLinks: 14, 10, A1, B 15, 10, B, C 16, 10, C, D1 17, 11, A1, B 18, 11, B, C 19, 11, C, D2 20, 12, A2, B 21, 12, B, C 22, 12, C, D1 23, 13, A2, B 24, 13, B, C 25, 13, C, D2

Déjame saber si alguna parte de la respuesta necesita una aclaración adicional.

Estoy utilizando la siguiente estructura de árbol y la planificación para desarrollar un esquema de db para el siguiente.

Lo que tengo de desarrollo hasta ahora está abajo,

El problema que tengo es si busco Y, se debe generar debajo del árbol.

La lógica que estoy usando es, Y tiene dos referencias cruzadas X, Z, esos dos nodos deben estar en el diagrama y los nodos principales hasta el nodo primario inicial.

Dado que estoy usando PHP para generar este árbol usando una tabla db mysql como se muestra arriba. La estructura de la base de datos se puede cambiar. Busqué en google una estructura de árbol similar pero no pude encontrar ninguna ayuda.

Nota

No te estoy pidiendo que escribas un código para mí. Todo lo que pido es algunas pautas sobre cómo se debe hacer esto.

Encontré a continuación útil pero aún diferente a mi escenario

¿Cuál es la forma más eficiente / elegante de analizar una mesa plana en un árbol?

Cómo representar una estructura de árbol en una db

Si alguien puede decirme qué bibliotecas de php debo usar para generar el árbol y cuál es la estructura db adecuada para usar?

Permítame repetir la pregunta solo para asegurarme de que la entiendo bien. Tienes nodos y dos tipos de relaciones: flechas y líneas verticales. Luego, dado un Nodo N, desea generar un subconjunto S (N) de Nodos con las siguientes reglas recursivas:

Regla 0: N está en S (N).
Regla 1: si el nodo M está conectado con N a través de una relación vertical, también está en S (N).
Regla 2: si el nodo M está en S (N), cualquier nodo con una flecha apuntando a M también está en S (N).

El conjunto S (N) es el conjunto mínimo de Nodos que cumplen esas reglas.

El ejemplo que da con N es Y, parece confirmar estas reglas.

Sin embargo, hay otro conjunto de Reglas diferente pero (al menos para mí) más natural, donde la Regla 1 anterior se reemplaza por

Regla 1 '': Si el Nodo M está en S (N), entonces cualquier Nodo conectado con M a través de la relación vertical también está en S (N).

En la secuela, asumiré las Reglas 0,1,2 confirmadas por su ejemplo, pero se puede utilizar un enfoque similar para las Reglas 0,1 '', 2 o cualquier modificación.

También entiendo que hay un error en su tabla en la fila 7, debería ser:

7 B2 B B1,B3 (not B2,B3)

Ahora a la solución propuesta.

Primero modificaría ligeramente su estructura de tabla: como "clave" es su clave principal, la regla para una clave externa es apuntar a la clave principal de la entrada relacionada. Es decir, en su caso, reemplazaría "node_id" por "node_name" o algo así simplemente para no confundir con "id", y reemplazaría las entradas de "node_parent_id" y "cross_ref" por sus "id" s. Por ejemplo, la fila número 15 se vería así:

15 ''Y'' [13] [14,16]

Alternativamente, si prefiere por razones de legibilidad, puede usar A, B, X, Y, etc. como claves principales , siempre que sean únicas, por supuesto, entonces su tabla seguirá siendo la misma, con la excepción del campo "id" que no es necesario. Asumiré el primer caso, pero puede adaptarlo al segundo con un simple reemplazo.

Eso es todo lo que necesitas, en cuanto a la mesa.

Ahora necesita una función recursiva para generar el subgrafo S (N) para cada Nodo N. dado

Implementaré el conjunto S como conjunto de conjuntos de todos los ID de sus nodos. Luego definiré dos funciones: una para expandir el conjunto inicialmente en base a las Reglas 1,2 y la otra para expandir el conjunto posteriormente solo en base a la Regla 2.

Para simplificar, asumiré que su tabla se importa a la memoria como matriz asociativa $ filas de filas, de manera que $ rows [$ id] representa la fila con ''id'' igual a $ id como, nuevamente, matriz asociativa. Asi que

$rows[15] = array(''id''=>15, ''node_name''=>''Y'', ''node_parent_id''=>array(13), ''cross_ref''=>array(14,16) );

Aquí está el código para las funciones:

function initial_expand_set ($node_id) { global($rows); // to access the array from outside $set = array($node_id); // Rule 0 $row = $rows[$node_id]; // Get current Node $parents = $row[''node_parent_id'']; // Get parents of the Node $set = $parents ? array_merge ($set, $parents) : $set; // Join parents to the set $vert_brothers = $row[''cross_ref'']; // Get vertical relations $set = $vert_brothers ? array_merge ($set, $vert_brothers) : $set; $set = expand_set($set); // Recursive function defined below return $set; }

Y la función recursiva:

// iterate over nodes inside the set, expand each node, and merge all together function expand_set (array $set) { global($rows); $expansion = $set; // Initially $expansion is the same as $set foreach ($set as $node_id) { $row = $rows[$node_id]; // Get Node // Get the set of parents of the Node - this is our new set $parents = $row[''node_parent_id'']; // Get parents of the Node // apply the recursion $parents_expanded = expand_set($parents); // merge with previous expansion $expansion = array_merge($expansion, $parents_expanded); } // after the loop is finished getting rid of redundant entries // array_unique generates associative array, for which I only collect values $expansion = array_values( array_unique($expansion) ); return $expansion; }

Espero que funcione para ti. :)

Si necesita más detalles o explicaciones, estaré encantado de ayudarle.

PD. Para los pedantes entre los lectores, tenga en cuenta que uso el espacio antes de ''('' para la definición de la función y no hay espacio para las llamadas a la función, como lo recomienda Douglas Crokford.

Si lo comprendo correctamente, tiene una clásica estructura de tablas lógicas autorreferenciales de muchos a muchos. Esto se maneja fácilmente creando tres tablas: una para representar sus ''nodos'', otra para representar las ''asociaciones'' padre-hijo entre los nodos ''y otra para representar las relaciones entre hermanos. No estoy convencido de que deba representar las relaciones entre hermanos directamente, ya que se pueden deducir de las relaciones padre-hijo. Sin embargo, dado que no ha representado líneas de relación "verdes" para todos los hermanos, asumiré que esta es una relación "especial". Las tablas / columnas se pueden modelar de la siguiente manera:

Nodo

node_id (pk)
. . .

Node_Map

parent_id (fk a node.node_id)
child_id (fk a node.node_id)

node_sibling_map

node_id (fk a node.node_id)
sibling_id (fk to node.node_id)

Para rellenar la tabla que ha descrito en este modelo, deberá emitir lo siguiente. (citas omitidas).

insertar en los valores de nodo (node_id) (A);
insertar en los valores de nodo (node_id) (B);
insertar en los valores de nodo (node_id) (C);
insertar en los valores de nodo (node_id) (A1);
insertar en los valores de nodo (node_id) (A2);
insertar en los valores de nodo (node_id) (B1);
insertar en los valores de nodo (node_id) (B2);
insertar en los valores de nodo (node_id) (B3);
insertar en los valores de nodo (node_id) (A2B1);
insertar en los valores de nodo (node_id) (CB3);
insertar en los valores de nodo (node_id) (A2B1B2);
insertar en los valores de nodo (node_id) (X);
insertar en los valores de nodo (node_id) (Y);
insertar en los valores de nodo (node_id) (Z);
insertar en los valores de node_map (parent_id, child_id) (A, A1);
insertar en los valores de node_map (parent_id, child_id) (A, A2);
insertar en los valores de node_map (parent_id, child_id) (B, B1);
insertar en los valores de node_map (parent_id, child_id) (B, B2);
insertar en los valores de node_map (parent_id, child_id) (B, B3);
insertar en los valores de node_map (parent_id, child_id) (C, CB3);
insertar en los valores de node_map (parent_id, child_id) (A2, A2B1);
insertar en los valores de node_map (parent_id, child_id) (B1, A2B1);
insertar en los valores de node_map (parent_id, child_id) (B2, A2B1B2);
insertar en los valores de node_map (parent_id, child_id) (B3, CB3);
insertar en los valores de node_map (parent_id, child_id) (C, CB3);
insertar en los valores de node_map (parent_id, child_id) (A2B1B2, X);
insertar en los valores de node_map (parent_id, child_id) (A2B1B2, Y);
insertar en los valores de node_map (parent_id, child_id) (A2B1B2, Z);
insertar en los valores de node_sibling_map (node_id, sibling_id) (B1, B2);
insertar en los valores de node_sibling_map (node_id, sibling_id) (B2, B3);
insertar en los valores de node_sibling_map (node_id, sibling_id) (X, Y);
insertar en los valores de node_sibling_map (node_id, sibling_id) (Y, Z);

Su estructura de db no parece ser un árbol, solo es un gráfico.

Le sugiero que deseche la base de datos relacional para esta estructura y eche un vistazo a algunas bases de datos OrientDB como Neo4j , OrientDB e Infinite Graph .

Pero si está obligado a usar MySQL, puede usar FlockDB que puede usarse para atravesar el nodo de MySQL (vea la fila como nodo) pero con alguna limitación. o puede probar otro motor MySQL como OQGRAPH que proporciona un motor gráfico para MySQL y MariaDB.

esto puede ayudarte

Las estructuras jerárquicas son un lugar común para los sitios web y las bases de datos relacionales; un ejemplo popular sería el clásico "directorio web", donde los elementos se almacenan en un árbol de directorios y los usuarios hacen clic en la estructura de categorías para encontrar elementos de su interés.

Un problema clásico del diseño de directorios es cómo almacenar la relación entre categorías. Tener pares de id / parentid en una tabla es una solución simple y lo suficientemente efectiva para directorios con poca profundidad, pero ¿qué sucede con las estructuras más grandes, como el volcado de directorios DMOZ?

Algunos materiales de lectura sobre árboles SQL pueden ser de su interés si está considerando construir una jerarquía grande.

En el lado de PHP de las cosas, Kevin van Zonneveld ha creado una pequeña y agradable función explodeTree para representar datos en una matriz multidimensional.

Para evitar que este tutorial sea enorme, recomiendo leer el primer enlace en particular para familiarizarse con los por qué y por qué no usar estructuras de árbol en SQL. En el proyecto de código se pueden encontrar más lecturas a la hora de acostarse sobre conjuntos anidados y jerarquía de datos . Un ejemplo de estructuras de árbol en acción

El siguiente script generará una estructura de árbol y la almacenará en MySQL. Es bastante largo, pero debería darle una buena visualización de cómo aprovechar las estructuras de los árboles y es lo suficientemente fácil de adaptar para sus propias necesidades.

Esta primera parte de una publicación de 2 partes le brinda el script que le permite crear y almacenar estructuras de directorios. Las notas al pie de la página deben guiarlo a través de la secuencia de comandos en caso de que tenga problemas o esté interesado en hacer pequeños retoques para sus propios requisitos. La segunda publicación ofrece una GUI básica y funciones de administración para ver y alterar la estructura de árbol.

Si entiendo la jerga correctamente (puede ser un poco pesado) esta secuencia de comandos es un "recorrido de árbol de preorden" que puede generar una nueva forma de ver y extrapolar sus datos.

This method avoids recursion, you can fetch breadcrumbs for a category thats 14 levels, 20 levels or even 50 levels deep using one query. In this particular script both the parent and child categories are fetched in one query. All subcategories are methodically encapsulated within their parent nodes, and each node can give you a calculation of how many subcategories there are without any further querying Generally, for static and/or large tree structures, this structuring of your categories is advantageous for speed and ease of querying. The cost is that updates to the tree structure can be expensive, i.e. removing or adding (and sometimes editing) a node in the middle of the tree, which requires altering all records to the ''right side'' of the tree to avoid having gaps or collisions in the tree structure. In general, you want to avoid having to update a large tree often, or save the updates for one particular moment where the whole tree can be rebuilt with its updates.

Guarde y ejecute el siguiente script para generar algunos datos de ejemplo. Se supone que tiene MySQL instalado y ya ha creado una base de datos llamada "prueba". Descargue esta lista de categorías 300K (1.7MB) como datos de muestra para trabajar con

Un ejemplo de estructuras de árbol en acción

Si entiendo la jerga correctamente (puede ser un poco pesado) esta secuencia de comandos es un "recorrido de árbol de preorden" que puede generar una nueva forma de ver y extrapolar sus datos.

Guarde y ejecute el siguiente script para generar algunos datos de ejemplo. Se supone que tiene MySQL instalado y ya ha creado una base de datos llamada "prueba".

<?php // buildtree.php mysql_connect(''localhost'',''root'',''root'') or die(''Cant connect to MySQL''); mysql_select_db(''test'') or die(''Cant connect to MySQL''); /* Using the dmozregional.txt file on innvo.com, otherwise you can pass a different file or even an array Contains around 314,000 categories Will take about 40 seconds to process, ensure you have enough memory (around 200MB in this case) and roughly 10x the size of your input file in general cases */ $tree = new generate_tree(fopen(''dmozregional.txt'',''r'')); $tree->to_mysql_data(); class generate_tree { var $cats = array(); var $thiscat = array(); var $depths = array(); var $lftrgt = array(); var $depth = 0; var $inc = 0; var $catid = 0; var $fp1,$fp2; /* Run generate_tree once if your dataset is small or memory is not an issue. */ public function generate_tree(&$linearcats) { $this->depth = 0; $this->cats = array(); echo "Step 1: Gathering Data: ".date(''H:i:s'')."/n"; if(is_array($linearcats)) // Run through array { foreach($linearcats as $cat) { $this->cats[$cat] = array(); // Adding to 2 dimension list of categories with $cat as the key array_shift($linearcats); } } elseif(is_resource($linearcats)) { while(!feof($linearcats)) { if(!trim($cat = trim(fgets($linearcats)))) continue; $this->cats[$cat] = array(); // Adding to 2 dimension list of categories with $cat as the key } } if(!is_resource($this->fp1)) // 1st Pass, open files { $this->fp1 = fopen(''/tmp/tree.txt'',''w''); $this->fp2 = fopen(''/tmp/top.txt'',''w''); } echo "Step 2: Tree Structure: ".date(''H:i:s'')."/n"; $this->cats = $this->explodeTree($this->cats); echo "Step 3: Pre-Order Tree Traversal: ".date(''H:i:s'')."/n"; $this->mptt($this->cats); } /******************************** Function explodeTree with thanks to Kevin van Zonneveld info: http://kevin.vanzonneveld.net/techblog/article/convert_anything_to_tree_structures_in_php/ Altered from original version but serves largely the same purpose Example input data is same/similar as example data in the above URL ********************************/ public function explodeTree($array) { if(!is_array($array) || !count($array)) return array(); $returnArr = array(); foreach ($array as $key => $val) { // Get parent parents and the current leaf $parents = preg_split("''/''",$key,-1,PREG_SPLIT_NO_EMPTY); $leaf = array_pop($parents); // Build parent structure // Might be slow for really deep and large structures $parentArr = &$returnArr; foreach($parents as $parent) { if(!isset($parentArr[$parent])) $parentArr[$parent] = array(); elseif(!is_array($parentArr[$parent])) $parentArr[$parent] = array(); $parentArr = &$parentArr[$parent]; } // Add the final part to the structure if(empty($parentArr[$leaf])) $parentArr[$leaf] = $val; elseif(is_array($parentArr[$leaf])) $parentArr[$leaf][] = $val; } return $returnArr; } /******************************** Function mptt (modified pre-order tree traversal) Used to recursively walk through the array and provide lft and rgt values (and category depth) ********************************/ public function mptt(&$cats) { foreach($cats as $catname => $array) { $this->depths[$this->depth] = 0; $this->thiscat[$this->depth] = $catname; // Marking this depth of categories as this category $imp = implode(''/'',$this->thiscat); // Full category path $this->lftrgt[$imp] = array(++$this->inc,++$this->catid); // Assign lft if(count($array)) { ++$this->depth; // Deeper $this->mptt($array); // Reiterate } fwrite($this->fp1,$this->lftrgt[$imp][0]."/t".(++$this->inc)."/t".count($this->thiscat)."/t".$this->lftrgt[$imp][1]."/t".strtoupper(md5($imp))."/t".$catname."/n"); // $lft $rgt $depth $id $hash $name if($this->depth == 0) fwrite($this->fp2,$this->lftrgt[$imp][1]."/n"); unset($this->lftrgt[$imp]); } --$this->depth; // Shallower array_pop($this->thiscat); // Pop this category depth as we''re moving up from here } /******************************** Function mysql_data Creates schema, deletes any old data and creates indexes if not already made. Deletes temporary file data that MySQL uses to load data into tables ********************************/ public function to_mysql_data() { echo "Step 4: MySQL Schema: ".date(''H:i:s'')."/n"; // Creating DB Schema and populating with data. Deleting any old data if present mysql_query(''CREATE TABLE IF NOT EXISTS category_tree ( lft mediumint(8) unsigned NOT NULL, rgt mediumint(8) unsigned NOT NULL, depth tinyint(3) unsigned NOT NULL, id mediumint(8) unsigned NOT NULL, hash binary(16) NOT NULL, name varbinary(255) NOT NULL) ENGINE=InnoDB;'') or die(mysql_error()); mysql_query(''TRUNCATE TABLE category_tree'') or die(mysql_error()); mysql_query(''LOAD DATA INFILE /'/tmp/tree.txt/' INTO TABLE category_tree FIELDS TERMINATED BY /'/t/' (lft,rgt,depth,id,@hash,name) SET hash = UNHEX(@hash)'') or die(mysql_error()); mysql_query(''INSERT INTO category_tree (lft,rgt,depth,id) SELECT 0,MAX(rgt)+1,0,0 FROM category_tree'') or die(mysql_error()); mysql_query(''CREATE TABLE IF NOT EXISTS category_top (id MEDIUMINT(8) unsigned NOT NULL,PRIMARY KEY (id)) ENGINE=MyISAM'') or die(mysql_error()); mysql_query(''TRUNCATE TABLE category_top'') or die(mysql_error()); mysql_query(''LOAD DATA INFILE /'/tmp/top.txt/' INTO TABLE category_top FIELDS TERMINATED BY /'/t/''') or die(mysql_error()); // Delete temporary data unlink(''/tmp/tree.txt''); unlink(''/tmp/top.txt''); echo "Step 5: MySQL Indexes: ".date(''H:i:s'')."/n"; // Adding indexes for SELECT speed. Script will die appropriately here if you have already created the indexes mysql_query(''ALTER TABLE category_tree ADD PRIMARY KEY (lft,rgt,depth);'') or die(''I1 ''.mysql_error()); mysql_query(''ALTER TABLE category_tree ADD UNIQUE (id);'') or die(''I2 ''.mysql_error()); mysql_query(''ALTER TABLE category_tree ADD UNIQUE (hash);'') or die(''I3 ''.mysql_error()); } } ?>

Descripción general de la secuencia de comandos

Lines 4-5: Connect to MySQL or terminate script Line 13: Generate the tree structure. You can call this more than once if you have a large dataset. One method would be to call generate_tree() for every top level category you have so that tree sizes are limited to them. Line 14: $tree->to_mysql_data() is called at the end to write data to MySQL, after all the following events have occurred Lines 28-61: Function generate_tree, invoked when the class is initiated. - Lines 33-49: Loads the data you pass into an array, with values situated in the array keys. You can pass an array to this function or a file resource. For files, ensure there is one record per line. - Lines 52-55: On first invocation, a couple of temporary files are created for storing data deriving from the tree structure - Line 58: Calls explodeTree() which converts the array to a multi-dimensional tree array - Line 60: mptt() to create the lft, rgt and depth values in order to use our tree in MySQL. Data is written to temporary files that are then used by MySQL to populate the tables.

La estructura de su base de datos no está normalizada, ya que tiene varios identificadores tanto en node_parent_id como en cross_refer . Debe separar esta información en tablas separadas.

Entonces, tendría su tabla de nodes , más una segunda tabla para describir las relaciones padre-hijo; esta tabla tendría un ID de nodo secundario y un ID de nodo principal.

Las referencias cruzadas deben estar en una tercera tabla, que de nuevo tiene dos columnas de ID de nodo, pero hay dos formas de hacerlo, porque las referencias cruzadas son bidireccionales. Una forma es almacenar cada referencia cruzada solo una vez, lo que significa que cuando consulta la tabla, debe verificar ambas posibilidades (una referencia cruzada entre X e Y podría almacenarse con X en la primera columna e Y en la segunda columna, o al revés, así que para encontrar X tendrías que revisar ambas columnas). La otra forma es almacenar cada referencia cruzada dos veces, una para cada dirección. Esto hace que la consulta sea más simple, pero está almacenando datos redundantes y puede llevar a inconsistencias, por ejemplo, si por alguna razón se elimina una referencia pero la otra no.

Encontrar rutas con esta estructura se convierte en un asunto mucho más simple porque, además, no tiene que analizar cadenas separadas por comas, lo que es más complejo y menos eficiente.

También puede usar esto para garantizar la integridad referencial, de modo que, por ejemplo, un nodo no tenga una identificación principal que no exista realmente en la base de datos.

Para más información, investigue "normalización de base de datos". (O puede deletrearlo con una "z" si así lo desea ;-P)

Es un problema bastante complejo, con el que estás tratando. Puede valer la pena revisar los siguientes artículos:

http://www.codeproject.com/Articles/22824/A-Model-to-Represent-Directed-Acyclic-Graphs-DAG-o http://www.freepatentsonline.com/6633886.html