Transcript Template file - Goldsmiths, University of London

Logic databases
Logic databases
1
Logic databases
Overview
 motivation and informal introduction of
deductive databases
 components of deductive databases




domains and axioms
queries
updates
integrity constraints
 further issues
2
Logic databases
Relational databases
Data
relations specified
extensionally
select / filter
Required
result
by evaluating a
(relational algebra)
formula
3
Logic databases
Example - database (extension)
Person
Name
Linda Fox
John Fox
Mary Fox
June Fox
Bill Fox
John Hunt
Jack Hunt
Helen Kent
Dean Kent
Parent
Dob Sex Address
F
M
F
F
M
M
M
F
F
P-name
C-name
Linda Fox
Linda Fox
Linda Fox
John Fox
John Fox
John Fox
Mary Fox
Mary Fox
June Fox
June Fox
Mary Fox
June Fox
Bill Fox
Mary Fox
June Fox
Bill Fox
John Hunt
Jack Hunt
Helen Kent
Dean Kent
4
Logic databases
Example - query #1
Find who is Dean Kent’s mother
SELECT
FROM
WHERE
Person.Name
Person, Parent
Person.Sex = ‘F’ AND
Person.Name = Parent.Name AND
Parent.Child = ‘Dean Kent’ ;
5
Logic databases
Example - query #2
Find who is Dean Kent’s grandmother, on his mother’s side
SELECT
FROM
WHERE
Person.Name
Person, Parent
Person.Sex = ‘F’ AND
Person.Name = Parent.Name AND
Parent.Child IN
(SELECT
Person.Name
FROM
Person, Parent
WHERE
Person.Sex = ‘F’ AND
Person.Name = Parent.Name AND
Parent.Child = ‘Dean Kent’);
6
Logic databases
Example - query #3
Find all mothers (and their addresses) who have at least one daughter
SELECT
FROM
WHERE
Name, Address
Person
Sex = ‘F’ AND EXISTS
(SELECT
*
FROM
Parent
WHERE
Person.Name = Parent.Name AND
Parent.Child IN
(SELECT
*
FROM
Person
WHERE
Sex = ‘F’)) ;
7
Logic databases
Example - query #4
Find all grandmothers (and their addresses)
who have at least one grand daughter
homework
8
Logic databases
Example #1 - conclusion
 the answer to ‘grandmother’ queries would
have been easier if a ‘Grandparent’ relation had
existed
 improper solution if the relation would have been
defined extensionally - redundancies (exemplified in
the following slides)
 therefore intensional definitions are required
(exemplified on the following slides)
 could the query language be simpler?
 yes; Datalog (Prolog like), for instance
