Quais são as opções para armazenar dados hierárquicos em um banco de dados relacional? [fechadas]

Boas visões gerais

De um modo geral, você está tomando uma decisão entre tempos de leitura rápidos (por exemplo, conjunto aninhado) ou tempos de gravação rápidos (lista de adjacências). Geralmente, você acaba com uma combinação das opções abaixo que melhor atendem às suas necessidades. A seguir, é apresentada uma leitura aprofundada:

• Mais uma comparação de intervalos aninhados vs. lista de adjacências : a melhor comparação que encontrei da lista de adjacências, caminho materializado, conjunto aninhado e intervalo aninhado.
• Modelos para dados hierárquicos : slides com boas explicações sobre tradeoffs e exemplos de uso
• Representando hierarquias no MySQL : visão geral muito boa do Nested Set em particular
• Dados hierárquicos em RDBMSs : conjunto de links mais abrangente e bem organizado que eu já vi, mas não muito na explicação

Opções

Conheço e tenho características gerais:

1. Lista de adjacências :
   • Colunas: ID, ParentID
   • Fácil de implementar.
   • O nó barato move, insere e exclui.
   • Caro para encontrar o nível, ascendência e descendentes, caminho
   • Evite N + 1 por meio de expressões de tabela comuns em bancos de dados que os suportam
2. Conjunto aninhado (também conhecido como Traversal de árvore de pré-encomenda modificada )
   • Colunas: Esquerda, Direita
   • Ascendência barata, descendentes
   • O(n/2)Movimentos, inserções e exclusões muito caros devido à codificação volátil
3. Tabela de ponte (também conhecida como tabela de fechamento / gatilhos w )
   • Usa tabela de junção separada com: ancestral, descendente, profundidade (opcional)
   • Ascendência e descendentes baratos
   • Escreve custos O(log n)(tamanho da subárvore) para inserção, atualizações e exclusões
   • Codificação normalizada: boa para estatísticas RDBMS e planejador de consultas em junções
   • Requer várias linhas por nó
