Datenbanken in Prolog SQL-Anweisungen und -Abfragen in Prolog umsetzen
Eine Ausarbeitung von Philipp Hauer vom 28.05.2008. ©
Inhalt
Logischer Ablauf | Exkurse |
---|---|
|
|
Beispieldatenbanken | |
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:
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 1712350393Wolf 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 |
Die Duplikate von '9' und 'hallo' werden entfernt. |
Liste = [0, 3, 9, 32, 'Zuhause', a, hallo, welt] |
Die Duplikate von '9' und 'hallo' werden beibehalten. |
Liste = [0, 3, 9, 9, 9, 32, 'Zuhause', a, hallo, hallo, welt] |
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
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 2die 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)).
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).
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 3der 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]