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



## Thomas Darimont (23. Dezember 2006)

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 (17. Januar 2007)

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


----------



## Thomas Darimont (17. Januar 2007)

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. Januar 2007)

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


----------



## carlkong (20. Januar 2007)

Gibts schon was neues?


----------



## Daniel_CB (23. Januar 2007)

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. Januar 2007)

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. Februar 2007)

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 (19. März 2007)

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 (20. März 2007)

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


----------



## Radhad (20. März 2007)

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 (2. April 2007)

Thomas Darimont hat gesagt.:


> 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 (2. April 2007)

Hallo,



> 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 (2. April 2007)

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 (2. April 2007)

Hallo,



> 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.



> *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


----------



## Radhad (2. April 2007)

Schwierig wird das ganze, wenn man lieber eine nur eine Tablle mit zusammengesetzten Primärschlüssel aus UserID und FreindID verwenden will... Bei http://www.lokalisten.de werden einem nur die Freunde eines Freundes angezeigt, das war es dann auch schon. Es scheint wohl nicht so einfach zu sein.


----------



## Exceptionfault (2. April 2007)

Die Frage "Wer kennt wen über wen?" ist nüchtern betrachtet, nichts anderes als ein extrem einfacher Pathfinding Algorithmus. Das schöne daran ist, dass übliche Parameter wie "Wegekosten" o.ä. wegfallen und nur die Anzahl der Knoten bis zum Ziel entscheidend für die kürzeste Strecke sind. Daher eignet sich hier das rekursive SQL ("connect by") von Oracle sehr gut. 

Rein aus Interesse habe ich mich mal an den wohl bekanntesten Pathfinding Algorithmus (A*) gemacht und in PL/SQL umgesetzt:

Als Grundlage dient mir ein Koordinatensystem mit fixen Orten, dargestellt durch folgende Tabelle und INSERTS

```
0 1 2 3 4 5 6 7 8 9101112 
 0A       B
 1                  H
 2            C
 3    D
 4          F           I
 5E
 6              G
 7      K
 8                  J     N
 9  M
10          L
11              O
12

CREATE TABLE places
(
    placeid     NUMBER(10,0)    CONSTRAINT NN_places_id     NOT NULL,
    name        VARCHAR2(30)    CONSTRAINT NN_places_name   NOT NULL,
    posx        NUMBER(10,0)    CONSTRAINT NN_places_posx   NOT NULL,
    posy        NUMBER(10,0)    CONSTRAINT NN_places_posy   NOT NULL
);

ALTER TABLE places
    ADD CONSTRAINT PK_places
    PRIMARY KEY ( placeid )
    USING INDEX;
    

INSERT INTO places VALUES(  1, 'A',  0,  0 ); 
INSERT INTO places VALUES(  2, 'B',  4,  0 );
INSERT INTO places VALUES(  3, 'C',  6,  2 );
INSERT INTO places VALUES(  4, 'D',  2,  3 );
INSERT INTO places VALUES(  5, 'E',  0,  5 );
INSERT INTO places VALUES(  6, 'F',  5,  4 );
INSERT INTO places VALUES(  7, 'G',  7,  6 );
INSERT INTO places VALUES(  8, 'H',  9,  1 );
INSERT INTO places VALUES(  9, 'I', 11,  4 );
INSERT INTO places VALUES( 10, 'J',  9,  8 );
INSERT INTO places VALUES( 11, 'K',  3,  7 );
INSERT INTO places VALUES( 12, 'L',  5, 10 );
INSERT INTO places VALUES( 13, 'M',  1,  9 );
INSERT INTO places VALUES( 14, 'N', 12,  8 );
INSERT INTO places VALUES( 15, 'O',  7, 11 );
```

Die einzelnen Orte sind untereinander mit Strassen verbunden. Als zusätzliche Information werden die Wegekosten abgelegt. In meinem Fall wurden sie einfach über die Länge der Strecke berechnet. Ich gehe also davon aus, dass ich auf allen Strecken gleich schnell voran komme, keine Steigungen o.ä. vorhanden sind etc..


