Systematische Herleitung von SQL durch Logik

Heute geht's um die Verwendung von Logik zur systematischen Herleitung von SQL. Gesucht wird eine Abfrage, um die Mitarbeiter auszugeben, welche an allen Projekten beteiligt sind. Dazu werden die bekannten Tabellen EMP und DEPT um die Tabellen PROJECT und EMP_PROJECT erweitert. Die Tabelle PROJECT speichert Projekte während die Tabelle EMP_PROJECT eine Zuordnung von Mitarbeitern zu Projekten vornimmt.

create table project
(
 pno integer not null,
 pname varchar2(15) not null,
 constraint pk_project primary key (pno)
);

create table emp_project
(
 empno integer not null,
 pno integer not null,
 percentage number(5,2) not null,
 constraint pk_emp_project primary key (empno, pno)
);

alter table emp_project
add constraint fk_emp_project_emp
foreign key (empno)
references emp (empno);

alter table emp_project
add constraint fk_emp_project_project
foreign key (pno)
references project (pno);

insert into project (pno, pname)
values (1, 'X100C');
insert into project (pno, pname)
values (2, 'P00A1');
insert into project (pno, pname)
values (3, 'P00A2');

insert into emp_project (empno, pno, percentage)
values (7369, 2, 30.00);
insert into emp_project (empno, pno, percentage)
values (7521, 1, 25.00);
insert into emp_project (empno, pno, percentage)
values (7566, 1, 10.00);
insert into emp_project (empno, pno, percentage)
values (7521, 2, 50.00);
insert into emp_project (empno, pno, percentage)
values (7521, 3, 50.00);
insert into emp_project (empno, pno, percentage)
values (7654, 3, 75.00);
insert into emp_project (empno, pno, percentage)
values (7654, 1, 5.00);
insert into emp_project (empno, pno, percentage)
values (7788, 1, 100.00);
insert into emp_project (empno, pno, percentage)
values (7844, 2, 65.00);
insert into emp_project (empno, pno, percentage)
values (7934, 2, 15.00);
insert into emp_project (empno, pno, percentage)
values (7900, 1, 80.00);

commit;

Kommen wir nun zurück zur Fragestellung, welche Mitarbeiter an allen Projekten beteiligt sind. Alternativ könnte man das auch so formulieren:

"Ausgabe aller Mitarbeiter für die für alle Projekte eine entsprechende Projektzuordnung exstiert".

Genau dafür gibt es den Allquantor (FORALL) und den Existenzquantor (EXISTS) aus der Prädikatenlogik.

FORALL x ( p( x ) ) ist genau dann wahr, wenn für alle x das Prädikat p( x ) wahr ist. Also handelt es sich im Wesentlichen um eine Kurzschreibweise für eine UND-Verknüpfung der Form:

p( x1 ) AND p( x2 ) AND ... AND p( xn )

EXISTS x ( p( x ) ) ist genau dann wahr, wenn ein x existiert, für das dass Prädikat p( x ) wahr ist. Also handelt es sich im Wesentlichen um eine ODER-Verknüpfung der Form:

p( x1 ) OR p( x2 ) OR ... OR p( xn )

Eine mögliche Formulierung mit dem Allquantor (FORALL) und dem Existenzquantor (EXISTS) sieht dann so aus:

{ E } WHERE
       FORALL P ( 
        EXISTS EP ( EP.EMPNO = E.EMPNO AND EP.PNO = P.PNO ) )

Da SQL kein FORALL unterstützt macht man sich folgende Regel zu Nutze:

FORALL x ( p( x ) ) ≡ NOT EXISTS ( NOT p( x ) )

Eine Anwendung auf die erste Formulierung ergibt dann:

{ E } WHERE
       NOT EXISTS P ( 
        NOT EXISTS EP ( EP.EMPNO = E.EMPNO AND EP.PNO = P.PNO ) )

Diese Variante kann man fast eins zu eins in SQL überführen:

select *
from emp e
where not exists
(
 select * 
 from project p
 where not exists
 (
  select *
  from emp_project ep
  where ep.empno = e.empno and ep.pno = p.pno
 )
);

Damit erhält man eine Lösung für die Problemstellung, auf die man so mitunter nicht direkt kommt.

Mit etwas Übung und den notwendigen Kenntnissen aus dem Bereich der Logik kann man damit "trial and error" bei vielen Problemen vermeiden und eine Lösung systematisch aus einer logischen Formulierung herleiten.

Als weiterführende Literatur zu diesem Thema sei das Buch "SQL and Relational Theory" von Chris Date und das Buch "Applied Mathematics for Database Professionals" von Lex de Haan und Toon Koppelaars empfohlen.

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.

Multiple Regression mit UTL_NLA

Heute geht's erneut um die multiple Regression, die in diesem Beispiel mithilfe von UTL_NLA durchgeführt wird. UTL_NLA stellt dazu BLAS (Basic Linear Algebra Subroutines) und LAPACK (Linear Algebra PACKage) bereit.

Wie im vorherigen Post zu diesem Thema, werden die folgenden Daten verwendet:

y = Nachgefragte Menge in 1000 Stück
x₁ = Werbeausgaben in 100.000 Euro für Printmedien
x₂ = Werbeausgaben in 100.000 Euro für Fernsehen
x₃ = Preis pro Mengeneinheit in 100 Euro

y	x1	x2	x3
500	1	1	20
800	3	1	20
1500	3	3	18
2500	6	4	15
3200	6	6	12

Man erhält die Koeffizienten der Regressionsfunktion in Form des Vektors b durch:

Die Matrix X im Beispiel:

Der Vektor y im Beispiel:

Die Berechnung des Vektors b umfasst also die Bestimmung der Inversen, die Multiplikation von Matrizen und die Multiplikation einer Matrix mit einem Vektor. All diese Operationen lassen sich mithilfe von UTL_NLA durchführen. Für die Multiplikation von Matrizen wird BLAS_GEMM verwendet, für die Multiplikation einer Matrix mit einem Vektor wird BLAS_GEMV verwendet und für die Lösung des Gleichungssystems kommt LAPACK_GESV zum Einsatz.

Die Werte für die Matrizen werden entweder Zeilen- oder Spaltenweise angeben, je nachdem für welches Argument man sich für den Parameter PACK entscheidet. Im folgenden Beispiel wurde als Argument für den Parameter PACK 'R' gewählt. Die Deklaration stellt sich dann wie folgt dar:

v_matrix_xt UTL_NLA_ARRAY_DBL := UTL_NLA_ARRAY_DBL(  1 , 1 , 1 , 1 , 1, 
                                                     1 , 3 , 3 , 6 , 6, 
                                                     1 , 1 , 3 , 4 , 6,
                                                     20, 20, 18, 15, 12 );
 
v_matrix_x UTL_NLA_ARRAY_DBL := UTL_NLA_ARRAY_DBL(   1 , 1 , 1 , 20,
                                                     1 , 3 , 1 , 20,
                                                     1 , 3 , 3 , 18,
                                                     1 , 6 , 4 , 15, 
                                                     1 , 6 , 6 , 12 ); 

Der Aufruf der Prozedur UTL_NLA.BLAS_GEMM ermittelt nun die Matrix X^TX.

UTL_NLA.BLAS_GEMM(
   transa => 'N',
   transb => 'N',
   m      => 4,
   n      => 4,
   k      => 5,
   alpha  => 1,
   a      => v_matrix_xt,
   lda    => 5,
   b      => v_matrix_x,
   ldb    => 4,
   beta   => 0,
   c      => v_matrix_xtx,
   ldc    => 4,
   pack   => 'R');

Nun wird der Vektor X^Ty mithilfe von UTL_NLA.BLAS_GEMV bestimmt:

UTL_NLA.BLAS_GEMV(
   trans  => 'N',
   m      => 4,
   n      => 5,
   alpha  => 1,
   a      => v_matrix_xt,
   lda    => 5,
   x      => v_vector_y,
   incx   => 1,
   beta   => 0,
   y      => v_vector_xty,
   incy   => 1,
   pack   => 'R');

Im finalen Schritt, zur Bestimmung der Koeffizienten, ist das folgende Gleichungssystem zu lösen:

X^TXb=X^Ty

Diese Aufgabe erledigt die Prozedur UTL_NLA.LAPACK_GESV, wobei sich das Ergebnis nach dem Aufruf in der Variablen befindet, die als Argument für den Parameter b übergeben wurde.

UTL_NLA.LAPACK_GESV(
   n      => 4,
   nrhs   => 1,
   a      => v_matrix_xtx,
   lda    => 4,
   ipiv   => v_matrix_p,
   b      => v_vector_xty,
   ldb    => 1,
   info   => v_result,
   pack   => 'R');

Die Ausgabe der Koeffizienten ergibt:

for i in 1..v_vector_xty.count loop
 dbms_output.put_line('b' || (i-1) || ' = ' || to_number(v_vector_xty(i)));
end loop;

b0 = 1440.8163265303169
b1 = 168.36734693877926
b2 = 266.32653061226313
b3 = -69.38775510202751

Die Regressionsfunktion ergibt sich somit zu:

y = 1440,8163 + 168,3673∙x₁ + 266,3265∙x₂ - 69,3878∙x₃

Abschließend sei noch erwähnt, dass eine Matrix bzw. ein Vektor vom Typ UTL_NLA_ARRAY_DBL bzw. UTL_NLA_ARRAY_FLT maximal 1.000.000 Elemente enthalten kann.

Natürlich befinden sich die Daten meist in einer Tabelle und man will die Matrix nicht manuell angeben. Vielmehr möchte man die Elemente durch SQL und PL/SQL gewinnen und in einer Variablen vom entsprechenden Typ speichern.

Aber das ist was für einen anderen Post...

BINARY_DOUBLE und die implizite Typ-Konvertierung

Heute geht's um die Verwendung des Datentyps BINARY_DOUBLE bzw. BINARY_FLOAT und die Vermeidung von impliziter Typ-Konvertierung.

Als Beispiel dient das Wallis-Produkt zur Berechnung der Kreiszahl Pi. Die Berechnung erfolgt durch den folgenden anonymen PL/SQL-Block:

declare
 v_pi binary_double := 1.0;
begin
 for i in 1 .. 1000000 loop
  v_pi := v_pi * (1.0 + (1.0 / (4.0 * i * i - 1.0)));
 end loop;
 v_pi := v_pi * 2.0;
 dbms_output.put_line(v_pi);
end;
/
3,1415918681921307E+000

PL/SQL-Prozedur erfolgreich abgeschlossen.

Abgelaufen: 00:00:05.07

Die Berechnung dauert ungefähr fünf Sekunden und gibt die Zahl Pi bis auf fünf Stellen genau an. Doch an welcher Stelle befindet sich nun das Optimierungspotenzial?

Literale vom Typ BINARY_DOUBLE bzw. BINARY_FLOAT enthalten den Buchstaben d (D) bzw. f (F). Ansonsten handelt es sich um Literale vom Typ NUMBER, die im vorherigen PL/SQL-Block zur Typ-Konvertierung geführt haben.

Der angepasste PL/SQL-Block sieht dann wie folgt aus:

declare
 v_pi binary_double := 1.0d;
begin
 for i in 1 .. 1000000 loop
  v_pi := v_pi * (1.0d + (1.0d / (4.0d * i * i - 1.0d)));
 end loop;
 v_pi := v_pi * 2.0d;
 dbms_output.put_line(v_pi);
end;
/
3,1415918681921489E+000

PL/SQL-Prozedur erfolgreich abgeschlossen.

Abgelaufen: 00:00:00.46

Jetzt reduziert sich die Dauer der Berechnung deutlich auf unter eine Sekunde.

Also sollte man bei der Verwendung von BINARY_DOUBLE bzw. BINARY_FLOAT stets auf die korrekte Angabe von Literalen achten.