studiVZ: "Über-drei-ecken"-Anzeige
0 0 
Volker Nebelung
0
studiVZ: "Über-drei-ecken"-Anzeige
Hi
Doofer Titel, ich weiss.
Was ich gerne wissen würde ist, wie macht man diese Abfragen dass im studiVZ z.B. steht dass ich X über Person Y kenne? Sind dafür nicht diverse Querverweisabfragen notwendig um soetwas herauszufinden?
Da ich nur in PHP arbeite und MySQL daher nur bedingt behersche würde ich gerne wissen wie man abfragen machen kann. Geht sowas auch aus PHP heraus? Und wie lauten die Befehle? Ist das einfach ein SELECT x FROM y WEHERE ... ? Gibt es dazu irgendwo programmierbeispiele?
grüsse
-
Hallo
Was ich gerne wissen würde ist, wie macht man diese Abfragen dass im studiVZ z.B. steht dass ich X über Person Y kenne?
was bedeutet das. Ich habe keine Ahnung vom studiVZ, außer dass es sowas gibt.
a) Bedeutet das, dass X ein direkter Bekannter von Person Y ist, aber kein
direkter Bekannter von Dir?Oder bedeutet es:
b) Die Bekanntschaft von X mit Dir geht mit den wenigsten Zwischenstufen über
Person Y?Und dazu kommt noch c)
Was ist, wenn X ein direkter Bekannter von Person Y und von Person Z ist, aber
kein direkter Bekannter von Dir - während Person Y und Person Z direkte Bekannte
von Dir sind. Was wäre dann die Anzeige?Sind dafür nicht diverse Querverweisabfragen notwendig um soetwas herauszufinden?
Das hängt von der Aufgabenstellung ab. Bei a) hält sich das in Grenzen und
läßt sich durch Einsatz bestimmter Muster optimieren.Freundliche Grüße
Vinzenz
-
Hallo
Hallo,
was bedeutet das. Ich habe keine Ahnung vom studiVZ, außer dass es sowas gibt.
a) Bedeutet das, dass X ein direkter Bekannter von Person Y ist, aber kein
direkter Bekannter von Dir?Oder bedeutet es:
b) Die Bekanntschaft von X mit Dir geht mit den wenigsten Zwischenstufen über
Person Y?Meines Wissens ist das bei StudiVZ so, dass du als Person X das Profil einer Person Y aufrufst und dann eine Kette X,A1,A2,...,An,Y von Personen mit n minimal ausgegeben wird (= Du bist über n Ecken mit Person Y in Kontakt).
Betrachtet man die Personen als Knoten und die Verknüpfungen zwischen zwei Personen als Kanten eines Graphen, eignet sich hervorragend der Dijkstra-Algorithmus zur Bestimmung der kürzesten Wege.
Gruß, Volker-
Hallo Volker,
Meines Wissens ist das bei StudiVZ so, dass du als Person X das Profil einer Person Y aufrufst und dann eine Kette X,A1,A2,...,An,Y von Personen mit n minimal ausgegeben wird (= Du bist über n Ecken mit Person Y in Kontakt).
Betrachtet man die Personen als Knoten und die Verknüpfungen zwischen zwei Personen als Kanten eines Graphen, eignet sich hervorragend der Dijkstra-Algorithmus zur Bestimmung der kürzesten Wege.
... der mir auch nicht unbekannt ist, siehe </archiv/2006/6/t130543/#m843861>.
Deswegen fragte ich ja nach den "Berechnungsvorschriften" :-)Freundliche Grüße
Vinzenz
-
Ich habe mich jetzt in den Dijkstra Algorhytmus via wikipedia eingelesen. Das ist wirklich interessant... wenn auch komplex.
Aber wie sähe so ein Ansatz in PHPüMySQL aus?
Ich habe mal eure links sowie google zurate gezogen und finde da aber kein beispiel wie man solche abfragen macht.
Wisst ihr mehr darüber?
-
Ich habe mich jetzt in den Dijkstra Algorhytmus via wikipedia eingelesen. Das ist wirklich interessant... wenn auch komplex.
Aber wie sähe so ein Ansatz in PHPüMySQL aus?
Auf reiner MySQL-Ebene wird das wohl kaum realisierbar sein (zumindest meines Wissens nach).
Ein Ansatz wäre, alle Personen aus der Datenbank zu lesen und sie als 2-dim. Array in PHP zu speichern. Ein Eintrag (a)ij wäre gleich 1, wenn eine Verknüpfung zwischen den beiden Personen Xi und Yj existiert. Darauf könnte man dann problemlos Dijkstra loslassen.Ob das bei StudiVZ nur mit Dijkstra so gemacht wird, wage ich allerdings zu bezweifeln. Da spielen bestimmt noch andere Algorithmen eine Rolle.
Gruß, Volker
-
Aber wie haben sie es dann getan? Schrieben die sich eigene PHP-Module sie sie serverseitig ansprechen können?
Ich meine, wenn ich das mal faktisch an zahlen festmache müsste, würde ich bei meiner prgrammierung jeweilos die Freunde-liste des users nehmen und bei allen seinen einträgen (sagen wir mal 30) wieder die freundelisten durchsuchen. Das alleine wäre schon auf der zweiten Ebene eine Abfrage von 900 Abfragen.
Man kann es sich ausmalen wie sich das in der 5. Ebene verhalten würde wenn die summe an abfragen exponentiell weiter steigt.Das muss doch machbar sein.
-
Hello,
Auf reiner MySQL-Ebene wird das wohl kaum realisierbar sein (zumindest meines Wissens nach).
für MySQL stimmt das wahrscheinlich, DB2 und Oracle (mindestens die beiden) können rekursive Abfrage, damit ist das Problem in SQL lösbar.
MfG
Rouven--
-------------------
sh:| fo:} ch:? rl:( br:& n4:{ ie:| mo:} va:) js:| de:] zu:| fl:( ss:) ls:& (SelfCode)
There's no such thing as a free lunch -- Milton Friedman
-
-
-
... der mir auch nicht unbekannt ist, siehe </archiv/2006/6/t130543/#m843861>.
Deswegen fragte ich ja nach den "Berechnungsvorschriften" :-)War von mir auch nicht als persönliche Belehrung an dich gedacht, sondern eher an den Threadersteller, sry ;-).
Gruß, Volker
-
-
-