Datalog
S. Costantini
Datalog base: notazione,
esempi, semantica
S. Costantini / Datalog e ASP
2
Datalog
• A language for Deductive Databases
– Extensional part: tables
– Intensional part: rules
S. Costantini / Datalog e ASP
3
Logic: Intuition
S. Costantini / Datalog e ASP
4
Datalog Terminology:
Atoms
• An atom is a predicate, or relation name
with variables or constants as arguments.
E.g.,
in(alan,r123)
part_of(r123,cs_building)
p(X,a)
S. Costantini / Datalog e ASP
5
Datalog Terminology:
Atoms
• Conventions:
– Databases: Predicates begin with a capital,
variables begin with lower-case. Example:
P(x,’a’) where ‘a’ is a constant, i.e., a data
item.
– Logic Programming: Variables begin with a
capital, predicates and constants begin with
lower-case. Example: p(X,a).
S. Costantini / Datalog e ASP
6
Datalog Terminology: Rules
• The head of a rule is an atom; the body
of a rule is the AND of one or more
atoms.
E.g.,
in(X,Y):- part_of(Z,Y), in(X,Z).
where “:-” stands for “”
S. Costantini / Datalog e ASP
7
Datalog Terminology: Rules
• Rules without body:
E.g.,
in(alan,r123).
S. Costantini / Datalog e ASP
8
Datalog and Transitivity
• Rule
in(X,Y):- part_of(X,Z),in(Z,Y)
defines in as the transitive closure of
part_of
S. Costantini / Datalog e ASP
9
Arithmetic Subgoals
• In addition to relations as predicates, a
predicate of the body can be an
arithmetic comparison.
– We write such atoms in the usual way,
e.g.: x < y.
S. Costantini / Datalog e ASP
10
Example: Arithmetic
• A beer is “cheap” if there are at least
two bars that sell it for under $2.
cheap(Beer) :sells(Bar1,Beer,P1),
sells(Bar2,Beer,P2), P1 < 2.00,
P2 < 2.00, Bar1 <> Bar2.
S. Costantini / Datalog e ASP
11
Datalog
Terminology:
p  q, not r.
or
p :- q, not r.
is a rule, where p is the head, or conclusion, or
consequent, and q, not r is the body, or the
conditions, or the antecedent. p, q and r are atoms.
A rule without body, indicated as
p .
or
p.
Is called a unit rule, or a fact.
This kind of rules ale also called Horn Clauses.
S. Costantini / Datalog e ASP
12
Datalog
Terminology:
p  q, not r
Atoms in the body can be called subgoals.
Atoms which occur positively in the body are
positive literals, and the negations are negative
literals.
S. Costantini / Datalog e ASP
13
Datalog
Terminology:
p  q, not r
We say that p depends on q and not r.
The same atom can occur in a rule both as a
positive literal, and inside a negative literal
(e.g. rule p  not p).
S. Costantini / Datalog e ASP
14
Datalog Programs
•
•
A Datalog theory, or “program”, is a
collection of rules.
In a program, predicates can be either
1. EDB = Extensional Database = facts.
2. IDB = Intensional Database = relation
defined by rules.
S. Costantini / Datalog e ASP
15
Expressive Power of
Datalog
• Without recursion, Datalog can express
all and only the queries of core relational
algebra.
• But with recursion, Datalog can express
more than these languages.
• Yet still not Turing-complete.
S. Costantini / Datalog e ASP
16
Example
p(X) r(X),q(X).
r(Z)  s(Z).
s(a).
s(b).
q(b).
• In every rule, each variable stands for the same
value.
• Thus, variables can be considered as
“placeholders” for values.
• Possible values are those that occur as
constants in some rule/fact of the program itself.
S. Costantini / Datalog e ASP
17
Datalog
Its grounding can be obtained by:
• considering the constants, here a,b.
• substituting variables with constants in any
possible (coherent) way)
• E. g., the atom r(Z) is transformed by grounding
over constants a, b into the two ground atoms
r(a), r(b).
S. Costantini / Datalog e ASP
18
Grounding
• E. g., the atom r(Z) is transformed by grounding
over constants a, b into the two ground atoms
r(a), r(b).
• Rule r(Z)  s(Z). is transformed into the two
rules
r(a)  s(a).
r(b)  s(b).
S. Costantini / Datalog e ASP
19
Datalog
Grounding of the program
p(a)  r(a),q(a).
p(b)  r(b),q(b).
r(a)  s(a).
r(b)  s(b).
s(a).
s(b).
q(b).
Semantics: Least Herbrand Model
M = {s(a),s(b),q(b),r(a),r(b),p(b)}
S. Costantini / Datalog e ASP
20
Datalog
A shortcut of the grounded program
p1  r1,q1.
p2  r2,q2.
r1  s1.
r2  s2.
s1.
s2.
q2.
M = {s1,s2,q2,r1,r2,p2}
S. Costantini / Datalog e ASP
21
Datalog semantics
• Without negation (no negative literal in
the body of rules): Least Herbrand
Model
– The head of a rule is in the Least Herbrand
Model only if the body is in the Least
Herbrand Model.
S. Costantini / Datalog e ASP
22
Least Herbrand Model:
Intuition
S. Costantini / Datalog e ASP
23
Least Herbrand Model:
Intuition
In the example: Least Herbrand Model
M0 = {in(alan,r123), part_of(r123,cs_building)}
M1= {in(alan,r123), part_of(r123,cs_building),
in(alan,cs_building)}
S. Costantini / Datalog e ASP
24
Least Herbrand Model: How to find it
p g,h.
g  r,s.
m  p,q.
r  f.
s.
f.
h.
Step 1: facts
M0 = {s,f,h}
Step 2: M1 = M0 plus what I can derive from facts
M1 = {s,f,h,r}
Step 3: M2 = M1 plus what I can derive from M1
M2 = {s,f,h,r,g}
Step 4: M3 = M2 plus what I can derive from M2
M3 = {s,f,h,r,g,p}
If you try to go on, no more added conclusions: fixpoint
S. Costantini / Datalog e ASP
25
Datalog con Negazione
S. Costantini / Datalog e ASP
26
Negated Subgoals
• We may put NOT in front of an atom, to
negate its meaning.
• Example:
at_home(alan):- not at_work(alan).
S. Costantini / Datalog e ASP
27
Negated Subgoals:
Intuition
• Given atom A,
not A holds if A cannot be proved
• Negation as finite failure
S. Costantini / Datalog e ASP
28
Minimal Models
• When there is no negation, a Datalog
program has a unique minimal model (one
that does not contain any other model).
• But with negation, there can be several
minimal models.
S. Costantini / Datalog e ASP
29
Cos’è un modello minimo: è un
insieme di atomi
Data una regola
A:- B1,...,Bn,not C1,...,not Cm
• Un modello è un insieme di atomi che se
NON contiene C1,...,Cm e contiene
B1,...,Bn allora deve contenere A
• Un modello minimo non è sovrainsieme di
un altro modello
S. Costantini / Datalog e ASP
30
Datalog semantics
• With negation: several proposals, in
deductive databases Answer Set
Semantics.
• Based on Answer Set Semantics: Answer
Set Programming, new logic programming
paradigm
S. Costantini / Datalog e ASP
31
Safe Rules
•
A rule is safe if:
1. Each variable in the head
2. Each variable in an arithmetic subgoal,
3. Each variable in a negated subgoal,
•
also appears in a nonnegated,
subgoal in the body.
We allow only safe rules.
S. Costantini / Datalog e ASP
32
Example: Unsafe Rules
•
Each of the following is unsafe and not
allowed:
1. s(X) :- r(Y).
2. s(X) :- r(Y), not r(X).
3. s(X) :- r(Y), X < Y.
• In each case, an infinity of X ’s can satisfy
the rule, even if R is a finite relation.
S. Costantini / Datalog e ASP
33
Non-Monotonicità
• Aggiungere nuove conoscenze può
portare a ritrarre precedenti
conclusioni.
• Vi possono essere conclusioni alternative
tramite cicli sulla negazione.
S. Costantini / Datalog e ASP
34
Non-Monotonicità =
Problema?
• No, se gestita con opportuni
strumenti semantici
• Non-Monotonic Reasoning (NMR) =
campo di ricerca in
– Intelligenza Artificiale
– Database deduttivi
• si propone di sfruttare la nonmonotonicità
S. Costantini / Datalog e ASP
35
DATALOG senza Negazione
• Semantica del Least Herbrand Model
• Paradigma procedurale della ricerca per
tentativi ripetuti
• Linguaggio Prolog (numerosi interpreti
fra i quali SICSTUS-Prolog, SWIProlog)
S. Costantini / Datalog e ASP
36
DATALOG + Negazione
• Semantica degli Answer Sets
• Paradigma dell’Answer Set Programming
(ASP)
• Negazione, insiemi-risposta alternativi
• Numerosi solver
S. Costantini / Datalog e ASP
37
Esempio NMR
persona(anna).
persona(carlo).
persona(giorgio).
malato(giorgio).
a_casa(X):- persona(X), not in_ufficio(X).
in_ufficio(X):- persona(X), not a_casa(X).
:- in_ufficio(X),malato(X). % constraint
S. Costantini / Datalog e ASP
38
Risultato atteso
• Anna e Carlo sono o a casa oppure in
ufficio.
• Giorgio non può essere in ufficio
perchè è malato e quindi sarà a casa.
S. Costantini / Datalog e ASP
39
NMR in pratica
• Vi sono vari linguaggi logici che
consentono non-monotonicità.
• Sono dotati di motori inferenziali
(inference engines, o solvers) in grado di
gestirla.
• Possibili soluzioni inesistenti o
altrernative.
• Uno di essi: smodels
S. Costantini / Datalog e ASP
40
Risultato di smodels
(inference engine per NMR)
• Answer: 1
malato(giorgio) a_casa(giorgio) a_casa(carlo)
in_ufficio(anna)
• Answer: 2
malato(giorgio) a_casa(giorgio) in_ufficio(carlo)
in_ufficio(anna)
S. Costantini / Datalog e ASP
41
Risultato di smodels
(inference engine per NMR)
• Answer: 3
malato(giorgio) a_casa(giorgio) in_ufficio(carlo)
a_casa(anna)
• Answer: 4
malato(giorgio) a_casa(giorgio) a_casa(carlo)
a_casa(anna)
S. Costantini / Datalog e ASP
42
Datalog con negazione: nuovo
Paradigma
di Programmazione Logica
Answer Set Programming
(ASP)
basato su Answer Set
Semantics
S. Costantini / Datalog e ASP
43
Uno sguardo sull’Answer
Set Programming (ASP)
S. Costantini / Datalog e ASP
44
Example: 3-coloring in ASP
Assigning colors red/blue/green to vertices of a
graph, so as no adjacent vertices have the
same color.
node(0..3).
col(red).
col(blue).
col(green).
edge(0,1).
edge(1,2).
edge(2,0).
edge(1,3).
edge(2,3).
S. Costantini / Datalog e ASP
45
3-coloring in Answer Set
Programming
color(X,red) | color(X,blue) | color(X,green) :- node(X).
:- edge(X,Y), col(C), color(X,C), color(Y,C).
% I constraint (regole con conclusione vuota)
% specificano cosa *non può* essere vero
S. Costantini / Datalog e ASP
46
Come “eseguire” il programma?
• Si usa un “Motore Inferenziale”, ad
esempio SMODELS (ma ce ne sono
diversi)
• Esso fornisce le soluzioni al problema
dato come “insiemi risposta, appunto
“Answer Set”
S. Costantini / Datalog e ASP
47
Come “eseguire” il programma?
• Sintassi:
lparse < 3col.txt | smodels 0
• lparse effettua il parsing del programma dato
e ne produce il grounding
• smodels calcola le risposte (smodels 0 le
chiede tutte)
…
…
S. Costantini / Datalog e ASP
48
Cosa si ottiene nell’esempio?
Answer1
color(0,red), color(1,blue), color(green), color(3,red)
Answer2
color(0,red), color(1,green), color(blue), color(3,red)
…
% e tutte le altre colorazioni, ognuna come
% “Answer Set”
…
S. Costantini / Datalog e ASP
49
Answer Set Semantics: su
cosa si basano gli Answer
Set e come si ottengono
S. Costantini / Datalog e ASP
50
Cos’è un modello minimo: è un
insieme di atomi
Data una regola
A:- B1,...,Bn,not C1,...,not Cm
• Un modello è un insieme di atomi che se
NON contiene C1,...,Cm e contiene
B1,...,Bn allora deve contenere A
• Un modello minimo non è sovrainsieme di
un altro modello
S. Costantini / Datalog e ASP
51
Modelli minimi Datalog
• I fatti fanno parte di tutti i modelli
minimi
• Tutto ciò che si deriva in modo aciclico
dai fatti fa parte di tutti i modelli minimi
• not A vale solo se non vale A
S. Costantini / Datalog e ASP
52
Esempio
a:- not b.
b:- e, not c.
c.
e.
M = {c, e, a}
S. Costantini / Datalog e ASP
53
Esempio
a:- not b.
b:- not a.
d:- c.
c
M1 = {c, d, a} M2 = {c, d, b}
Cicli: vari modelli (diversi Answer Sets)
S. Costantini / Datalog e ASP
54
Cos’è un Answer Set
• E’ un modello minimo dove però dati due
qualunque atomi che ne fanno parte,
nessuno di essi può dipendere
(direttamente o indirettamente) dalla
negazione dell’altro
• (negazione coerente)
S. Costantini / Datalog e ASP
55
Esempio
a:- not b.
b:- not a.
p:- not p, not a.
{b,p} modello minimo, NO answer set
{a} modello minimo, answer set
S. Costantini / Datalog e ASP
56
Come si trovano gli Answer Set
• Cicli pari (dipendenze cicliche che
coinvolgono un numero pari di atomi)
a:- not b.
b:- not a.
M1 = {a}
M2 = {b}
S. Costantini / Datalog e ASP
57
Come si trovano gli Answer Set
• Cicli pari
a:- not b.
b:- not c.
c:- not d.
d:- not a.
M1 = {a,c}
M2 = {b,d}
S. Costantini / Datalog e ASP
58
Come si trovano gli Answer Set
• Ogni ciclo pari ha due Answer Set, uno
costituito dagli atomi “pari” del ciclo, l’altro
da quelli “dispari”.
• Se vi sono diversi cicli pari, gli answer set
si combinano
S. Costantini / Datalog e ASP
59
Come si trovano gli Answer Set
a:- not b.
b:- not c.
c:- not d.
d:- not a.
M11 = {a,c,e}
M21 = {b,d,e}
e:- not f.
f:- not e.
M12 = {a,c,f}
M22 = {b,d,f}
S. Costantini / Datalog e ASP
60
Come si trovano gli Answer Set
• Cicli dispari (dipendenze cicliche che
coinvolgono un numero dispari di atomi)
p:- not p.
No Answer Set: contraddizione sulla
negazione {p}
S. Costantini / Datalog e ASP
61
Come si trovano gli Answer Set
• Cicli dispari (dipendenze cicliche che
coinvolgono un numero dispari di atomi)
a:- not b.
b:- not c.
c:- not a.
No Answer Set: contraddizione sulla
negazione Es. {a,c} {a,b} {b,c}
S. Costantini / Datalog e ASP
62
Come si trovano gli Answer Set
• Programmi con cicli dispari: possono
avere Answer Set solo se:
– vi sono anche cicli pari
– vi sono connessioni fra cicli pari e dispari
che “rimuovono” le contraddizioni
• Chiamiamo queste speciali connessioni
“Handle”
S. Costantini / Datalog e ASP
63
Come si trovano gli Answer Set:
OR Handle
• OR Handle: legata a regola alternativa
per uno degli atomi del ciclo dispari
a:- not b.
p:- not p.
b:- not a.
p:- a.
OR handle
M = {a,p}
S. Costantini / Datalog e ASP
64
Come si trovano gli Answer Set
• OR Handle: legata a regola alternativa per uno
degli atomi del ciclo dispari
a:- not b.
p:- not q.
b:- not a.
q:- not r.
r:- not p.
q:- not b. OR handle
M = {a,q,r}
S. Costantini / Datalog e ASP
65
Come si trovano gli Answer Set
• OR handle: regola alternativa per un
qualche atomo che fa parte del ciclo
dispari. Il corpo deve essere VERO per
“supportare” l’atomo
S. Costantini / Datalog e ASP
66
Come si trovano gli Answer Set
• AND Handle: letterale aggiuntivo in una
delle regole del ciclo dispari:
a:- not b.
p:- not p, not a. AND
b:- not a.
handle
M = {a}
S. Costantini / Datalog e ASP
67
Come si trovano gli Answer Set
• Cicli dispari: Answer set se Handle da
cicli pari
a:- not b.
p:- not p, a.
AND
b:- not a.
handle
M = {b}
S. Costantini / Datalog e ASP
68
Come si trovano gli Answer Set
• Cicli dispari: Answer set se Handle da
cicli pari
• AND handle: letterale L (A oppure not A)
nel corpo di una regola del ciclo dispari,
dove A fa parte di un ciclo pari. L deve
essere FALSO per “aprire” il ciclo
dispari rendendo falso uno dei suoi atomi
S. Costantini / Datalog e ASP
69
Come si trovano gli Answer Set
1.
2.
3.
4.
5.
6.
Si cercano gli Answer Set della parte aciclica “di
base” del programma
Si cercano gli Answer Set dei cicli pari
Si combinano le due componenti
Si estendono alla parte aciclica “intermedia” (se c’è)
Fra gli Answer Set risultanti si selezionano quelli (se
vi sono) che forniscono handle ai cicli dispari
Si riconsidera la parte aciclica “top” rimanente (se
c’è)
S. Costantini / Datalog e ASP
70
Come si trovano gli Answer Set
c.
d:- c.
a:- not b.
b:- not a.
e:- b.
h:- b,p.
p:- not p.
p:- e.
g:- p.
S. Costantini / Datalog e ASP
71
Come si trovano gli Answer Set:
parte aciclica di base
c.
d:- c.
M1 = {c,d}
S. Costantini / Datalog e ASP
72
Come si trovano gli Answer Set:
ciclo pari e parte aciclica intermedia
a:- not b.
b:- not a.
e:- b.
M1 = {c,d}
M11 = {a,c,d} M12 = {b,c,d,e}
S. Costantini / Datalog e ASP
73
Come si trovano gli Answer Set:
ciclo dispari e parte aciclica”top”
p:- not p.
p:- e.
g:- p.
• Si seleziona M12 per dare la OR handle
all’atomo p.
M = {b,c,d,e,p,g}
S. Costantini / Datalog e ASP
74
Caso problematico
p:- not p, not a.
q:- not q, not b.
a:- not b.
b:- not a.
Per ciclo pari M1 = {a} M2 = {b}
ma non abbiamo le due AND handle per i cicli
dispari (richiesta contraddittoria): no Answer Set
S. Costantini / Datalog e ASP
75
Caso problematico Risolto
p:- not p, not a.
p:- e.
q:- not q, not b.
a:- not b.
e:- not f.
b:- not a.
f:- not e.
Per cicli pari
M11 = {a,e} M12 = {a,f}
M21 = {b,e} M12 = {b,f}
Con M21 otteniamo M1 = {b,p,e}
S. Costantini / Datalog e ASP
76
ASP più in dettaglio
S. Costantini / Datalog e ASP
77
Answer Set Programming
Constraints
:- v,w,z.
rephrased as
p :- not p, v,w,z.
S. Costantini / Datalog e ASP
78
Answer Set Programming
Disjunction
v | w |z.
rephrased as
v :- not w, not z.
w :- not v, not z.
z :- not v, not w.
S. Costantini / Datalog e ASP
79
Answer Set Programming
Choice (XOR)
v+w+z.
rephrased as
v | w | z.
:- w, z.
:- v, z.
:- v, w.
S. Costantini / Datalog e ASP
80
Answer Set Programming
Classical Negation ¬p
- p :- q,r.
rephrased as
p' :- q,r.
:- p,p‘
S. Costantini / Datalog e ASP
81
Answer Set Programming
A party: guests that hate each other cannot seat together,
guests that love each other should sit together
table(1..3).
guest(1..5).
hates(1,3). hates(2,4).
hates(1,4). hates(2,3).
hates(4,5). hates(1,5).
likes(2,5).
S. Costantini / Datalog e ASP
82
Answer Set Programming
% Choice rules
1{at_table(P,T) : table(T)}1 :- guest(P).
0{at_table(P,T) : guest(P)}3 :- table(T).
S. Costantini / Datalog e ASP
83
Answer Set Programming
% Choice rules
n { p(X,Y) : d1(X) } m :- d2(Y).
Meaning: forall Y which is a d2 we admit only
answer sets with at least n atoms and at most
m atoms
of the form p(X,Y), where X is a d1
S. Costantini / Datalog e ASP
84
Answer Set Programming
% hard constraint
:- hates(P1,P2),at_table(P1,T),at_table(P2,T),
guest(P1),guest(P2),table(T).
S. Costantini / Datalog e ASP
85
Answer Set Programming
% should be a soft constraint!
:- likes(P1,P2), at_table(P1,T1),
at_table(P2,T2),
T1 != T2,
guest(P1), guest(P2),table(T1),table(T2).
S. Costantini / Datalog e ASP
86