Erzielen Sie eine Hierarchie, eine Eltern-Kind-Beziehung auf effektive und einfache Weise

Lesezeit: 11 Minuten

Erzielen Sie eine Hierarchie eine Eltern Kind Beziehung auf effektive und einfache
Saschi Kant

Ich habe so einen Tisch

create table site
(
site_Id int(5),
parent_Id int(5),
site_desc varchar2(100)
);

Bedeutung der Felder:

  • site_Id : ID der Sites
  • parent_Id : Übergeordnete ID der Site
  • site_desc : Obwohl für die Frage nicht relevant, enthält es die Beschreibung der Site

Die Anforderung ist, dass ich, wenn ich eine site_id als Eingabe habe, alle IDs benötige, die unter der Site gekennzeichnet sind. Zum Beispiel:

                    A
                   / \
                  B   C
                / | \ /\
               D  E F G H
              /\
             I  J

Alle Knoten sind die site_Id.

Die Tabelle enthält Daten wie diese:

Site_id  | Parent_ID  |  site_desc
_________|____________|___________
 A       |   -1       |   
 B       |    A       |
 C       |    A       |
 D       |    B       |
 E       |    B       |
 F       |    B       |
 I       |    D       |
 J       |    D       |

……

A ist der Elternteil von B und C und so weiter.

Wenn B die angegebene Eingabe ist, muss die Abfrage D, E, I, F, J abrufen

Dies wird derzeit durch mehrere Abfragen in einer Schleife erreicht, aber ich dachte daran, dies mit einer minimalen Anzahl von Abfragen zu erreichen.

Was ich derzeit mache ist:

Stimme ab

Der Algorithmus geht so:

Initially create a data set object which you will populate, by fetching data from the data base. 
Create a method which takes the parent id as parameter and returns its child nodes if present, and returns -1, if it doesnt have a child. 
Step1: Fetch all the rows, which doesn't have a parent(root) node. 
Step2: Iterate through this result. For example if prod1 and prod2 are the initial returned nodes, in the resultset. 
Iterating this RS we get prod1, and we insert a row in our DataSET obj. 
Then we send the id of prod1 to getCHILD method, to get its child, and then again we iterate the returned resultset, and again call the getCHILD method, till we dont get the lowest node.

Ich brauche die beste optimierte Technik innerhalb meiner Datenmodellbeschränkung. Fühlen Sie sich frei zu antworten, wenn Sie einen Vorschlag haben.
Bitte schlagen Sie etwas vor. Vielen Dank im Voraus.

  • kann die Frage zu “IDs, die unter der Website getaggt sind” nicht verstehen

    – hjpotter92

    16. Juni 2012 um 15:56 Uhr

  • @T-ShirtDude OP bedeutet alle untergeordneten (oder untergeordneten) Websites für eine bestimmte Website.

    – Herr

    16. Juni 2012 um 16:06 Uhr

  • Im Allgemeinen sind Baummodelle in SQL “schwierig”, aber nicht unmöglich. Je nachdem, wie groß Ihr Baum ist, könnte es sein, wenn Sie diese Abfragen zur Laufzeit durchführen sehr schleppend. In der Vergangenheit habe ich Dinge auf Beilage oder Overnight-Batch vorgetaggt.

    – Sean

    16. Juni 2012 um 16:32 Uhr

  • Da MySQL keine rekursiven Abfragen unterstützt, werden Sie es schwer haben, mit diesem Design zu arbeiten. Sie sollten erwägen, Ihr Datenmodell mithilfe von verschachtelten Sätzen oder einer Abschlusstabelle zu ändern (suchen Sie nach diesen Begriffen und Sie werden jede Menge Informationen darüber finden).

    – ein Pferd ohne Name

    13. Juli 2012 um 9:57 Uhr


  • @a_horse_with_no_name: Das kann ich verstehen, aber das Ändern des Datenmodells ist bei mir nicht möglich, da dies in vielen Lösungsteams in meinem Projekt referenziert wird, und es so viel 500 Instanzen gibt, in denen diese Tabelle referiert wird, ich frage nur nach dem beste Technik, um die Ergebnismenge zu erhalten

    – Saschi Kant

    13. Juli 2012 um 10:03 Uhr

Erzielen Sie eine Hierarchie eine Eltern Kind Beziehung auf effektive und einfache
Bill Karwin

Wenn Sie das Datenmodell nicht ändern können und MySQL verwenden, stecken Sie leider in einer Situation fest, in der Sie rekursive Abfragen benötigen und ein DBMS verwenden, das keine rekursiven Abfragen unterstützt.

Quassnoi hat eine interessante Reihe von Blog-Artikeln geschrieben, die Techniken zum Abfragen hierarchischer Daten zeigen. Seine Lösungen sind ziemlich clever, aber sehr komplex.
http://explainextended.com/2009/03/17/hierarchical-queries-in-mysql/

