Datalog

Datalog i​st eine Datenbank-Programmiersprache für deduktive Datenbanken, d​ie Prolog syntaktisch u​nd semantisch ähnelt.

Sie g​eht zurück a​uf die Arbeit v​on Herve Gallaire u​nd Jack Minker i​m Jahr 1978.[1]

Datalog unterscheidet s​ich von Prolog i​n den folgenden Punkten:

  1. Zusammengesetzte Terme dürfen nicht als Argumente von Prädikaten vorkommen. So ist zum Beispiel erlaubt, dagegen verboten.
  2. In Datalog geschriebene Programme müssen im Hinblick auf Negation und Rekursion stratifiziert sein.
  3. Datalog-Programme können effizient bottom-up ausgewertet werden, wobei nur eine endliche Menge an Fakten abgeleitet werden kann und die Auswertungszeit beschränkt ist.
  4. Die Reihenfolge der Regeln spielt in einem Datalog-Programm keine Rolle.

Ein Vorteil gegenüber relationalen Kalkülen i​st die Möglichkeit, Rekursion o​hne vorgegebene Rekursionstiefe definieren z​u können. Die Terminierung d​er Rekursion k​ann durch deduktive Abgeschlossenheit erreicht werden, a​lso durch Erreichen d​es kleinsten Fixpunktes.

Derzeit entwickeln Forscher a​uf Basis v​on Datalog, d​as für extreme Parallelität geeignet ist, d​ie Programmiersprache Boom[2] für d​ie effiziente Nutzung v​on Rechnerwolken.[3]

Beispiel-Programm

 
% koeln ist mit duesseldorf verbunden
verbunden(koeln,duesseldorf).
% duesseldorf ist mit dortmund verbunden
verbunden(duesseldorf,dortmund).
% hannover ist mit dortmund verbunden
verbunden(hannover,dortmund).
% wenn X mit Y verbunden ist, dann auch Y mit X
verbunden(Y,X) :- verbunden(X,Y).
% X ist mit Z verbunden, wenn X mit einem beliebigen Y verbunden ist, das wiederum mit Z verbunden ist
verbunden(X,Z) :- verbunden(X,Y),verbunden(Y,Z).
% Anfrage: Ist koeln mit hannover verbunden?
?- verbunden(koeln,hannover)?

Einzelnachweise
  1. Logic and Data Bases. Symposium on Logic and Data Bases, Centre d’études et de recherches de Toulouse in „Advances in Data Base Theory“. Plenum Press, New York 1978
  2. BOOM: Generating Big Clouds from Small Programs. 23. Dezember 2009
  3. Besserer Code für die Wolke. heise.de; Technology Review online, 23. Dezember 2009
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.