Baumstruktur in einem Statement abgrasen
0 0 
dedlfix
Baumstruktur in einem Statement abgrasen
Hallo liebes Forum,
gegeben sei eine Baumstruktur à la:
id | parent_id | eigenschaft
----+-----------+-------------
1 | NULL | ja
2 | NULL | nein
3 | 1 | NULL
4 | 3 | NULL
5 | 2 | NULL
etc. Die Urahneneltern :-) haben also eine bestimmte Eigenschaft, die ihre Kinder nicht haben.
Angenommen, ich bekomme nun den Input 4 und möchte diese Eigenschaft des Stammesvaters :-) herausfinden. Geht das irgendwie mit einem SQL-Statement?
Ich möchte vermeiden, dass ich auf Schleifen von Programmiersprachen ausweichen muss, in denen ich mich jeweils eine Generation nach oben hangele, weil ich auf SQL-Basis nach o.g. Eigenschaft filtern und ordnen möchte.
Obwohl ich glaube, dass dies eine Standardfragestellung ist, habe ich leider keine Antwort finden können.
Danke für eure Hilfe!
Peter
-
yo,
Angenommen, ich bekomme nun den Input 4 und möchte diese Eigenschaft des Stammesvaters :-) herausfinden. Geht das irgendwie mit einem SQL-Statement?
das sind rekursive konstrukte und sollten im daten-design vermieden werden, werden aber oft eingesetzt. soviel zur theorie und praxis. was deine abfrage betrifft, ja es geht über einen Selfjoin.
SELECT tab1.*, tab2.*
FROM tabelle AS tab1
LEFT JOIN tabelle AS tab2
ON (tab1.id = tab2.parent_id)
WHERE tab1.id = 4Ilja
-
Hallo Ilja,
erstmal danke für deine Antwort.
Angenommen, ich bekomme nun den Input 4 und möchte diese Eigenschaft des Stammesvaters :-) herausfinden. Geht das irgendwie mit einem SQL-Statement?
das sind rekursive konstrukte und sollten im daten-design vermieden werden, werden aber oft eingesetzt. soviel zur theorie und praxis.
Wie könnte man diese Konstrukte vermeiden?
was deine abfrage betrifft, ja es geht über einen Selfjoin.
SELECT tab1.*, tab2.*
FROM tabelle AS tab1
LEFT JOIN tabelle AS tab2
ON (tab1.id = tab2.parent_id)
WHERE tab1.id = 4Hm, entweder ich versteh's falsch, oder diese Abfrage bezieht sich nur auf eine Vater-Sohn-Generation. Das Problem ist, dass ich nicht im Voraus weiß, wieviele das jeweils sind.
Bye,
Peter-
yo,
Wie könnte man diese Konstrukte vermeiden?
in deinem fall indem man eine zusätzliche tabelle einführt, in der zwei spalten die beziehungen unter den mitarbeitern darstellen. damit ist es möglich, mitarbeiter eingeben zu können, ohne dass man vorher den vorgesetzten eingegeben haben muss. damit ist die problematik der rekursion gelöst, aber nicht die problematik der abfrage. man muss sich vor augen führen, dass die datensätze in einer tabelle eine unsortierte menge ist, es also nach keinen festen pfaden geordnet ist. es ist dem datenbank-administrator überlassen, geeignete wege dafür zu finden.
Hm, entweder ich versteh's falsch, oder diese Abfrage bezieht sich nur auf eine Vater-Sohn-Generation. Das Problem ist, dass ich nicht im Voraus weiß, wieviele das jeweils sind.
ja, die lösung bezieht sich nur darauf, eine ebene abzugreifen. anderes wäre das schwer möglich, da man für jede ebene einen selfjoin bilden muss. mal von dem aufwand und der performance abgesehen, kann man solche konstrukte eben nur rekursiv lösen, sprich es erfordert ein wenig programmieraufwand mit mehreren abfragen. rekursionen sind aber wiederum wie bereits angesprochen bei relationenalen datenbanken nicht erlaubt oder sagen wir mal nicht empfohlen.
Ilja
-
Hallo,
Wie könnte man diese Konstrukte vermeiden?
in deinem fall indem man eine zusätzliche tabelle einführt, in der zwei spalten die beziehungen unter den mitarbeitern darstellen. damit ist es möglich, mitarbeiter eingeben zu können, ohne dass man vorher den vorgesetzten eingegeben haben muss.
Das löst das Problem nicht, weil es sich um Vertragsdaten handelt. Nehmen wir einen Domainvertrag, so ist dieser einem Webhostingvertrag untergeordnet. Mitarbeiter existieren unabhängig von Vorgesetzten, Unterverträge nicht.
Bye,
Peter
-
-
-
Hallo,
das sind rekursive konstrukte und sollten im daten-design vermieden werden, werden aber oft eingesetzt.
Ich denke, dass solche Konstrukte deshalb so oft eingesetzt werden, weil es eben häufig so erforderlich ist. Dumm ist nur das das Relationale Datenbankmodell keine wirklich gute Antwort dafür bereit hat. Deshalb aber darauf zu verzichten zu sollen halte ich aber doch für zu gewagt. Wieso soll ich eine real existierende Situation vermeiden, weil die technischen Hilfsmittel ungenügend sind?
@Peter: Ich persönlich löse das Problem meist indem ich mir in jedem Datensatz die ID des Wurzel-Elements mitführe (auch wenn das der 'reine' Lehre der Redundanz-VErmeidung zuwiderläuft). Damit habe ich zumindest die Möglichkeit, mir alle Daten eines Baums mit einem Statement abzufragen, welche ich dann innerhalb des Programms weiter auswerte. das ist vielleich nicht die beste aller Lösungen[1] aber im Normalfall kann ich gut damit leben.
Grüße
Klaus[1] Oracle z.B. biete die Möglichkeit einer hierarchichen Abfrage, allerdings ist diese auch nur bedingt zielführend.
-
yo,
Deshalb aber darauf zu verzichten zu sollen halte ich aber doch für zu gewagt. Wieso soll ich eine real existierende Situation vermeiden, weil die technischen Hilfsmittel ungenügend sind?
man muss nicht auf etwas verzichten, man muss solche rekursionen nur erkennen und wenn gewollt auflösen. wie bereits beschrieben wirkt in seinem falle eine zusätzliche tabelle wunder, was die problematik der rekursion betrifft.
Ilja
-
Hallo,
man muss nicht auf etwas verzichten, man muss solche rekursionen nur erkennen und wenn gewollt auflösen. wie bereits beschrieben wirkt in seinem falle eine zusätzliche tabelle wunder, was die problematik der rekursion betrifft.
Was bietet eine zusätzliche Tabelle an Vorteilen bezüglich der Abbildung rekursiver Modelle im Vergleich zur Verwendung von selbstbezüglichen Feldern? Ok, eine zusätzliche Tabelle ist notwendig, wenn ich Graphen abbilden will, da die Knoten hier in einer n:m-Beziehung stehen, aber für Bäume, deren Knoten in einer 1:n-Beziehung stehen, halte ich eine zusätzliche Tabelle für unnötig. Im Gegenteil, wenn ich die Baum-Beziehung in einer zweiten Tabelle abbilde, muss ich durch zusätzliche Logik verhindern, dass nicht doch noch n:m-Beziehungen entstehen.[1]
Grüße
Klaus[1] unabhängig davon, dass ich bei Bäumen auch verhindern sollte, dass Schleifen entstehen.
-
Hallo,
Was bietet eine zusätzliche Tabelle an Vorteilen bezüglich der Abbildung rekursiver Modelle im Vergleich zur Verwendung von selbstbezüglichen Feldern? Ok, eine zusätzliche Tabelle ist notwendig, wenn ich Graphen abbilden will, da die Knoten hier in einer n:m-Beziehung stehen, aber für Bäume, deren Knoten in einer 1:n-Beziehung stehen, halte ich eine zusätzliche Tabelle für unnötig.
Ich hab die Datenbankdogmen ;-) nicht im Kopf, aber das widerspricht AFAIK auch einer dieser Normalformen, weil sich je genau ein Datensatz beider Tabellen auf dasselbe Realobjekt bezieht, weshalb man sie zusammenlegen sollte. Möglicherweise habe ich hier nicht den Blick für die "Vorteilstiefe", aber ich habe so das Gefühl, dass damit wirklich nichts gewonnen ist. Sollte ich falsch liegen, kannst du mich ja gerne noch mal mit der Nase draufstoßen.
Bye,
Peter -
yo,
Was bietet eine zusätzliche Tabelle an Vorteilen bezüglich der Abbildung rekursiver Modelle im Vergleich zur Verwendung von selbstbezüglichen Feldern?
n:m beziehungen sind nicht der einzige grund für eine weitere tabelle. rekursive beziehungen sind es ebenfalls. deutlich wird die problematik, wenn man mit referentieller integrität arbeitet.
wenn man nun eine person aufnehmen will, deren vorgesetzter noch nicht vorhanden ist, dann wird die aufnahme der person abgelehnt. es kann in der realität durchaus vorkommen, dass ich jemanden eingeben muss, der erst noch keinen vorgestzten hat. die zusätzliche tabelle spiegelt die realität also besser wider und löst bestimmte problematiken, die duch eine direkte rekursion entstehen würden.
Ilja
-
Hallo Ilja,
wenn man nun eine person aufnehmen will, deren vorgesetzter noch nicht vorhanden ist, dann wird die aufnahme der person abgelehnt. es kann in der realität durchaus vorkommen, dass ich jemanden eingeben muss, der erst noch keinen vorgestzten hat.
SET vorgesetzter=NULL
die zusätzliche tabelle spiegelt die realität also besser wider und löst bestimmte problematiken, die duch eine direkte rekursion entstehen würden.
Deren Lösung hast du bisher aber noch nicht angeführt.
Bye,
Peter-
yo,
Deren Lösung hast du bisher aber noch nicht angeführt.
ein weitere tabelle, bestehend aus zwei spalten, der id und der entsprechenden parent_id. wüßte nicht, warum ich diese lösung vorenthalten habe.
Ilja
-
Hallo Ilja,
Deren Lösung hast du bisher aber noch nicht angeführt.
ein weitere tabelle, bestehend aus zwei spalten, der id und der entsprechenden parent_id. wüßte nicht, warum ich diese lösung vorenthalten habe.
Du hast uns vorenthalten, weshalb das eine Lösung des Rekursionsproblems sein soll.
Bye,
Peter-
yo,
Du hast uns vorenthalten, weshalb das eine Lösung des Rekursionsproblems sein soll.
spät die erklärung, aber besser als gar keine. rekursionen machen probleme bei RDBMS, weil entweder bei direkter rekursion zeilen voneinder abhängig sind, bzw. indirekte rekursion bei zwei tabellen. diese ---> gegenseitigen <--- abhängigkeiten sind es, die probleme bereiten.
man muss sich vor augen führen, dass rekursion ein gängiges mittel in der praxis ist, also man kann nicht sagen, man darf es nicht benutzen. es eher man sollte es nicht benutzen.
sicherlich lassen sich bestimmte probleme damit lösen, indem ich zum beispiel NULL werte in bestimmten spalten zulasse. aber nicht immer geht das und es ergeben sich auch andere probleme.
probleme der direkten rekursion sind zum beispiel, wenn otto der chef von karl ist und karl der chef von otto. dann habe ich damit probleme der gegenseitigen abhängigkeit, man könnte weder karl noch otto löschen, die sich sicherlich mit wiederum extra regeln beheben lassen. aber ich muss bei solch einem daten-design immer wieder aufpassen.
ein anderes beispiel für indirekte rekursion wären fußballspieler. dabei gibt es eine tabelle spieler und eine tabelle manschaften. jeder spieler muss einer manschaft zugeordnet sein und jede manschaft hat einen kapitän. bei dieser gegensaeitigen abhängkeit der zwei tabelle habe ich nun das ei und henne problem, ich kann keinen spieler eingeben, weil es noch keine manschaft gibt. und ich kann keine manschaft eingeben, weil es noch keinen spieler gibt, der kapitän sein kann.
was macht nun eine zusätzliche tabelle ? nun, es nimmt die gegenseitige abhängigkeit raus. im beispiel der direkten rekursion mit den chefs würden die beiden ids nun in einer zusätzlichen tabelle gespeichert werden und ich könnte sie problemlos löschen, weil ja beide personen für sich nicht gelöscht werden, sondern nur die beziehung untereinander in der zusätzlichen tabelle. eine gegenseitige abhängigkeit ist somit nicht mehr möglich.
Ilja
-
Hallo Ilja,
danke für deine Antwort!
probleme der direkten rekursion sind zum beispiel, wenn otto der chef von karl ist und karl der chef von otto. dann habe ich damit probleme der gegenseitigen abhängigkeit, man könnte weder karl noch otto löschen, die sich sicherlich mit wiederum extra regeln beheben lassen. aber ich muss bei solch einem daten-design immer wieder aufpassen.
Stimmt, Rekursionen können zyklische Graphen abbilden, Nested Sets nur Bäume ...
ein anderes beispiel für indirekte rekursion wären fußballspieler. dabei gibt es eine tabelle spieler und eine tabelle manschaften. jeder spieler muss einer manschaft zugeordnet sein und jede manschaft hat einen kapitän. bei dieser gegensaeitigen abhängkeit der zwei tabelle habe ich nun das ei und henne problem, ich kann keinen spieler eingeben, weil es noch keine manschaft gibt. und ich kann keine manschaft eingeben, weil es noch keinen spieler gibt, der kapitän sein kann.
Nun ja, du musst ja Foreign Keys nicht derart exzessiv nutzen bzw. kannst das Anlegen von Mannschaft samt Kapitän in eine Transaktion packen, die eine Ausnahme für Foreign Keys erlaubt.
Bei mir könnte es ein ähnliches Problem geben, da es sich um Kunden und Verträge handelt. Nach deiner Argumentation könnte ich keinen Kunden anlegen, weil es noch keine Vertrag für ihn gibt, und umgekehrt. Die Lösung war in diesem Falle die Abstraktion von "Kunde" zu "Person", die auch unabhängig von Verträgen existieren und deshalb zuerst angelegt werden können. Personen, denen langfristig kein Vertrag zugeordnet sind, können ja potentielle Geschäftspartner o.ä. sein.
Ich habe mir mal die Sache mit den Nested Sets durchgelesen und für gut befunden. Auf Grund der Tatsache, dass es sich in meinem Falle aber nicht um tiefe, sondern bloß um viele Bäume handelt (von denen in der Regel nur einer verarbeitet werden soll), werde ich bei meinem PHP-Workaround bleiben und mit Erscheinen von MySQL 5 auf eine Stored Function ausweichen, die mit Hilfe einer Schleife dasselbe realisiert -- bloß bequem in Form von SELECT *, getMain(id) AS main FROM contract. :-)
Bye,
Peter-
Tag nochmal,
Ich habe mir mal die Sache mit den Nested Sets durchgelesen und für gut befunden. [...]
Hier wollte ich noch, falls es jemanden interessiert :-), ergänzen, dass mir die Redundanz der Informationen nicht gefällt. Berechnet man solche Werte bei Bedarf, ist der Hauptvorteil der Nested Sets aber wieder dahin.
Bye,
Peter-
yo,
Hier wollte ich noch, falls es jemanden interessiert :-), ergänzen, dass mir die Redundanz der Informationen nicht gefällt. Berechnet man solche Werte bei Bedarf, ist der Hauptvorteil der Nested Sets aber wieder dahin.
beim entwerfen von einem daten-design ist es eher selten, dass man sich vorteile ohne nachteile erkaufen kann. nimmt man zum beispiel einen index, so hilft mir dieser abfragen schneller auszuführen, macht das einfügen, ändern und löschen (also DML befehle) von daten aber problematischer. es ist halt die aufgabe des datenbank-administrators abzuwägen, was das beste ist.
Ilja
-
-
-
-
-
-
-
Hallo,
wenn man nun eine person aufnehmen will, deren vorgesetzter noch nicht vorhanden ist, dann wird die aufnahme der person abgelehnt. es kann in der realität durchaus vorkommen, dass ich jemanden eingeben muss, der erst noch keinen vorgestzten hat.
Wie kommst Du zu dieser Aussage? Ein Datenfeld, welches eine Fremdschlüssel besitzt muss nicht zwangsläufig auch NOT NULL sein. Klar, man bekommt Probleme, da man ja diese Person dann nicht von einem Wurzel-Element unterscheiden kann. Aber das gleiche Problem hast Du auch, wenn Du das ganze in eine separate Tabelle auslagerst.
die zusätzliche tabelle spiegelt die realität also besser wider und löst bestimmte problematiken, die duch eine direkte rekursion entstehen würden.
Welche Problematiken löst eine zweite Tabelle im Falle einer Baumstruktur, welche nicht auch durch die Einbindung der Struktur-Informationen in die 'Haupt'-Tabelle gelöst werden? Vielleicht habe ich da was grundlegendes übersehen, als klär mich auf.
Grüße
Klaus
-
-
-
-
Hallo Klaus,
Ich persönlich löse das Problem meist indem ich mir in jedem Datensatz die ID des Wurzel-Elements mitführe (auch wenn das der 'reine' Lehre der Redundanz-VErmeidung zuwiderläuft).
das Mitführen der Tiefe kann auch ganz hilfreich sein (ebenfalls redundant). Wenn der OP auf Schleifen in der API verzichten will, könnte er ggf. auf Stored Procedures ausweichen, falls sein DBMS diese unterstützt. Selbstverständlich sollte er die Performance beider Lösungen prüfen.
Freundliche Grüße
Vinzenz
-
Hallo Vinzenz,
das Mitführen der Tiefe kann auch ganz hilfreich sein (ebenfalls redundant). Wenn der OP auf Schleifen in der API verzichten will, könnte er ggf. auf Stored Procedures ausweichen, falls sein DBMS diese unterstützt. Selbstverständlich sollte er die Performance beider Lösungen prüfen.
Ich hatte eher an die letztere Lösung gedacht, weil diese Werte dann auch im DBMS verarbeitbar wären (Sortieren etc.). Momentan bin ich genötigt, MySQL 4.1 zu verwenden, aber MySQL 5 soll ja Stored Procedures unterstützen.
Könntest du mal, wenn du Lust hast, erklären, wie das (unabhängig vom DBMS) funktionieren würde? Danke!
Bye,
Peter
-
-
-
-
echo $begrüßung;
gegeben sei eine Baumstruktur à la:
Angenommen, ich bekomme nun den Input 4 und möchte diese Eigenschaft des Stammesvaters :-) herausfinden. Geht das irgendwie mit einem SQL-Statement?Wenn du die Tabellenstruktur ändern kannst/darfst, könntest du mal schauen, ob die das "Nested Sets"-Modell zusagt.
Das Einfügen/Löschen von Daten ist zwar aufwändiger, weil die Links-Rechts-Informationen des Baumes (sprich mehrerer bis vieler Datensätze) geändert werden müssen, jedoch bietet dieses Modell zahlreiche Möglichkeiten der Abfrage, bei der Baumteile ohne Rekursion in einer Abfrage ermittelt werden können.Normalerweise geht der Nested-Set-Baum von _einem_ Root-Objekt aus. Es ist aber auch möglich, mehrere Bäume quasi parallel zu verwalten, wenn noch ein weiteres Baumunterscheidungsmerkmal herangezogen werden kann.
Google gibt dir noch weitere Suchergebnisse (auch mit mehr Abfragebeispielen als mein obiger Link) zum Stichwort "Nested Set" aus...
Es gibt auch ein PEAR-Package namens DB_NestedSet.
echo "$verabschiedung $name";