Ok, eu escrevi classes PHP que estendem as classes de tabela, linha e conjunto de linhas do Zend Framework DB. Estou desenvolvendo isso de qualquer maneira porque estou falando em PHP Tek-X em algumas semanas sobre modelos de dados hierárquicos.
Não quero postar todo o meu código no Stack Overflow porque eles são licenciados implicitamente sob Creative Commons se eu fizer isso. atualizar: Enviei meu código para a incubadora de extras do Zend Framework e minha apresentação é Modelos para dados hierárquicos com SQL e PHP no slideshare.
Vou descrever a solução em pseudocódigo. Estou usando a taxonomia zoológica como dados de teste, baixados de ITIS.gov . A tabela é
longnames :CREATE TABLE `longnames` (
`tsn` int(11) NOT NULL,
`completename` varchar(164) NOT NULL,
PRIMARY KEY (`tsn`),
KEY `tsn` (`tsn`,`completename`)
)
Criei uma tabela de fechamento para os caminhos na hierarquia da taxonomia:
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 a chave primária de um nó, você pode obter todos os seus descendentes desta maneira:
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;
A junção para
closure AS p é incluir o id pai de cada nó. A consulta faz um bom uso dos í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 | |
+----+-------------+-------+--------+---------------+---------+---------+----------+------+-----------------------------+
E dado que tenho 490.032 linhas em
longnames e 4.299.883 linhas em closure , ele é executado em um bom tempo:+--------------------+----------+
| 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 |
+--------------------+----------+
Agora eu pós-processo o resultado da consulta SQL acima, classificando as linhas em subconjuntos de acordo com a hierarquia (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;
Também defino classes para Rows e Rowsets. Um Rowset é basicamente um array de linhas. Uma Row contém uma matriz associativa de dados de linha e também contém um Rowset para seus filhos. O Rowset filho para um nó folha está vazio.
Rows e Rowsets também definem métodos chamados
toArrayDeep() que despejam seu conteúdo de dados recursivamente como uma matriz simples. Então eu posso usar todo o sistema junto assim:
// 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());
A saída é a seguinte:
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',
),
),
),
),
)
Re seu comentário sobre o cálculo da profundidade - ou realmente o comprimento de cada caminho.
Supondo que você acabou de inserir um novo nó em sua tabela que contém os nós reais (
longnames no exemplo acima), o id do novo nó é retornado por LAST_INSERT_ID() no MySQL ou então você pode obtê-lo de alguma forma. 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;
