Flatten Lista de Adjacência Hierarquia a uma lista de todos os caminhos

StackOverflow https://stackoverflow.com/questions/764497

Foi útil?

Solução

Para fazer consultas multi-nível através de uma adjacência-lista simples invariavelmente envolve auto-deixou-junta. É fácil fazer uma tabela alinhado à direita: 

SELECT category.category_id,
    ancestor4.category_id AS lvl4,
    ancestor3.category_id AS lvl3,
    ancestor2.category_id AS lvl2,
    ancestor1.category_id AS lvl1
FROM categories AS category
    LEFT JOIN categories AS ancestor1 ON ancestor1.category_id=category.category_id
    LEFT JOIN categories AS ancestor2 ON ancestor2.category_id=ancestor1.parent
    LEFT JOIN categories AS ancestor3 ON ancestor3.category_id=ancestor2.parent
    LEFT JOIN categories AS ancestor4 ON ancestor4.category_id=ancestor3.parent;

Para deixou-align-lo como seu exemplo é um pouco mais complicado. Isto vem à mente: 

SELECT category.category_id,
    ancestor1.category_id AS lvl1,
    ancestor2.category_id AS lvl2,
    ancestor3.category_id AS lvl3,
    ancestor4.category_id AS lvl4
FROM categories AS category
    LEFT JOIN categories AS ancestor1 ON ancestor1.parent IS NULL
    LEFT JOIN categories AS ancestor2 ON ancestor1.category_id<>category.category_id AND ancestor2.parent=ancestor1.category_id
    LEFT JOIN categories AS ancestor3 ON ancestor2.category_id<>category.category_id AND ancestor3.parent=ancestor2.category_id
    LEFT JOIN categories AS ancestor4 ON ancestor3.category_id<>category.category_id AND ancestor4.parent=ancestor3.category_id
WHERE
    ancestor1.category_id=category.category_id OR
    ancestor2.category_id=category.category_id OR
    ancestor3.category_id=category.category_id OR
    ancestor4.category_id=category.category_id;

iria trabalhar para hierarquias n-tier.

Desculpe, consultas arbitrária de profundidade não são possíveis no modelo de lista de adjacência. Se você estiver fazendo esse tipo de consulta muito, você deve mudar seu esquema para um dos outros modelos de armazenamento de informações hierárquicas : relação de adjacência completa (armazenando todas as relações ancestral-descendente), materializado caminho ou conjuntos aninhados

.

Se as categorias não se movimentar muito (que é normalmente o caso para uma loja como seu exemplo), eu tenderia para conjuntos aninhados.

Outras dicas

Como mencionado, SQL não tem nenhuma maneira limpa para implementar tabelas com variados dinamicamente número de colunas. As apenas duas soluções que tenho usado antes são: 1. Um número fixo autojunções, dando um número fixo de colunas (como por bobince) 2. Gerar os resultados como uma corda em uma única coluna

O segundo sons um grotescas inicialmente; armazenar IDs como corda ?! Mas quando a saída é formatada como XML ou algo assim, as pessoas não parecem se importar tanto.

Igualmente, este é de pouca utilidade se você então querer juntar-se nos resultados em SQL. Se o resultado for a ser fornecido para um aplicativo, ele pode ser muito adequado. Pessoalmente, porém, eu prefiro fazer o achatamento na aplicação em vez de SQL


Eu estou preso aqui em uma tela de 10 polegadas sem acesso a SQL, então não posso dar o código testado, mas o método básico seria utilizar a recursividade de alguma forma;
- A função escalar recursiva pode fazer isso
- MS SQL pode fazer isso usando um recursiva instrução WITH (mais eficiente)

Função Escalar (algo como): 

CREATE FUNCTION getGraphWalk(@child_id INT)
RETURNS VARCHAR(4000)
AS
BEGIN

  DECLARE @graph VARCHAR(4000)

  -- This step assumes each child only has one parent
  SELECT
    @graph = dbo.getGraphWalk(parent_id)
  FROM
    mapping_table
  WHERE
    category_id = @child_id
    AND parent_id IS NOT NULL

  IF (@graph  IS NULL)
    SET @graph = CAST(@child_id AS VARCHAR(16))
  ELSE
    SET @graph = @graph + ',' + CAST(@child_id AS VARCHAR(16))

  RETURN @graph

END


SELECT
  category_id                         AS [category_id],
  dbo.getGraphWalk(category_id)       AS [graph_path]
FROM
  mapping_table
ORDER BY
  category_id

Eu não usei um recursiva COM em quando, mas vou dar a sintaxe um ir embora eu não tenho SQL aqui para testar qualquer coisa:)

recursiva COM 

WITH
  result (
    category_id,
    graph_path
  )
AS
(
  SELECT
    category_id,
    CAST(category_id AS VARCHAR(4000))
  FROM
    mapping_table
  WHERE
    parent_id IS NULL

  UNION ALL

  SELECT
    mapping_table.category_id,
    CAST(result.graph_path + ',' + CAST(mapping_table.category_id AS VARCHAR(16)) AS VARCHAR(4000))
  FROM
    result
  INNER JOIN
    mapping_table
      ON result.category_id = mapping_table.parent_id
)

SELECT
  *
FROM
  result
ORDER BY
  category_id


Editar - saída para ambos é o mesmo: 

1   '1'
2   '1,2'
3   '1,2,3'
4   '1,2,4'
5   '1,2,5'
6   '1,6'
7   '1,6,7'
8   '1,6,7,8'
9   '1,6,9'

Atravessando uma árvore de profundidade arbitrária geralmente envolve código de procedimento recursiva, a menos que você faça uso das características especiais de alguns bancos de dados.

Na Oracle, a cláusula CONNECT BY lhe permitirá percorrer a árvore em primeira ordem de profundidade, se você usar adjacência lista, como você fez aqui.

Se você usar conjuntos aninhados, o número de seqüência esquerda irá fornecer-lhe com o fim de visitar os nós.

Na verdade, pode ser feito com SQL dinâmico dentro de um procedimento lojas. Você, então, tornar-se limitado ao que pode ser feito sith o procedimento armazenado. Obviamente, torna-se um desafio para EXEC os resultados em uma tabela temporária não saber quantas colunas que esperar. No entanto, se o objetivo é a saída para uma página web ou outro UI, em seguida, pode valer a pena o esforço ...

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top