PostgreSQL ist ein weiteres Open-Source-RDBMS, das dies tut unterstützt rekursive Abfragen, sodass Sie einen ganzen Baum abrufen könnten, der so gespeichert ist, wie Sie es zeigen. Aber wenn Sie das Datenmodell nicht ändern können, gehe ich davon aus, dass Sie nicht zu einem anderen RDBMS wechseln können.

Es gibt mehrere alternative Datenmodelle, die es viel einfacher machen, beliebig tiefe Bäume abzurufen:

  • Abschlusstabelle
  • Nested Sets, auch bekannt als Modified Preorder Tree Traversal
  • Pfadaufzählung, auch bekannt als materialisierter Pfad

Diese behandle ich in meiner Präsentation Modelle für hierarchische Daten mit SQL und PHPund in meinem Buch SQL Antipatterns: Vermeidung der Fallstricke der Datenbankprogrammierung.

Schließlich gibt es eine andere Lösung, die ich im Code für verwendet habe Schrägstrich, für ihre Kommentarhierarchien: Sie speichern “parent_id” wie in Adjacency List, aber sie speichern auch eine “root_id”-Spalte. Jedes Mitglied eines gegebenen Baums hat den gleichen Wert für root_id, der der höchste Vorgängerknoten in seinem Baum ist. Dann ist es einfach, einen ganzen Baum in einer Abfrage abzurufen:

SELECT * FROM site WHERE root_id = 123;

Dann ruft Ihre Anwendung alle Knoten aus der Datenbank in ein Array zurück, und Sie müssen den Code schreiben, um dieses Array zu durchlaufen und die Knoten in eine Baumdatenstruktur im Speicher einzufügen. Dies ist eine gute Lösung, wenn Sie viele separate Bäume haben und jeder Baum relativ wenige Einträge hat. Es ist gut für Slashdots Fall.

Erzielen Sie eine Hierarchie eine Eltern Kind Beziehung auf effektive und einfache
Zane Bien

Gestern hatte ich diese Frage beantwortet, die genau mit Ihrem von Ihnen beschriebenen Problem zusammenhängt: Aus einer gegebenen Adjazenzliste möchten Sie alle untergeordneten Knoten eines bestimmten übergeordneten Knotens erhalten – und vielleicht in einem eindimensionalen Array, über das Sie leicht iterieren können.

Sie können dies mit nur einem Aufruf der Datenbank tun, aber es gibt eine Art Haken: Sie müssen zurückkehren alle Zeilen aus der Tabelle. MySQL unterstützt keine rekursiven Abfragen, also müssen Sie stattdessen im Wesentlichen das tun SELECTim Anwendungscode eingeben.

Ich werde einfach meine Antwort wiederholen, auf die ich oben verlinkt habe, aber im Grunde genommen, wenn Sie eine Ergebnismenge (vielleicht von PDOStatement->fetchAll(PDO::FETCH_ASSOC) oder andere Methoden) im Format von etwas wie:

Array
(
    [0] => Array
    (
        [site_id] => A
        [parent_id] => -1
        [site_desc] => testtext
    )
    [1] => Array
    (
        [site_id] => B
        [parent_id] => A
        [site_desc] => testtext
    )
    [2] => Array
    (
        [site_id] => C
        [parent_id] => A
        [site_desc] => testtext
    )
    [3] => Array
    (
        [site_id] => D
        [parent_id] => B
        [site_desc] => testtext
    )
    [4] => Array
    (
        [site_id] => E
        [parent_id] => B
        [site_desc] => testtext
    )
    [5] => Array
    (
        [site_id] => F
        [parent_id] => B
        [site_desc] => testtext
    )
    [6] => Array
    (
        [site_id] => I
        [parent_id] => D
        [site_desc] => testtext
    )
    [7] => Array
    (
        [site_id] => J
        [parent_id] => D
        [site_desc] => testtext
    )
)

Sie können alle Kinder/Enkelkinder/Urenkelkinder/so weiter von allen abrufen site_id (vorausgesetzt, Sie kennen die ID) mit dieser rekursiven Funktion:

function fetch_recursive($src_arr, $id, $parentfound = false, $cats = array())
{
    foreach($src_arr as $row)
    {
        if((!$parentfound && $row['site_id'] == $id) || $row['parent_id'] == $id)
        {
            $rowdata = array();
            foreach($row as $k => $v)
                $rowdata[$k] = $v;
            $cats[] = $rowdata;
            if($row['parent_id'] == $id)
                $cats = array_merge($cats, fetch_recursive($src_arr, $row['site_id'], true));
        }
    }
    return $cats;
}

