Datalog
S. Costantini
Logic As a Query Language
• If-then logical rules have been used in
many systems.
• Recursive rules extend relational algebra
--- have been used to add recursion to
SQL-99.
S. Costantini / Logical Query
Languages
2
Datalog
• A language for Deductive Databases
– Extensional part: tables
– Intensional part: rules
S. Costantini / Logical Query
Languages
3
Logic: Intuition
S. Costantini / Logical Query
Languages
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 / Logical Query
Languages
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 / Logical Query
Languages
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 / Logical Query
Languages
7
Datalog Terminology: Facts
• Rules without body called “facts”:
E.g.,
in(alan,r123).
• Facts constitute the extensional part of
a deductive database, i.e., define tables.
S. Costantini / Logical Query
Languages
8
Alternative notation
• Explicitly list attributes
• E.g., facts:
in(Object:alan,Place:r123)
• E.g., rules:
in(Object:X,Place:Y):part_of(Place: Z, Place:Y),
in(Object:X, Place:Z).
S. Costantini / Logical Query
Languages
9
Datalog semantics
• 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 / Logical Query
Languages
10
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 / Logical Query
Languages
11
Least Herbrand Model:
Intuition
S. Costantini / Logical Query
Languages
12
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 / Logical Query
Languages
13
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 / Logical Query
Languages
14
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 / Logical Query
Languages
15
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) AND
Sells(bar2,beer,p2) AND p1 < 2.00
AND p2 < 2.00 AND bar1 <> bar2
S. Costantini / Logical Query
Languages
16
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 / Logical Query
Languages
17
Negated Subgoals:
Intuition
• Given atom A,
not A holds if A cannot be proved
• Negation as finite failure
S. Costantini / Logical Query
Languages
18
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 / Logical Query
Languages
19
Example: Unsafe Rules
•
Each of the following is unsafe and not
allowed:
1. S(x) <- R(y)
2. S(x) <- R(y) AND NOT R(x)
3. S(x) <- R(y) AND x < y
• In each case, an infinity of x ’s can satisfy
the rule, even if R is a finite relation.
S. Costantini / Logical Query
Languages
20
Datalog Programs
•
•
A Datalog program is a collection of
rules.
In a program, predicates can be either
1. EDB = Extensional Database = stored
table.
2. IDB = Intensional Database = relation
defined by rules.
S. Costantini / Logical Query
Languages
21
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 / Logical Query
Languages
22
Datalog semantics
• With negation: several proposals, in
deductive databases answer set
semantics.
S. Costantini / Logical Query
Languages
23
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 / Logical Query
Languages
24
Non-Monotonicità
• Aggiungere nuove conoscenze può
portare a ritrarre precedenti
conclusioni.
• Vi possono essere conclusioni alternative
tramite cicli sulla negazione.
S. Costantini / Logical Query
Languages
25
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 / Logical Query
Languages
26
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 / Logical Query
Languages
27
DATALOG + Negazione
• Semantica degli Answer Sets
• Paradigma dell’Answer Set Programming
(ASP)
• Negazione, insiemi-risposta alternativi
• Numerosi solver
S. Costantini / Logical Query
Languages
28
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 / Logical Query
Languages
29
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 / Logical Query
Languages
30
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 / Logical Query
Languages
31
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 / Logical Query
Languages
32
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 / Logical Query
Languages
33