Hierarchische Kennzeichnung in SQL

Question

Ich habe eine PHP-Webanwendung, die eine MySQL-Datenbank für das Tagging von Objekten verwendet, in der ich die Tag-Struktur verwendet habe, die als Antwort auf diese SO-Frage .

Ich möchte eine Tag-Hierarchie implementieren, bei der jedes Tag ein eindeutiges übergeordnetes Tag haben kann. Die Suche nach einem übergeordneten Tag T würde dann mit allen Nachkommen von T übereinstimmen (d. h. T, Tags, deren Elternteil T ist (Kinder von T), Enkel von T usw.).

Am einfachsten scheint es zu sein, der Tag-Tabelle ein Feld ParentID hinzuzufügen, das die ID des übergeordneten Tags eines Tags enthält, oder eine magische Zahl, wenn der Tag keinen übergeordneten Tag hat. Die Suche nach Nachkommen erfordert dann jedoch wiederholte vollständige Durchsuchungen der Datenbank, um die Tags in jeder "Generation" zu finden, was ich gerne vermeiden möchte.

Ein (vermutlich) schnellerer, aber weniger normalisierter Weg wäre eine Tabelle, die alle Kinder eines jeden Tags oder sogar alle Nachkommen eines jeden Tags enthält. Dies birgt jedoch die Gefahr inkonsistenter Daten in der Datenbank (z. B. wenn ein Tag das Kind von mehr als einem Elternteil ist).

Gibt es eine gute Möglichkeit, Abfragen zum schnellen Auffinden von Nachkommen zu machen, während die Daten so normalisiert wie möglich bleiben?

Answer 1

Ich habe es mit zwei Spalten implementiert. Ich vereinfache es hier ein wenig, weil ich den Tag-Namen in einem separaten Feld/Tabelle aufbewahren musste, weil ich ihn für verschiedene Sprachen lokalisieren musste:

• Tag
• Pfad

Sehen Sie sich zum Beispiel diese Zeilen an:

tag            path
---            ----
database       database/
mysql          database/mysql/
mysql4         database/mysql/mysql4/
mysql4-1       database/mysql/mysql4-1/
oracle         database/oracle/
sqlserver      database/sqlserver/
sqlserver2005  database/sqlserver/sqlserver2005/
sqlserver2005  database/sqlserver/sqlserver2008/

usw.

Die Verwendung des like Operator auf das Pfadfeld können Sie leicht alle benötigten Tag-Zeilen erhalten:

SELECT * FROM tags WHERE path LIKE 'database/%'

Es gibt einige Implementierungsdetails, z. B. müssen beim Verschieben eines Knotens in der Hierarchie auch alle Kinder geändert werden usw., aber das ist nicht schwer.

Vergewissern Sie sich auch, dass die Länge Ihres Pfades lang genug ist - in meinem Fall habe ich nicht den Tag-Namen für den Pfad verwendet, sondern ein anderes Feld, um sicherzustellen, dass ich keine zu langen Pfade erhalte.

Answer 2

Alis Antwort enthält einen Link zu Joe Celkos Bäume und Hierarchien in SQL für Smarties Das bestätigt meinen Verdacht, dass es keine einfache Datenbankstruktur gibt, die das Beste aus allen Welten bietet. Die beste Struktur für meine Zwecke scheint der in diesem Buch beschriebene "Frequent Insertion Tree" zu sein, der dem "Nested Set Model" aus Alis Link ähnelt, jedoch mit nicht-konsekutiver Indexierung. Dies ermöglicht O(1) Einfügungen ( a la unstrukturierte BASIC-Zeilennummerierung), wobei der Index bei Bedarf gelegentlich umstrukturiert wird.

Answer 3

Ein paar Möglichkeiten hier

Answer 4

Sie könnten eine sogenannte Hierarchy Helper Table (Hierarchie-Hilfstabelle) erstellen, wie Kimball sie nennt.

Angenommen, Ihre Hierarchie sieht so aus: A -> B | B -> C | C -> D

würden Sie Datensätze in eine Tabelle einfügen, die wie folgt aussieht

ParentID, ChildID, Depth, Highest Flag, Lowest Flag
A, A, 0, Y, N
A, B, 1, N, N
A, C, 2, N, N
A, D, 3, N, Y
B, B, 0, N, N
B, C, 1, N, N
B, D, 2, N, Y
C, C, 0, N, N
C, D, 1, N, Y
D, D, 0. N, Y

Ich glaube, ich habe das sowieso richtig..... Der Punkt ist, Sie immer noch speichern Sie Hierarchie richtig, Sie erstellen Sie einfach diese Tabelle VON Ihrer richtigen Tabelle. DIESE Tabelle lässt sich wie eine Banshee abfragen. Angenommen, Sie wollen wissen, was die erste Ebene unter B ist.

WHERE parentID = 'B' and Depth = 1

Answer 5

Ich würde eine Art von Array verwenden, um die Kinder-Tags zu speichern, dies sollte viel schneller sein als eine Tabelle auf sich selbst zu verbinden (vor allem, wenn Sie eine große Anzahl von Tags haben). Ich habe nachgeschaut, und ich kann nicht sagen, ob mysql einen nativen Array-Datentyp hat, aber Sie können dies emulieren, indem Sie eine Textspalte verwenden und ein serialisiertes Array in ihr speichern. Wenn Sie die Dinge weiter beschleunigen wollen, sollten Sie in der Lage sein, einen Textsuchindex auf diese Spalte zu setzen, um herauszufinden, welche Tags miteinander verbunden sind.

[Bearbeiten] Nach der Lektüre von Alis Artikel habe ich noch etwas weiter gesucht und Folgendes gefunden este Präsentation über eine Reihe von Ansätzen zur Implementierung von Hierarchien in Postgres. Könnte für Erklärungszwecke trotzdem hilfreich sein.