AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Datenbanken Effiziente Datenbankstruktur für soziale Netzwerke gesucht

Effiziente Datenbankstruktur für soziale Netzwerke gesucht

Ein Thema von Dani · begonnen am 26. Okt 2008 · letzter Beitrag vom 21. Nov 2008
Antwort Antwort
Benutzerbild von Dani
Dani

Registriert seit: 19. Jan 2003
732 Beiträge
 
Turbo Delphi für Win32
 
#1

Effiziente Datenbankstruktur für soziale Netzwerke gesucht

  Alt 26. Okt 2008, 16:16
Datenbank: MySQL • Version: 5.0.51b • Zugriff über: Zend Framework
Servus!

Einige kennen sicherlich die Website XING. Im Wesentlichen plegt man dort Geschäftskontakte. Ein nettes Feature ist, dass man sich zu jedem User anzeigen lassen kann, über welche Ecken man mit dem User in Verbindung steht. Man kann sowohl die kürzeste Verbindung als auch alle Verbindungen der Länge N <= 5 anzeigen lassen.
Beispiel:
dies ist nicht XING, sondern so soll das Ganze eines Tages mal aussehen
... S c h n i p p ...

Dieses Feature soll ich nun in einer ähnlichen Website realisieren. Die Frage ist, wie eine effiziente Implementierung aussehen könnte. Auf der Datenbankseite hab ich bisher nur die 'naive' Struktur:
http://img143.imageshack.us/img143/7149/dbschemabp5.png
Damit bliebe wohl nur eine Breitensuche, wenn wirklich alle Verbindungen gefunden werden müssen. Etwas subpotimal
Falls jemand schonmal etwas in die Richtung gemacht hat, wäre ich für Tipps unendlich dankbar

[edit=Sharky]Bild auf wunsch des Autors entfernt. Mfg, Sharky[/edit]
Miniaturansicht angehängter Grafiken
db_schema_312.png  
Dani H.
At Least I Can Say I Tried
  Mit Zitat antworten Zitat
SirTwist

Registriert seit: 28. Sep 2006
198 Beiträge
 
Delphi XE Professional
 
#2

Re: Effiziente Datenbankstruktur für soziale Netzwerke gesuc

  Alt 26. Okt 2008, 22:16
Hm... nur ein paar verworrene Gedanken meinerseits:

Wenn Du 1000 Benutzer hast, dann könnte man über eine Matrix (1000 x 1000) angeben, über wieviele Ecken zwei Leute sich kennen (minimal). Dabei könntest Du eine Grenze max_ecken einführen, die dafür sorgt, dass nicht alle Felder besetzt werden (nämlich jeweils die Felder von je Personen, die sich über mehr als max_ecken kennen, bleiben leer).

Wenn nun max_user größer wird und max_ecken klein bleibt, wird deine Matrix sehr spärlich besetzt und es kann sinnvoll sein, sie über eine Tabelle (user1, user2, anz_ecken) zu ersetzen. Außerdem ist die Matrix natürlich diagonalsymetrisch (da gabs auch mal einen Fachausdruck für), so dass Du (user2, user1, anz_ecken) gar nicht erst zu setzen brauchst.

Natürlich müsste die Tabelle immer aktualisiert werden, wenn user1 oder user2 an seinen oder ihren Kontakten rumfummelt. Das dürfte aber deutlich seltener auftreten als die Anzeige der möglichen Verbindungen.

Nun weißt Du aber nur, welche Beziehungen es sich lohnt anzugucken. Man könnte aber die Tabelle erweitern (user1, user2, anz_ecken, pfad). Wobei pfad eine Liste der UserIDs ist, über die die Beziehung aufgebaut ist. Ich speichere sowas gerne als Text-Feld ab und mache mir dann die MySQL-spezifische(?) Funktion FIND_IN_SET zu Nutze. Mit "FIND_IN_SET(user.id, relation.pfad)" kann ich alle User-Einträge auswählen, deren IDs in der Liste vorkommen.

Keinen blassen Schimmer, ob Dir das weiterhilft. ist jedenfalls reine Theorie und basiert auf keinerlei Erfahrung mit großen Userzahlen Viel Spaß!

Sir Twist
  Mit Zitat antworten Zitat
Benutzerbild von jfheins
jfheins

Registriert seit: 10. Jun 2004
Ort: Garching (TUM)
4.579 Beiträge
 
#3

Re: Effiziente Datenbankstruktur für soziale Netzwerke gesuc

  Alt 26. Okt 2008, 22:22
Übrigens: falls du es doch so machen musst, ,wie eingangs vorgeschlagen, könnte es effizienter sein, nicht von einem ausgehend bis zu einer tiefe von 6 zu suchen, sondern vielmehr von beiden ausgehend bbis zu einer tiefe von 3. Da sich mit jedem Schritt in die Tiefe die Breite exponentiell erhöht, könnte man damit wesentlichen Aufwand sparen

Außerdem kannst du - bei der Suche nach einer Verbindung - in deer Breite die Suche bei den KOntakten beginnen, die ihrerseits die meisten Kontakte haben
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#4

