Data Mining mit Bordmitteln - Teil 1

Mit diesem Post möchte ich eine Reihe starten, welche sich mit dem Thema Data Mining beschäftigt; konkret die Implementierung von Algorithmen mit Bordmitteln samt den Besonderheiten, die im Datenbankumfeld zu beachten sind.

Als Beispiel dient ein Algorithmus zur Klassifikation auf der Basis von Entscheidungsbäumen - der ID3-Algorithmus. Doch bevor wir uns mit der Implementierung des Algorithmus beschäftigen, schauen wir uns zunächst das Ergebnis an. Zunächst wird der Algorithmus mit der Prozedur init initialisiert:

exec dm_id3.init(1,10);

Das erste Argument bestimmt das Projekt, während das zweite Argument die minimale Anzahl von Beobachtungen in einem Knoten festlegt; in diesem Fall muss jeder Knoten mindestens 10 Beobachtungen enthalten.

Das Projekt nimmt Bezug auf eine Tabelle, welche die Daten des Data Sets "Chess (King-Rook vs. King)" enthält.

Nach der erfolgreichen Initialisierung erfolgt ein Aufruf der Table-Funtion gain. Man erhält den Gain bzw. den Gain Ratio, also wie sehr sich ein Attribut zur weiteren Zerlegung eignet:

select * from table(dm_id3.gain(0)) order by gain desc;

NODE   ATTRIBUTE          INFO      SPLIT_INFO GAIN     
------ ------------------ --------- ---------- ---------- 
0      BLACK_KING_RANK    3.5041597 3.1896893  0.31446969 
0      WHITE_KING_RANK    3.5041597 3.2139022  0.29025673 
0      BLACK_KING_FILE    3.5041597 3.3190435  0.18511551 
0      WHITE_KING_FILE    3.5041597 3.3388416  0.16531733 
0      WHITE_ROOK_FILE    3.5041597 3.4540855  0.05007348 
0      WHITE_ROOK_RANK    3.5041597 3.4579962  0.04616276 

Man sieht, dass das Attribut "BLACK_KING_RANK" am besten geeignet ist, um eine Zerlegung des Root-Knoten vorzunehmen.

Um den Entscheidungsbaum zu erzeugen, wird die Prozedur make_tree aufgerufen:

exec dm_id3.make_tree(0);

Nun werfen wir einen Blick auf den erzeugten Entscheidungsbaum:

select * from table(dm_id3.show_tree(1));

NODE                              SUPPORT  PREDICTION   CONFIDENCE DEPTH
--------------------------------- -------- ------------ ---------- ------
0: 1 = 1                          28056    fourteen     4553       1
   1: BLACK_KING_RANK = 1         3664     eight        591        2
      9: WHITE_KING_FILE = a      372      eleven       89         3
         49: WHITE_ROOK_RANK = 1  36       draw         10         4
         50: WHITE_ROOK_RANK = 2  48       eight        19         4
         51: WHITE_ROOK_RANK = 3  48       ten          25         4
         52: WHITE_ROOK_RANK = 4  48       twelve       22         4
         53: WHITE_ROOK_RANK = 5  48       eleven       13         4
         54: WHITE_ROOK_RANK = 6  48       fourteen     13         4
         55: WHITE_ROOK_RANK = 7  48       fourteen     13         4
         56: WHITE_ROOK_RANK = 8  48       eleven       12         4
      10: WHITE_KING_FILE = b     620      ten          163        3
...

Man sieht unter anderem, dass das Attribut "BLACK_KING_RANK" tatsächlich für die Zerlegung des Root-Knoten verwendet wurde.

So viel für heute... in den kommenden Postings erfolgt dann die eigentliche Implementierung der eben gezeigten Funktionen.

Ermittlung von Feiertagen per Table Function

Heute geht's um die Ermittlung von Feiertagen in Deutschland; und das wieder mal per Table Function.

Da viele Feiertage (z.B. Rosenmontag) eine Abhängigkeit zum Osterdatum besitzen, benötigt man zunächst eine Funktion zur Berechnung des Osterdatums; genauer gesagt zur Bestimmung von Ostersonntag:

