Datalog


Datalog

Datalog ist eine Datenbank-Programmiersprache für deduktive Datenbanken, die Prolog syntaktisch und semantisch ähnelt.

Sie geht zurück auf die Arbeit von Herve Gallaire und Jack Minker im Jahr 1978. Sie ist eigentlich nur von theoretischer Bedeutung, da es bis heute keine kommerzielle Datenbank gibt, die Datalog anbietet.

Datalog unterscheidet sich von Prolog in den folgenden Punkten:

  1. Zusammengesetzte Terme dürfen nicht als Argumente von Prädikaten vorkommen. So ist zum Beispiel P(1,2) erlaubt, P(f(1),2) 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 ist die Möglichkeit, Rekursion ohne vorgegebene Rekursionstiefe definieren zu können. Die Terminierung der Rekursion kann durch deduktive Abgeschlossenheit erreicht werden, also durch Erreichen des kleinsten Fixpunktes.

Derzeit entwickeln Forscher auf Basis von Datalog, das für extreme Parallelität geeignet ist, die Programmiersprache Boom[1] für die effiziente Nutzung von Rechnerwolken.[2]

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).

Weblinks

Quellennachweis

  1. [1] BOOM: Generating Big Clouds from Small Programs, 23. Dezember 2009
  2. [2] Technology Review online, 23. Dezember 2009

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Datalog — is a query and rule language for deductive databases that syntactically is a subset of Prolog. Its origins date back to the beginning of logic programming, but it became prominent as a separate area around 1977 when Hervé Gallaire and Jack Minker …   Wikipedia

  • Datalog — Apparu en 1977 Auteur Hervé Gallaire et Jack Minker Paradigme Langage de requête Datalog est un langage de requête et de règles pour les bases d …   Wikipédia en Français

  • datalog — da|ta|log sb., en, er, erne …   Dansk ordbog

  • datalog — s ( en, er) …   Clue 9 Svensk Ordbok

  • Final Fantasy XIII — Final Fantasy XIII …   Wikipedia

  • Final Fantasy XIII — Обложка европейского издания Разработчик Square Enix Издатель Square Enix …   Википедия

  • Conjunctive query — In database theory, a conjunctive query is a restricted form of first order queries. A large part of queries issued on relational databases can be written as conjunctive queries, and large parts of other first order queries can be written as… …   Wikipedia

  • Konjunktive Anfrage — Konjunktive Anfragen sind eine Einschränkung von Anfragen der Prädikatenlogik und haben eine Reihe an wünschenswerten Eigenschaften, die in der Datenbanktheorie intensiv untersucht worden sind. Viele Anfragen an relationale Datenbanken und damit… …   Deutsch Wikipedia

  • Complexity of constraint satisfaction — The complexity of constraint satisfaction is the application of computational complexity theory on constraint satisfaction. It has mainly been studied for discriminating between tractable and intractable classes of constraint satisfaction… …   Wikipedia

  • SQL — This article is about the database language. For the airport with IATA code SQL, see San Carlos Airport. SQL Paradigm(s) Multi paradigm Appeared in 1974 Designed by Donald D. Chamberlin Raymond F. Boyce Developer …   Wikipedia