De acuerdo, he escrito clases de PHP que amplían las clases de tablas, filas y conjuntos de filas de Zend Framework DB. He estado desarrollando esto de todos modos porque estoy hablando en PHP Tek-X en un par de semanas sobre modelos de datos jerárquicos.
No quiero publicar todo mi código en Stack Overflow porque implícitamente obtienen una licencia de Creative Commons si lo hago. actualización: Envié mi código a la incubadora de extras de Zend Framework y mi presentación es Modelos para datos jerárquicos con SQL y PHP en slideshare.
Describiré la solución en pseudocódigo. Estoy usando taxonomía zoológica como datos de prueba, descargados de ITIS.gov
. La tabla es longnames :
CREATE TABLE `longnames` (
`tsn` int(11) NOT NULL,
`completename` varchar(164) NOT NULL,
PRIMARY KEY (`tsn`),
KEY `tsn` (`tsn`,`completename`)
)
He creado una tabla de cierre para las rutas en la jerarquía de taxonomía:
CREATE TABLE `closure` (
`a` int(11) NOT NULL DEFAULT '0', -- ancestor
`d` int(11) NOT NULL DEFAULT '0', -- descendant
`l` tinyint(3) unsigned NOT NULL, -- levels between a and d
PRIMARY KEY (`a`,`d`),
CONSTRAINT `closure_ibfk_1` FOREIGN KEY (`a`) REFERENCES `longnames` (`tsn`),
CONSTRAINT `closure_ibfk_2` FOREIGN KEY (`d`) REFERENCES `longnames` (`tsn`)
)
Dada la clave principal de un nodo, puede obtener todos sus descendientes de esta manera:
SELECT d.*, p.a AS `_parent`
FROM longnames AS a
JOIN closure AS c ON (c.a = a.tsn)
JOIN longnames AS d ON (c.d = d.tsn)
LEFT OUTER JOIN closure AS p ON (p.d = d.tsn AND p.l = 1)
WHERE a.tsn = ? AND c.l <= ?
ORDER BY c.l;
La unión a closure AS p es incluir la identificación principal de cada nodo.
La consulta hace un buen uso de los índices:
+----+-------------+-------+--------+---------------+---------+---------+----------+------+-----------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-------+--------+---------------+---------+---------+----------+------+-----------------------------+
| 1 | SIMPLE | a | const | PRIMARY,tsn | PRIMARY | 4 | const | 1 | Using index; Using filesort |
| 1 | SIMPLE | c | ref | PRIMARY,d | PRIMARY | 4 | const | 5346 | Using where |
| 1 | SIMPLE | d | eq_ref | PRIMARY,tsn | PRIMARY | 4 | itis.c.d | 1 | |
| 1 | SIMPLE | p | ref | d | d | 4 | itis.c.d | 3 | |
+----+-------------+-------+--------+---------------+---------+---------+----------+------+-----------------------------+
Y dado que tengo 490.032 filas en longnames y 4.299.883 filas en closure , se ejecuta en muy buen tiempo:
+--------------------+----------+
| Status | Duration |
+--------------------+----------+
| starting | 0.000257 |
| Opening tables | 0.000028 |
| System lock | 0.000009 |
| Table lock | 0.000013 |
| init | 0.000048 |
| optimizing | 0.000032 |
| statistics | 0.000142 |
| preparing | 0.000048 |
| executing | 0.000008 |
| Sorting result | 0.034102 |
| Sending data | 0.001300 |
| end | 0.000018 |
| query end | 0.000005 |
| freeing items | 0.012191 |
| logging slow query | 0.000008 |
| cleaning up | 0.000007 |
+--------------------+----------+
Ahora postproceso el resultado de la consulta SQL anterior, clasificando las filas en subconjuntos de acuerdo con la jerarquía (pseudocódigo):
while ($rowData = fetch()) {
$row = new RowObject($rowData);
$nodes[$row["tsn"]] = $row;
if (array_key_exists($row["_parent"], $nodes)) {
$nodes[$row["_parent"]]->addChildRow($row);
} else {
$top = $row;
}
}
return $top;
También defino clases para filas y conjuntos de filas. Un Rowset es básicamente una matriz de filas. Una fila contiene una matriz asociativa de datos de fila y también contiene un conjunto de filas para sus elementos secundarios. El conjunto de filas secundario para un nodo hoja está vacío.
Rows y Rowsets también definen métodos llamados toArrayDeep() que vuelcan su contenido de datos recursivamente como una matriz simple.
Entonces puedo usar todo el sistema junto así:
// Get an instance of the taxonomy table data gateway
$tax = new Taxonomy();
// query tree starting at Rodentia (id 180130), to a depth of 2
$tree = $tax->fetchTree(180130, 2);
// dump out the array
var_export($tree->toArrayDeep());
La salida es la siguiente:
array (
'tsn' => '180130',
'completename' => 'Rodentia',
'_parent' => '179925',
'_children' =>
array (
0 =>
array (
'tsn' => '584569',
'completename' => 'Hystricognatha',
'_parent' => '180130',
'_children' =>
array (
0 =>
array (
'tsn' => '552299',
'completename' => 'Hystricognathi',
'_parent' => '584569',
),
),
),
1 =>
array (
'tsn' => '180134',
'completename' => 'Sciuromorpha',
'_parent' => '180130',
'_children' =>
array (
0 =>
array (
'tsn' => '180210',
'completename' => 'Castoridae',
'_parent' => '180134',
),
1 =>
array (
'tsn' => '180135',
'completename' => 'Sciuridae',
'_parent' => '180134',
),
2 =>
array (
'tsn' => '180131',
'completename' => 'Aplodontiidae',
'_parent' => '180134',
),
),
),
2 =>
array (
'tsn' => '573166',
'completename' => 'Anomaluromorpha',
'_parent' => '180130',
'_children' =>
array (
0 =>
array (
'tsn' => '573168',
'completename' => 'Anomaluridae',
'_parent' => '573166',
),
1 =>
array (
'tsn' => '573169',
'completename' => 'Pedetidae',
'_parent' => '573166',
),
),
),
3 =>
array (
'tsn' => '180273',
'completename' => 'Myomorpha',
'_parent' => '180130',
'_children' =>
array (
0 =>
array (
'tsn' => '180399',
'completename' => 'Dipodidae',
'_parent' => '180273',
),
1 =>
array (
'tsn' => '180360',
'completename' => 'Muridae',
'_parent' => '180273',
),
2 =>
array (
'tsn' => '180231',
'completename' => 'Heteromyidae',
'_parent' => '180273',
),
3 =>
array (
'tsn' => '180213',
'completename' => 'Geomyidae',
'_parent' => '180273',
),
4 =>
array (
'tsn' => '584940',
'completename' => 'Myoxidae',
'_parent' => '180273',
),
),
),
4 =>
array (
'tsn' => '573167',
'completename' => 'Sciuravida',
'_parent' => '180130',
'_children' =>
array (
0 =>
array (
'tsn' => '573170',
'completename' => 'Ctenodactylidae',
'_parent' => '573167',
),
),
),
),
)
Vuelve a tu comentario sobre cómo calcular la profundidad, o realmente la longitud de cada camino.
Suponiendo que acaba de insertar un nuevo nodo en su tabla que contiene los nodos reales (longnames en el ejemplo anterior), la identificación del nuevo nodo es devuelta por LAST_INSERT_ID() en MySQL o puede obtenerlo de alguna manera.
INSERT INTO Closure (a, d, l)
SELECT a, LAST_INSERT_ID(), l+1 FROM Closure
WHERE d = 5 -- the intended parent of your new node
UNION ALL SELECT LAST_INSERT_ID(), LAST_INSERT_ID(), 0;
