4. Datalog
Un programma datalog è un insieme di regole.
Ogni regola ha la seguente struttura p :- p1, p2, ..., pn, dove p (LHS, Right Hand Side) si chiama testa e p1,…pn vanno a comporre il corpo (RHS, Left Hand Side) della regola.
Ogni p si chiama letterale ed è un’istanza di un predicato, così formato:
- Nome
- Lista di argomenti tra parentesi tonde:
- costanti
- variabili
- simbolo “don’t care” (_), che non può comparire nella testa di una regola
Regola di safety n.1: le variabili del LHS devono comparire in un letterale del RHS.
Esempio di regola in datalog
StudenteMat(M) :- Studente(M, N, C, CL), Esame(M, CC, D, V),
Corso(CC, "Matematica", DOC)
Fatti
Una regola può essere formata solo dalla testa (LHS), ma in tal caso può avere solo costanti al suo interno (vedi regola 1 della safety).
Queste regole particolari si chiamano fatti.
Esempio: Parte_di(a,b)
Regole datalog e basi di dati
D’ora in poi useremo il seguente DB per i prossimi esempi.
Ogni tupla corrisponde a un fatto di base (o letterale ground). Esempio: Genitori(”Carlo”, “Antonio”)
Unificazione
Una regola ha un’interpretazione:
- Il LHS è vero se il RHS è vero
- Il RHS è vero se per ogni letterale presente tutte le variabili sono unificabili, ovvero sostituibili con valori costanti che rendono vero il letterale.
Esempio: Genitori(X,Y) ha come unificazioni possibili tutte le tuple della tabella genitori.
Si definisce DB Intensionale l’insieme dei predicati che sono a sinistra di una regola.
Si definisce DB Estensionale l’insieme delle tabelle presenti nel DB.
Di solito si impone che essi abbiano intersezione vuota.
Query in datalog
La sintassi è ? - p(v1,...vn), dove p è un letterale e v1,…vn sono variabili del letterale.
Esempio: ? - Genitori("Anna",X).
Una query viene anche chiamate goal.
Un goal con solo costanti restituisce true o false.
Negazione in datalog
Alcuni letterali del corpo possono essere negati.
L’uso della negazione in Datalog aumenta il potere espressivo del linguaggio, ma il suo uso richiede cautela:
(\lnot)
q(X) :- \lnot p(X)
p(0)
? - q(X)Questa query produce un risultato potenzialmente infinito!
Query ricorsive
In datalog è possibile effettuare delle query ricorsive.
Una query ricorsiva (immediata) presenta il letterale della testa all’interno del corpo della regola:
Antenato(X,Y) :- Genitore(X,Y)
Antenato(X,Y) :- Antenato(X,Z),Genitore(Z,Y)
Valutazione delle query ricorsive
Viene eseguito il seguente processo iterativo: parto dall’insieme vuoto, e ad ogni iterazione applico le regole e unisco il risultato al risultato precedente.
Predicati e funzioni
Nella definizione delle regole è possibile usare predicati speciali:
- Operatori di confronto: =, , >, ≥, <, ≤
- Funzioni aritmetiche: +, -, *, /
Regole ben formate
La negazione deve essere safe: tutte le variabili di un letterale negato (o di un letterale con predicati built-in) devono comparire anche in un letterale positivo del corpo della regola.
Esempio: S(X) :- R(X) non va bene.
La negazione deve essere stratificata: non ci devono essere cicli di dipendenza tra letterali negati.
Esempio: P(X) :- R(X),S(Y,X)
R(Y) :- T(X,Y),¬ P(Y).
Non va bene!
