Datalog jest postrzegany często jako język zbudowany z klauzul Horna, w których nie występują symbole funkcyjne. Program w Datalogu (podobnie jak w Prologu) składa się z reguł typu „jeżeli-to”, w skład których wchodzą predykaty (nazwy funkcji logicznych), atomy relacyjne (predykat i jego argumenty) oraz atomy arytmetyczne (wyrażenia arytmetyczne wraz z argumentami).
Każda reguła składa się z: nagłówka – atomu relacyjnego symbolu ← – zwykle czytanego jako słowo „jeżeli" treści – jednego lub więcej atomów relacyjnych bądź arytmetycznych zwanych podzdaniami połączonych spójnikami logicznymi AND („i”) oraz OR („lub”)
Przykładami reguł w Datalogu są: JestSynem(X,Y) ← JestMężczyzną(X) AND JestRodzicem(Y,X) DroższyProdukt(X,Y) ← ProduktNaStanie(X,Cena1) AND ProduktNaStanie(Y,Cena2) AND Cena1 > Cena2
Jedną z częściej podkreślanych właściwości Datalogu jest istnienie trzech równoważnych (choć znacząco różniących się) podejść do definiowania semantyki programu. Te trzy podejścia to: semantyka teoriomodelowa semantyka stałopunktowa semantyka dowodowa