Datalog

Un linguaggio di programmazione logica per basi di dati derivato dal Prolog

Utilizza predicati di due tipi:

• estensionali: relazioni della base di dati
• intensionali: corrispondono alle visite

Il linguaggio è basato su regole utilizzate per “definire” i predicati estensionali

Datalog, sintassi

Regole: $testa \leftarrow corpo$

• $testa$ è un predicato atomico (intensionale)
• $corpo$ è una lista (congiunzione) di predicati atomici

Le interrogazioni sono specificate per mezzo di predicati atomici (convenzionalmente preceduti da “?”)

Datalog, semantica

La definizione della semantica delle regole ricorsive è delicata (in particolare con la negazione)

Potere espressivo:

• Datalog non ricorsivo senza negazione è equivalente al calcolo senza negazione e senza quantificatore universale
• Datalog non ricorsivo con negazione è equivalente al calcolo e all’algebra
• Datalog ricorsivo senza negazione e calcolo sono incomparabili
• Datalog ricorsivo con negazione è più espressivo di calcolo e algebra