Angenommen, Sie wollten alle untergeordneten Elemente von abrufen site_id Dwürden Sie die Funktion wie folgt verwenden:

$nodelist = fetch_recursive($pdostmt->fetchAll(PDO::FETCH_ASSOC), 'D');
print_r($nodelist);

Würde ausgeben:

[0] => Array
(
    [site_id] => D
    [parent_id] => B
    [site_desc] => testtext
)
[1] => Array
(
    [site_id] => I
    [parent_id] => D
    [site_desc] => testtext
)
[2] => Array
(
    [site_id] => J
    [parent_id] => D
    [site_desc] => testtext
)

Beachten Sie, dass wir die Informationen des Elternteils zusammen mit seinen Kindern, Enkelkindern usw. beibehalten (wie tief die Verschachtelung auch geht).

  • Oder Sie können eine einzelne Abfrage schreiben, die all diese Logik kombiniert … Aber nur, wenn die Tiefe des Baums begrenzt ist.

    – Stijn de Witt

    1. Februar 2013 um 22:00 Uhr

Sehen Sie sich das verschachtelte Mengenmodell an, wenn Sie dies in einzelnen Abfragen tun möchten: http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/

Eine andere Alternative besteht darin, alle Beziehungen in eine Verknüpfungstabelle aufzunehmen. Jede Site hätte also einen Link zu ihrem Elternteil, ihrem Großelternteil usw. Jede Beziehung ist explizit. Dann fragen Sie einfach diese Verknüpfungstabelle ab, um alle Nachkommen zu erhalten.

  • Unterstützt mysql Verknüpfungsabfragen?

    – Saschi Kant

    16. Juni 2012 um 16:22 Uhr

  • @SashiKant Ich bin mir nicht sicher, was du meinst. Wenn Sie fragen, ob MySQL das Verknüpfen von Tabellen unterstützt, lautet die Antwort mit Sicherheit “Ja”, da das Verknüpfen von Tabellen oder jeder anderen Tabellenstruktur von Ihnen entworfen werden muss. Bitte lesen Sie auch den von mir bereitgestellten Link.

    – Herr

    16. Juni 2012 um 16:39 Uhr

  • Ich kann das verstehen, aber das Ändern des Datenmodells ist bei mir nicht möglich, da dies in vielen Lösungsteams in meinem Projekt referenziert wird, und es so viel 500 Instanzen gibt, in denen diese Tabelle referenziert wird, ich frage nur nach der besten Technik dazu erhalten Sie die Ergebnismenge

    – Saschi Kant

    13. Juli 2012 um 10:07 Uhr

  • @siride: Nur zur Info, deine “andere Alternative” heißt Schließung Tisch.

    – ypercubeᵀᴹ

    5. August 2012 um 0:20 Uhr

  • Sehen Sie sich die hervorragende Diashow von Bill Karwin an: Modelle für hierarchische Daten

    – ypercubeᵀᴹ

    5. August 2012 um 0:35 Uhr

Zunächst würde ich eine etwas andere Methode zum Speichern eines Baums empfehlen: Abschlusstabelle. Wenn Sie mehr darüber wissen möchten, können Sie finden SQL-Antimuster Buch recht interessant.

Das gesagt. Der einfachste Weg, meiner Meinung nach, eine solche Struktur zu erzeugen, ist folgender: http://jsbin.com/omexix/3/edit#javascript

Ich hoffe, Sie haben keine Probleme beim Lesen des JavaScript-Codes. Ich habe es verwendet, weil die Erstellung von nicht klassifizierten Objekten in JavaScript nicht so hackig aussieht. Es ist möglich, dasselbe zu implementieren, ohne auf Objekte (oder Referenzen) zu verweisen, indem Sie mehrdimensionale Arrays verwenden, aber es sieht irgendwie verwirrend aus.

Hier ist, was der Algorithmus tut:

  • wir durchlaufen die Liste der Knoten, Einmal
  • Wenn der Elternknoten des Knotens nicht existiert, wird ein Platzhalter im Array erstellt
  • Wenn der Knoten keinen Elternknoten hat, wird er in der Liste der Wurzelknoten platziert
  • Wenn der Knoten keinen Platzhalter im Array hat, wird der Platzhalter erstellt
  • Werte aus dem Knoten werden dem Platzhalter zugewiesen
  • Der Knoten wird beim übergeordneten Knoten registriert, wenn er einen übergeordneten Knoten hat

Das ist es. Grundsätzlich erzeugen Sie zwei Listen: mit allen Knoten und nur mit dem Wurzelknoten.

1646592858 55 Erzielen Sie eine Hierarchie eine Eltern Kind Beziehung auf effektive und einfache
Dan

