[Oracle] Wer kennt wen über wen? Pfade in einem Graph auflisten - Relationale Datenbanksysteme @ tutorials.de: Forum & Hilfe

**Thomas Darimont** · 23.12.06, 02:00

Hallo!

Gerade im Bereich von Social Networking Sites wie openbc / xing oder neuerdings auch das studivz findet sich eine interessante Funktionalität: Die Visualisierung des Pfades innerhalb eines Bekanntheitsgraphen der aufzeigt über welche Personen eine Person eine gewisse andere Person kennt.

Hierzu bin ich gerade über einen Interessanten Artikel gestolpert der diese Problematik (Edge list model of a non-tree graph) anhand eines Airline / Flughafen / Flugplan Szenarios erklärt.
http://www.artfulsoftware.com/mysqlb...qled1ch20.html

Wenn ich die nächsten Tage mal etwas Zeit finde baue ich dazu vielleicht mal ein kleines Beispiel.

Gruß Tom

carlkong · 17.01.07, 22:25

Da wäre ich sehr interessiert dran! Wie siehts aus mit einem Beispiel?

**Thomas Darimont** · 17.01.07, 22:38

Hallo,

hatte bisher leider keine Zeit diese spannende Sache weiter zu verfolgen. Na ja, werd mal schauen ob ich am Wochenende mal Zeit dafür habe...

Gruß Tom

carlkong · 18.01.07, 19:52

Das wäre echt total super! Ich bin gespannt!

carlkong · 20.01.07, 21:52

Gibts schon was neues?

Daniel_CB · 23.01.07, 12:29

Also ich habe eine PHP Klasse geschrieben die dieses möglich macht.

als Grundlage dient eine Datenbank mit folgenden spalten.

USER_ID USER_FRIEND
2 1
1 2

als Pfade kommt

2=>1
bei mehren verbindungen

10=>8=>3=>1

so als BSP.

bei interesse ICQ 292913800

**Thomas Darimont** · 23.01.07, 20:49

Hallo,

hatte am Wochenende genug damit zu tun mit Dominik die ca. 800 MB Attachments des tutorials.de Forums zu retten ... übrigens erfolgreich

Vielleicht nächstes Wochenende.

Gruß Tom

**Thomas Darimont** · 26.02.07, 23:01

Hallo,

hier mal ein kleines Beispiel zum Aufbau eines Bekanntheitsgraphen in Oracle 10g mithilfe der neuen hierarchischen Abfragemöglichkeiten
in Oracle 10g -> http://www.oracle.com/technology/ora...ectby_10g.html

Unsere User Tabelle:

            
                    sql Code: 
                  
                        CREATE TABLE t_user (id number NOT NULL, name varchar2(45) NOT NULL, PRIMARY KEY  (id));
INSERT INTO t_user VALUES (1,'Tom');
INSERT INTO t_user VALUES (2,'Fritz');
INSERT INTO t_user VALUES (3,'Hans');
INSERT INTO t_user VALUES (4,'Anne');
INSERT INTO t_user VALUES (5,'Paula');

Unsere Friends Tabelle:

            
                    sql Code: 
                  
                        CREATE TABLE t_friend (id number NOT NULL , userid number NOT NULL, friendid number NOT NULL, PRIMARY KEY  (id));
INSERT INTO t_friend VALUES(1,1,2);
INSERT INTO t_friend VALUES(2,1,4);
INSERT INTO t_friend VALUES(3,2,1);
INSERT INTO t_friend VALUES(4,2,3);
INSERT INTO t_friend VALUES(5,2,4);
INSERT INTO t_friend VALUES(6,3,2);
INSERT INTO t_friend VALUES(7,4,1);
INSERT INTO t_friend VALUES(8,4,5);
INSERT INTO t_friend VALUES(9,5,4);

Unsere User Tabelle:

            
                    sql Code: 
                  
                        SQL> SELECT * FROM t_user;
 
        ID NAME
---------- ---------------------------------------------
         1 Tom
         2 Fritz
         3 Hans
         4 Anne
         5 Paula

Unsere User Tabelle:

Unsere Friend Tabelle:

            
                    sql Code: 
                  
                        SQL> SELECT * FROM t_friend;
 
        ID     USERID   FRIENDID
---------- ---------- ----------
         1          1          2
         2          1          4
         3          2          1
         4          2          3
         5          2          4
         6          3          2
         7          4          1
         8          4          5
         9          5          4
 
9 rows selected.

Damit haben wir einen Bekanntheitsgraphen definiert wie man ihn in der Grafik im Anhang sehen kann.

Möchten wir nun wissen über welche Verbindung User 3 den user 5 kennt so können wir folgende Abfrage benutzen:

            
                    sql Code: 
                  
                        SELECT socialnetwork.path 
FROM 
(SELECT
f.* ,
 3 || SYS_CONNECT_BY_PATH(f.friendid,'-') path
FROM
t_friend f
connect BY nocycle prior f.friendid = f.userid
start WITH f.userid = 3) socialnetwork
WHERE friendid = 5
ORDER BY length(socialnetwork.path)

