Datalog

Note

Datalog è un linguaggio query basato sul Prolog. È un linguaggio basato sulla programmazione logica, che è un paradigma di programmazione basato su delle regole.

Ogni regola è composta da una testa (LHS) e da un corpo (RHS) seguendo la sintassi:

P :- P1, P2, ..., Pn

Dove ogni rappresenta un predicato composto da nome, eventuale negazione e argomenti (possono essere costanti, variabili, simbolo "don't care"). Hanno l'interpretazione che la testa è vera se il corpo è vero.

Ciascuna -upla di una base di dati corrisponde ad un fatto, cioè una regola in cui la testa è un letterale senza variabili, il cui corpo non contiene condizioni ed è omesso.

Per eseguire una query (detta goal in datalog) si usa la sintassi:

? :- P1, P2, ..., Pn

Che restituirà un insieme per le variabili trovate. In caso non ci siano variabili un goal restituisce true o false.

Consideriamo in questa pagina la base di dati contenente le tabelle $à$ e . Degli esempi di regole possono essere:

Padre(X, Y) :- Persona(X, _, 'M'), Genitore(X, Y)
Madre(X, Y) :- Persona(X, _, 'F'), Genitore(X, Y)

Un fatto di questa base di dati può essere:

Genitore("Carlo", "Antonio")

Un esempio di Goal può essere:

? :- Padre("Carlo", X)

Che restituirà .

Corrispondenza con l'algebra relazionale

Possiamo vedere una corrispondenza tra Datalog e l'algebra relazionale. Le variabili in testa sono l'equivalente delle proiezioni, i predicati sono l'equivalente delle selezioni e l'insieme di predicati è l'equivalente dei join tra loro.

Per esempio l'espressione corrispondente di in algebra relazionale sarebbe:

Database estensionale e intensionale

Definiamo il database estensionale (EDB) come l'insieme delle tabelle presenti nel DB, e il database intensionale (IDB) come l'insieme dei predicati che sono a sinistra in una regola, che sono quindi la conoscenza dedotta a partire da EDB. Si impone che:

Tip

Nella definizione delle regole si possono usare predicati speciali, come operatori di confronto (, , , , , ) e funzioni aritmetiche (, , , ). Tuttavia bisogna stare attenti a non creare "cicli infiniti".

Negazione in Datalog

Note

Alcuni letterali del corpo possono essere negati tramite l'espressione not. L'uso della negazione in Datalog aumenta il potere espressivo del linguaggio, tuttavia richiede cautela poiché può portare a risultati infiniti.

Senza la negazione Datalog permette di rappresentare gli operatori , con rappresentato da:

P(X, Y) :- R(X, Y)
P(X, Y) :- S(X, Y)

Per ottenere la differenza serve il not:

P(X, Y) :- R(X, Y), not S(X, Y)

Evitare risultati infiniti

Per evitare risultati infiniti la negazione dev'essere safe, quindi tutte le variabili di un letterale negato devono comparire in un letterale positivo del corpo della regola. Questo esclude regole come:

S(X, Y) :- R(X), not Q(Y)

Inoltre, la negazione dev'essere stratificata, quindi non ci devono essere cicli di dipendenza tra letterali negati. Questo esclude regole come:

P(X) :- R(X), not P(x)

Query ricorsive

Note

È possibile effettuare query ricorsive, dove il letterale della testa si presenta all'interno del corpo della regola. Per esempio:

Antenato(X, Y) :- Genitore(X, Y)
Antenato(X, Y) :- Antenato(X, Z), Genitore(Z, Y)

Si può immaginare che questo processo sia eseguito iterativamente: Fino a quando .

Potere espressivo di Datalog

Siccome Datalog dispone di query ricorsive, è chiuso transitivamente. Questo non vale per l'algebra relazionale e di conseguenza Datalog ha più potere espressivo dell'algebra relazionale.