Datalog ist eine logische Programmiersprache, die speziell für die effiziente Integration von relationalen Datenbanken mit der logischen Programmierung geschaffen wurde. Logische Programme in Datalog entsprechen Anfragen an die Datenbank.
Wir nehmen an, daß die Menge 
der Prädikatsnamen in
zwei Mengen 
und 
aufgeteilt ist, für die
gelten: 
und
. Die Elemente aus EPred
bezeichnen extensional definierte Prädikate, d.h. Prädikate, die den
Datenbankrelationen entsprechen. Die Ensprechung läuft wie folgt: Der
Relationenname entspricht dem Prädikatsnamen, und es existiert eine
feste Abbildung zwischen den Attributen und den Argumentstellen. IPred
bezeichnet intensional definierte Prädikate, d.h. Prädikate, die
durch Datalog Programme definiert werden. Für das weitee reicht die
Vorstellung, daß die extensionale Datenbank EDB die Daten
repräsentiert, die effektiv in der relationalen Datenbank gespeichert
sind. Damit ist EDB eine Menge von Grundfakten, (genauer müßte EDB
mithilfe einer extensionalen Herbrandbasis über Epred definiert
werden, [[CGT90]]).
Die Bedingung (1) garnatiert, daß die extensionale Datenbank nicht durch Datalofg Regeln geändert werden kann. Bedingung (2) ist eine Sicherheitsbedingung. Sie sorgt dafür, daß nur eine endliche Menge von Fakten aus einem Datalogprogramm abgeleitet werden kann.
In diesem reinen (engl. pure) Datalog formulierte Anfragen lassen sich in relationale Algebra ohne Differenzoperator übersetzen, sogenannte monotone rel. Algebra. Dabei resultieren Prädikate im Körper in Joins bei Variablengleichheiten, sonst in kartesischen Produkten. Die Variablen im Kopf entspechen einer anschließenden Projektion. Dieses reine Datalog ist ausdrucksmächtiger als monotone rel. Algebra, da rekursive Regeln nicht in rel. Algebra ausdrückbar sind. Allerdings ist sie zur vollen rel. Algebra unvergleichbar, da Ausdrücke mit dem Differenzoperator formulierbar sind, die keine Entsprechung in Datalog haben.
Neben diesem reinen Datalog gibt es noch eine Reihe von Erweiterungen. Die wichtigsten davon, auf die wir aber nicht näher eingehen, sind:
(unter gleichzeitiger Beschränkung der Variablen
im Built-In Prädikat durch andere Prädikate im Körper der Regel).
Die erste Erweiterung hat seine Entsprechung in der Selektion von Konstanten in der relationalen Algebra. Die zweite Erweiterung, d.h. die Negation ,,not`` im Regelkörper darf nicht verwechselt werden mit dem Operator ,,not`` in Sql. Dort ist ,,not`` rein syntaktischer Zucker, sprich überflüssig. Bei Datalog führt die Einführung von ,,not`` zu Anfragen, die in rel. Algebra den Differenzoperator benötigen. Das bedeutet hinsichtlich der Ausdrucksmächtigkeit, daß stratified Datalog nun einen Teil dessen abdeckt was nur mit voller relationaler Algebra ausgedrückt werden kann, nicht aber mit der monotonen Variante.