[Oracle] Wer kennt wen über wen? Pfade in einem Graph auflisten

[Thomas Darimont]

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/mysqlbook/sampler/mysqled1ch20.html

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

Gruß Tom

 

[carlkong]

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

 

[Thomas Darimont]

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]

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

 

[carlkong]

Gibts schon was neues?

 

[Daniel_CB]

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]

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]

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/oramag/webcolumns/2003/techarticles/gennick_connectby_10g.html

Unsere User Tabelle:

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:

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> select * from t_user;

        ID NAME
---------- ---------------------------------------------
         1 Tom
         2 Fritz
         3 Hans
         4 Anne
         5 Paula

Unsere User Tabelle:

Unsere Friend Tabelle:

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:

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:

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]

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

#
(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]

Hallo,

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.

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