4. Coluna de linhagem (também conhecida como caminho materializado , enumeração de caminho)
   • Coluna: linhagem (por exemplo, / pai / filho / neto / etc ...)
   • Descendentes baratos via consulta de prefixo (por exemplo LEFT(lineage, #) = '/enumerated/path')
   • Escreve custos O(log n)(tamanho da subárvore) para inserção, atualizações e exclusões
   • Não relacional: depende do tipo de dados Array ou formato de seqüência de caracteres serializada
5. Intervalos aninhados
   • Como o conjunto aninhado, mas com real / float / decimal para que a codificação não seja volátil (movimentação / inserção / exclusão de baixo custo)
   • Tem problemas reais / de flutuação / representação decimal / precisão
   • A variante de codificação da matriz adiciona a codificação ancestral (caminho materializado) para "livre", mas com a dificuldade adicional da álgebra linear.
6. Mesa plana
   • Uma lista de adjacências modificada que adiciona uma coluna de nível e classificação (por exemplo, pedido) a cada registro.
   • Barato para iterar / paginar
   • Movimentação e exclusão caras
   • Bom uso: discussão por tópicos - fóruns / comentários do blog
7. Várias colunas de linhagem
   • Colunas: uma para cada nível de linhagem, refere-se a todos os pais até a raiz, os níveis inferiores ao nível do item são definidos como NULL
   • Ancestrais baratos, descendentes, nível
   • Inserção barata, excluir, mover as folhas
   • Inserção cara, exclusão, movimentação dos nós internos
   • Limite rígido para a profundidade da hierarquia

Notas específicas do banco de dados

MySQL

• Use variáveis ​​de sessão para a lista de adjacências

Oráculo

• Use CONNECT BY para percorrer as Listas de Adjacência

PostgreSQL

• tipo de dados ltree para caminho materializado

servidor SQL

• Resumo geral
• O ano de 2008 oferece que o tipo de dados HierarchyId parece ajudar na abordagem da coluna Lineage e expandir a profundidade que pode ser representada.

Minha resposta favorita é a sugerida pela primeira frase deste tópico. Use uma lista de adjacências para manter a hierarquia e use conjuntos aninhados para consultar a hierarquia.

O problema até agora é que o método de cobertura de uma lista de adjacências para conjuntos aninhados tem sido terrivelmente lento porque a maioria das pessoas usa o método RBAR extremo conhecido como "Push Stack" para fazer a conversão e é considerado caro demais para alcançar o Nirvana da simplicidade de manutenção da Lista de Adjacências e do incrível desempenho dos Conjuntos Aninhados. Como resultado, a maioria das pessoas acaba tendo que se contentar com um ou outro, especialmente se houver mais do que, digamos, uns péssimos 100.000 nós. O uso do método push stack pode levar um dia inteiro para fazer a conversão no que os MLM'ers considerariam uma pequena hierarquia de milhões de nós.

Eu pensei em dar à Celko um pouco de concorrência criando um método para converter uma Lista de Adjacências em conjuntos aninhados em velocidades que parecem impossíveis. Aqui está o desempenho do método push stack no meu laptop i5.

Duration for     1,000 Nodes = 00:00:00:870 
Duration for    10,000 Nodes = 00:01:01:783 (70 times slower instead of just 10)
Duration for   100,000 Nodes = 00:49:59:730 (3,446 times slower instead of just 100) 
Duration for 1,000,000 Nodes = 'Didn't even try this'

E aqui está a duração do novo método (com o método push stack entre parênteses).

Duration for     1,000 Nodes = 00:00:00:053 (compared to 00:00:00:870)
Duration for    10,000 Nodes = 00:00:00:323 (compared to 00:01:01:783)
Duration for   100,000 Nodes = 00:00:03:867 (compared to 00:49:59:730)
Duration for 1,000,000 Nodes = 00:00:54:283 (compared to something like 2 days!!!)

Sim esta correto. 1 milhão de nós convertidos em menos de um minuto e 100.000 nós em menos de 4 segundos.

Você pode ler sobre o novo método e obter uma cópia do código no seguinte URL. http://www.sqlservercentral.com/articles/Hierarchy/94040/

Também desenvolvi uma hierarquia "pré-agregada" usando métodos semelhantes. Os MLM e as pessoas que fazem listas de materiais estarão particularmente interessados ​​neste artigo. http://www.sqlservercentral.com/articles/T-SQL/94570/

Se você der uma olhada em qualquer um dos artigos, vá para o link "Participar da discussão" e deixe-me saber o que você pensa.

Esta é uma resposta muito parcial à sua pergunta, mas espero que ainda seja útil.

O Microsoft SQL Server 2008 implementa dois recursos extremamente úteis para gerenciar dados hierárquicos:

• o tipo de dados HierarchyId .
• expressões de tabela comuns, usando a palavra - chave with .

Veja "Modelar suas hierarquias de dados com o SQL Server 2008", de Kent Tegels, no MSDN, para iniciar. Consulte também minha própria pergunta: Consulta recursiva da mesma tabela no SQL Server 2008

Este design ainda não foi mencionado:

Várias colunas de linhagem

Embora tenha limitações, se você pode suportá-las, é muito simples e muito eficiente. Recursos:

• Colunas: uma para cada nível de linhagem, refere-se a todos os pais até a raiz, os níveis abaixo do nível dos itens atuais são definidos como 0 (ou NULL)
• Há um limite fixo para a profundidade da hierarquia
• Ancestrais baratos, descendentes, nível
• Inserção barata, excluir, mover as folhas
• Inserção cara, exclusão, movimentação dos nós internos

Segue um exemplo - árvore taxonômica dos pássaros, de modo que a hierarquia é Classe / Ordem / Família / Gênero / Espécie - a espécie é o nível mais baixo, 1 linha = 1 táxon (que corresponde às espécies no caso dos nós das folhas):

CREATE TABLE `taxons` (
  `TaxonId` smallint(6) NOT NULL default '0',
  `ClassId` smallint(6) default NULL,
  `OrderId` smallint(6) default NULL,
  `FamilyId` smallint(6) default NULL,
  `GenusId` smallint(6) default NULL,
  `Name` varchar(150) NOT NULL default ''
);

e o exemplo dos dados:

+---------+---------+---------+----------+---------+-------------------------------+
| TaxonId | ClassId | OrderId | FamilyId | GenusId | Name                          |
+---------+---------+---------+----------+---------+-------------------------------+
|     254 |       0 |       0 |        0 |       0 | Aves                          |
|     255 |     254 |       0 |        0 |       0 | Gaviiformes                   |
|     256 |     254 |     255 |        0 |       0 | Gaviidae                      |
|     257 |     254 |     255 |      256 |       0 | Gavia                         |
|     258 |     254 |     255 |      256 |     257 | Gavia stellata                |
|     259 |     254 |     255 |      256 |     257 | Gavia arctica                 |
|     260 |     254 |     255 |      256 |     257 | Gavia immer                   |
|     261 |     254 |     255 |      256 |     257 | Gavia adamsii                 |
|     262 |     254 |       0 |        0 |       0 | Podicipediformes              |
|     263 |     254 |     262 |        0 |       0 | Podicipedidae                 |
|     264 |     254 |     262 |      263 |       0 | Tachybaptus                   |

Isso é ótimo porque, dessa maneira, você realiza todas as operações necessárias de uma maneira muito fácil, desde que as categorias internas não alterem seu nível na árvore.

Modelo de adjacência + Modelo de conjuntos aninhados

Fui a ele porque eu poderia inserir novos itens na árvore facilmente (você só precisa da identificação de um ramo para inserir um novo item) e também consultá-lo rapidamente.

+-------------+----------------------+--------+-----+-----+
| category_id | name                 | parent | lft | rgt |
+-------------+----------------------+--------+-----+-----+
|           1 | ELECTRONICS          |   NULL |   1 |  20 |
|           2 | TELEVISIONS          |      1 |   2 |   9 |
|           3 | TUBE                 |      2 |   3 |   4 |
|           4 | LCD                  |      2 |   5 |   6 |
|           5 | PLASMA               |      2 |   7 |   8 |
|           6 | PORTABLE ELECTRONICS |      1 |  10 |  19 |
|           7 | MP3 PLAYERS          |      6 |  11 |  14 |
|           8 | FLASH                |      7 |  12 |  13 |
|           9 | CD PLAYERS           |      6 |  15 |  16 |
|          10 | 2 WAY RADIOS         |      6 |  17 |  18 |
+-------------+----------------------+--------+-----+-----+

• Toda vez que você precisar de todos os filhos de qualquer pai, basta consultar a parentcoluna.
• Se você precisou de todos os descendentes de qualquer pai ou mãe, consulte itens que tenham lftentre lfte rgtdo pai.
• Se você precisou de todos os pais de qualquer nó até a raiz da árvore, consulte itens com lftmenos do que o nó lfte rgtmaiores que o nó rgte classifique-os por parent.

Eu precisava tornar o acesso e a consulta à árvore mais rápidos do que as inserções, por isso escolhi esse

O único problema é corrigir as colunas lefte rightao inserir novos itens. bem, eu criei um procedimento armazenado para ele e o chamei toda vez que inseri um novo item que era raro no meu caso, mas é muito rápido. Eu obtive a idéia do livro de Joe Celko, e o procedimento armazenado e como eu o criei são explicados aqui no DBA SE https://dba.stackexchange.com/q/89051/41481

Se o seu banco de dados suportar matrizes, você também poderá implementar uma coluna de linhagem ou caminho materializado como uma matriz de IDs pai.

Especificamente com o Postgres, você pode usar os operadores set para consultar a hierarquia e obter um excelente desempenho com os índices GIN. Isso torna a localização de pais, filhos e profundidade bastante trivial em uma única consulta. As atualizações também são bastante gerenciáveis.

Tenho uma descrição completa do uso de matrizes para caminhos materializados, se você estiver curioso.

Esta é realmente uma questão de estaca quadrada, furo redondo.

Se bancos de dados relacionais e SQL são o único martelo que você tem ou deseja usar, as respostas postadas até agora são adequadas. No entanto, por que não usar uma ferramenta projetada para lidar com dados hierárquicos? O banco de dados de gráficos é ideal para dados hierárquicos complexos.

As ineficiências do modelo relacional, juntamente com as complexidades de qualquer solução de código / consulta para mapear um modelo gráfico / hierárquico em um modelo relacional, simplesmente não compensa o esforço, quando comparado à facilidade com que uma solução de banco de dados gráfico pode resolver o mesmo problema.

Considere uma lista de materiais como uma estrutura de dados hierárquica comum.

class Component extends Vertex {
    long assetId;
    long partNumber;
    long material;
    long amount;
};

class PartOf extends Edge {
};

class AdjacentTo extends Edge {
};

Caminho mais curto entre dois subconjuntos : algoritmo transversal de gráfico simples. Caminhos aceitáveis ​​podem ser qualificados com base em critérios.

Semelhança : Qual é o grau de semelhança entre duas montagens? Execute um percurso nas duas subárvores calculando a interseção e a união das duas subárvores. O percentual semelhante é a interseção dividida pela união.

Fechamento transitivo : Percorra a subárvore e resuma o (s) campo (s) de interesse, por exemplo: "Quanto alumínio há em uma submontagem?"

Sim, você pode resolver o problema com o SQL e um banco de dados relacional. No entanto, existem abordagens muito melhores se você estiver disposto a usar a ferramenta certa para o trabalho.

Estou usando o PostgreSQL com tabelas de fechamento para minhas hierarquias. Eu tenho um procedimento armazenado universal para todo o banco de dados:

CREATE FUNCTION nomen_tree() RETURNS trigger
    LANGUAGE plpgsql
    AS $_$
DECLARE
  old_parent INTEGER;
  new_parent INTEGER;
  id_nom INTEGER;
  txt_name TEXT;
BEGIN
-- TG_ARGV[0] = name of table with entities with PARENT-CHILD relationships (TBL_ORIG)
-- TG_ARGV[1] = name of helper table with ANCESTOR, CHILD, DEPTH information (TBL_TREE)
-- TG_ARGV[2] = name of the field in TBL_ORIG which is used for the PARENT-CHILD relationship (FLD_PARENT)
    IF TG_OP = 'INSERT' THEN
    EXECUTE 'INSERT INTO ' || TG_ARGV[1] || ' (child_id,ancestor_id,depth) 
        SELECT $1.id,$1.id,0 UNION ALL
      SELECT $1.id,ancestor_id,depth+1 FROM ' || TG_ARGV[1] || ' WHERE child_id=$1.' || TG_ARGV[2] USING NEW;
    ELSE                                                           
    -- EXECUTE does not support conditional statements inside
    EXECUTE 'SELECT $1.' || TG_ARGV[2] || ',$2.' || TG_ARGV[2] INTO old_parent,new_parent USING OLD,NEW;
    IF COALESCE(old_parent,0) <> COALESCE(new_parent,0) THEN
      EXECUTE '
      -- prevent cycles in the tree
      UPDATE ' || TG_ARGV[0] || ' SET ' || TG_ARGV[2] || ' = $1.' || TG_ARGV[2]
        || ' WHERE id=$2.' || TG_ARGV[2] || ' AND EXISTS(SELECT 1 FROM '
        || TG_ARGV[1] || ' WHERE child_id=$2.' || TG_ARGV[2] || ' AND ancestor_id=$2.id);
      -- first remove edges between all old parents of node and its descendants
      DELETE FROM ' || TG_ARGV[1] || ' WHERE child_id IN
        (SELECT child_id FROM ' || TG_ARGV[1] || ' WHERE ancestor_id = $1.id)
        AND ancestor_id IN
        (SELECT ancestor_id FROM ' || TG_ARGV[1] || ' WHERE child_id = $1.id AND ancestor_id <> $1.id);
      -- then add edges for all new parents ...
      INSERT INTO ' || TG_ARGV[1] || ' (child_id,ancestor_id,depth) 
        SELECT child_id,ancestor_id,d_c+d_a FROM
        (SELECT child_id,depth AS d_c FROM ' || TG_ARGV[1] || ' WHERE ancestor_id=$2.id) AS child
        CROSS JOIN
        (SELECT ancestor_id,depth+1 AS d_a FROM ' || TG_ARGV[1] || ' WHERE child_id=$2.' 
        || TG_ARGV[2] || ') AS parent;' USING OLD, NEW;
    END IF;
  END IF;
  RETURN NULL;
END;
$_$;

Em seguida, para cada tabela em que tenho uma hierarquia, crio um gatilho

CREATE TRIGGER nomenclature_tree_tr AFTER INSERT OR UPDATE ON nomenclature FOR EACH ROW EXECUTE PROCEDURE nomen_tree('my_db.nomenclature', 'my_db.nom_helper', 'parent_id');

Para preencher uma tabela de fechamento da hierarquia existente, eu uso este procedimento armazenado:

CREATE FUNCTION rebuild_tree(tbl_base text, tbl_closure text, fld_parent text) RETURNS void
    LANGUAGE plpgsql
    AS $$
BEGIN
    EXECUTE 'TRUNCATE ' || tbl_closure || ';
    INSERT INTO ' || tbl_closure || ' (child_id,ancestor_id,depth) 
        WITH RECURSIVE tree AS
      (
        SELECT id AS child_id,id AS ancestor_id,0 AS depth FROM ' || tbl_base || '
        UNION ALL 
        SELECT t.id,ancestor_id,depth+1 FROM ' || tbl_base || ' AS t
        JOIN tree ON child_id = ' || fld_parent || '
      )
      SELECT * FROM tree;';
END;
$$;

As tabelas de fechamento são definidas com 3 colunas - ANCESTOR_ID, DESCENDANT_ID, DEPTH. É possível (e até aconselho) armazenar registros com o mesmo valor para ANCESTOR e DESCENDANT e um valor zero para DEPTH. Isso simplificará as consultas para recuperação da hierarquia. E eles são realmente muito simples:

-- get all descendants
SELECT tbl_orig.*,depth FROM tbl_closure LEFT JOIN tbl_orig ON descendant_id = tbl_orig.id WHERE ancestor_id = XXX AND depth <> 0;
-- get only direct descendants
SELECT tbl_orig.* FROM tbl_closure LEFT JOIN tbl_orig ON descendant_id = tbl_orig.id WHERE ancestor_id = XXX AND depth = 1;
-- get all ancestors
SELECT tbl_orig.* FROM tbl_closure LEFT JOIN tbl_orig ON ancestor_id = tbl_orig.id WHERE descendant_id = XXX AND depth <> 0;
-- find the deepest level of children
SELECT MAX(depth) FROM tbl_closure WHERE ancestor_id = XXX;