9
Logic databases
‘Grandparent’ relation - extensionally
Parent
Name
Linda Fox
Linda Fox
Linda Fox
John Fox
John Fox
John Fox
Mary Fox
Mary Fox
June Fox
June Fox
Grandparent
Child
Mary Fox
June Fox
Bill Fox
Mary Fox
June Fox
Bill Fox
John Hunt
Jack Hunt
Helen Kent
Dean Kent
Name
Linda Fox
Linda Fox
Linda Fox
Linda Fox
John Fox
John Fox
John Fox
John Fox
Grandchild
John Hunt
Jack Hunt
Hellen Kent
Dean Kent
John Hunt
Jack Hunt
Helen Kent
Dean Kent
10
Logic databases
not really
a good solution
11
Logic databases
‘Grandparent’ relation - intensionally
Parent
Name
Linda Fox
Linda Fox
Linda Fox
John Fox
John Fox
John Fox
Mary Fox
Mary Fox
June Fox
June Fox
Child
Mary Fox
June Fox
Bill Fox
Mary Fox
June Fox
Bill Fox
John Hunt
Jack Hunt
Helen Kent
Dean Kent
A is Grandparent of B
IFF
/* there is a C such that */
A is the Parent of C
AND
C is the Parent of B
12
Logic databases
Activity
Reconsider the issues discussed so far on the Person’ relation below,
which substitutes the previous (page 4) Person and Parent relations.
Person’
Name
Linda Fox
John Fox
Mary Fox
June Fox
Bill Fox
John Hunt
Jack Hunt
Helen Kent
Dean Kent
Dob Sex Address
F
M
F
F
M
M
M
F
F
Mother
null
null
Linda Fox
Linda Fox
Linda Fox
Mary Fox
Mary Fox
June Fox
June Fox
Father
null
null
John Fox
John Fox
John Fox
null
nul
null
null
13
Logic databases
Example - database (extension) #2
Person
Name
Linda Fox
John Fox
Mary Fox
June Dyer
Bill Dyer
John Hunt
Rose Hunt
Helen Kent
Dean Kent
Parent
Dob Sex Address
F
M
F
F
M
M
M
F
F
Name
Linda Fox
John Fox
Mary Fox
Mary Fox
John Hunt
June Dyer
Jack Hunt
Jack Hunt
Child
Mary Fox
Mary Fox
John Hunt
Rose Hunt
June Dyer
Bill Dyer
Helen Kent
Dean Kent
14
Logic databases
Example - query #5
Find who Bill Dyer’s ancestors are.
 recursive query
 not possible to answer in the relational model
 another formalism is necessary - which allows
recursive definitions
15
Logic databases
Recursive definition
A is ancestor of P
IFF
A is parent of P
A is ancestor of P
IFF
 B (B is ancestor of P AND A is parent of B)
16
Logic databases
Intermediate conclusion
 a mechanism is required to
 allow relations to be intensionally defined
 allow new facts to be deduced from the
database
 based on the defined facts and rules
 by means of some reasoning methods
 note
 the motivation for deductive databases is more
complex (i.e. not reduced to the above two aspects)
17
Logic databases
Deductive database - informal definition
 a database that supports the definition of both facts
(extensionally defined relations) and rules (intensionally
defined relations) and which supplies a reasoning
mechanism by means of which existing or new facts
can be deduced from the database
 a deductive database uses logic (first order predicate
logic) as its representational formalism
18
Logic databases
Relational vs Deductive databases
model theoretic
extensionally
defined relations
evaluating
a formula
result
proof theoretic
ground axioms
deductive axioms
reasoning
mechanism
result
19
Logic databases
Deductive databases - domains
name(‘Linda Fox’).
name(‘John Fox’).
name(‘Mary Fox’).
name(‘June Dyer’).
name(‘Bill Dyer’).
name(‘John Hunt’).
...
sex(m).
sex(f).
sex(other).
month(1).
month(2).
...
month(12).
20
Logic databases
Deductive databases - ground axioms
person(‘Linda Fox’, dob(10, 12, 1823), f).
person(‘John Fox’, dob(2, 11, 1811, m).
person(‘Mary Fox’, dob(12, 4, 1850), f).
person(‘John Hunt’, dob(30, 1, 1875), m).
person(‘Rose Hunt’, dob(25, 3, 1877), f).
...
parent(‘Linda Fox’, ‘Mary Fox’).
parent(‘John Fox’, ‘Mary Fox’).
parent(‘Mary Fox’, ‘John Hunt’).
parent(‘Mary Fox’, ‘Rose Hunt’).
...
married_to(‘Linda Fox’, ‘John Fox’).
%having a child together
married_to(‘John Hunt’, ‘Christa Wolf’). %does not mean ‘married’
...
%powerful representation!
21
Logic databases
Deductive databases - deductive axioms
ancestor(X, Y, 1) :parent(X, Y).
ancestor(X, Y, Distance) :parent(X, Z),
ancestor(Z, Y, Init_dist),
Distance is Init_dist +1.
%built in arithmetics
brother_or_sister(X, Y) :parent(Z, X), parent(Z, Y).
%can be refined using ‘sex’
unfaithful(X, Y) :married_to(X, Y),
parent(X, Z),
not parent(Y, Z).
%negation as failure
22
Logic databases
Language elements








constants, terms (structured objects), variables
assertions (unnamed attributes)
definitions
generalised Horn clauses
closed world assumption
negation as finite failure
built in Arithmetic (scalar functions)
how to design the database?
 depends on what we want to express
 example: reification -> a more a powerful representation
23
Logic databases
Normal forms - CNF
 conjunctive normal form (CNF)
 a conjunction of disjunctions of literals
 e.g. (A1A2A3)  (B1B2B3)  (C1 C2)
 every formula can be brought to CNF
24
Logic databases
Normal forms - clausal
 clausal form
 equivalent to CNF
 each disjunction (in CNF) is represented separately as
an implication; e.g.:
(A1A2A3)  (B1B2B3)  (C1 C2)
• becomes
A1, A2, A3
(reads: it is true that A1A2A3)
B1  B2, B3
(reads: B1 if B2  B3)
 C1,C2
(reads: C1  C2 is false)
 all literals are positive
 every formula can be brought to the clausal form
25
Logic databases
Normal forms - Horn clauses
 DEF1: a clause with just one literal (implicitly
positive) in the conclusion
 B1  B2, B3 is a Horn clause
 B1, B2  B3 is not a Horn clause
 DEF2: a disjunction with one positive literal
only
 B1  B2  B3 is a Horn clause
 B1  B2  B3 is not a Horn clause
26
Logic databases
Logic database
 In the rest of this lecture, a logic
database is considered to be a set of
Horn clauses enhanced with negation
as finite failure (generalised Horn
clauses)
27
Logic databases
Queries
Yes/No queries
Is Bill Dyer a man?
:- person(‘Bill Dyer’, _, m).
Find value(s) queries - use of only ground axioms
Who is Linda Fox married to?
:- married_to(‘Linda Fox’, X).
28
Logic databases
Queries
Find value(s) queries - use of deductive axioms
Who are the brothers and sisters of John Hunt?
:- brother_or_sister(‘John Hunt’, X).
%one sol at a time
:- forall(brother_or_sister(John Hunt’, X)). %all sols
Find value(s) queries - use of recursive deductive axioms
Who are the ancestors of John Hunt?
:- ancestor(‘John Hunt’, X).
:- forall(ancestor(John Hunt’, X)).
%one sol. at a time
%all sols.
29
Logic databases
Reasoning mechanism
 resolution
(X  A1  A2  ...  An)
(X  B1  B2  ...  Bm)
(A1  A2  ...  An  B1  B2  ...  Bm)
 A1, A2, ... , An, B1, B2, ... , Bm are all positive or negative literals
30
Logic databases
Resolution for Horn clauses
X  A1 , A2 , ... , Ak , ... , An
Ak  B1 , B2 , ... , Bm
X  A1 , A2 , ... , B1 , ... , Bm, ..., An
31
Logic databases
Basic manipulation primitives
assert(person(‘Brooklin Peckham’, dob(1, 3, 1899), m)).
assert(parent(‘Brooklin Peckham’, ‘David Peckham’)).
assert(parent(‘Brooklin Peckham’, ‘Gingy Spicy’)).
assert(married_to(‘David Peckham’, Gingy Spicy’)).
...
retract(person(‘Linda Fox’, _, _, _)).
retract(married_to(‘Linda Fox’, ‘John Fox’)).
...
32
Logic databases
Updating the databse
 via assert and retract
 equivalent to delete / insert
 note the same formalism for data definition
and data manipulation
33
Logic databases
Integrity constraints
 integrity constraints and rules in deductive
databases are syntactically indistinguishable
 rules - are sentences which define the data and
are part of the database (Kowalski)
 integrity constraints - are sentences which
constrain the data and are not part of the database
(Kowalski)
 the same sentence can be regarded, in different
contexts, as rule or integrity constraint
34
Logic databases
Sentence as rule
person(‘Linda Fox’, dob(10, 12, 1823), f).
person(‘John Fox’, dob(2, 11, 1811, m).
...
parent(‘Linda Fox’, ‘Mary Fox’).
parent(‘John Fox’, ‘Mary Fox’).
...
%two different persons are married if they have a child together
% parent(X, Z)  parent(Y, Z)  different(X,Y) married_to(X, Y)
%definition - part of the database (definition)
married_to(X, Y) :parent(X, Z),
parent(Y, Z),
not X = Y.
35
Logic databases
Sentence as a constraint
person(‘Linda Fox’, dob(10, 12, 1823), f).
...
parent(‘Linda Fox’, ‘Mary Fox’).
parent(‘John Fox’, ‘Mary Fox’).
...
married_to(‘Linda Fox’, ‘John Fox’).
...
%if two different persons have a child together then they must be
%married
%constraint - not part of the database (definition)
%parent(X, Z)  parent(Y, Z)  different(X,Y)  married_to(X, Y)
:- parent(X, Z), parent(Y, Z), not X = Y, not married_to(X, Y).
36
Logic databases
Constraints enforcement #1
%a simple checking mechanism at the time of update
make_parent(X, Y) :parent(X, Y).
make_parent(X, Y) :not parent(X, Y), %X is bound from the head; it is an update
not (parent(Z, Y), not married_to(X, Z)),
assert(parent(X, Y)).
37
Logic databases
Constraints enforcement #2
%automatic consistency maintenance
is_parent_of(X, Y) :parent(X, Y).
is_parent_of(X, Y) :not parent(X, Y), %X is bound from the head; it is an update
parent(Z, Y),
not married_to(X, Z),
assert(married_to(X, Z)), % automatic consistency maintenance
assert(parent(X, Y)).
is_parent_of(X, Y) :not parent(X, Y), %X is bound from the head; it is an update
not (parent(Z, Y), not married_to(X, Z)),
assert(parent(X, Y)).
38
Logic databases
Integrity constraints
 what about ‘retract’? homework!
 there are other mechanisms (even other logic
models) of integrity maintenance
 note the syntactic equivalence (same
formalism) between data definition and
integrity constraints definition (and data
manipulation)
39
Logic databases
Constraints enforcement #3
%constraints declaration (part of the db); checked after every update
% operation
constraint(“:- parent(X, Z), parent(Y, Z), not X = Y, not married_to(X, Y).”).
constraint(“…”).
%constraints declaration (part of the db); constraints are linked to
% update operations - their checking is triggered by corresponding updates
trigger(make_parent(X, Y),
“:- parent(X, Z), parent(Y, Z), not X = Y, not married_to(X, Y).”).
%etc.
%preconditions ...
40
Logic databases
Datalog and Prolog
 we have used a combination of Datalog and Prolog
 Datalog incorporates the ‘forall’ predicate - for set
processing
 Datalog is insensitive to the order of the clauses
 special control predicates (e.g. ‘cut’) do not exist in
Datalog
 Datalog does not contain function symbols
 however, extensions to pure Datalog exist that include:
built in predicates (e.g. arithmetics), negation, functions
(for complex objects).
41
Logic databases
Approaches to deductive databases
 evolutionary approaches
 add a Prolog like system to a relational
database
 revolutionary approaches
 propose new architectures; e.g. Datalog
42
Logic databases
Further issues
 persistency
 transaction support
 security / recovery / concurrency
 ...
43
Logic databases
Advantages of deductive databases
 representational uniformity
 operational uniformity
 semantic modelling
 extended application
44
Logic databases
Conclusions
 deductive databases
 uniform representation formalism
 powerful
 still problems when dealing with large
applications
 terminology
 knowledge base management systems preferred
45