Als Ergebnis erhalten wir:

            
                    Code:
                  
                   	SQL> select socialnetwork.path
  2  from
  3  (select
  4  f.* ,
  5   3 || SYS_CONNECT_BY_PATH(f.friendid,'-') path
  6  from
  7  t_friend f
  8  connect by nocycle prior f.friendid = f.userid
  9  start with f.userid = 3) socialnetwork
 10  where friendid = 5
 11  order by length(socialnetwork.path)
 12  /

PATH
---------------------------------------------------
3-2-4-5
3-2-1-4-5

Das bedeutet, dass der User 3 den User 5 über zwei verschiedene Verbindungen kennt:

1) 3-2-4-5
2) 3-2-1-4-5

Auf ähnliche Weise funktionieren auch die Beziehungsgraphen in den großen Networking Communities
wie Beispielsweise Xing/OpenBC, facebook, studivz und myspace.

Gruß Tom

Silverboy · 19.03.07, 16:41

Hi.

Kenne mich in oracle leider überhaupt nit aus. Lässt sich dieser Select denn auch auf MySQL anpassen?
Oder könntest mir kurz erkläeren was der folgende code genau macht

            
                    Code:
                  
                   	#
(SELECT
#
f.* ,
#
 3 || SYS_CONNECT_BY_PATH(f.friendid,'-') path
#
FROM
#
t_friend f
#
connect BY nocycle prior f.friendid = f.userid
#
start WITH f.userid = 3)

Grüße
Silverboy

**Thomas Darimont** · 20.03.07, 01:08

Hallo,

Zitat:

Kenne mich in oracle leider überhaupt nit aus. Lässt sich dieser Select denn auch auf MySQL anpassen?

Nein, in MySQL existieren die notwendigen Elemente dazu nicht... im Link in meinem ersten post findest du jedoch ein paar Lösungsvorschläge zu diesem Problem für MySQL.

Zitat:

Oder könntest mir kurz erkläeren was der folgende code genau macht

Im Prinzip macht der Ausdruck nichts anderes als die hierarchische Verknüpfung der beiden beteiligten Tabellen über die angegebenen Spalten herzustellen. Da wir in unserem Graph Zyklen haben die das hierarchische auflösen erschweren, lasse ich die Zyklen ignorieren.

Gruß Tom

Radhad · 20.03.07, 08:38

Muss die Tabelle "Friend" einen eigenen primärschlüssel haben oder geht das auch wenn man einen zusammengesetzten PK verwendet aus den beiden FK's?

Dani87 · 02.04.07, 10:45

Zitat:

Zitat von Thomas Darimont

Auf ähnliche Weise funktionieren auch die Beziehungsgraphen in den großen Networking Communities
wie Beispielsweise Xing/OpenBC, facebook, studivz und myspace.

Wie kommt es dann, dass ich auf studivz öfters schon mysql Fehlermeldungen gesehen habe?

Die müssen das mit mysql umgesetzt haben, nur wie?

**Thomas Darimont** · 02.04.07, 12:59

Hallo,

Zitat:

Wie kommt es dann, dass ich auf studivz öfters schon mysql Fehlermeldungen gesehen habe?

Die müssen das mit mysql umgesetzt haben, nur wie?

Ich hab doch nicht geschrieben, dass die dort Oracle verwenden, oder? ...
Ich meinte damit, dass das Prinzip ähnlich ist.

Gruß Tom

Dani87 · 02.04.07, 13:11

Du hast geschrieben, dass es auf ähnliche Weise funktioniert.

Das wird wohl stimmen! Zweifelsohne!

Da die Funktionen die du bei deiner Abfrage verwendet hast in mysql nicht funktionieren bzw. existieren, wird das ganze wohl ganz anders aussehen. Deshalb lässt sich das wohl nicht mit studivz und ähnlichen Plattformen die mit mysql arbeiten vergleichen.

Ganz allgemein gesagt wird das alles "ähnlich" sein, wobei ähnlich sich in diesem Zusammenhang sehr "dehnen" lässt.

lg dani

**Thomas Darimont** · 02.04.07, 13:15

Hallo,

Zitat:

Du hast geschrieben, dass es auf ähnliche Weise funktioniert.

Das wird wohl stimmen! Zweifelsohne!

Da die Funktionen die du bei deiner Abfrage verwendet hast in mysql nicht funktionieren bzw. existieren, wird das ganze wohl ganz anders aussehen. Deshalb lässt sich das wohl nicht mit studivz und ähnlichen Plattformen die mit mysql arbeiten vergleichen.

Deshalb trägt der Thread ja auch die Kennzeichnung [Oracle]

Weiterhin ist im Link im ersten Post gezeigt wie man diese Aufgabe auch mit MySQL lösen kann.

Zitat:

Ganz allgemein gesagt wird das alles "ähnlich" sein, wobei ähnlich sich in diesem Zusammenhang sehr "dehnen" lässt.
lg dani

und was ist nun dein Problem?

Gruß Tom