Abflachungslistenhierarchie auf eine Liste aller Pfade reduzieren

Question

Ich habe eine Tabelle, in der hierarchische Informationen mithilfe des Adjazenzlistenmodells gespeichert werden. (A. Selbst verweis Schlüssel verwendet - Beispiel unten kann diese Tabelle aussehen familiar):

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 zu „glätten“ die obigen Daten in so etwas wie das?

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 eine „Pfad“ durch die Hierarchie, außer es eine Zeile für jeder Knoten (nicht nur jeder Knoten Blatt) ist. Die Spalte category_id repräsentiert den aktuellen Knoten und die Spalten "lvl" sind seine Vorfahren. Der Wert für den aktuellen Knoten muss auch in der Spalte mit der höchsten Rechten liegen. Der Wert in der Spalte lvl1 wird immer den Stammknoten darstellen, die Werte in lvl2 werden immer direkte Nachkommen von lvl1 sein und so weiter.

Wenn möglich, wäre die Methode zum Generieren dieser Ausgabe in SQL und würde für n-Tier-Hierarchien funktionieren.

Answer 1

Um mehrstufige Abfragen über eine einfache Adjazenzliste auszuführen, sind immer Self-Left-Joins erforderlich. Es ist einfach, einen rechtsbündigen Tisch 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 den Sinn:

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; 

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

Sorry, Abfragen mit beliebiger Tiefe sind im Adjazenzlistenmodell nicht möglich. Wenn Sie diese Art von Abfrage häufig durchführen, sollten Sie Ihr Schema in einen der folgenden Werte ändern: other models of storing hierarchical information: vollständige Adjazenzbeziehung (Speichern aller Vorgänger-Nachkommen-Beziehungen), materialisierter Pfad oder verschachtelte Sätze.

Wenn sich die Kategorien nicht viel bewegen (was normalerweise bei einem Geschäft wie Ihrem Beispiel der Fall ist), würde ich zu verschachtelten Mengen neigen.

Answer 2

Das Verarbeiten eines Baumes mit beliebiger Tiefe ist im Allgemeinen mit rekursivem prozeduralem Code verbunden, sofern Sie nicht die speziellen Funktionen einiger DBMS nutzen.

In Oracle ermöglicht die CONNECT BY-Klausel, dass Sie die Baumtiefe in erster Ordnung durchqueren, wenn Sie die Adjazenzliste verwenden, wie Sie es hier getan haben.

Wenn Sie verschachtelte Sätze verwenden, erhalten Sie mit der linken Folgenummer die Anweisung, die Knoten zu besuchen.

Answer 3

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

Die zweite man klingt zunächst grotesk; Speichern von IDs als String ?! Aber wenn die Ausgabe als XML oder so formatiert ist, scheint es den Leuten nicht so viel auszumachen.

Gleichermaßen ist dies von geringem Nutzen, wenn Sie dann die Ergebnisse in SQL beitreten möchten. Wenn das Ergebnis einer Anwendung bereitgestellt werden soll, kann es sehr geeignet sein. Persönlich aber ich bevorzuge die Abflachung in der Anwendung zu tun, anstatt SQL

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

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 

I haven‘ t verwendet eine rekursive WITH in einer Weile, aber ich gebe die Syntax ein, obwohl ich hier keine SQL habe, um irgendetwas 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

Eigentlich mit dynamischem SQL innerhalb eines Shops Verfahren durchgeführt werden kann. Sie werden dann darauf beschränkt, was mit der gespeicherten Prozedur geschehen kann. Offensichtlich wird es zu einer Herausforderung für EXEC, die Ergebnisse in eine temporäre Tabelle zu übertragen, ohne zu wissen, wie viele Spalten zu erwarten sind. Wenn das Ziel jedoch die Ausgabe auf einer Webseite oder einer anderen Benutzeroberfläche ist, lohnt sich der Aufwand ...