Appiattire adiacenza Lista gerarchia per un elenco di tutti i percorsi

Question

Ho una tabella che memorizza le informazioni gerarchico utilizzando il modello di adiacenza List. (Utilizza una chiave autoreferenziale -. Questo esempio seguente tabella può sembrare familiare ):

category_id name                 parent
----------- -------------------- -----------
1           ELECTRONICS          NULL
2           TELEVISIONS          1
3           TUBE                 2
4           LCD                  2
5           PLASMA               2
6           PORTABLE ELECTRONICS 1
7           MP3 PLAYERS          6
8           FLASH                7
9           CD PLAYERS           6
10          2 WAY RADIOS         6

---

Qual è il metodo migliore per "appiattire" i dati di cui sopra in qualcosa di simile?

category_id lvl1        lvl2        lvl3        lvl4
----------- ----------- ----------- ----------- -----------
1           1           NULL        NULL        NULL
2           1           2           NULL        NULL
6           1           6           NULL        NULL
3           1           2           3           NULL
4           1           2           4           NULL
5           1           2           5           NULL
7           1           6           7           NULL
9           1           6           9           NULL
10          1           6           10          NULL
8           1           6           7           8

---

Ogni riga è un "percorso" attraverso la Gerarchia, tranne c'è una riga per ogni nodo (non solo ogni nodo foglia ). La colonna category_id rappresenta il nodo corrente e le colonne "LVL" sono i suoi antenati. Il valore per il nodo corrente deve essere nella colonna di destra lvl più lontano. Il valore nella colonna lvl1 sempre rappresentare il nodo radice, valori in lvl2 rappresenterà sempre diretti discendenti di lvl1, e così via.

Se possibile il metodo per generare questo risultato sarebbe in SQL, e avrebbe lavorato per le gerarchie n-tier.

Answer 1

Per fare query multi-livello attraverso una semplice liste di adiacenza coinvolge invariabilmente auto-sinistra-join. E 'facile fare un tavolo allineato a destra:

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;

Per sinistra allinearlo come il vostro esempio è un po 'più complicato. Questo viene in 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;

  

avrebbe funzionato per le gerarchie n-tier.

Siamo spiacenti, query arbitrarie-profondità non sono possibili nel modello con liste di adiacenza. Se stai facendo questo tipo di interrogazione molto, è necessario modificare lo schema ad uno dei altri modelli di memorizzazione di informazioni gerarchiche :. piena relazione di adiacenza (la memorizzazione di tutti i rapporti antenato-discendente), il percorso, o insiemi nidificati materializzato

Se le categorie non si muovono in giro un sacco (che di solito è il caso di un negozio come tuo esempio), vorrei tendere set nidificati.

Answer 2

Come già detto, SQL non ha modo pulito per implementare le tabelle con diversi dinamicamente il numero di colonne. Le uniche due soluzioni che ho usato prima sono: 1. Un numero fisso self-join, dando un numero fisso di colonne (AS per BobInce) 2. Generare i risultati come una stringa in una singola colonna

La seconda suona grottesca inizialmente; memorizzare gli ID come stringa ?! Ma quando l'uscita è formattato in formato XML o qualcosa del genere, la gente non sembrano in mente così tanto.

Allo stesso modo, questo è di poca utilità se poi si desidera unire i risultati in SQL. Se il risultato è da fornire a un'applicazione, può essere molto adatto. Personalmente, però, preferisco fare l'appiattimento nella domanda piuttosto che SQL

Sono bloccato qui su uno schermo da 10 pollici che non hanno accesso a SQL, quindi non posso dare il codice testato, ma il metodo di base sarebbe quella di utilizzare la ricorsione in qualche modo;
- Una funzione scalare ricorsiva può fare questo
- MS SQL può farlo utilizzando un ricorsiva con un comunicato (bassi consumi)

funzione scalare (qualcosa di simile):

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

Non ho usato un ricorsiva CON in un po ', ma io darò la sintassi un andare, anche se non ho SQL qui per provare qualcosa:)

ricorsiva con un

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

Modifica - USCITA per entrambi è la stessa:

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'

Answer 3

Movimento di un albero di profondità arbitraria generalmente coinvolge codice di procedura ricorsiva, a meno che non si fanno uso delle peculiarità di alcuni DBMS.

In Oracle, la clausola CONNECT BY vi permetterà di attraversare l'albero in modo approfondito primo ordine se si utilizza lista di adiacenza, come avete fatto qui.

Se si utilizzano gli insiemi nidificati, il numero di sequenza sinistra vi fornirà l'ordine di visitare i nodi.

Answer 4

In realtà può essere fatto con SQL dinamico all'interno di una procedura di negozi. È quindi diventa limitata a ciò che può essere fatto sith la stored procedure. Ovviamente diventa una sfida a exec i risultati in una tabella temporanea senza sapere quante colonne aspettarsi. Tuttavia, se l'obiettivo è quello di uscita a una pagina web o un altro utente allora può essere vale la pena ...