[pepe24]

Hallo,

ich wollte mal nachfragen, ob sich einer von Euch vllt. schon einmal mit so etwas beschäftigt hat. Ich will nicht die zehntausendste Community aufmachen, mich interessiert allerdings die Theorie dieser SQL-Abfrage.

Man hat bei einer solchen Abfrage ja einen Startknoten (ich) und einen Zielknoten (Person, die man über 3 Ecken kennt). Der in diesem Kontext angepriesene Algorithmus von http://de.wikipedia.org/wiki/Dijkstra-Algorithmus hilft hier meines Erachtens nur bei der Optimierung der Suchanfrage dieser Kette aber noch nicht bei der gesuchten Grundidee.

Meine Idee wäre ein Nested Set Model des Anfangsknotens, respektive des
Zielknotens anzufertigen. Sobald ein Datensatz der entstandenen Datenbäume des Anfangs- und Zielknotens überein stimmen, hat man eine Verbindung. Das ist aber wahrscheinlich wenig performant und auch wenig flexibel.

Über eine Diskussion würde ich mich freuen.
Gruß,

pepe

[Ben]

Hallo,
jau, das finde ich auch sehr interessant. Allerdings kann ich da auch nur den Begriff der Graphentheorie in den Raum werfen, was deine Anmerkung bzgl. des Dijstra-Algorithmus ja nur erweitert .

Bin durchaus interessiert an praktischen Tipps, da das doch ein wirklich interessantes Themengebiet ist.

Grüße, Ben.

[Basti]

Hi.

Ich hab den Wikipedia-Artikel des genannten Algorithmus grad mal überflogen. Hier haben die Verbindungen der Knoten ja alle das gleiche Gewiht, den gleichen Preis oder wie auch immer das in der Fachsprache genannt wird.

Nach meinem Gefühl würd ich sagen: Abwechselnd von Start- und Zielknoten jeweils eine Ebene weiter alle Knoten einlesen und nach übereinstummen in der jeweils anderen Menge suchen. Dabei doppelte ignorieren.

Von Paul zu Alex also zuerst alle Kontakte von Paul einlesen und gucken, ob Alex dabei ist (in Menge S). Dann alle Kontakte von Alex einlesen (in Menge Z) und schauen, ob ein Knoten aus Menge S dabei ist. Dann alle direkten Kontakte aus Menge S nehmen, doppelte löschen und wieder schauen, ob einer aus Menge Z dabei ist usw.

Hab das aber nie gelernt/studiert und ich bin mir sicher, dass es hierfür Standardlösungen gibt.

Was die Lösung hier angeht, so wüsste ich nicht, dass man da was mit SQL machen könnte. In PHP würd ich wahrscheinlich für beide Mengen ein assoziatives Array anlegen, bei denen der Schlüssel den Namen des Knotens angibt und der Wert den Pfad enthält.

Basti

PS:
Nested Sets sind hier bestimmt untauglich, da die ja enorm teuer sind, was das hinzufügen von Knoten angeht. Ich hab aber nicht so ganz verstanden, ob du diese Bäume als Hilfe meintest, die pro Anfrage gebaut und dann wieder gelöst werden oder ob diese quasi als Cache des kürzesten Weges permanent gepeichert werden sollen (oder gar eine Mischung aus beidem - Erweiterung bei Bedarf). Für ersteres sind Nested Sets sicher nicht geeinget, letzteres wahrscheinlich auch weniger (pro neuem Kontakt müssten ja alle Bäume aktualisiert - und dazu natürlch auch gelockt werden, da ja jeder Baum die Kürzeste Verbindung "seines" Benutzers zu allen anderen enthielte).

[Ben]

Bei XING gibt es in der Gruppe "PHP-Entwicklung" einen entsprechenden Thread dazu: https://www.xing.com/app/forum?op=sh...les&id=1690189

Auch sehr interessant zu lesen, wie ich finde.

[Nachtrag]
Vor allem auch dieser Link hier: http://www.boost.org/libs/graph/doc/index.html

[pepe24]

Ich hab den Wikipedia-Artikel des genannten Algorithmus grad mal überflogen. Hier haben die Verbindungen der Knoten ja alle das gleiche Gewiht, den gleichen Preis oder wie auch immer das in der Fachsprache genannt wird.

Stimmt. Also zur Grundidee trägt der Algorithmus wohl wenig bei. Erst wenn diese Bekanntschaftsbeziehung qualitativ bewertet werden soll, kommt er (in welcher weise auch immer) ins Spiel.

Das Nested Set Model ist zu unperformant, das stimmt wohl. Self Joins sind das ebenfalls ab einer bestimmten Menge an Benutzern. Man wird die Self Joins also begrenzen müssen auf jeweils den direkten und indirekten (also bis 2. Grad). Ebenfalls denke ich, dass man den maximalen Rang der Bekanntheitsgrade auf höchstens 6 oder 7 beschränken muss, um die Datenmenge etwas im Zaum zu halten.
Hier kommt meines Erachtens noch eine Variable ins Spiel, die man nicht außer Acht lassen kann. Je reichhaltiger die erste(n) Abfrage(n) ist/ sind, desto höher die Wahrscheinlichkeit, schnell eine Übereinstimmung zu finden. Denn die Anzahl an Datensätzen zwischen Anfang und Ziel wächst mit exorbitanter Geschwindigkeit (nahe quadratischem Wachstumsfaktor). Also ist man wahrscheinlich auf sicherer Seite, wenn man die Komplexität der Abfrage mit steigender Knotentiefe, in Anbetracht der großen Datenmenge, progressiv drosselt - also ab dem 2. Grad des Anfangs- bzw. Zielknotens nur noch direkte Freundschaftsbeziehungen ausliest. Die verbildlichung als Baumstruktur - in Form assoziativer Arrays - finde ich ganz gut und man kann ziemlich sicher sein, dass man dadurch die schnellste Verbindung zwischen diesen Knoten erhält.

Im Hardcode selbst, ist es aus Performancegründen unumgänglich, die Auswertung und Eingrenzung der Datensätze zwischen MySQL und PHP aufzuteilen. Sonst ergibt das wohl einen Flaschenhals.

Ein super Thema! Ich denke, dass ich das Anfang Februar mal simulieren werde, wenn ich wieder ein bisschen Zeit hab. Werde mich dann mit Ergebnissen wiedermelden. Aber bis dahin könnte man doch die Theorie hier noch ein bisschen diskutieren.

Gruß,
Peter

[pepe24]

Hier noch ein paar interessante Links:
eine fertige Implementation (für Genebereich) http://www.godatabase.org/dev/sql/doc/godb-sql-doc.html

ein sehr interessanter Artikel, zu einer MYSQL umsetzung http://www.zdnet.de/builder/program/...9124191,00.htm

(unten) http://www.informatik.hu-berlin.de/f...506/se-graphen

http://www.artfulsoftware.com/mysqlb...qled1ch20.html

(Links aus XING-Diskussion // MYSQL-FORUM)