```
CREATE TABLE roads
(
    sourceid    NUMBER(10,0)    CONSTRAINT NN_roads_source  NOT NULL,
    targetid    NUMBER(10,0)    CONSTRAINT NN_roads_target  NOT NULL,
    cost        NUMBER(5,0)     CONSTRAINT NN_roads_cost    NOT NULL
);

ALTER TABLE roads 
    ADD CONSTRAINT PK_roads
    PRIMARY KEY ( sourceid, targetid )
    USING INDEX;
    
CREATE UNIQUE INDEX idx_roads_inv    
    ON roads ( targetid, sourceid );
    
INSERT INTO roads VALUES (  1,  4,  10 );
INSERT INTO roads VALUES (  9, 14,  15 );
INSERT INTO roads VALUES ( 10, 14,  10 );
INSERT INTO roads VALUES ( 14, 15,  25 );
INSERT INTO roads VALUES ( 12, 15,   5 );
INSERT INTO roads VALUES ( 13, 12,  15 );
INSERT INTO roads VALUES ( 13,  5,  15 );
INSERT INTO roads VALUES (  5,  4,   7 );
INSERT INTO roads VALUES (  8,  9,  12 );
INSERT INTO roads VALUES (  8,  3,  10 );
INSERT INTO roads VALUES (  3,  4,  15 );
INSERT INTO roads VALUES (  3,  2,   7 );
INSERT INTO roads VALUES (  1,  2,  15 );
INSERT INTO roads VALUES (  7, 10,   7 );
INSERT INTO roads VALUES (  6,  7,   7 );
INSERT INTO roads VALUES (  7, 11,  15 );
INSERT INTO roads VALUES ( 11,  5,  13 );
INSERT INTO roads VALUES (  8,  7,  23 );
```

Daraus ergibt sich dann folgende Karte:
(siehe Anhang...)


Der Algorithmus selbst benötigt 2 temporäre Tabellen zur Berechnung:

```
CREATE GLOBAL TEMPORARY TABLE freelist (
    placeid     NUMBER(10,0),
    parentid    NUMBER(10,0),
    abscost     NUMBER(10,0),
    calccost    NUMBER(10,0),
    CONSTRAINT PK_FREELIST
    PRIMARY KEY ( placeid )
    USING INDEX
);

CREATE GLOBAL TEMPORARY TABLE locklist (
    placeid     NUMBER(10,0),
    parentid    NUMBER(10,0),
    abscost     NUMBER(10,0),
    calccost    NUMBER(10,0),
    CONSTRAINT PK_LOCKLIST
    PRIMARY KEY ( placeid )
    USING INDEX
);
```

Die Funktionsweise des A* Algorithmus möchte ich hier nicht erläutern, das würde den Rahmen sprengen, darum hier einfach der Sourcecode meines Packages:

