Die Oracle Datenbank als Graph Datenbank

Graph Datenmodelle und Graph Datenbanken haben in den letzten Jahren immer mehr an Bedeutung gewonnen, weil sie auf die Abbildung und das Analysieren von hochgradig vernetzen Informationen spezialisiert sind. Beispiele dafür sind semantische Netze, die insbesondere in der Wissenspräsentation verbreitet sind oder auch soziale Netzwerke.

Die Oracle Datenbank ist eine multimodale Datenbank. Sie kennt also nicht nur das relationale Datenmodell sondern unterstützt andere Datenmodelle. In Bezug auf Netzwerk- oder Graphen werden entsprechende Datenmodelle bereits seit Version 10.2 unterstützt. Das gilt für räumliche (z.B. Straßen- oder Leitungsnetze) als auch semantische Netze ("Linked Data"). Mit Version 12.2 der Oracle DB wurde neu die Unterstützung für das Property Graph Datenmodell eingeführt.

Dieser Beitrag fokussiert sich darauf, wie Property Graphs in der Oracle DB abgebildet und geladen werden können. Dazu werde ich das relational modelierte HR Schema in ein Graph-Datenmodell übertragen. Auch eine erste Analyse mit Hilfe des Dijkstra−Algorithmus für "Kürzeste−Wege" Berechnungen werde ich zeigen. Alles, was Sie zum Verständnis benötigen, sind SQL Kenntnisse.

Auf die sehr umfassenden Möglichkeiten der Graphen-Analyse mittels der im Oracle Home bereitgestellten Java API sowie das Visualisieren von Graphen mit Open Source Werkzeugen werde ich in einem zweiten Blog-Beitrag zu späterer Zeit eingehen.

Property Graphs kurz erklärt

Allen bekannten und von Graph-Datenbanken unterstützten Datenmodellen liegt ein Netzwerk von Knoten und Kanten zugrunde. Ein solches Datenmodell legt den Schwerpunkt auf die Beziehungen zwischen Informationen und deren Analyse mittels Graph-Algorithmen oder auch einer deklarativen Graph-Anfragesprache.

Beim Property Graph, der generischsten Art von Graphen, repräsentieren die Knoten Informationstypen. Diese sind über Kanten mit anderen Knoten verbunden. Beiden, sowohl Knoten als auch Kanten, können eine beliebige Anzahl von Attributen, engl. Properties genannt, zugeordnet werden [Abb. 1]. Typischerweise werden diese Attribute als Key-Value-Paare abgebildet und gespeichert. Die Attribute von Knoten oder Kanten müssen nicht identisch sein, weder in der Anzahl noch in ihren Inhalten. In der Praxis werden jedoch Knoten gleicher Informationstypen gleichartige Attribute aufweisen ebenso wie die Attribute von Kanten, die in der Regel mindestens ein gleiches Etikett (engl. Label) tragen. Etiketten sind eine zusätzliche Eigenschaft, die Kanten tragen können. Knoten können keine Etikette zugeordnet werden. Es ist jedoch möglich, ein Attribut als Etikett zu deklarieren.

Abb. 1: Ausschnitt aus dem HR Beispielschema der Oracle Datenbank − Modellierung als Property Graph

Alle Funktionalität rund um Property Graphs ist Teil der Datenbank Option Spatial and Graph. Voraussetzung ist eine Enterprise Edition in der Version 12.2 oder höher. Zusätzlich benötigt wird die Option Partitioning. Für eine Evaluierung können Sie entweder

• die Oracle DB Express Edition,
• die Oracle DB EE plus benötigte DB Optionen über das OTN License Agreement oder
• den Oracle Database Cloud Service (Enterprise Edition High Performance) über einen Oracle Cloud Trial Account

nutzen. Für diesen Blog-Beitrag habe ich eine Oracle DB 18c genutzt, bereitgestellt als Cloud Service über die Oracle Cloud [Abb. 2].

Abb. 2: Oracle DB 18c Instanz in der Oracle Cloud

Um mit Property Graphs in der Datenbank zu arbeiten, müssen folgende technischen Voraussetzungen erfüllt sein:

• Der Datenbank Parameter MAX_STRING_SIZE ist auf "extended" gesetzt für die Container Datenbank.
• Java 8 oder höher ist installiert.
• Das Default Character Set ist AL32UTF8, das NLS Character Set AL16UTF16.

Der Default Wert für MAX_STRING_SIZE ist "standard". Daher folgt hier eine kurze Beschreibung, wie die Änderung auf "extended" erfolgt. Bitte beachten Sie zusätzliche Hinweise zum Umschalten des Parameters in der Dokumentation.

prompt$ sqlplus / as sysdba
Connected.

SQL> alter session set container=CDB$ROOT;
Session altered.
SQL> alter system set max_string_size=extended scope=SPFILE;
System altered.
SQL> shutdown immediate;
Database closed.
Database dismounted.
ORACLE instance shut down.
SQL> startup upgrade;
ORACLE instance started.
...
Database mounted.
SQL> alter pluggable database all open upgrade;
Pluggable database altered.
SQL> quit

prompt$ cd $ORACLE_HOME/rdbms/admin
prompt$ mkdir /home/oracle/utl32k_cdb_pdbs_output
prompt$ $ORACLE_HOME/perl/bin/perl $ORACLE_HOME/rdbms/admin/catcon.pl -u SYS -d $ORACLE_HOME/rdbms/admin -l '/home/oracle/utl32k_cdb_pdbs_output' -b utl32k_cdb_pdbs_output utl32k.sql
...
Enter Password:
catcon.pl: completed successfully
prompt$ sqlplus / as sysdba

SQL> shutdown immediate;
SQL> startup
SQL> alter pluggable database all open read write;
Pluggable database altered.
SQL> quit

prompt$ mkdir /home/oracle/utlrp_cdb_pdbs_output
prompt$ $ORACLE_HOME/perl/bin/perl $ORACLE_HOME/rdbms/admin/catcon.pl -u SYS -d $ORACLE_HOME/rdbms/admin -l '/home/oracle/utlrp_cdb_pdbs_output' -b utlrp_cdb_pdbs_output utlrp.sql
...
Enter Password:
...
catcon.pl: completed successfully

prompt$ sqlplus / as sysdba

SQL> alter session set container=PDB1;
Session altered.
SQL> show parameters max_string;

Nicht zwingend notwendig aber empfehlenswert sind zusätzlich das Anlegen:

• eines Datenbank Nutzers (hier PGUSER) und
• eines eigenen Tablespace, welcher als Default Tablespace diesem Nutzer zugeordnet wird.

prompt$ sqlplus / as sysdba
SQL> alter session set container=PDB1;
SQL> create bigfile tablespace pgtbs datafile '+data' size 512m reuse autoextend on next 128M maxsize unlimited extent management local;
SQL> select * from v$tablespace;
SQL> create user pguser identified by Welcome123#;
SQL> grant connect, resource, alter session to pguser;
SQL> alter user pguser default tablespace pgtbs;
SQL> grant unlimited tablespace to pguser;

Einen Property Graph erzeugen

Bevor Knoten und Kanten geladen werden können, muß der Graph definiert werden. Dafür wird die Prozedur CREATE_PG im PL/SQL Paket OPG_APIS aufgerufen.

SQL> conn pguser/Welcome123#@pdb1
SQL> exec opg_apis.create_pg(graph_name => 'pgtest',
SQL>                         dop => 4,
SQL>                         num_hash_ptns => 8,
SQL>                         tbs => 'PGTBS');
SQL> select table_name from user_tables;

Die einzelnen Parameter für den Aufruf der Prozedur beziehen sich dabei auf:

• den Namen des Graphen
• den Grad der Parallelisierung
• die Anzahl der (automatisch erzeugten) Hash Partitionen, auf welche die Knoten und Kanten verteilt werden
• den verwendeten Tablespace

Optional kann auch noch angegeben werden, daß die Daten komprimiert gespeichert werden. Im Aufruf der Prozedur weiter oben wurde dieser Parameter nicht gesetzt.

Die Prozedur legt mehrere Tabellen mit dem Präfix PGTEST an [Abb. 3]. In der Tabelle mit der Endung VT$ werden die Knoten (engl. Vertices) mit ihren Attributen abgelegt, in der Tabelle mit der Endung GE$ die Kanten (engl. Edges) inlusive ihrer Attribute.

Abb. 3: Tabellen für den Graph PGTEST dargestellt im Oracle SQL Developer

An dieser Stelle soll ein kurzer Blick auf die Definition dieser beiden Tabellen geworfen werden.

SQL> desc pgtestVT$;
Name Null?    Type
---- -------- ---------------------------
VID  NOT NULL NUMBER
K             NVARCHAR2(3100)
T             NUMBER(38)
V             NVARCHAR2(15000)
VN            NUMBER
VT            TIMESTAMP(6) WITH TIME ZONE
SL            NUMBER
VTS           DATE
VTE           DATE
FE            NVARCHAR2(4000)

SQL> desc pgtestGE$;
Name Null?    Type
---- -------- ---------------------------
EID  NOT NULL NUMBER
SVID NOT NULL NUMBER
DVID NOT NULL NUMBER
EL            NVARCHAR2(3100)
K             NVARCHAR2(3100)
T             NUMBER(38)
V             NVARCHAR2(15000)
VN            NUMBER
VT            TIMESTAMP(6) WITH TIME ZONE
SL            NUMBER
VTS           DATE
VTE           DATE
FE            NVARCHAR2(4000)

Die Definition orientiert sich am sogenannten Oracle Flat File Format für Property Graphs.
Eine Zeile in der Tabelle für Knoten ist repräsentiert durch:

• VID: ein eindeutiger INTEGER Wert für den Knoten
• K: Name des Attribut-Schlüssels im Key-Value-Paar (welches ein Attribut des Knotens beschreibt)
• T: Datentyp für den Attribut-Wertes
• V: Attribut-Wert, sofern nicht numerisch oder ein Datum. Für die vereinfachte Suche mittels Volltext-Index können numerische oder Datumswerte zusätzlich als STRING hier gespeichert werden.
• VN: Numerischer Attribut-Wert
• VT: Datum bzw. Zeitstempel als Attribut-Wert
• Alle weiteren Spalten der Tabelle werden in diesem Post nicht verwendet.

Eine Zeile in der Tabelle für Kanten ist repräsentiert durch:

• EID: ein eindeutiger INTEGER Wert für die Kante
• SVID: ID des Quell-Knotens der Kante
• DVID: ID des Ziel-Knotens der Kante
• EL: Ein Etikett für die Kante
• K: Name des Attribut-Schlüssels im Key-Value-Paar (welches ein Attribut des Knotens beschreibt)
• T: Datentyp für den Attribut-Wertes
• Alle anderen Attribute sind identisch zu den gleichnamigen Attributen der Knoten-Tabelle.

Einen Property Graph laden

Für das Laden der Knoten und Kanten gibt es mehrere Möglichkeiten. Je nach Format der Ausgangsdaten ist es möglicherweise notwendig, diese in ein Datenformat zu transformieren, welches von Spatial and Graph unterstützt wird. Das sind neben dem Oracle Flat File Format auch GraphSON, GraphML oder GML.

Das nachfolgende Beispiel ist die einfachste Form des Ladens, mittels INSERT. Dieses Vorgehen ist jedoch nur dann sinnvoll, wenn die Anzahl der zu ladenden Daten überschaubar ist. Typischerweise enthalten Graphen jedoch eine sehr große Anzahl an Knoten und Kanten. Dann empfehlen sich bekannte und bewährte Werkzeuge, wie SQL*Loader oder das Laden über External Tables.

truncate table pgtestVT$;
insert into pgtestVT$(vid,k,t,v,vn,vt) values(1,'type',1,'City',null,null);
insert into pgtestVT$(vid,k,t,v,vn,vt) values(1,'city_name',1,'Zürich',null,null);
insert into pgtestVT$(vid,k,t,v,vn,vt) values(1,'city_lon',4,null,8.54,null);
insert into pgtestVT$(vid,k,t,v,vn,vt) values(1,'city_lat',4,null,47.38,null);
insert into pgtestVT$(vid,k,t,v,vn,vt) values(1,'city_ranking',2,null,0,null);
insert into pgtestVT$(vid,k,t,v,vn,vt) values(2,'type',1,'City',null,null);
insert into pgtestVT$(vid,k,t,v,vn,vt) values(2,'city_name',1,'Genève',null,null);
insert into pgtestVT$(vid,k,t,v,vn,vt) values(2,'city_lat',4,null,46.21,null);
insert into pgtestVT$(vid,k,t,v,vn,vt) values(2,'city_ranking',2,null,1,null);
insert into pgtestVT$(vid,k,t,v,vn,vt) values(2,'city_member_count',2,null,1225,null);
insert into pgtestVT$(vid,k,t,v,vn,vt) values(3,'type',1,'City',null,null);
insert into pgtestVT$(vid,k,t,v,vn,vt) values(3,'city_name',1,'Lausanne',null,null);
insert into pgtestVT$(vid,k,t,v,vn,vt) values(3,'city_lon',4,null,6.62,null);
insert into pgtestVT$(vid,k,t,v,vn,vt) values(3,'city_lat',4,null,46.52,null);
insert into pgtestVT$(vid,k,t,v,vn,vt) values(3,'city_ranking',2,null,2,null);
insert into pgtestVT$(vid,k,t,v,vn,vt) values(3,'city_member_count',2,null,635,null);
insert into pgtestVT$(vid,k,t,v,vn,vt) values(4,'type',1,'City',null,null);
insert into pgtestVT$(vid,k,t,v,vn,vt) values(4,'city_name',1,'Bern',null,null);
insert into pgtestVT$(vid,k,t,v,vn,vt) values(4,'city_lon',4,null,7.44,null);
insert into pgtestVT$(vid,k,t,v,vn,vt) values(4,'city_lat',4,null,46.95,null);
insert into pgtestVT$(vid,k,t,v,vn,vt) values(4,'city_ranking',2,null,3,null);
insert into pgtestVT$(vid,k,t,v,vn,vt) values(5,'type',1,'City',null,null);
insert into pgtestVT$(vid,k,t,v,vn,vt) values(5,'city_name',1,'Vienna',null,null);
insert into pgtestVT$(vid,k,t,v,vn,vt) values(5,'city_lon',4,null,16.37,null);
insert into pgtestVT$(vid,k,t,v,vn,vt) values(5,'city_lat',4,null,48.22,null);
insert into pgtestVT$(vid,k,t,v,vn,vt) values(5,'city_ranking',2,null,0,null);
insert into pgtestVT$(vid,k,t,v,vn,vt) values(5,'city_member_count',2,null,1367,null);
insert into pgtestVT$(vid,k,t,v,vn,vt) values(6,'type',1,'Country',null,null);
insert into pgtestVT$(vid,k,t,v,vn,vt) values(6,'country_name',1,'Switzerland',null,null);
insert into pgtestVT$(vid,k,t,v,vn,vt) values(6,'country_code',1,'ch',null,null);
insert into pgtestVT$(vid,k,t,v,vn,vt)  values(7,'type',1,'Country',null,null);
insert into pgtestVT$(vid,k,t,v,vn,vt) values(7,'country_name',1,'Austria',null,null);
insert into pgtestVT$(vid,k,t,v,vn,vt) values(7,'country_code',1,'at',null,null);
commit;
truncate table pgtestGE$;
insert into pgtestGE$(EID,SVID,DVID,EL,K,T,V,VN,VT) values(1000,1,6,'locatedIn','weight',null,3,1.0,null);
insert into pgtestGE$(EID,SVID,DVID,EL,K,T,V,VN,VT) values(1001,2,6,'locatedIn','weight',null,3,1.0,null);
insert into pgtestGE$(EID,SVID,DVID,EL,K,T,V,VN,VT) values(1002,3,6,'locatedIn','weight',null,3,1.0,null);
insert into pgtestGE$(EID,SVID,DVID,EL,K,T,V,VN,VT) values(1003,4,6,'locatedIn','weight',null,3,1.0,null);
insert into pgtestGE$(EID,SVID,DVID,EL,K,T,V,VN,VT) values(1004,5,7,'locatedIn','weight',null,3,1.0,null);
commit;
select * from pgtestVT$;
select * from pgtestGE$;

Das HR Schema als Property Graph

Zusätzlich soll ein zweiter Graph erstellt werden. Dieser wird mit Daten aus dem HR Schema aus den Oracle Database Examples gefüllt. Die Daten müssen in ein lesbares Format transferiert werden, hier auch wieder das Oracle Flat File Format.

Ein relationales Schema kann recht einfach in ein Property Graph Datenmodell umgewandelt werden. Hier sind die wesentlichen Schritte und zu beachtende Hinweise:

• Die IDs für Knoten und Kanten in den Zieltabellen (xVT$ und xGE$) müssen INTEGER-Werte sein. Daher habe ich für jede Tabelle mit einem Nicht-INTEGER Primärschlüssel eine zusätzliche Spalte mit einem Surrogate Key angelegt.
• Das Ziel sind 2 Tabellen, eine für die Knoten, die andere für Kanten. Über alle Knoten und Kanten soll es eindeutige Schlüssel geben. Daher habe ich jedem Informationstyp ein Offset zugewiesen.
• Alle Spaltennamen einer Tabelle im Ausgangsschema, die nicht Primär− oder Fremdschlüssel sind, werden in die Spalte K übertragen.
• Der Wert einer Spalte wird in Abhängigkeit vom Datentyp entweder in die Spalte V, VN oder VT übertragen. Werte aus VN und VT können zusätzlich noch mittel Datentyp-Umwandlung für eine Volltextindexierung nach V geschrieben werden.
• Fremdschlüssel-Beziehungen werden in Kanten aufgelöst.
• Tabellen, die M:N Beziehungen abbilden, können weitere Spalten beinhalten, die als Attribute von Kanten gespeichert werden.
• Knoten haben keine Etiketten zugeordnet. Es kann aber eine Spalte als Etikett deklariert werden. Für diesen Zweck wird das in den Ausgangsdaten nicht enthaltene Attribut TYPE eingeführt, welches die Art der Information beschreibt.
• Kanten (in der Zieltabelle) tragen Etiketten. Diese beschreiben die Art der Beziehung zwischen den beiden beteiligten Knoten.
• Für bestimmte Algorithmen in der Graphentheorie werden gewichtete Kanten vorausgesetzt. Zu diesem Zweck erhalten alle Kanten das zusätzliche Attribut WEIGHT mit dem Wert 1.0.
• Befüllen der Zieltabellen mit Knoten und Kanten

Die Transformation selbst ist einfaches SQL, also leicht verständlich. Das vollständige SQL Skript befindet sich in diesem GitHub Repository.

--
-- Schema/Nutzer: HR
--

-- Schritt 1: Sequenzen, um Surrogate Keys zu erzeugen
create sequence seq_nodes;
create sequence seq_edges start with 800000;

-- Zusätzliche Spalte mit Surrogate Key f�r Tabellen mit nicht-numerischem Primärschlüssel
alter table jobs add (surrogate_key number(10));
update jobs set surrogate_key = seq_nodes.nextval;

alter table countries add (surrogate_key number(10));
update countries set surrogate_key = seq_nodes.nextval;

commit;

-- Schritte 2 bis 4
create or replace view tmp_regions_nodes
as
select region_id + 100000 as vid
, '_type' as k
, 1 as t
, 'region' as v
, null as vn
, null as vt from hr.regions
union all
select region_id + 100000 as vid
, 'region_name' as k
, 1 as t
, region_name as v
, null as vn
, null as vt from hr.regions
order by 1,2;

create or replace view tmp_jobs_nodes
as
select surrogate_key + 200000 as vid
, '_type' as k
, 1 as t
, 'job' as v
, null as vn
, null as vt from hr.jobs
union all
select surrogate_key + 200000 as vid
, 'job_id' as k
, 1 as t
, job_id as v
, null as vn
, null as vt from hr.jobs
union all
select surrogate_key + 200000 as vid
, 'job_title' as k
, 1 as t
, job_title as v
, null as vn
, null as vt from hr.jobs
union all
select surrogate_key + 200000 as vid
, 'min_salary' as k
, 2 as t
, to_char(min_salary) as v
, min_salary as vn
, null as vt from hr.jobs
union all
select surrogate_key + 200000 as vid
, 'max_salary' as k
, 2 as t
, to_char(max_salary) as v
, max_salary as vn
, null as vt from hr.jobs
order by 1,2;

-- Analog vorgehen für Tabellen LOCATIONS, EMPLOYEES, DEPARTMENTS, COUNTRIES

-- Schritte 5 bis 8
create table tmp_countries_rel_regions as
select seq_edges.nextval as eid
, c.surrogate_key + 700000 as country_id
, r.region_id + 100000 as region_id
from hr.countries c join hr.regions r on c.region_id = r.region_id;

create or replace view tmp_countries_regions_edges
as
select eid
, country_id as svid
, region_id as dvid
, 'is_located_in' as el
, 'weight' as k
, 3 as t
, null as v
, 1.0 as vn
, null as vt from tmp_countries_rel_regions
order by 1,2,3;

create table tmp_departments_rel_locations as
select seq_edges.nextval as eid
, d.department_id + 500000 as department_id
, l.location_id + 300000 as location_id
from hr.departments d join hr.locations l on d.location_id = l.location_id;

create or replace view tmp_departments_locations_edges
as
select eid
, department_id as svid
, location_id as dvid
, 'is_located_in' as el
, 'weight' as k
, 3 as t
, null as v
, 1.0 as vn
, null as vt from tmp_departments_rel_locations
order by 1,2,3;

-- Analog vorgehen für 5 weitere Fremdschlüsselbeziehungen

-- Rechte vergeben auf neu angelegten Tabellen und Views
begin
  for x in (
    select table_name
    from user_tables
    where upper(table_name) like 'TMP%'
  )
  loop
    execute immediate 'grant select on ' || x.table_name || ' to pguser';
  end loop;
end;
/

begin
  for x in (
    select view_name
    from user_views
    where upper(view_name) like 'TMP%'
  )
  loop
    execute immediate 'grant select on ' || x.view_name || ' to pguser';
  end loop;
end;
/


--
-- Schema: PGUSER
--

-- Graph definieren
exec opg_apis.create_pg('hrgraph', 2, 2, 'PGTBS');

-- Knoten laden
insert /*+ APPEND */ into HRGRAPHVT$ (vid,k,t,v,vn,vt)
select * from hr.tmp_countries_nodes where v is not null;
commit;
insert /*+ APPEND */ into HRGRAPHVT$ (vid,k,t,v,vn,vt)
select * from hr.tmp_departments_nodes where v is not null;
commit;
insert /*+ APPEND */ into HRGRAPHVT$ (vid,k,t,v,vn,vt)
select * from hr.tmp_employees_nodes where v is not null;
commit;
insert /*+ APPEND */ into HRGRAPHVT$ (vid,k,t,v,vn,vt)
select * from hr.tmp_jobs_nodes where v is not null;
commit;
insert /*+ APPEND */ into HRGRAPHVT$ (vid,k,t,v,vn,vt)
select * from hr.tmp_locations_nodes where v is not null;
commit;
insert /*+ APPEND */ into HRGRAPHVT$ (vid,k,t,v,vn,vt)
select * from hr.tmp_regions_nodes where v is not null;
commit;

select * from hrgraphvt$;


-- Kanten laden
select * from hrgraphge$;

insert /*+ APPEND */ into hrgraphge$ (eid,svid,dvid,el,k,t,v,vn,vt)
select * from hr.tmp_countries_regions_edges;
commit;
insert /*+ APPEND */ into hrgraphge$ (eid,svid,dvid,el,k,t,v,vn,vt)
select * from hr.tmp_departments_locations_edges;
commit;
insert /*+ APPEND */ into hrgraphge$ (eid,svid,dvid,el,k,t,v,vn,vt)
select * from hr.tmp_departments_managers_edges;
commit;
insert /*+ APPEND */ into hrgraphge$ (eid,svid,dvid,el,k,t,v,vn,vt)
select * from hr.tmp_employees_departments_edges;
commit;
insert /*+ APPEND */ into hrgraphge$ (eid,svid,dvid,el,k,t,v,vn,vt)
select * from hr.tmp_employees_jobs_edges;
commit;
insert /*+ APPEND */ into hrgraphge$ (eid,svid,dvid,el,k,t,v,vn,vt)
select * from hr.tmp_employees_managers_edges;
commit;
insert /*+ APPEND */ into hrgraphge$ (eid,svid,dvid,el,k,t,v,vn,vt)
select * from hr.tmp_locations_countries_edges;
commit;

select * from hrgraphge$;

Analyse eines Property Graph

Bei der Analyse eines Graphen steht häufig im Mittelpunkt, wie über die Knoten und Kanten traversiert werden kann oder welche Muster im Graph erkannt werden. Dafür gibt es eine Vielzahl von Algorithmen aus der Graphentheorie, die Anwendung finden.

Die Unterstützung von Property Graphs für die Oracle Datenbank sieht die Möglichkeit vor, solche Algorithmen als Prozeduren des PL/SQL Pakets OPG_APIS aufzurufen oder von außerhalb der Datenbank über die Java API. Letztere ist sehr umfangreich und beinhaltet vorimplementiert ungefähr 40 Algorithmen. Diese sind in einem Analyse-Framework zusammengefaßt. Die Algorithmen laden den Graph oder Teile davon in den Hauptspeicher und analysieren diesen dort parallel.

Hier und heute möchte mich in diesem Abschnitt darauf beschränken, eine "Kürzeste-Wege"-Berechnung (engl. Shortest Path) mittels des zuvor erwähnten PL/SQL Package durchzuführen. Der dafür verwendete Algorithmus ist Dijkstra. Dieser ermittelt die kürzeste Verbindung zwischen 2 Knoten unter Berücksichtung von Gewichtungen auf den Kanten und gibt diese aus. Als ein einfaches Beispiel nutze ich die hierarchische Struktur von EMPLOYEES und deren Beziehung zu DEPARTMENTS. Der Ausgangsknoten ist dabei das Department mit dem Namen "IT", der Zielknoten ist Employee "Stephen King".

declare
  wt1 varchar2(100);            -- Arbeitstabelle
  n number;
  path    varchar2(1000);
  weights varchar2(1000);
begin
  -- Vorbereitender Schritt
  opg_apis.find_sp_prep('hrgraphGE$', wt1);
  dbms_output.put_line('Arbeitstabelle:  ' || wt1);

  -- Berechnung
  opg_apis.find_sp(
    'hrgraphGE$',
    500060,                     -- Startknoten: Department mit ID 60 (plus Offset)
    400100,                     -- Zielknoten: Employee mit ID 100 (plus Offset)
    wt1,                        -- Arbeitstabelle (für Dijkstra Algorithmus)
    dop => 1,                   -- Grad der Parallelisierung
    stats_freq=>1000,           -- Frequenz zum Sammeln von Statistiken
    path_output => path,        -- Kürzester Weg als Sequenz von Knoten (Shortest Path)
    weights_output => weights,  -- Gewichtung der Kanten
    options => null
  );
  dbms_output.put_line('Pfad:            ' || path);
  dbms_output.put_line('Gewichtungen:    ' || weights);

  -- Aufräumen
  opg_apis.find_sp_cleanup('hrgraphGE$', wt1);
end;
/

Das Ergebnis sieht dann folgermaßen aus:

Arbeitstabelle:  "HRGRAPHGE$$TWFS205"
Pfad:            500060    400103    400102    400100
Gewichtungen:    4    3    1    1   1

Eine solche Abfrage geht natürlich auch mit SQL über Joins und die CONNECT BY Klausel. Je entfernter jedoch die Knoten voneinander liegen, je unterschiedlicher die Informationstypen sind, umso aufwändiger ist die Berechnung in einem relationalen Datenmodell. Je höher der Grad der Komplexität eines Graphen ist, umso effizienter sind die Algorithmen der Graph-Analyse. Wie eingangs schon erwähnt, werde ich auf die Analyse und das Visualisieren von Graphen zu einem späteren Zeitpunkt detailliert eingehen. Als kleine Vorausschau will ich hier aber schon mal den erzeugten HRGRAPH visuell abbilden [Abb. 4].

Abb. 4: HRGRAPH dargestellt mit Cytoscape 3.7.1 (unter Nutzung eines Plugins für die Oracle Datenbank)

Lizenzhinweis

Property Graph ist ein Feature der Option Spatial and Graph, welche die Oracle Datenbank Enterprise Edition voraussetzt. Zusätzlich wird die Option Partitioning benötigt.

Weitere Informationen

• AskTOM "Oracle Spatial and Graph Office Hours". Webinare zum Thema Graph.
• "Property Graph Developer's Guide" als Teil von Oracle Spatial and Graph 18c
• Oracle Spatial and Graph Blog − Graph Features
• "Graph Database From scratch in 45 minus" von Gianni Ceresa, datalys.ch. Vortrag auf ITOUG 2019.

 

Zurück zur Community-Seite