Flatten Adjazenzliste Hierarchie, um eine Liste aller Pfade

Question

Ich habe eine Tabelle, die hierarchischen Informationen über das Adjazenzliste Modell speichert. (Verwendet eine selbst verweis Schlüssel -. Beispiel unten kann diese Tabelle aussehen vertraut ):

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

---

Was ist die beste Methode, um die oben genannten Daten in so etwas wie dieses "abzuflachen"?

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

---

Jede Zeile ist ein „Pfad“ durch die Hierarchie, außer es gibt eine Zeile für ist jeder Knoten (nicht nur jeder Blattknoten ). Die category_id Spalte stellt den aktuellen Knoten und die „LVL“ Spalten sind seine Vorfahren. Der Wert für den aktuellen Knoten muss auch in der am weitesten rechts lvl Spalte sein. Der Wert in der Spalte lvl1 immer den Wurzelknoten repräsentiert, Werte in lvl2 immer vertreten direkte Nachkommen von lvl1, und so weiter.

Wenn möglich, das Verfahren diese Ausgabe in SQL wäre zu erzeugen und funktionieren würde für n-Tier-Hierarchien.

Answer 1

über eine einfache adjacency-Liste Multi-Level-Abfragen zu tun beinhaltet ausnahmslos selbstlinks verbindet. Es ist einfach, eine rechtsbündige Tabelle zu machen:

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;

Um linksbündig auszurichten es wie Ihr Beispiel ein wenig komplizierter ist. Dies kommt in dem Sinne:

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;

  

funktionieren würde für n-Tier-Hierarchien.

Sorry, beliebige eingehende Anfragen sind nicht möglich, in dem adjacency-Liste Modell. Wenn Sie diese Art der Abfrage eine Menge tun, sollten Sie Ihr Schema zu einer der

Answer 2

Wie bereits erwähnt, hat SQL keine saubere Möglichkeit, Tabellen zu implementieren mit dynamisch variierender Anzahl von Spalten. Die beiden einzigen Lösungen, die ich verwendet habe vor, sind: 1. Eine feste Anzahl Selbst tritt, eine feste Anzahl von Spalten geben (AS pro bobince) 2. Generieren Sie die Ergebnisse als String in einer einzigen Spalte

Die zweite klingt zunächst grotesk; Speichern von IDs als String ?! Aber, wenn die Ausgabe als XML oder etwas formatiert ist, die Leute scheinen nicht so viel zu kümmern.

Ebenso ist dies sehr wenig, wenn man dann auf den Ergebnissen in SQL beitreten möchten. Wenn das Ergebnis zu einer Anwendung zugeführt werden soll, kann es sehr geeignet sein. Persönlich aber ich ziehe die Abflachung in der Anwendung zu tun, anstatt SQL

Ich bin ohne Zugriff auf SQL hier auf einem 10-Zoll-Bildschirm geklebt, so kann ich nicht den getesteten Code geben, aber die grundlegende Methode wäre Rekursion in irgendeiner Weise zu verwenden;
- Eine rekursive Skalarfunktion kann diese
tun - MS SQL kann dies eine rekursive WITH-Anweisung (sehr effizient) mit

Scalar-Funktion (so etwas wie):

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

Ich habe eine rekursive MIT in einer Weile nicht benutzt, aber ich werde die Syntax eines selbst gehen zu geben, obwohl ich SQL nicht hier habe etwas zu testen:)

rekursive MIT

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

EDIT - OUTPUT für beide ist das gleiche:

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'

einen Baum beliebiger Tiefe Verfahrgeschwindigkeit allgemein rekursive prozeduralen Code beinhaltet, es sei denn, Sie nutzen die Besonderheiten einiger DBMS machen.

In Oracle, die CONNECT BY-Klausel ermöglicht es ihnen, den Baum in die Tiefe erster Ordnung zu durchlaufen, wenn Sie Adjazenzliste verwenden, wie Sie hier getan haben.

Wenn Sie verschachtelte Gruppen verwenden, wird die linke Sequenznummer versehen Sie mit der Reihenfolge der Knoten zu besuchen.

kann tatsächlich mit dynamischem SQL innerhalb eines Shops Verfahrens durchgeführt werden. Sie werden dann beschränkt, was kann sith der gespeicherten Prozedur durchgeführt werden. Offensichtlich wird es eine Herausforderung, die Ergebnisse in eine temporäre Tabelle exec nicht zu wissen, wie viele Spalten zu erwarten. Wenn jedoch das Ziel für die Ausgabe auf einer Webseite oder anderen UI ist, dann kann es sich lohnen die Mühe ...

Answer 3

Wie bereits erwähnt, hat SQL keine saubere Möglichkeit, Tabellen zu implementieren mit dynamisch variierender Anzahl von Spalten. Die beiden einzigen Lösungen, die ich verwendet habe vor, sind: 1. Eine feste Anzahl Selbst tritt, eine feste Anzahl von Spalten geben (AS pro bobince) 2. Generieren Sie die Ergebnisse als String in einer einzigen Spalte

Die zweite klingt zunächst grotesk; Speichern von IDs als String ?! Aber, wenn die Ausgabe als XML oder etwas formatiert ist, die Leute scheinen nicht so viel zu kümmern.

Ebenso ist dies sehr wenig, wenn man dann auf den Ergebnissen in SQL beitreten möchten. Wenn das Ergebnis zu einer Anwendung zugeführt werden soll, kann es sehr geeignet sein. Persönlich aber ich ziehe die Abflachung in der Anwendung zu tun, anstatt SQL

Ich bin ohne Zugriff auf SQL hier auf einem 10-Zoll-Bildschirm geklebt, so kann ich nicht den getesteten Code geben, aber die grundlegende Methode wäre Rekursion in irgendeiner Weise zu verwenden;
- Eine rekursive Skalarfunktion kann diese
tun - MS SQL kann dies eine rekursive WITH-Anweisung (sehr effizient) mit

Scalar-Funktion (so etwas wie):

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

Ich habe eine rekursive MIT in einer Weile nicht benutzt, aber ich werde die Syntax eines selbst gehen zu geben, obwohl ich SQL nicht hier habe etwas zu testen:)

rekursive MIT

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

EDIT - OUTPUT für beide ist das gleiche:

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 4

einen Baum beliebiger Tiefe Verfahrgeschwindigkeit allgemein rekursive prozeduralen Code beinhaltet, es sei denn, Sie nutzen die Besonderheiten einiger DBMS machen.

In Oracle, die CONNECT BY-Klausel ermöglicht es ihnen, den Baum in die Tiefe erster Ordnung zu durchlaufen, wenn Sie Adjazenzliste verwenden, wie Sie hier getan haben.

Wenn Sie verschachtelte Gruppen verwenden, wird die linke Sequenznummer versehen Sie mit der Reihenfolge der Knoten zu besuchen.

Answer 5

kann tatsächlich mit dynamischem SQL innerhalb eines Shops Verfahrens durchgeführt werden. Sie werden dann beschränkt, was kann sith der gespeicherten Prozedur durchgeführt werden. Offensichtlich wird es eine Herausforderung, die Ergebnisse in eine temporäre Tabelle exec nicht zu wissen, wie viele Spalten zu erwarten. Wenn jedoch das Ziel für die Ausgabe auf einer Webseite oder anderen UI ist, dann kann es sich lohnen die Mühe ...