Exceptionfault

Schon vor längerer Zeit gab es im Datenbank Forum von Tutorials.de eine Diskussion zu rekursivem SQL. Genauer ging es darum, wie Social Network Seiten wie Xing oder StudiVZ die Bekanntschaftsgraphen “Wer kennt wen über wen?” abzubilden. Eins meiner Postings ist dabei sicher ein bisschen über das Ziel hinaus geschossen, aber der entstandene Algorithmus ist es allemal wert hier abzulegen.

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:

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.