create or replace function easter_day
(
 p_year_in in integer
)
return date
as
 v_k integer;
 v_m integer;
 v_s integer;
 v_a integer;
 v_d integer;
 v_r integer;
 v_og integer;
 v_sz integer;
 v_oe integer;
 v_os integer;
 v_day integer;
 v_month integer;
begin
 v_k := floor(p_year_in / 100);
 v_m := 15 + floor((3 * v_k + 3) / 4) - floor((8 * v_k + 13) / 25);
 v_s := 2 - floor((3 * v_k + 3) / 4);
 v_a := mod(p_year_in, 19);
 v_d := mod((19 * v_a + v_m), 30);
 v_r := floor(v_d / 29) + (floor(v_d / 28) - floor(v_d / 29)) * floor(v_a / 11);
 v_og := 21 + v_d - v_r;
 v_sz := 7 - mod((p_year_in + floor(p_year_in / 4) + v_s), 7);
 v_oe := 7 - mod(v_og - v_sz, 7);
 v_os := v_og + v_oe;
 if (v_os <= 31) then
  v_day := v_os;
  v_month := 3;
 else
  v_day := v_os - 31;
  v_month := 4;
 end if;
 return to_date(v_day || '.' || v_month || '.' || p_year_in, 'DD.MM.YYYY');
end easter_day;

Dabei handelt es sich im Wesentlichen um die ergänzte Osterformel von Carl-Friedrich Gauß; diese wurde durch Hermann Kinkelin und Christian Zeller dahingehend ergänzt, dass Ausnahmeregeln in der Formel berücksichtigt werden. Siehe dazu auch den entsprechenden Eintrag auf der deutschsprachigen Seite von Wikipedia.

Kommen wir nun zur eigentlichen Table-Function, für die zuächst die Objekt-Typen erstellt werden müssen:

create type holiday_t as object
(
 holiday_date date,
 holiday_name varchar2(30),
 holiday_desc varchar2(100)
);
/
create type holiday_tab as table of holiday_t;
/

Die eigentliche Table-Function liefert nun die "Feiertage" der jeweiligen Jahre:

create or replace function german_holidays
(
 p_year_start_in in integer,
 p_year_end_in in integer
) 
return holiday_tab pipelined
as
 v_easter_day date;
begin
 for y in p_year_start_in .. p_year_end_in loop
  
  v_easter_day := easter_day(y);

  pipe row (
   holiday_t(
    to_date('01.01.' || y, 'DD.MM.YYYY'),
    'Neujahrstag',
    'Gesetzlicher Feiertag'));

  pipe row (
   holiday_t(
    to_date('06.01.' || y, 'DD.MM.YYYY'),
    'Heilige Drei Könige',
    'Nur BW, BY und ST'));

  pipe row (
   holiday_t(
    v_easter_day - interval '52' day,
    'Weiberdonnerstag',
    '-'));

  pipe row (
   holiday_t(
    v_easter_day - interval '48' day,
    'Rosenmontag',
    '-'));

  pipe row (
   holiday_t(
    v_easter_day - interval '46' day,
    'Aschermittwoch',
    '-'));

  pipe row (
   holiday_t(
    v_easter_day - interval '3' day,
    'Gründonnerstag',
    '-'));

  pipe row (
   holiday_t(
    v_easter_day - interval '2' day,
    'Karfreitag',
    'Gesetzlicher Feiertag'));

  pipe row (
   holiday_t(
    v_easter_day + interval '1' day,
    'Ostermontag',
    'Gesetzlicher Feiertag'));

  pipe row (
   holiday_t(
    to_date('01.05.' || y, 'DD.MM.YYYY'),
    'Tag der Arbeit',
    'Gesetzlicher Feiertag'));

  pipe row (
   holiday_t(
    v_easter_day + interval '39' day,
    'Christi Himmelfahrt',
    'Gesetzlicher Feiertag'));

  pipe row (
   holiday_t(
    v_easter_day + interval '50' day,
    'Pfingstmontag',
    'Gesetzlicher Feiertag'));

  pipe row (
   holiday_t(
    v_easter_day + interval '60' day,
    'Fronleichnam',
    'Nur BW, BY, HE, NW, RP'));

  pipe row (
   holiday_t(
    to_date('08.08.' || y, 'DD.MM.YYYY'),
    'Augsburger Friedensfest',
    'Nur im Stadtgebiet Augsburg'));

  pipe row (
   holiday_t(
    to_date('08.08.' || y, 'DD.MM.YYYY'),
    'Mariä Himmelfahrt',
    'Nur SL und Teilen von BY'));

  pipe row (
   holiday_t(
    to_date('03.10.' || y, 'DD.MM.YYYY'),
    'Tag der Deutschen Einheit',
    'Gesetzlicher Feiertag'));

  pipe row (
   holiday_t(
    to_date('31.10.' || y, 'DD.MM.YYYY'),
    'Reformationstag',
    'Nur BB, MV, SL, SN und TH'));

  pipe row (
   holiday_t(
    to_date('01.11.' || y, 'DD.MM.YYYY'),
    'Allerheiligen',
    'Nur BW, BY, NW, RP und SL'));

  pipe row (
   holiday_t(
    to_date('11.11.' || y, 'DD.MM.YYYY'),
    'Karnevalsbeginn',
    '-'));

  pipe row (
   holiday_t(
    to_date('25.12.' || y, 'DD.MM.YYYY'),
    '1. Weihnachtstag',
    'Gesetzlicher Feiertag'));

  pipe row (
   holiday_t(
    to_date('26.12.' || y, 'DD.MM.YYYY'),
    '2. Weihnachtstag',
    'Gesetzlicher Feiertag'));

 end loop;
end german_holidays;

Für das Jahr 2012 erhält man dann:

select 
 * 
from 
 table(german_holidays(2012, 2012));

HOLIDAY_DATE  HOLIDAY_NAME                   HOLIDAY_DESC
------------- ------------------------------ ----------------------------
01.01.12      Neujahrstag                    Gesetzlicher Feiertag
06.01.12      Heilige Drei Könige            Nur BW, BY und ST
16.02.12      Weiberdonnerstag               -
20.02.12      Rosenmontag                    -
22.02.12      Aschermittwoch                 -
05.04.12      Gründonnerstag                 -
06.04.12      Karfreitag                     Gesetzlicher Feiertag
09.04.12      Ostermontag                    Gesetzlicher Feiertag
01.05.12      Tag der Arbeit                 Gesetzlicher Feiertag
17.05.12      Christi Himmelfahrt            Gesetzlicher Feiertag
28.05.12      Pfingstmontag                  Gesetzlicher Feiertag
07.06.12      Fronleichnam                   Nur BW, BY, HE, NW, RP
08.08.12      Augsburger Friedensfest        Nur im Stadtgebiet Augsburg
08.08.12      Mariä Himmelfahrt              Nur SL und Teilen von BY
03.10.12      Tag der Deutschen Einheit      Gesetzlicher Feiertag
31.10.12      Reformationstag                Nur BB, MV, SL, SN und TH
01.11.12      Allerheiligen                  Nur BW, BY, NW, RP und SL
11.11.12      Karnevalsbeginn                -
25.12.12      1. Weihnachtstag               Gesetzlicher Feiertag
26.12.12      2. Weihnachtstag               Gesetzlicher Feiertag

Mit Bezug auf das vorherige Posting ergibt sich nun die Möglichkeit, die Zeitdimension um die Feiertage zu erweitern.

Zeitdimension per Table Function erstellen

Heute geht's um die Erstellung einer Zeitdimension mithilfe einer Table-Function. Dazu verwendet man im Wesentlichen die Möglichkeiten der Funktion to_char, wie das folgende Beispiel zeigt.

Zunächst wird der Objekt-Typ erstellt:

create type time_dim_t as object
(
 v_day date,
 v_day_name varchar2(30),
 v_day_of_week integer,
 v_day_of_month integer,
 v_day_of_year integer,
 v_week integer,
 v_week_start date,
 v_week_end date,
 v_iso_week integer,
 v_iso_week_start date,
 v_iso_week_end date,
 v_month integer,
 v_month_name varchar2(30),
 v_month_start date,
 v_month_end date,
 v_month_days integer,
 v_quarter integer,
 v_quarter_name varchar(2),
 v_quarter_start date,
 v_quarter_end date,
 v_quarter_days integer,
 v_year integer,
 v_year_start date,
 v_year_end date,
 v_year_days integer,
 v_is_leap_year varchar2(1)
);
/

Hinzu kommt der Table-Typ:

create type time_dim_tab as table of time_dim_t;
/

Damit sind alle Vorbereitungen getroffen, um die Table-Function zu erstellen:

create or replace function time_dim
(
 p_year_start_in in integer,
 p_year_end_in in integer
) 
return time_dim_tab pipelined
as
 v_day date;
 v_day_name varchar2(30); 
 v_day_of_week integer;
 v_day_of_month integer;
 v_day_of_year integer; 
 v_week integer;
 v_week_start date;
 v_week_end date;
 v_iso_week integer;
 v_iso_week_start date;
 v_iso_week_end date;
 v_month integer;
 v_month_name varchar2(30);
 v_month_start date;
 v_month_end date;
 v_month_days integer;
 v_quarter integer;
 v_quarter_name varchar(2);
 v_quarter_start date;
 v_quarter_end date;
 v_quarter_days integer;
 v_year integer;
 v_year_start date;
 v_year_end date;
 v_year_days integer;
 v_is_leap_year varchar2(1);
begin

 begin

  for y in p_year_start_in .. p_year_end_in loop
   
   v_year := y;
   v_year_start := to_date('01.01.' || v_year, 'DD.MM.YYYY');
   v_year_end := to_date('31.12.' || v_year, 'DD.MM.YYYY');
   v_year_days := v_year_end - v_year_start + 1;
  
   if (v_year_days = 366) then
    v_is_leap_year := 'Y';
   else
    v_is_leap_year := 'N';
   end if;
   
   for q in 1 .. 4 loop
   
    v_quarter := q;
    v_quarter_name := 'Q' || v_quarter;
    case v_quarter_name
     when 'Q1' then
      v_quarter_start := to_date('01.01.' || v_year, 'DD.MM.YYYY');
      v_quarter_end := to_date('31.03.' || v_year, 'DD.MM.YYYY');
     when 'Q2' then
      v_quarter_start := to_date('01.04.' || v_year, 'DD.MM.YYYY');
      v_quarter_end := to_date('30.06.' || v_year, 'DD.MM.YYYY');
     when 'Q3' then
      v_quarter_start := to_date('01.07.' || v_year, 'DD.MM.YYYY');
      v_quarter_end := to_date('30.09.' || v_year, 'DD.MM.YYYY');
     when 'Q4' then
      v_quarter_start := to_date('01.10.' || v_year, 'DD.MM.YYYY');
      v_quarter_end := to_date('31.12.' || v_year, 'DD.MM.YYYY');
    end case;
    v_quarter_days := v_quarter_end - v_quarter_start + 1;
    
    for m in to_number(to_char(v_quarter_start, 'MM')) .. 
             to_number(to_char(v_quarter_end, 'MM')) loop
   
     v_month := m;
     v_month_start := to_date('01.' || v_month || '.' || v_year, 'DD.MM.YYYY');
     v_month_end := last_day(v_month_start);
     v_month_days := v_month_end - v_month_start + 1;
     v_month_name := to_char(v_month_start, 'MONTH');
 
     for d in 1 .. v_month_days loop
     
      v_day := to_date(d || '.' || v_month || '.' || v_year, 'DD.MM.YYYY');
      v_day_of_week := to_number(to_char(v_day, 'D'));
      v_day_of_month := to_number(to_char(v_day, 'DD'));
      v_day_of_year := to_number(to_char(v_day, 'DDD'));
      v_day_name := to_char(v_day, 'DAY');
      v_week := to_number(to_char(v_day, 'WW'));
      v_week_start := trunc(v_day, 'WW');
      v_week_end := v_week_start + interval '6' day;
      v_iso_week := to_number(to_char(v_day, 'IW'));
      v_iso_week_start := trunc(v_day, 'IW');
      v_iso_week_end := v_iso_week_start + interval '6' day;
 
      pipe row
     (
      time_dim_t
      (
       v_day,
       v_day_name,
       v_day_of_week,
       v_day_of_month,
       v_day_of_year,
       v_week,
       v_week_start,
       v_week_end,
       v_iso_week,
       v_iso_week_start,
       v_iso_week_end,
       v_month,
       v_month_name,
       v_month_start,
       v_month_end,
       v_month_days,
       v_quarter,
       v_quarter_name,
       v_quarter_start,
       v_quarter_end,
       v_quarter_days,
       v_year,
       v_year_start,
       v_year_end,
       v_year_days,
       v_is_leap_year 
      )
     );  
     end loop;
    
    end loop;
    
   end loop;
   
  end loop;

 end;

end;

Ein Aufruf der Table-Function für die Jahre 2011 und 2012 sieht dann wie folgt aus:

select * from table(time_dim(2011, 2012));

Auf der Grundlage dieser Table-Function kann dann eine Zeitdimension erstellt werden; sei es als Star- oder Snowflake-Schema, was durch entsprechende Projektionen erreicht werden kann.

Eine Ergänzung wäre die Angabe von Feiertagen, welche oftmals im iCal-Format bereitstehen. Vielleicht widme ich ein weiteres Posting diesem Thema, um zu zeigen, wie man dieses Format in SQL bereitstellen kann.

Dynamischer Rückgabetyp bei Table Functions

Heut geht's um den Einsatz von Table Functions, die einen dynamischen Rückgabetyp besitzen.

Der normale Fall sieht dabei wie folgt aus:

Man erstellt einen Objekt-Typ und gibt die Attribute mit Namen und Typ an.

create type val_t as object
(
 v1 number,
 v2 number,
 v3 number
);
/

Jetzt fehlt noch der Table-Typ von dem gerade erstellen Objekt-Typ.

create type val_tab as table of val_t;
/

Die Table-Function soll nun das Einmaleins bis 3 ausgeben.

create or replace function multiplication_table return val_tab pipelined is
 v_column_count integer := 3;
begin
 for i in 1..v_column_count loop
  pipe row ( val_t (i*1,i*2,i*3) );
 end loop;
 return;
end multiplication_table;

Soweit so gut, jedoch wollen wir auch das Einmaleins bis 5, 10, 100 oder einer anderen natürlichen Zahl n, ohne dafür jeweils eine eigene Table Function samt den notwendigen Objekt-Typen erstellen zu wollen.

Dazu sind einige Funktionen zu implementieren, welche es erlauben, den Rückgabetyp dynamisch zu erstellen. Für die Aufgabe ergibt sich folgenden Struktur:

create or replace type multiplication_table as object
(
 v_row_types anytype,
 v_column_count integer,
 v_rows_processed integer,
 
 static function show_table(
  p_column_count_in in integer
 ) return anydataset pipelined using multiplication_table,
 
 static function ODCITableDescribe(
  rtype out anytype, 
  p_column_count_in in integer
 ) return number,
 
 static function ODCITablePrepare(
  sctx out multiplication_table, 
  tf_info SYS.ODCITabFuncInfo,
  p_column_count_in in integer
 ) return number,
 
 static function ODCITableStart(
  sctx in out multiplication_table, 
  p_column_count_in in integer
 ) return number,

 member function ODCITableFetch(
  self in out multiplication_table, 
  nrows in number, 
  rws out anydataset
 ) return number,

 member function ODCITableClose(
  self in multiplication_table 
 ) return number
);

Dabei wird der Rückgabetyp durch die Funktion ODCITableDescribe beschrieben, also die Anzahl und Typen der Attribute festgelegt. Konkret für die Lösung der Aufgabe bedeutet dies, das für das Einmaleins bis n auch n Attribute vorhanden sein müssen. Die Funktion ODCITableFetch liefert dann die Zeilen zurück, indem die Bestandteile des Objekt-Typs mit Werten gefüllt werden.

