nicht angemeldet
Hallo Marc,
folgendes Problem. Ich realisiere gerade eine Graphenstruktur. Dazu speichere ich in einer MySQL
welche Version von MySQL? Bei Deinem Problem ist das die entscheidende Frage - wie so oft bei Fragen zu MySQL. Die Fähigkeiten der verschiedenen MySQL-Versionen sind enorm unterschiedlich. Der vernünftigste und beste meiner Lösungsansätze setzt MySQL 5.0 voraus, unter MySQL 4.1 läuft wenig.
Tabelle jeweils die Kanten (also eine Spalte mit "Knoten1" und eine mit "Knoten2"). Nun möchte ich gerne eine Liste von Nachbarknoten für KnotenX ausgeben und gleichzeitig auszählen wieviele weitere Kanten an die jeweiligen Nachbarknoten angrenzen. Dabei soll der Graph ungerichtet sein. Also sprich wenn ich in der Tabelle eine Kante mit "Knoten1": X und "Knoten2": Y habe, dann soll sowohl von X->Y als auch X<-Y eine Kante gezählt werden.
Hier drückst Du Dich etwas unklar aus: Wird beim Anlegen von X->Y gleichzeitig auch Y->X angelegt? Wird verhindert, dass doppelte Einträge vorhanden sind? Gut, meinem Lösungsvorschlag sollte es gleichgültig sein.
Nachbarknoten von X: Knoten Y - 27 weitere Verbindungen Knoten Z - 12 weitere Verbindungen
Äh ja, ganz verstehe ich das nicht, Deine Angabe ist definitiv fehlerhaft: Entweder haben alle Nachbarknoten eine ungerade Anzahl von weiteren Verbindungen oder eine gerade Anzahl von Verbindungen. Das hängt von Deiner Definition ab.
Schauen wir uns Knoten X an: Y ist ein Nachbarknoten von X Somit gibt es die Kanten X->Y und Y->X. Y habe drei weitere Nachbarknoten A, B und C, somit gibt es sechs weitere Verbindungen von Y (2 zu A, 2 zu B und 2 zu C).
a) Wenn Du X->Y und Y->X überhaupt nicht mitzählst, muss das Ergebnis 6 sein - und immer gerade, egal für welchen Nachbarknoten. b) Zählst Du zwar X->Y nicht, dafür aber Y->X, dann ist Dein Ergebnis 7 - und immer ungerade, egal für welchen Nachbarknoten.
Bitte spezifiziere daher Deine Anforderung genauer. Gilt a) oder b)
Erschwerend kommt noch hinzu, das ich zu "Knoten X" noch weitere Informationen aus einer zweiten Tabelle mit den Knoteninfos abrufen will. Der derzeitige Befehl für den Knoten mit der ID 'X' sieht ungefähr so aus:
Das ist kein Problem.
SELECT knoten.name, [...] FROM kanten LEFT JOIN knoten ON kanten.knoten1 != 'X' AND kanten.knoten1 = knoten.ID OR kanten.knoten2 != 'X' AND kanten.knoten2 = knoten.ID WHERE kanten.knoten1 = 'X' OR kanten.knoten2 = 'X';
Auch wenn ich Cruz weitgehend nicht zustimme, so hat er recht, dass Dein JOIN ungünstig gewählt ist.
Kann ich das auszählen der Verbindungen der Nachbarknoten noch irgendwie in der Abfrage realisieren
Ja, Du kannst das in einer Abfrage realisieren, wenn Deine MySQL-Version dies zuläßt.
oder muss ich das extra machen?
Gegebenenfalls musst Du das Problem in der Anwendung lösen, wenn Deine MySQL-Version Dir nicht das zur Verfügung stellt, was Du brauchst.
Genug Vorgeplänkel - ein paar Lösungshinweise:
Aufgabe 1: Ermittle die Liste der Nachbarknoten Anmerkung: Statt des Knotennamens verwende ich die ID des Knotens, die Erweiterung auf den Knotennamen erfordert einen INNER JOIN.
Mit
/*
Teil 1:
Betrachteter Knoten ist in kanten.knoten1 zu finden,
die Nachbarn stehen somit in kanten.knoten2
*/
SELECT
k3.knoten2 nbk
FROM kanten k3
WHERE k3.knoten1 = 1
UNION
/*
Teil 2:
Betrachteter Knoten ist in kanten.knoten2 zu finden,
die Nachbarn stehen somit in kanten.knoten1
*/
SELECT
k4.knoten1
FROM kanten k4
WHERE k4.knoten2 = 1
/*
Hinweis:
UNION filtert standardmäßig doppelte Einträge aus,
somit werden X->Y und Y->X im Ergebnis nur einmal
auftreten.
*/
ermittelst Du die Liste der Nachbarknotens des Knotens mit der ID 1. Schöner als Dein JOIN, wahrscheinlich performanter als Dein JOIN.
Du möchtest Details zu Deinem Knoten, kein Problem: Entweder Du joinst innerhalb der beiden SELECT-Anweisungen (geht immer bei v4.0 und größer, doppelter SQL-Code) oder Du verwendest ein Subselect (benötigt MySQL v4.1 und neuer, einfacher SQL-Code). Um herauszufinden, welche Version performanter ist, nutze EXPLAIN:
Hier Beispielcode mit Subquery - nachträglich eingefügt - bitte lies die Kommentare weiter unten :-)
SELECT
K1.name ak_name, -- Ausgangsknoten
NB.knt,
K2.name nb_name, -- Nachbarknoten
NB.nbk Nachbar
FROM ( -- Version mit Subquery
SELECT
k3.knoten2 knt,
k3.knoten1 nbk
FROM kanten k3
WHERE k3.knoten2 = 1
UNION
SELECT
k4.knoten1,
k4.knoten2
FROM kanten k4
WHERE k4.knoten1 = 1 ) NB -- Tabellenalias erforderlich, s.u.
INNER JOIN Knoten K1
ON NB.knt = K1.ID
INNER JOIN Knoten K2
ON NB.nbk = K2.ID
liefert Dir Details über Deine Knoten aus der Tabelle knoten. Wie Du an weitere Details kommen kannst, sollte klar sein.
Aufgabe 2: Ermittle die Anzahl der Nachbarknoten aller Knoten Aufbauend auf Aufgabe 1 kann man mit Subqueries die Anzahl der Nachbarn aller Knoten bestimmen. Subqueries werden erst ab MySQL-Version 4.1 unterstützt.
Um die Anzahl der Nachbarn zu haben, benötigen wir zunächst alle existierenden Kanten, d.h. neben dem Nachbarknoten auch den Ausgangsknoten selbst.
Wie vorhin vereinigen wir die beiden Mengen miteinander, d.h. der Ausgangsknoten kann einmal in kanten.knoten1 und das andere Mal in kanten.knoten2 stehen.
SELECT
k1.knoten1 KA, -- Ausgangsknoten
k1.knoten2 KN -- Nachbarknoten
FROM kanten k1
UNION
SELECT
k2.knoten2,
k2.knoten1
FROM kanten k2
Wollen wir nun zählen, wieviele Nachbarknoten es gibt, so müssen wir nur zählen, wie oft ein Ausgangsknoten in dieser Menge vorkommt. D.h. wir verwenden das Ergebnis dieser Abfrage als "Tabelle", die befragt wird:
SELECT
KL.KA knoten, -- Für jeden Ausgangsknoten
COUNT(KL.KA) anzahl -- zähle, wie oft er vorkommt
-- soviele Nachbarknoten müssen existieren :-)
FROM (
SELECT
k1.knoten1 K1,
k1.knoten2 K2
FROM kanten k1
UNION
SELECT
k2.knoten2,
k2.knoten1
FROM kanten k2) KL -- Beachte: Aliasname ist hier vorgeschrieben,
-- siehe [Handbuch](http://dev.mysql.com/doc/refman/5.0/en/unnamed-views.html)
Die Anzahl der weiteren Verbindungen berechnet sich aus der Anzahl der Nachbarknoten je nach Deiner Definition:
Entweder: weitere_Verbindungen = 2 * Anzahl - 1 oder weitere_Verbindungen = 2 * Anzahl - 2
Wie geht es weiter: Das hängt wiederum von Deiner MySQL-Version ab :-) Während UNION in einem Subselect kein Problem ist, stellen Aggregatsfunktionen durchaus eines dar. Du kannst (nach meinem Wissen und meinen Versuchen mit MySQL 4.1.x) nicht auf das Ergebnis von Aufgabe 2 als unbenannter View zugreifen - und um das Gesamtergebnis in einem Schritt zu bekommen, benötigst Du einen View. Views gibt es aber erst ab MySQL-Version 5.0, Du siehst wieder die Abhängigkeiten. Mit MySQL 4.1 kannst Du wie folgt vorgehen:
-
Speichere das Ergebnis von Aufgabe 2 in einer temporären Tabelle, d.h. erstelle diese zunächst mit CREATE TEMPORARY TABLE, fülle sie dann mit INSERT ... SELECT.
-
Joine das Ergebnis von Aufgabe 1 mit der temporären Tabelle. Ich würde die WHERE-Klausel, mit der Du Deine Datensätze einschränkst (Aufgabe 1), erst hier einsetzen.
-
Nach Auswertung lösche die temporäre Tabelle.
Damit ist Dein Problem gelöst.
- MySQL 5.0: Statt einer temporären Tabelle erstelle einmal einen View mit dem Statement aus Aufgabe 2. Greife auf diesen View wie eine Tabelle zu. D.h. dieser Schritt ist ein einziges Mal vorzunehmen.
[CREATE VIEW](http://dev.mysql.com/doc/refman/5.0/en/create-view.html) vw_nachbarn AS
SELECT
KL.KA knoten, -- Für jeden Ausgangsknoten
COUNT(KL.KA) anzahl -- zähle, wie oft er vorkommt
-- soviele Nachbarknoten müssen existieren :-)
FROM (
SELECT
k1.knoten1 K1,
k1.knoten2 K2
FROM kanten k1
UNION
SELECT
k2.knoten2,
k2.knoten1
FROM kanten k2) KL
Erstelle ein SELECT-Statement, in dem Du das Statement aus Aufgabe 1 mit dem View joinst (hier mit Fall b)):
SELECT
k1.name ak_name, -- Ausgangsknoten
nb.knt, -- ID des Ausgangsknotens
-- wegen WHERE-Klausel nur 1 möglich
k2.name nb_name, -- Nachbarknoten
nb.nbk Nachbar,
2 * vwn.Anzahl - 1 AS Verbindungen -- Berechnung nach b)
FROM (
SELECT
k3.knoten2 knt,
k3.knoten1 nbk
FROM kanten k3
WHERE k3.knoten2 = 1
UNION
SELECT
k4.knoten1,
k4.knoten2
FROM kanten k4
WHERE k4.knoten1 = 1 ) nb
INNER JOIN Knoten k1
ON nb.knt = k1.ID
INNER JOIN Knoten k2
ON nb.nbk = k2.ID
INNER JOIN vw_nachbarn vwn
ON nb.nbk = vwn.Knoten
Weiter vereinfachen lässt sich das Statement, indem Du auch aus Aufgabe 1 einen View erzeugst - und die WHERE-Klausel, sowie die Knotendetails erst in das endgültige Statement packst:
Erzeuge die Liste der Nachbarknoten (aller Knoten)
CREATE VIEW vw_nachbarliste AS
SELECT
k1.knoten2 knt,
k1.knoten1 nbk
FROM kanten k1
UNION
SELECT
k2.knoten1,
k2.knoten2
FROM kanten k2
Damit ergibt sich eine übersichtliche Lösung mit
SELECT
k1.name ak_name, -- Ausgangsknoten
-- weitere Details nach Bedarf
nbl.knt ausgangsknoten, -- ID des Ausgangsknotens
k2.name nb_name, -- Nachbarknoten
-- auch hier weitere Spalten möglich
nbl.nbk nachbarknoten,
2 * vwn.Anzahl - 1 AS Verbindungen -- Berechnung nach b)
FROM vw_nachbarliste nbl
INNER JOIN Knoten k1
ON nbl.knt = k1.ID
INNER JOIN Knoten k2
ON nbl.nbk = k2.ID
INNER JOIN vw_nachbarn vwn
ON nbl.nbk = vwn.Knoten
WHERE k1.name = 'X' -- mit einfacher WHERE-Klausel
-- wobei mir die ID in der WHERE-Klausel lieber wäre, da mutmaßlich
-- performanter. Was Du verwenden kannst, ergibt sich allerdings aus
-- Deiner Anwendung.
Du siehst, wie der Einsatz von Views zu übersichtlicherem und verständlicherem SQL-Code führt, der außerdem die von Dir gewünschte Lösung in einer einzigen Query ermöglicht, somit die Programmierung in der API enorm vereinfacht. Wahrscheinlich ist das resultierende Statement zusätzlich noch performanter als das Absetzen von Einzelabfragen in der API. Das hieße: nur Vorteile, keinerlei Nachteile. Die Entscheidung sollte Dir leicht fallen.
Die Performance prüfst Du erneut mit EXPLAIN. Vergiß nicht, dass die den Views zugrundeliegenden Abfragen bei der Ausführung ebenfalls ausgeführt werden müssen - und eventuell nicht performant sind. Optimiere nach Bedarf.
Da die Aufgabe so lösbar ist, dass Du nicht in einer Schleife Queries absetzen musst, solltest Du diese auch so lösen. In der API resultiert (insbesondere aus der Version mit dem expliziten View unter MySQL 5.0 und höher) einfacher, leicht zu lesender und verständlicher Code - und entspricht damit dem Anliegen von Cruz. Views helfen, SQL-Code einfach und damit verständlich zu halten. Dennoch sollte man die Performance mit EXPLAIN überprüfen.
Im Augenblick habe ich keine 5.x-Version von MySQL greifbar, dennoch sollten die Statements weitgehend fehlerfrei sein. Die Versionen für 4.x sind getestet :-)
Grundsätzlich ist Dein Problem wunderschön geeignet, um die enormen Fortschritte von MySQL von Version zu Version zu demonstrieren.
Freundliche Grüße
Vinzenz