```
CREATE OR REPLACE FUNCTION CALCCOSTS( sourceid        IN places.placeid%TYPE,
                                      targetid        IN places.placeid%TYPE )
                                      RETURN             NUMBER
IS
    s       places%ROWTYPE;
    t       places%ROWTYPE;
    calc    NUMBER;
BEGIN
    SELECT  *
    INTO    s
    FROM    places
    WHERE   placeid = sourceid;
    
    SELECT  *
    INTO    t
    FROM    places 
    WHERE   placeid = targetid;
    
    calc := 5 * ROUND( SQRT( (t.POSX - s.POSX)*(t.POSX - s.POSX) + (t.POSY - s.POSY)*(t.POSY - s.POSY) ) );
    DBMS_OUTPUT.put_line( '=> Calculation distance between ' || TO_CHAR( sourceid ) || ' and ' || to_char( targetid ) || ' => ' || to_char( calc ) );
    RETURN  calc;
END;                        
/

SHO ERRORS

CREATE OR REPLACE PACKAGE A_STAR
IS

    PROCEDURE SEARCH(   sourceid    IN places.placeid%TYPE,
                        targetid    IN places.placeid%TYPE );
    
END;
/

SHOW ERRORS


CREATE OR REPLACE PACKAGE BODY A_STAR
IS

    targetnode      places.placeid%TYPE;

    ------------------------------------------------------------------------------------------------
    PROCEDURE INIT_SEARCH
    IS
    BEGIN
        DELETE FROM LOCKLIST;
        DELETE FROM FREELIST;
        targetnode := NULL;
    END;
    
    ------------------------------------------------------------------------------------------------
    PROCEDURE ADD_TO_LOCKLIST( n_placeid  IN places.placeid%TYPE,
                               n_parentid IN places.placeid%TYPE,
                               n_abscost  IN NUMBER,
                               n_calccost IN NUMBER,
                               n_rowt     OUT locklist%ROWTYPE )
    IS
    BEGIN
        DBMS_OUTPUT.put_line( '=> Adding node to locklist: ' || TO_CHAR( n_placeid ));
        INSERT INTO LOCKLIST VALUES( n_placeid, n_parentid, n_abscost, n_calccost ) 
        RETURNING placeid, parentid, abscost, calccost INTO n_rowt;
        DELETE FROM FREELIST WHERE placeid = n_placeid;
    END;
      
    ------------------------------------------------------------------------------------------------
    PROCEDURE STEP_FORWARD( rowt OUT locklist%ROWTYPE )
    IS
    BEGIN
        SELECT  *
        INTO    rowt
        FROM    FREELIST
        WHERE   ABSCOST + CALCCOST = ( SELECT MIN( ABSCOST + CALCCOST ) FROM FREELIST )
        AND     ROWNUM  = 1;      
    END;
    
    ------------------------------------------------------------------------------------------------
    PROCEDURE MERGE_FREELIST( source    IN locklist%ROWTYPE )
    IS
    BEGIN
        MERGE INTO FREELIST f
        USING   (
                    -- finde alle orte, die mit der source verbunden sind und noch nicht in der
                    -- lockliste drin stehen
                    SELECT  sourceid AS PLACEID,
                            cost      
                    FROM    roads
                    WHERE   targetid = source.placeid
                    AND     sourceid NOT IN ( SELECT PLACEID FROM locklist )
                    UNION
                    SELECT  targetid AS PLACEID,
                            cost
                    FROM    roads
                    WHERE   sourceid = source.placeid
                    AND     targetid NOT IN ( SELECT PLACEID FROM locklist )
        ) r
        ON (
            f.PLACEID = r.PLACEID   
        )
        WHEN MATCHED THEN
            UPDATE SET      f.PARENTID = source.placeid,
                            f.ABSCOST  = source.abscost + r.cost
                   WHERE    f.ABSCOST  > source.abscost + r.cost                        
        WHEN NOT MATCHED 
            THEN INSERT VALUES ( r.PLACEID, source.PLACEID, source.abscost + r.cost, CALCCOSTS( r.placeid, targetnode ));
    
    END;    
    
    ------------------------------------------------------------------------------------------------
    PROCEDURE SEARCH(   sourceid        IN places.placeid%TYPE,
                        targetid        IN places.placeid%TYPE )
    IS
        rowt locklist%rowtype;
        i   PLS_INTEGER := 1;
    BEGIN
        INIT_SEARCH;
        
        targetnode := targetid;
        ADD_TO_LOCKLIST( sourceid, sourceid, 0, 0, rowt );
        
        WHILE rowt.placeid <> targetid LOOP
            MERGE_FREELIST( rowt );        
            STEP_FORWARD( rowt );
            ADD_TO_LOCKLIST( rowt.placeid, rowt.parentid, rowt.abscost, rowt.calccost,  rowt );
            i := i+1;
            IF i >= 1000 THEN 
                RETURN;
            END IF;
        END LOOP;
        
    END;
    
    

END;
/

SHOW ERRORS
```

Der Aufruf erfolgt dann einfach mit 

```
set serveroutput on
exec A_STAR.SEARCH( 9, 1 );
```
Wobei die beiden Parameter die ID`s des Startknoten und des Zielknoten angeben.

Wer sich detailiert damit auseinadersetzen will, kann mal hier ( http://www.gamasutra.com/features/20010314/pinter_pfv.htm ) etwas tiefer nachlesen. Meine Implementation ist dagegen recht rudimentär.


----------



## Dani87 (2. April 2007)

Thomas Darimont hat gesagt.:


> 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.



Damit hast du wohl Recht. Sry nicht gesehen. ;-) Ich dachte es geht jetzt nur um mysql.


Hmm, was das Beispiel angeht - Damit komme ich irgendwie nicht ganz klar. Bin selber dabei eine Lösung zu finden. Bin bereits soweit gekommen, dass ich eine Person zwischen zwei Personen bestimmen kann. Wobei die Lösung mehr oder weniger mit php umgesetzt wurde, mit array Funktionen. Würde mich freuen wenn jemand aus diesem Forum mal ein Script speziell für mysql entwickeln könnte.


----------



## Thomas Darimont (2. April 2007)

Hallo,



> Hmm, was das Beispiel angeht - Damit komme ich irgendwie nicht ganz klar. Bin selber dabei eine Lösung zu finden. Bin bereits soweit gekommen, dass ich eine Person zwischen zwei Personen bestimmen kann. Wobei die Lösung mehr oder weniger mit php umgesetzt wurde, mit array Funktionen. Würde mich freuen wenn jemand aus diesem Forum mal ein Script speziell für mysql entwickeln könnte.


Genau dieses Problem wird in dem Link in meinem ersten Post für MySQL (zum Teil über Stored procedures) gelöst: http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html

Gruß Tom


----------