Re: Effiziente Datenbankstruktur für soziale Netzwerke gesuc

  Alt 27. Okt 2008, 08:12
Wenn Du deine 'user_has_contact' 1x mit sich selbst verjoinst, dann hast Du schon alle Verbindungen der Länge 1 (Ich->Kumpel->Du)
Du musst also nur die Tabelle 5x mit sich selbst verknüpfen und dann hast Du alles, was Du brauchst.

Das dürfte sogar einigermaßen fix gehen, weil Du das ja nur für eine Person machst.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Benutzerbild von Dani
Dani

Registriert seit: 19. Jan 2003
732 Beiträge
 
Turbo Delphi für Win32
 
#5

Re: Effiziente Datenbankstruktur für soziale Netzwerke gesuc

  Alt 13. Nov 2008, 21:44
Vielen Dank schonmal für die Anregungen!
Ich habe in der Zwischenzeit versucht, Alzairmars Ansatz als Query umzusetzen. Das kam dabei heraus:

SQL-Query für Verbindungen der Länge 5 (Maximum)
SQL-Code:
SELECT DISTINCT
   -- Benötigt wird in diesem Beispiel der Name und die ID des Benutzers
   c1.user_iduser AS u1_id, u1.name AS u1_name,
   c2.user_iduser AS u2_id, u2.name AS u2_name,
   c3.user_iduser AS u3_id, u3.name AS u3_name,
   c4.user_iduser AS u4_id, u4.name AS u4_name,
   c5.user_iduser AS u5_id, u5.name AS u5_name
FROM
   -- u1 ist der erste Benutzer im Kontakte-Pfad (Start), u5 der letzte (Ziel)
   `user_has_contact` AS c1,
   `user_has_contact` AS c2,
   `user_has_contact` AS c3,
   `user_has_contact` AS c4,
   `user_has_contact` AS c5,
   `user` AS u1,
   `user` AS u2,
   `user` AS u3 ,
   `user` AS u4,
   `user` AS u5
WHERE
    -- Die Namen der Benutzer stehen in der Tabelle 'user'
    (c1.user_iduser=u1.iduser) AND (c2.user_iduser=u2.iduser) AND (c3.user_iduser=u3.iduser) AND
    (c4.user_iduser=u4.iduser) AND (c5.user_iduser=u5.iduser) AND

    -- Der Pfad muss mit dem Start-Benutzer u1 beginnen.
    (c1.user_iduser=%s) AND

    -- Der Pfad muss über 5 Benutzer (u1..u5) gehen, wobei zwischen u_n und u_n+1 eine
    -- "Ist-Kontakt-Von" Beziehung bestehen muss.
    (c1.contact_iduser=c2.user_iduser) AND
    (c2.contact_iduser=c3.user_iduser) AND
    (c3.contact_iduser=c4.user_iduser) AND
    (c4.contact_iduser=c5.user_iduser) AND

    -- Der Pfad muss mit dem Ziel-Benutzer u5 enden.
    (c5.user_iduser=%s) AND

    -- Der Pfad darf keine Zyklen enthalten. Die Zusicherung, dass kein User sich
    -- selbst als Kontakt haben darf, wurde hier verwendet.
    -- Dadurch wird auch verhindert, dass der Ziel-Benutzer an einer anderen Position
    -- als dem letzten Pfadelement steht.
    (c1.user_iduser!=c3.user_iduser) AND (c1.user_iduser!=c4.user_iduser) AND
    (c2.user_iduser!=c4.user_iduser) AND (c2.user_iduser!=c5.user_iduser) AND
    (c3.user_iduser!=c5.user_iduser)
Da ich ein Datenbanken/SQL-Neuling bin, gibt es hier bestimmt noch einiges an Optimierungspotential
Falls jemandem etwas auffällt, nur raus damit!
Dani H.
At Least I Can Say I Tried
  Mit Zitat antworten Zitat
Benutzerbild von Dani
Dani

Registriert seit: 19. Jan 2003
732 Beiträge
 
Turbo Delphi für Win32
 
#6

Re: Effiziente Datenbankstruktur für soziale Netzwerke gesuc

  Alt 18. Nov 2008, 13:43
Wäre es evtl. sinnvoll, die Query durch eine View zu vereinfachen oder wäre dann zu erwarten, dass der Speicherverbrauch der Datenbank explodiert?
Dani H.
At Least I Can Say I Tried
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#7

Re: Effiziente Datenbankstruktur für soziale Netzwerke gesuc

  Alt 18. Nov 2008, 14:15
Eher eine Funktion (UDF). Eine View ist nur eine kompilierte Query, sodaß beim Aufruf der Overhead des Übersetztens eingespart wird. Speicher verbraucht eine View (bis auf den Quellcode) nicht.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Benutzerbild von Dani
Dani

Registriert seit: 19. Jan 2003
732 Beiträge
 
Turbo Delphi für Win32
 
#8

Re: Effiziente Datenbankstruktur für soziale Netzwerke gesuc

  Alt 21. Nov 2008, 12:21
Ah, okay. Wie man sieht, muss ich noch jede Menge Unwissenheit abbauen

Tausend Dank nochmal
Dani H.
At Least I Can Say I Tried
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 10:21 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz