Datenbanken in Prolog SQL-Anweisungen und -Abfragen in Prolog umsetzen

Eine Ausarbeitung von Philipp Hauer vom 28.05.2008. ©

Inhalt

Logischer Ablauf Exkurse
  1. Vorwort
  2. Grundlagen
    1. Definition einer Datenbasis
    2. Projektion
    3. Selektion
    4. Projektion mit Selektion
    5. UND/ODER-Verknüpfungen
    6. Join - Verknüpfung von Tabellen
    7. INSERT und DELETE: Einfügen und Löschen von Datensätzen
  3. Fortgeschrittenes
    1. Suchen ohne Sortieren
    2. Suchen und Sortieren
    3. Selektion mit Joker und Platzhalter
    4. Aggregatfunktionen
      1. Anzahl
      2. Summe
      3. Minimum und Maximum
      4. Durchschnitt
  4. Zusammenfassung der Systemprädikate
  1. Vergleichsoperatoren
  2. fail
  3. Suchen mit findall/3
  4. Sortieren mit sort/2 und msort/2
  5. String-Analyse und -Manipulation mit sub_string/5
  6. Entfernen von Duplikaten in Listen
  7. Länge von Listen bestimmen
  8. Summe von Listenelementen ermitteln
  9. Minima und Maxima von Listen ermitteln
  10. Komplexität der Listenbildung
Beispieldatenbanken
  1. Kontaktbuch
  2. Monatsnamen
  3. Bestellungen
  4. Zeugnisse

Vorwort

SQL, eine Programmiersprache der 4. Generation, wurde speziell zum Erstellen, Verwalten und Manipulieren von Datenbanken erschaffen. Im Folgenden möchte ich zeigen, dass sich viele Funktionalitäten von SQL auch in Prolog, einer Programmiersprache der 5. Generation, realisieren lassen. Dabei beginnen wir bei einfachen SQL-Anweisungen und arbeiten uns zu komplizierteren Abfragen und Aggregatfunktionen vor.

Dabei geht es vor allem darum, möglichst viele verschiedene Lösungsansätze und -tricks aufzuzeigen, sodass man mit den erlernten Mitteln später selber arbeiten, variieren und neu kombinieren kann.

Grundlagen

Definition einer Datenbasis

Es soll eine Datenbank für ein Handy-Adressbuch mit Informationen zu den Kontakten erstellt werden:

Name Telefonnummer Geburtstag Geburtsmonat Geburtsjahr
Meier 01712350393 21 01 1988
Wolf 029185930292 01 05 1985
Engel 021394210239 14 09 1988
Muse 03924019510 19 02 1997

Dazu wird jeder Datensatz (jede Zeile) als Fakt in Prolog abgelegt, wobei ein Argument für ein Datenfeld/Spalte steht:

%% person(Name, Telefonnummer, Geburtstag, Geburtsmonat, Geburtsjahr).
person('Meier', 01712350393,21,01,1988).
person('Wolf', 029185930292,01,02,1985).
person('Engel', 021394210239,14,09,1988).
person('Muse', 03924019510,19,02,1997).

Die Daten Geburtstag, Geburtsmonat und Geburtsjahr lassen sich noch schachteln. Das vereinfacht später das Arbeiten mit der Wissenbasis und schafft Übersichtlichkeit:

%% person(Name, Telefonnummer, Geburstag(Geburtstag, Geburtsmonat, Geburtsjahr)).
person('Meier', 01712350393, gebu(21,01,1988)).
person('Wolf', 029185930292, gebu(01,02,1985)).
person('Engel', 021394210239, gebu(14,09,1988)).
person('Muse', 03924019510, gebu(19,02,1997)).

Projektion

Projektion ist das Auswählen bestimmter Datenfelder (Spalten/Attribute) zur Anzeige. Zu Beginn wollen wir alle gespeicherten Kontakte mit Namen und Telefonnummer ausgeben lassen. In SQL wäre das:

SELECT Name, Telefonnummer
FROM Kontakte
;

Selbe Anfrage in Prolog:

?- person(Name,Tel, _).

Hier nutzen wir anonyme Variablen (_). Damit kennzeichnen wir die Datenfelder, die wir nicht ausgeben wollen. Hier zeigt sich bereits ein Vorteil der Verschachtelung, da wir die gesamten Geburtsdaten mit nur einer Variablen ansprechen können.
Die Anfrage liefert somit:

Name = 'Meier',
Tel = 1712350393 ;

Name = 'Wolf',
Tel = 29185930292 ;

Name = 'Engel',
Tel = 21394210239 ;

Name = 'Muse',
Tel = 3924019510

Selektion

Bei der Selektion geht es um die Auswahl von Datensätzen, die einer bestimmten Bedingung genügen. So wollen wir alle Datensätze jener Kontakte ausgegeben haben, die im Jahr 1988 geboren sind.

SQL:

SELECT *
FROM Kontakte
WHERE Geburtsjahr = 1988
;

Prolog:

?- person(Name,Tel, gebu(Geburtstag,Geburtsmonat,1988)).
%% oder
?- person(Name,Tel, gebu(Geburtstag,Geburtsmonat,X)), X = 1988.

liefert:

Name = 'Meier',
Tel = 1712350393,
Geburtstag = 21,
Geburtsmonat = 1 ;

oder:

Name = 'Meier',
Tel = 1712350393,
Geburtstag = 21,
Geburtsmonat = 1,
X = 1988 ;

Projektion mit Selektion

Wie auch in SQL lassen sich in Prolog Projektion und Selektion verknüpfen.

UND/ODER-Verknüpfungen

UND-Verknüpfungen werden in Prolog mit einem Komma zwischen den Einzelfragen gekennzeichnet. Hierfür wollen wir alle Kontakte ausgeben, die vor dem Jahre 1990 im Monat Sempember geboren sind.

SELECT Name, Telefonnummer, Geburtstag, Geburtsmonat, Geburtsjahr
FROM Kontakte
WHERE Geburtsjahr < 1990
AND Geburtsmonat = 09
;

?- person(Name,Tel, gebu(Geburtstag,09,X)), X < 1990.

liefert:

Name = 'Engel',
Tel = 21394210239,
Geburtstag = 14,
X = 1988 ;

Bei diesem Beispiel haben wir zum ersten Mal mit Vergleichsoperatoren gearbeitet. Weitere sind:

Exkurs Vergleichsoperatoren
Schreibweise Operation
X =:= Y numerisch gleich
X =\= Y numerisch ungleich
X < Y X kleiner als Y
X > Y X größer als Y
X =< Y X kleiner gleich Y
X >= Y X größer gleich Y
X = Y unifizierbar
X \= Y nicht unifizierbar
X == Y identisch mit
X \== Y nicht identisch mit

nach [1].

ODER-Verknüpfungen werden in Prolog mit einem Semikolon zwischen den Einzelfragen gekennzeichnet. Nun wollen wir alle Kontakte ausgeben, die entweder im Jahr 1988 oder im Jahr 1997 geboren sind.

SELECT Name, Telefonnummer, Geburtstag, Geburtsmonat, Geburtsjahr
FROM Kontakte
WHERE Geburtsjahr = 1988
OR Geburtsjahr = 1997
;

?- person(Name,Tel, gebu(Geburtstag,Geburtsmonat,X)), (X = 1988; X=1997).
%% oder
?- person(Name,Tel, gebu(Geburtstag,Geburtsmonat,1988)); person(Name,Tel, gebu(Geburtstag,Geburtsmonat,1997)).

Join - Verknüpfung von Tabellen

Zur unserer Datenbank bzw. Wissensbasis in Prolog fügen wir noch Fakten über die Monate hinzu:

%% monat(Monat,Monatsname).
monat(01, 'Januar').
monat(02, 'Februar').
monat(03, 'März').
monat(04, 'April').
monat(05, 'Mai').
monat(06, 'Juni').
monat(07, 'Juli').
monat(08, 'Augst').
monat(09, 'September').
monat(10, 'Oktober').
monat(11, 'November').
monat(12, 'Dezember').

Tabellen können verknüpft werden, sofern sie ein gemeinsames Attribut (i. d. R. das Schlüsselattribut) besitzen. Datensätze die bei diesem Attribut den gleichen Wert aufweisen, werden in einer neuen Tabelle ausgegeben.

Jetzt wollen wir beide Tabellen verbinden, das gemeinsame Attribut/Schlüssel ist der Monat. Wichtig ist das dieser Schlüssel in beiden Teilanfragen mit der gleichen Variablen belegt ist und nicht anonymisiert (_) wird.

?- person(Name,_, gebu(_,Geburtsmonat,_)), monat(Geburtsmonat,Monatsname).

liefert:

Name = 'Meier',
Geburtsmonat = 1,
Monatsname = 'Januar' ;

Name = 'Wolf',
Geburtsmonat = 5,
Monatsname = 'Mai' ;

Name = 'Engel',
Geburtsmonat = 9,
Monatsname = 'September' ;

Name = 'Muse',
Geburtsmonat = 2,
Monatsname = 'Februar'

Also:

Name Geburtsmonat Monatsname
Meier 1 Januar
Wolf 5 Mai
Engel 9 September
Muse 2 Februar

INSERT und DELETE - Einfügen und Löschen von Datensätzen

Nach dem Konsultieren einer Wissensbasis sind alle Fakten im Zwischenspeicher von Prolog geladen und können dann nicht mehr verändert werden. Erst erneutes Konsultieren lädt die Wissensbasis erneut. Um trotzdem Veränderungen durchzuführen müssen wir unsere Datenbasis als dynamisch definieren. Das geschieht mit dem Befehl :- dynamic funktor/stelligkeit:

:- dynamic person/3.
person('Meier', 01712350393, gebu(21,01,1988)).
person('Wolf', 029185930292, gebu(01,02,1985)).
person('Engel', 021394210239, gebu(14,09,1988)).
person('Muse', 03924019510, gebu(19,02,1997)).

Mit dem Befehl listing(funktor/stelligkeit) lassen sich die aktuellen Fakten im Zwischenspeicher ausgeben.

?- listing(person/3).

gibt Folgendes aus:

- dynamic person/3.
person('Meier', 1712350393, gebu(21, 1, 1988)).
person('Wolf', 29185930292, gebu(1, 5, 1985)).
person('Engel', 21394210239, gebu(14, 9, 1988)).
person('Muse', 3924019510, gebu(19, 2, 1997)).

Zu einer dynamischen Datenbasis können nun Fakten hinzugefügt und gelöscht werden. Dazu stehen diverse Befehle zur Verfügung:

Befehl Beschreibung
asserta(fakt). Fügt einen neuen Fakt am Anfang des Stapels ein.
assertz(fakt). Fügt einen neuen Fakt am Ende des Stapels ein.
retract(fakt). Löscht Fakt.
retractall(fakt). Löscht alle Fakten des Funktors
Befehl Ausgabe bei
?- listing(person/3).
asserta( person('Fischer', 09012394012, gebu(01,01,1992))). person('Fischer', 9012394012, gebu(1, 1, 1992)).
person('Meier', 1712350393, gebu(21, 1, 1988)).
person('Wolf', 29185930292, gebu(1, 5, 1985)).
person('Engel', 21394210239, gebu(14, 9, 1988)).
person('Muse', 3924019510, gebu(19, 2, 1997)).
assertz( person('Fischer', 09012394012, gebu(01,01,1992))). person('Meier', 1712350393, gebu(21, 1, 1988)).
person('Wolf', 29185930292, gebu(1, 5, 1985)).
person('Engel', 21394210239, gebu(14, 9, 1988)).
person('Muse', 3924019510, gebu(19, 2, 1997)).
person('Fischer', 9012394012, gebu(1, 1, 1992)).
retract( person('Wolf', 29185930292, gebu(1, 5, 1985))). person('Meier', 1712350393, gebu(21, 1, 1988)).
person('Engel', 21394210239, gebu(14, 9, 1988)).
person('Muse', 3924019510, gebu(19, 2, 1997)).
retractall(person(_,_,_)).  

nach [2].

Eleganter geht das mit der Definition einer Regel zum Einfügen und Löschen, die wir in die Prolog-Datenbasis schreiben:

einfuegen(Name, Tel, GebuTag, GebuMonat, GebuJahr):-
   assertz(person(Name, Tel,gebu(GebuTag, GebuMonat, GebuJahr))).

Der SQL-UPDATE-Befehl wird mittels Löschen und neuem Einfügen in Prolog implementiert.

Suchen ohne Sortieren

Nun beginnen wir mit den kniffligeren Dingen. Da wir immer komplexere Aufgaben an Prolog stellen, ist es von Vorteil, Anfragen als Regeln in unsere Datenbasis zu schreiben und diese dann aufzurufen (Wissen um die Lösungssuche in Prolog samt Backtracking und Unifikation ist zum Verständnis hilfreich).

Wir wollen die Namen der Kontakte mit dazugehöriger Telefonnummer auf dem Bildschirm ausgegeben. Dazu nutzen wir die Befehle write/1 und nl (new line, erzeugt eine neue Ziele).

abfrage1:-
   person(Name,Tel,_),
   write(Name), write(' hat die telefonnummer '),write(Tel),nl,
   fail.

?- abfrage1.

liefert:

Meier hat die telefonnummer 1712350393
Wolf hat die telefonnummer 29185930292
Engel hat die telefonnummer 21394210239
Muse hat die telefonnummer 3924019510

Wichtig dabei ist das fail. Dadurch wird Prolog gezwungen nach weiteren Kontakten zu suchen, bis es alle Fakten in der Datenbasis durchgegangen hat.

Exkurs: fail

fail schlägt - im Gegensatz zum Cut ! - immer fehl und zwingt Prolog zum Backtracking, sodass er nach neuen Lösungen und Belegungen für die vorhergehenden Bedingungen sucht.

Die Ausgabe1 lässt sich noch optimieren:

abfrage1:-
   write('Kontaktbuch:'),nl,
   (
      person(Name,Tel,_),
      write(Name), write(' hat die telefonnummer '),write(Tel),nl,
      fail
   ).

Durch die Klammersetzung beschränkt sich das fail nur auf die Befehle innerhalb der Klammer, sodass Backtracking nur dort durchgeführt wird. Ergo wird "Kontaktbuch:" nur einmal ausgegeben.

Natürlich lässt sich diese Abfrage auch ohne write und fail realisieren: etwas uneleganter geht es mit der Regel:

abfrage1(Name,Telefonnummer):- person(Name,Telefonnummer,_).

Suchen und Sortieren

Für Weiteres benötigen wir eine Reihe von neuen Befehlen, die in Prolog standardmäßig implementiert sind.

Exkurs: Suchen mit findall/3

findall(?Template,+Generator,?Liste) sucht alle Lösungen des Generator-Ziels und gibt sie in Form des Templates als Liste aus. Dazu einige erklärende Beispiele mit Hilfe unserer Kontaktdatenbasis:

person('Meier', 01712350393, gebu(21,01,1988)).
person('Wolf', 029185930292, gebu(01,02,1985)).
person('Engel', 021394210239, gebu(14,09,1988)).
person('Muse', 03924019510, gebu(19,02,1997)).

Anfrage 1:

?- findall(X, person(X, _, _), Liste).

Gibt die Namen aller erfassten Kontakte in einer Liste aus. Ausgabe:

Liste = ['Meier', 'Wolf', 'Engel', 'Muse']

Anfrage 2:

?- findall(X,
           (person(X,_,gebu(_,_,Jahr)),Jahr < 1990),
           Liste).

Zur besseren Übersichtlichkeit wurden die einzelnen Argumente in neue Zeilen geschrieben. Im Generator können auch Bedingungen eingegeben werden. Hier möchten wir alle Namen der Kontakte in einer Liste ausgegeben haben, die vor 1990 geboren wurden. Ausgabe:

Liste = ['Meier', 'Wolf', 'Engel']

Anfrage 3:

?- findall([Name-hat-am-Tag-Monat-Jahr-geburtstag],
           person(Name,Tel,gebu(Tag,Monat,Jahr)),
           Liste).

Im Template definieren wir die Form der einzelnen Listenelemente. Es können auch komplexe Gebilde sein, die man frei bestimmen kann. Ausgabe:

Liste = [
['Meier'-hat-am-21-1-1988-geburtstag],
['Wolf'-hat-am-1-5-1985-geburtstag],
['Engel'-hat-am-14-9-1988-geburtstag],
['Muse'-hat-19-2-1997-geburtstag]
]

Exkurs: Sortieren mit sort/2 und msort/2

Für das Sortieren von Listen gibt es zahlreichen Befehle, die für uns relevanten sind:

  • sort(+UnsortiereListe,-SortiereListe) sortiert die Liste und entfernt Duplikate.
  • msort(+UnsortiereListe,-SortiereListe) sortiert die Liste und behält Duplikate.

Für alle Sortierungen gilt:

  • Zahlen vor Großbuchstaben vor Kleinbuchstaben
  • Buchstaben alphabetisch, Zahlen aufsteigend
Befehl Ausgabe

?- sort([9,a,3,hallo, 32,'Zuhause', 0, hallo, 9, welt, 9], Liste).

Die Duplikate von '9' und 'hallo' werden entfernt.

Liste = [0, 3, 9, 32, 'Zuhause', a, hallo, welt]

?- msort([9,a,3,hallo, 32,'Zuhause', 0, hallo, 9, welt, 9],Liste).

Die Duplikate von '9' und 'hallo' werden beibehalten.

Liste = [0, 3, 9, 9, 9, 32, 'Zuhause', a, hallo, hallo, welt]

?- sort([9,a,3,hallo, 32,'Zuhause', 0, hallo, 9, welt, 9], Liste), reverse(Liste, UmgedrehteListe).

Möchte man eine absteigende Sortierung (Zahlen absteigend, Buchstaben alphabetisch rückwärts), so muss man die sortierte Liste dem Befehl reverse/2 übergeben. reverse/2 dreht die Liste um.

Liste = [0, 3, 9, 32, 'Zuhause', a, hallo, welt],

UmgedrehteListe = [welt, hallo, a, 'Zuhause', 32, 9, 3, 0]

Abfrage 2

Es sollen alle Namen unserer Kontaktdatenbank alphabetisch sortiert ausgegeben werden. Wir wollen unsere Ergebnisse auf dem Bildschirm ausgeben.

SELECT Name
FROM Kontakte
ORDER BY Name
;

abfrage2:-
   findall(Name,
           person(Name,_,_),
           Liste),
   sort(Liste,SListe),
   write(SListe).

ergibt:

['Engel', 'Meier', 'Muse', 'Wolf']

Abfrage 3

Die Kür: Nun sollen alle Kontakte mit allen dazugehörigen Informationen sortiert nach dem Geburtsjahr ausgegeben werden. Und zwar ohne Listen bei der Ausgabe (Wissen um Rekursion und Listen (Kopf, Rest) nötig und Kenntnis vom Cut und Backtracking hilfreich).

SELECT *
FROM Kontakte
ORDER BY Geburtsjahr
;

abfrage3:-
   findall([Jahr,person(Name,Tel,geburtstag_am(Tag,Monat,Jahr))],
           person(Name,Tel,gebu(Tag,Monat,Jahr)),
           Liste),
   sort(Liste,SListe),
   streichen(SListe,SSListe),
   ausgabe(SSListe),!.

ausgabe([K]):- write(K),nl.
ausgabe([K|Rs]):- write(K),nl,ausgabe(Rs).

streichen([],[]).
streichen([[_,B]|Rs],[B|Qs]):- streichen(Rs,Qs).

liefert:

person(Wolf, 29185930292, geburtstag_am(1, 5, 1985))
person(Engel, 21394210239, geburtstag_am(14, 9, 1988))
person(Meier, 1712350393, geburtstag_am(21, 1, 1988))
person(Muse, 3924019510, geburtstag_am(19, 2, 1997))

Zur Erklärung: Um zu Sortieren nutzen wir einen Trick: Wir schreiben vor jedes Listenelement noch einmal mit Kommata getrennt das Jahr, sodass findall/3 am Ende folgende Liste ausgibt:
Liste = [
[1988, person('Meier', 1712350393, geburtstag_am(21, 1, 1988))],
[1985, person('Wolf', 29185930292, geburtstag_am(1, 5, 1985))],
[1988, person('Engel', 21394210239, geburtstag_am(14, 9, 1988))],
[1997, person('Muse', 3924019510, geburtstag_am(19, 2, 1997))]
]

Nun sortiert sort/2 jedes Listenelement, wobei allein nach dem ersten Zeichen - dem Jahr - sortiert wird. Nun sorgt unsere selbst definierte rekursive Regel streichen/2 dafür, dass das Jahr am Anfang jedes Listenelements gelöscht wird. Anschließend nutzen wir die Regel ausgabe/1, um jedes Listenelement einzeln in eine extra Zeile auszugeben. Der grüne Cut ! unterdrückt unnötiges Backtracking und damit praktisch das Fragen von Prolog nach "More?"; ist aber für die Lösung nicht nötig.

Selektion mit Joker und Platzhalter

Eines der ersten Dinge, die man in SQL lernt, sind Abfragen wie: Zeige alle Namen an, die mit "M" beginnen oder die Zeichenfolge "ei" im Namen tragen.

SELECT Name
FROM Kontakte
WHERE Name LIKE "M*"
OR Name LIKE "*ei*"
;

Oder: Zeige alle Namen, die genau 5 Zeichen lang sind und mit "l" enden.

SELECT Name
FROM Kontakte
WHERE Name LIKE "????l"
;

Dabei steht der Joker * für beliebig viele Buchstaben bzw. Zeichen und der Platzhalter ? für genau ein Zeichen. Um solche Anfragen in Prolog zu realisieren, benötigen wir den mächtigen Befehl sub_string/5:

Exkurs: String-Analyse und -Manipulation mit sub_string/5

sub_string(+String,?Davor,?Länge,?Danach,?Sub) kopiert einen Teil aus String heraus. Dabei gilt:

  • String: Gesamtstring, aus dem der Ausschnitt kopiert werden soll.
  • Davor/Danach: Anzahl der Zeichen vor/nach dem Ausschnitt.
  • Länge: Anzahl der Zeichen des Ausschnitts.
  • Sub: Ausschnitt aus String.

Der Befehl sub_atom/5 leistet gleiches, nur dass er Ausschnitt als Atom ausgegeben wird. Er kann für unsere Zwecke ebenso eingesetzt werden.

Anfrage Antwort
?- sub_string('hallowelt', Davor, Laenge, Danach, 'lowe').
Dieser Befehl ermittelt die Position des Ausschnitts "lowe" in der Zeichenkette "hallowelt".
Davor = 3,
Laenge = 4,
Danach = 2 ;

Vor der Zeichenkette "lowe" sind 3 Zeichen (hal) und danach 2 (lt). Die Länge des Ausschnitts beträgt 4.
?- sub_string(hallowelt,0,_,_,h).
Prüft, ob "hallowelt" mit einem "h" beginnt.
Yes
?- sub_string(hallowelt,_,9,_,_).
Prüft, ob "hallowelt" genau 9 Zeichen lang ist.
Yes
?- sub_string(hallowelt,_,5,_,X).
Gibt alle möglichen Ausschnitte aus "hallowelt" mit einer Länge von 5 Zeichen aus.
X = "hallo" ;
X = "allow" ;
X = "llowe" ;
X = "lowel" ;
X = "owelt"
?- sub_atom(hallowelt,_,5,_,X).
Gleiche Anfrage nur mit sub_atom/5. Hier werden die Ergebnisse als Atome ausgegeben. Die Wahl der sub-Funktion spielt lediglich beim Ausgeben der Ausschnitte eine Rolle.
X = hallo ;
X = allow ;
X = llowe ;
X = lowel ;
X = owelt

Nun wissen wir alles, um auch solche SQL-Abfragen in Prolog implementieren:

abfrage4(Name):-
   person(Name,_,_),
   sub_string(Name,0,1,_,'M').

liefert:

Name = 'Meier' ;
Name = 'Muse'

oder mit Ausgabe:

abfrage5:-
   write('mit m beginnen:'),nl,
   (
      person(Name,_,_),
      sub_string(Name,0,1,_,'M').
      write(Name),nl,
      fail
   ).

liefert:

mit m beginnen:
Meier
Muse

 Und jetzt alle Namen, die genau 5 Zeichen lang sind und mit "l" enden:

abfrage6:-
   write('namen, die 5 zeichen lang sind und mit "l" enden:'),nl,
   (
      person(Name,_,_),
      sub_string(Name,_,1,0,'l'),
      sub_string(Name,_,5,_,_),
      write(Name),nl,
      fail
   ).

ergibt:

namen, die 5 zeichen lang sind und mit "l" enden:
Engel

Aggregatfunktionen

Für die Demonstration von Aggregatfunktionen (Anzahl/count(), Summe/sum(), Minimum/min(), Maximum/max(), Durschnitt/avg() etc.) benötigen wir eine neue Datenbasis. Wir wählen die Datenbank eines Online-Kaufhauses, in dem sämtliche Bestellungen erfasst werden:

%%bestellung(Kunde,ArtikelNr,Anzahl,Datum(Monat,Tag,Jahr)).
bestellung('Meier',1001,2,datum(8,2,2008)).
bestellung('Engel',1012,1,datum(8,8,2008)).
bestellung('Meier',1021,1,datum(8,12,2008)).
bestellung('Fischer',1001,1,datum(9,11,2008)).
bestellung('Meier',1055,3,datum(10,22,2008)).
bestellung('Will',1001,2,datum(10,26,2008)).
bestellung('Fischer',1002,4,datum(11,02,2008)).
bestellung('Muse',1009,10,datum(11,11,2008)).

Anfrage 7: Anzahl

Die Kür#2: Wir möchten folgende Abfrage in Prolog implementieren: Die Anzahl der Bestellungen zu jedem Kunden.

SELECT Kunde, count(ArtikelNr) AS AnzahlDerBestellungen
FROM Bestellungen
GROUP BY Kunde
;

abfrage7:-
   findall(Kunde,
           bestellung(Kunde,_,_,_),
           KList),
   list_to_set(KList,SKList),
   zaehle(SKList,KListA),
   ausgabe(KListA),!.

zaehle([],[]).
zaehle([K|Rs],Qs):-
   findall(K,
           bestellung(K,_,_,_),
           AList),
   length(AList, Anzahl),
   zaehle(Rs,Ws),
   Qs = [[K-hat-Anzahl-bestellung(en)]|Ws].

ausgabe([K]):- write(K),nl.
ausgabe([K|Rs]):- write(K),nl,ausgabe(Rs).

Der Aufruf von abfrage7/0 liefert:

[Meier-hat-3-bestellung(en)]
[Engel-hat-1-bestellung(en)]
[Fischer-hat-2-bestellung(en)]
[Will-hat-1-bestellung(en)]
[Muse-hat-1-bestellung(en)]

Es werden alle vorhandenen - auch mehrmals vorkommenden - Kunden der bestellung-Fakten in eine Liste geschrieben:
KListe = [Meier, Engel, Meier, Fischer, Meier, Will, Fischer, Muse]

In dieser wird dann mittels des Systemprädikats list_to_set/2 alle Duplikate gelöscht:
SKListe = [Meier, Engel, Fischer, Will, Muse]

Die selbstdefinierte rekursive Regel zaehle/2 sucht nun zu jedem Kunden die Anzahl der Bestellungen. So hat die AListe bei K = Meier den Inhalt [Meier,Meier,Meier], da für Meier 3 Bestellungen in der Datenbasis existieren. Das Systemprädikat length/2 zählt die Listenelemente dieser Liste und gibt diese als Variable Anzahl aus. Die Rekursion setzt ein, diesmal jedoch ohne den eben bearbeiteten Listenkopf. Das ganze geschieht so lange, wie Elemente in der Ausgangsliste sind. Anschließend wird im Rekursionsaufstieg jeder Kunde mit seiner Anzahl an Bestellungen nacheinander in die Ergebnisliste Qs geschrieben. Die Ausgabe erfolgt wieder mit unserer Regel ausgabe/2, die wir schon aus "Suchen und Sortieren - Abfrage 3" kennen. Ebenso bekannt ist das optionale Setzen des grünen Cuts !, der unnötiges Backtracking von Prolog verhindert.

Exkurs: Entfernen von Duplikaten in Listen

Das Entfernen von Duplikaten aus Listen kann auf verschiedene Arten durchgeführt werden:

  • list_to_set(+ListeMitDuplikate,-ListeOhneDuplikate): Dieses Prädikat ist bereits standardmäßig in Prolog implementiert.
  • das Sortierprädikat sort/2 haben wir bereits kennen gelernt. Es löscht ebenso Duplikate. Dass die Liste dabei noch sortiert wird, ist in unserem Fall obsolet.
  • Definition einer eigenen Regel. Möchte man ohne Systemprädikate auskommen, könnte die rekursive Regel so aussehen:

menge([K],[K]).
menge([K|Rs],[K|RM]):-not(member(K,Rs)),menge(Rs,RM).
menge([K|Rs],RM):-member(K,Rs),menge(Rs,RM),!.

Das Listenprädikat member(K,Rs) prüft, ob das Element K in der Liste Rs enthalten ist (3. Regel). not() dient der Negierung, d. h. es ist erfüllt, wenn K kein Element von Rs ist (2. Regel). Der optionale Cut verhindert, dass beim Aufrufen der Regel die gleiche Lösung mehrfach ausgegeben wird. Das würde beim Verwenden des Prädikats in einer anderen Abfrage (wie bei uns), aber keine Rolle spielen.

Anfrage Antwort
?- list_to_set([5,2,3,2,5,1,9,2,2], Set). Set = [5, 2, 3, 1, 9]
?- sort([5,2,3,2,5,1,9,2,2], Set). Set = [1, 2, 3, 5, 9]
?- menge([5,2,3,2,5,1,9,2,2], Set). Set = [3, 5, 1, 9, 2]
Vielleicht erkennen Sie, warum list_to_set/2 und menge/2 unterschiedliche Listen ausgeben und was das über die Arbeitsweise der Prädikate aussagt. ;-)

Exkurs: Länge von Listen bestimmen

Auch bei der Bestimmung von der Listenlänge bzw. der Anzahl der Listenelemente gibt es verschiedene Möglichkeiten.

  • length(+Liste,-Anzahl): Systemprädikat und damit standardmäßig in Prolog implementiert.
  • Definition einer eigenen Regel:

anzahl([],0).
anzahl([_|Rs],A):-
   anzahl(Rs,A1),
   A is A1 + 1.

Anfrage Antwort
?- length([1,42,9012,12,1],Anzahl). Anzahl = 5
?- anzahl([1,42,9012,12,1],Anzahl). Anzahl = 5

Summe

Exkurs: Summe von Listenelementen ermitteln

Zur Bestimmung der Summe von Zahlenlisten ist es nötig eine eigene Regel zu schreiben: summe(+Liste,-Summe).

summe([],0).
summe([X|Rs], N):-
   summe(Rs,N1),
   N is N1 + X.

Anfrage Antwort
?- summe([2,4,100],Summe). Summe = 106

Die Umsetzung der SQL-Aggregatfunktion sum() in Prolog gestaltet sich analog zur Anzahlimplementation, nur dass hier nicht length/2, sondern unsere selbst definierte Regel summe/2 zum Einsatz kommt.

Minium und Maximum

Um das Minium (min()) bzw. Maximum (max()) einer Liste zu bestimmten, sortiert man die Liste und liest dann das erste bzw. das letzte Element aus.

Definition des Maximum:

max(Liste,Max):-
   msort(Liste,SListe),
   last(SListe,Max).

Das Prädikat last/2 liefert das letzte Element der Liste als Ergebnis und kann alternativ auch selbst definiert werden:

letztes_element([X],X).
letztes_element([_|Rs],X):- letztes_element(Rs,X).

Definition des Minimums:

min(Liste,Min):-
   msort(Liste,SListe),
   erstes_element(SListe,Min).

erstes_element([X|_],X).

Anfrage Antwort
?- max([2,5,3,9,1,10,6],Max). Max = 10
?- min([2,5,3,9,1,10,6],Min). Min = 1

Auch hier gestaltet sich die Prolog-Implementation der SQL-Befehle min() bzw. max() analog zur Anzahl, nur dass wir statt length/2 unsere Regeln min/2 bzw. max/2 nutzen.

Trotzdem möchte ich diese Definition noch einmal an einem anderem - einfacheren ;-) - Beispiel demonstrieren. Dazu folgende Datenbank: Die Zeugnisnoten von Schülern werden in einer Prolog Wissensbasis als Fakten abgelegt:

%%zeugnis(Schueler, Note1, Note2, Note3, Note4).
zeugnis('Flink',2,3,2,5).
zeugnis('Pfiffig',1,1,2,1).
zeugnis('Faul',3,4,3,5).
zeugnis('Albern',3,2,3,3).
zeugnis('Klug',1,1,1,1).

Gesucht ist die beste Note von jedem Schüler.

beste_note:-
   zeugnis(Name,N1,N2,N3,N4),
   NotenL = [N1,N2,N3,N4],     &&Listenbildung!
   min(NotenL,Beste),
   write('die beste note von '),write(Name),write(' ist '),write(Beste), nl,
   fail.

min(Liste,Min):-
   msort(Liste,SListe),
   erstes_element(SListe,Min).

erstes_element([X|_],X).

der Aufruf von beste_note/0 liefert:

die beste note von Flink ist 2
die beste note von Pfiffig ist 1
die beste note von Faul ist 3
die beste note von Albern ist 2
die beste note von Klug ist 1

Beim Vergleich der Abfragen, die sich auf unsere Bestellungs- und unserer Zeugnisdatenbank beziehen, zeigen sich grundlegende Unterschiede hinsichtlich der Lösungsansätze:

Exkurs: Komplexität der Listenbildung

Der Umfang der Implementation von Aggregatfunktionen und ähnlich geartete Aufgaben in Prolog hängt von der Art der Wissenbasis hinsichtlich der Fakten bzw. von der Komplexität der Listenbildung ab: Sind die nötigen Informationen auf verschiedene Fakten verteilt, so ist eine Listenbildung mit findall/2 nötig (siehe Anzahl beim Bestellungsbeispiel). Sind die Informationen jedoch in einem Fakt zu finden, ist nur eine einfache Listenbildung mit List = [Element1, Element2, ...] zu realisieren (siehe Zeugnisbeispiel):

Beispielfakten notwendige Listenbildung mit:
bestellung('Meier',1001,2,datum(8,2,2008)).
bestellung('Engel',1012,1,datum(8,8,2008)).

Hier soll eine Liste aus den Anzahlwerten der bestellten Waren einer jeden Bestellung erstellt werden. Z. B. zur späteren Ermittlung der höchsten Bestellmenge. Für weiterführende Informationen siehe Anzahl-Abfrage.
findall(Anzahl, bestellung(_,_,Anzahl,_), Liste).
zeugnis('Flink',2,3,2,5).
zeugnis('Pfiffig',1,1,2,1).

Hier wollen wir alle Noten in eine Liste zusammenfassen, um beispielsweise später die beste, die schlechteste oder den Durchschnitt zu berechnen.
Liste = [Note1, Note2, Note3, Note4].

Durchschnitt

Was zur Realisierung der avg()-Funktion in Prolog nötig ist, können wir bereits: Summe der Liste (summe/2) bestimmen und durch die Länge (length/2) teilen.

Für unser Zeugnisbeispiel wäre die Lösung:

durchschnitt:-
   zeugnis(Name,N1,N2,N3,N4),
   NotenL = [N1,N2,N3,N4],
   summe(NotenL,Summe),
   length(NotenL,Anzahl),
   Durchschnitt is Summe/Anzahl,
   write('der durchschnitt von '),write(Name),write(' ist '),write(Durchschnitt), nl,
   fail.

summe([],0).
summe([X|Rs], N):-
   summe(Rs,N1),
   N is N1 + X.

durchschnitt/0 liefert:

der durchschnitt von Flink ist 3
der durchschnitt von Pfiffig ist 1.25
der durchschnitt von Faul ist 3.75
der durchschnitt von Albern ist 2.75
der durchschnitt von Klug ist 1

Zusammenfassung der Systemprädikate

Hier ein Zusammenfassung aller Prolog-Befehle und -Prädikate (Systemprädikate und/oder Listenprädikate), die wir genutzt haben:

  Prädikat Kurze Beschreibung Anwendung/ Beispiel:
Dynamische Datenbankverwaltung :- dynamic funktor/stelligkeit. definiert die entsprechenden Fakten als dynamisch. mehr...
  listing(funktor/stelligkeit) gibt alle Fakten des Zwischenspeichers aus mehr...
  asserta(fakt). Fügt einen neuen Fakt am Anfang des Stapels ein mehr...
  assertz(fakt). Fügt einen neuen Fakt am Ende des Stapels ein mehr...
  retract(fakt). Löscht Fakt mehr...
  retractall(fakt). Löscht alle Fakten des Funktors. mehr...
Ausgabe write(+X) gibt X auf dem Bildschirm aus mehr...
  nl erzeugt eine neue Zeile auf dem Bildschirm mehr...
Backtrackingmanipulation fail erzwingt Backtracking mehr...
  ! verhindert Backtracking (Cut) mehr...
Suchen findall(?Template, +Generator, ?Liste) sucht alle Lösungen des Generator-Ziels und gibt sie in Form des Templates als Liste aus. mehr...
Sortieren sort(+L,-SL) sortiert die Liste L; löscht Duplikate mehr...
  msort(+L,-SL) sortiert die Liste L; behält Duplikate mehr...
  reverse(+L,-RL) dreht die Liste L um mehr...
Stringanalyse und Stringmanipulation sub_string(+String, ?Davor, ?Länge, ?Danach, ?Sub) Kopiert aus String den Ausschnitt Sub mit Informationen zu der Position und Länge des Ausschnitts. Liefert Strings. mehr...
  sub_atom(+Atom, ?Davor, ?Länge, ?Danach, ?Sub) Kopiert aus Atom den Ausschnitt Sub mit Informationen zu der Position und Länge des Ausschnitts. Liefert Atome. mehr...
Listenbefehle list_to_set(+L,-L2) Löscht Duplikate der Liste L und gibt sie als L2 aus. mehr...
  length(+L,-Anzahl) Gibt die Anzahl der Listenelemente der Liste L aus. mehr...
  last(+L,-E) Gibt das letzte Listenelement der Liste L als E aus. mehr...
  member(+X,+L) Prüft ob X ein Listenelement der Liste L ist. mehr...
  append(+L1,+L2,-GL) Hängt Liste L1 an die Liste L2 an und gibt sie als GL aus. /
  delete(+L,+X,-GL) Löscht das Element X aus der Liste L und gibt sie als GL aus. /
Sonstiges not(bedingung) Negierung. Ist erfüllt, wenn die Bedingung fehlschlägt. mehr...

Quellen

  • [1] Tino Hempel: "Selektionsbedingungen und Arithmetik". URL: http://www.tinohempel.de/info/info/datenbanken_prolog/arithmetik.htm [Stand: 26.05.08]
  • [2] Tino Hempel: "Aktionsabfragen zur Pflege des Datenbestands". URL: http://www.tinohempel.de/info/info/datenbanken_prolog/aktionsabfragen.html [Stand: 26.05.08]
  • [3] Thorsten Joachims: "Programmierkurs Prolog". URL: www-ai.cs.uni-dortmund.de/LEHRE/PROLOG/FOLIEN/Folien_Terme_MetaProgrammierung.pdf [Stand: 26.05.08]
  • [4] Dipl. Inf. Björn Pelzer: "'Strings' in Prolog - Atome (3)". URL: www.uni-koblenz.de/~bpelzer/kipr/strings.pdf [Stand: 26.05.08]
  • [5] Dipl. Inf. Björn Pelzer: "Sortieren". URL: www.uni-koblenz.de/~bpelzer/kipr/aufgaben310106.pdf [Stand: 26.05.08]
  • [6] H.-U. Zimmermann: "7.2 Die Liste, eine rekursive Datenstruktur". URL: http://www.h-u-zimmermann.de/umitschrift/node35.html [Stand: 26.05.08]