Vielleicht möchten Sie einen Blick auf die werfen Verschlusstabelle Muster. ich habe das gefunden Seite? ˅ informativ. Soweit ich gesehen habe, gibt es auch mehrere StackOverflow-Fragen zu diesem Konzept, zB hier.

1646592858 144 Erzielen Sie eine Hierarchie eine Eltern Kind Beziehung auf effektive und einfache
ravnur

Wenn Sie Ihre nicht aktualisieren site Tabelle oft können Sie die folgende Strategie anwenden:

create table site
(
site_Id int(5),
parent_Id int(5),
site_desc varchar2(100),
parents_path varchar(X)
);

parents_path entspricht dem Pfad zum ausgewählten Knoten vom Stamm. Zum Beispiel für Blatt J es sollte sein |A|B|D|.

Vorteile: – Sie benötigen eine einzige Abfrage, um das Ergebnis zu erhalten;

Nachteile: – mehr Abfragen während Updates (aber Sie können Updates mit Bedacht durchführen);

Ich hoffe es hilft

1646592858 785 Erzielen Sie eine Hierarchie eine Eltern Kind Beziehung auf effektive und einfache
LSerni

Andere haben bereits vorgeschlagen, wie dies mit geringfügigen Änderungen an der Tabellenstruktur zu tun ist.

Wenn Sie die Struktur nicht ändern möchten (auch wenn dies am besten wäre), können Sie Folgendes tun:

  • AUSWÄHLEN * FROM site ORDER BY Parent_ID, Site_id;

Es kann in der Regel davon ausgegangen werden, dass sich einmal vergebene IDs nicht ändern; Wenn die IDs nicht gemischt werden, dh Knoten C nicht unter Knoten B verschoben wird, dann ist es wahr, dass untergeordnete Knoten immer höhere IDs als ihre Eltern haben, und die obige Sortierung garantiert, dass alle Eltern vor ihren Kindern abgerufen werden .

Das sind also die Hypothesen:

- we prefer not to change the table layout
- we never change the IDs once assigned
- we never reorder the tree, moving IDs around

Daher wird es möglich, den Baum im Speicher zu erstellen (und sogar die Abfrage selbst zu reduzieren, indem eine WHERE Site_ID >= B hinzugefügt wird).

Der erste Knoten, der durchkommt, ist B und wird in den Baum eingefügt.

Alle nachfolgenden Knoten können in ihrem Parent_ID-ten Knoten gespeichert werden, der sicher zuvor geladen wurde.

Dies würde in Python ganz gut gehen (Sie ändern direkt den übergeordneten Knoten).

Die Anfrage “Alle Nachkommen von B abrufen” kann in PHP wie folgt beantwortet werden:

$nodes  = array( $parent_id );

$cursor = SQLQuery("SELECT * FROM site WHERE Site_ID > ? "
        .  "ORDER BY Parent_ID, Site_Id ;", $parent_id);

while ($tuple = SQLFetchTuple($cursor))
    if (in_array($tuple['Parent_ID'], $nodes))
        $nodes[] = $tuple['Site_Id'];
SQLFree($cursor);

// The first node is the global parent, and may be array_shift'ed away
    // if desired.

Ein anderer Weg
ziemlich brutal

Eine andere Möglichkeit besteht darin, die “descendant_of”-Relation rekursiv in einer anderen Tabelle zu speichern:

    TRUNCATE descendants;
    INSERT INTO descendants ( node, of ) VALUES ( -1, NULL );

    INSERT INTO descendants SELECT SiteId, ParentId FROM site JOIN
           descendants ON ( site.ParentId = descendants.of );

Und wiederholen Sie die INSERTs, bis die Anzahl der eingefügten Zeilen gleich Null ist (oder die Gesamtzahl der Zeilen in den Nachkommen nicht mehr zunimmt; die Abfrage der Tabellengröße ist in den meisten DBs sehr schnell).

An diesem Punkt haben Sie alle einstufigen Beziehungen gespeichert. Jetzt:

INSERT IGNORE INTO descendants SELECT s1.node, s2.of FROM
           descendants AS s1 JOIN descendants AS s2 ON (s1.of = s2.node);

… erneut, bis die Anzahl der Nachkommen nicht mehr zunimmt (es wird eine Anzahl von Einsätzen benötigt, die der maximalen Anzahl von Ebenen entspricht). Die Gesamtzahl der JOINs ist doppelt so hoch wie die Anzahl der Ebenen.

Wenn Sie nun alle Nachkommen von Knoten 16 erhalten möchten, fragen Sie einfach ab

SELECT node FROM descendants WHERE of = 16;

958800cookie-checkErzielen Sie eine Hierarchie, eine Eltern-Kind-Beziehung auf effektive und einfache Weise

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy