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.