create or replace type body multiplication_table as

  static function ODCITableDescribe(
   rtype out anytype, 
   p_column_count_in in integer
  ) return number as
   v_record_structure anytype;
  begin
   anytype.begincreate(dbms_types.typecode_object, v_record_structure);
   for i in 1 .. p_column_count_in loop
    v_record_structure.addattr(   
       ANAME     => '#' || to_char(i),
       TYPECODE  => dbms_types.typecode_number,
       PREC      => null,
       SCALE     => null,
       LEN       => null,
       CSID      => null,    
       CSFRM     => null,
       ATTR_TYPE => null
     );
   end loop;
   v_record_structure.endcreate();
   anytype.begincreate(dbms_types.typecode_table, rtype); 
   rtype.setinfo(
    null, 
    null, 
    null, 
    null, 
    null, 
    v_record_structure, 
    dbms_types.typecode_object, 
    0); 
   rtype.endcreate(); 
   return odciconst.success;
  end ODCITableDescribe;

  static function ODCITablePrepare(
   sctx out multiplication_table, 
   tf_info SYS.ODCITabFuncInfo,
   p_column_count_in in integer
  ) return number as
   prec pls_integer; 
   scale pls_integer; 
   len pls_integer; 
   csid pls_integer; 
   csfrm pls_integer; 
   record_desc anytype; 
   aname varchar2(30); 
   dummy pls_integer;
  begin 
   dummy := tf_info.RetType.GetAttrElemInfo(
    null, 
    prec, 
    scale, 
    len, 
    csid, 
    csfrm, 
    record_desc, 
    aname); 
   sctx := multiplication_table(record_desc, p_column_count_in, 0); 
   return odciconst.success; 
  end ODCITablePrepare;

  static function ODCITableStart(
   sctx in out multiplication_table, 
   p_column_count_in in integer
  ) return number as
  begin
   return odciconst.success; 
  end ODCITableStart;

  member function ODCITableFetch(
   self in out multiplication_table, 
   nrows in number, 
   rws out anydataset
  ) return number as
  begin
   rws := null; 
   if (self.v_rows_processed < self.v_column_count) then
    self.v_rows_processed := self.v_rows_processed + 1;
    anydataset.begincreate(dbms_types.typecode_object, self.v_row_types, rws); 
    rws.addinstance;
    rws.piecewise();
    for i in 1 .. self.v_column_count loop
     rws.setnumber(self.v_rows_processed * i);
    end loop;
    rws.endcreate;
   end if;
   return odciconst.success;
  end ODCITableFetch;

  member function ODCITableClose(
   self in multiplication_table 
  ) return number as
  begin
   return odciconst.success; 
  end ODCITableClose;

end;

Ein Aufruf mit dem Argument 4 liefert dann:

select * from table(multiplication_table.show_table(4));

#1      #2      #3      #4                     
------- ------- ------- -------
1       2       3       4                      
2       4       6       8                      
3       6       9       12                     
4       8       12      16                     

Während die Wahl des Arguments 6 einen Objekt-Typ mit zwei zusätzlichen Spalten zur Folge hat:

select * from table(multiplication_table.show_table(6));

#1      #2      #3      #4      #5      #6                 
------- ------- ------- ------- ------- -------
1       2       3       4       5       6              
2       4       6       8       10      12           
3       6       9       12      15      18               
4       8       12      16      20      24              
5       10      15      20      25      30
6       12      18      24      30      36

Weitere Informationen dazu findet man im Data Cartridge Developer's Guide.

Berechnung der Potenzmenge mithilfe von POWERMULTISET

Heute geht's um die Berechnung der Potenzmenge mithilfe der vorhandenen Table Function POWERMULTISET. Als Potenzmenge bezeichnet man die Menge aller Teilmengen einer gegebenen Grundmenge. Die Potenzmenge einer endlichen Menge mit n Elementen enthält 2ⁿ Elemente. Nehmen wir als Beispiel die Menge M = { 1, 2, 3 }. Da es sich um eine endliche Menge mit 3 Elementen handelt, enthält die Potenzmenge 2³ = 8 Elemente, die da wären:

1.  {   }
2.  { 1 }
3.  { 2 }
4.  { 3 }
5.  { 1, 2 }
6.  { 1, 3 }
7.  { 2, 3 }
8.  { 1, 2, 3 }

Anmerkung: Eine Menge enthält keine Ordnung, sodass z.B. { 1, 2 } = { 2, 1 } ist.

Die Table Function POWERMULTISET erwartet als Argument eine Nested Table. Dazu erstellen wir zunächst den entsprechenden Typ:

create type num_nt as table of integer;
/

Jetzt kann die Funktion aufgerufen werden:

select 
 column_value 
from 
 table(powermultiset(num_nt(1,2,3)))
order by 
 cardinality(column_value);

Man erhält nun die folgenden sieben Zeilen:

COLUMN_VALUE
----------------------------
EXAMPLE.NUM_NT('1')
EXAMPLE.NUM_NT('2')
EXAMPLE.NUM_NT('3')
EXAMPLE.NUM_NT('1','2')
EXAMPLE.NUM_NT('1','3')
EXAMPLE.NUM_NT('2','3')
EXAMPLE.NUM_NT('1','2','3')

Man erkennt, dass eine Teilmenge fehlt: die leere Menge; somit verhält sich die Implementierung leider nicht ganz so wie in der Mathematik.

Neben der Table Function POWERMULTISET gibt es auch die Table Function POWERMULTISET_BY_CARDINALITY, die alle Teilmengen zu einer gegebenen Kardinalität zurückgibt. Man erhält alle zwei-elementigen Teilmengen mithilfe der folgenden Abfrage:

select
 column_value
from 
 table(powermultiset_by_cardinality(num_nt(1,2,3),2));

Man erhält die folgenden drei Zeilen:

COLUMN_VALUE
----------------------------
EXAMPLE.NUM_NT('1','2')
EXAMPLE.NUM_NT('1','3')
EXAMPLE.NUM_NT('2','3')

Also wiedermal ein nettes Feature, welches man mitunter bei einigen Problemen verwenden kann.

Dijkstra-Algorithmus mit PL/SQL

Der Algorithmus von Edsger W. Dijkstra dient der Ermittlung der kürzesten Pfade ausgehend von einem Startknoten zu allen anderen Knoten in einem Graphen.

Die Darstellung des Graphen erfolgt in Form einer einfachen Tabelle mit den Spalten ID, SOURCE, DESTINATION und DISTANCE.

Als Beispiel dient der folgende Graph:



Die zugehörige Tabelle stellt sich dann wie folgt dar:

        ID     SOURCE DESTINATION DISTANCE
---------- ---------- ----------- --------
         1          1           2        4
         1          1           3        6
         1          1           4        8
         1          2           5        7
         1          2           3        1
         1          3           4        2
         1          3           5        5
         1          3           6        4
         1          4           6        5
         1          5           7        6
         1          6           5        1
         1          6           7        8

Auf dieser Grundlage sollen jetzt die kürzesten Wege ausgehend von Knoten 1 gefunden werden, wenngleich von jedem Knoten begonnen werden kann.

Der Aufruf der PL/SQL-Table-Function geht so:

select * from table(dijkstra(1,1)) order by vertex;

    VERTEX DISTANCE PREDECESSOR PATH
---------- -------- ----------- -----------------------
         1        0             1
         2        4           1 1 -> 2
         3        5           2 1 -> 2 -> 3
         4        7           3 1 -> 2 -> 3 -> 4
         5       10           3 1 -> 2 -> 3 -> 5
         6        9           3 1 -> 2 -> 3 -> 6
         7       16           5 1 -> 2 -> 3 -> 5 -> 7

Die Spalte DISTANCE gibt die minimale Distanz zum jeweiligen Knoten an, die Spalte PREDECESSOR enthält den direkten Vorgänger und die Spalte PATH enthält die Knoten, welche auf dem kürzesten Weg zurückgelegt wurden.

Nach dieser kurzen Demonstration der Funktionsweise hier der zugehörige Code:

-- Tabelle

drop table graph;

create table graph
(
 id integer,
 source integer,
 destination integer,
 distance number(38,2) not null
);

alter table graph
add constraint pk_graph
primary key (id, source, destination);

alter table graph
add constraint c_graph_source
check (source > 0);

alter table graph
add constraint c_graph_destination
check (destination > 0);

alter table graph
add constraint c_graph_distance
check (distance >= 0);

-- Daten

insert into graph(id,source,destination,distance)
values(1,1,2,4);
insert into graph(id,source,destination,distance)
values(1,1,3,6);
insert into graph(id,source,destination,distance)
values(1,1,4,8);
insert into graph(id,source,destination,distance)
values(1,2,5,7);
insert into graph(id,source,destination,distance)
values(1,2,3,1);
insert into graph(id,source,destination,distance)
values(1,3,4,2);
insert into graph(id,source,destination,distance)
values(1,3,5,5);
insert into graph(id,source,destination,distance)
values(1,3,6,4);
insert into graph(id,source,destination,distance)
values(1,4,6,5);
insert into graph(id,source,destination,distance)
values(1,5,7,6);
insert into graph(id,source,destination,distance)
values(1,6,5,1);
insert into graph(id,source,destination,distance)
values(1,6,7,8);
commit;

-- Type

drop type dijkstra_tab;

drop type dijkstra_t;

create type dijkstra_t as object
(
 vertex integer,
 distance binary_double,
 predecessor integer,
 path varchar2(4000)
);
/

create type dijkstra_tab as table of dijkstra_t;
/

-- Table function

create or replace
function dijkstra(p_graph_in in binary_integer, p_vertex_in in binary_integer) return dijkstra_tab pipelined
is
 
 graph_not_found exception;
 vertex_not_found exception;
 
 type unchecked_tab is table of binary_integer index by binary_integer;
 type predecessor_tab is table of binary_integer index by binary_integer;
 type distance_tab is table of binary_double index by binary_integer;
 
 cursor init_cur is
  select source vertex
  from graph
  where id = p_graph_in
   union
  select destination vertex
  from graph
  where id = p_graph_in;

 cursor distance_cur(pc_vertex_in in binary_integer) is
  select destination, distance
  from graph
  where id = p_graph_in and source = pc_vertex_in;
 
 i binary_integer;
 v_dummy varchar(10);
 v_unchecked unchecked_tab;
 v_predecessor predecessor_tab;
 v_distance distance_tab;
 v_minimum binary_integer;
 v_alternative binary_double;
 v_path varchar2(4000);
 
begin

 begin
  select 'TRUE' into v_dummy
  from dual
  where exists
  (
   select *
   from graph
   where id = p_graph_in
  );
 exception
  when no_data_found then
   raise graph_not_found;
 end;
 
 begin
  select 'TRUE' into v_dummy
  from dual
  where exists
  (
   select *
   from graph
   where id = p_graph_in and (source = p_vertex_in or destination = p_vertex_in)
  );
 exception
  when no_data_found then
   raise vertex_not_found;
 end;
 
 begin
  for init_rec in init_cur loop
   v_unchecked(init_rec.vertex) :=  null;
   v_predecessor(init_rec.vertex) := null;
   v_distance(init_rec.vertex) := binary_double_infinity;
  end loop;
  v_distance(p_vertex_in) := 0;
 end;

 begin
  while (v_unchecked.count > 0) loop
   v_minimum := null;
   i := v_unchecked.first;
   while (i is not null) loop
    if (v_minimum is null) then
     v_minimum := i;
    else
     if (v_distance(i) < v_distance(v_minimum)) then
      v_minimum := i;
     end if;
    end if;
    i := v_unchecked.next(i);
   end loop;
   v_unchecked.delete(v_minimum);
   for distance_rec in distance_cur(v_minimum) loop
    if (v_unchecked.exists(distance_rec.destination)) then
     v_alternative := v_distance(v_minimum) + distance_rec.distance;
     if (v_alternative < v_distance(distance_rec.destination)) then
      v_distance(distance_rec.destination) := v_alternative;
      v_predecessor(distance_rec.destination) := v_minimum;
     end if;
    end if;
   end loop;
   if (v_distance(v_minimum) = binary_double_infinity) then
    v_path := '';
   else
    v_path := v_minimum;
   end if;
   i := v_predecessor(v_minimum);
   while (i is not null) loop
    v_path :=  i || ' -> ' || v_path;
    i := v_predecessor(i);
   end loop;
   pipe row( dijkstra_t (
    v_minimum, 
    v_distance(v_minimum), 
    v_predecessor(v_minimum), 
    v_path ) );
  end loop;
 end;

exception
 when graph_not_found then
  raise_application_error(-20010, 'DIJKSTRA: The graph was not found.');
 when vertex_not_found then
  raise_application_error(-20011, 'DIJKSTRA: The vertex to start the algorithm was not found.');
 when others then
  raise_application_error(-20012, 'DIJKSTRA: Unexpected error: ' || substr(1,200,SQLERRM)); 
end;