DATALOG

Dazy

Description

tp, Supérieur, TP

• cours - matière potentielle : n°

1DATALOG NFP120 --- an 8 Spécification Logique et Validation des Programmes Séquentiels Cours n° 4 2 Faiblesses de ProPlog ProPlog permet d'exprimer paul_en_tp_CDI :- paul_a_CDL, paul_a_Syst . john_ en_tp_CDI :- john_a_CDL, john_a _Syst. ... mais pas ‘pour tout étudiant quelconque' étudiant__en_ tp_CDI :- étudiant__a_ CDL, étudiant__a_ Syst.

• sémantique logique
• vérité de proplog…
• interprétation de herbrand
• ttftttftt …
• faiblesses de proplog proplog
• portée de qx dans qx
• bp
• atomes
• atome
• variable
• variables
• interprétation
• interprétations

Sujets

• Variable
• Herbrand
• Sémantique
• Interprétation
• Syntaxe

Informations

• Publié par: nachig
• Nombre de lectures: 52
• Langue: Français

Extrait

NFP120 ---

an 8

Spécification Logique et Validation des Programmes Séquentiels

Cours n° 4

DATALOG

Nouvelle Syntaxe(informelle)

1

3 alphabets : Variables,Constantes et Prédicats Variables, ... }, X2 = {X1 : V Constantes :D = {a , b , c , ... } (univers du discours , univers de Herbrand) Prédicats{p , q , ... }: P = les prédicats sont des fonctions qui retournent T ou F les prédicats sont des noms de relation Les atomes de DATALOG sont de la forme : P(t1 , … , tn) où p est un prédicat d’arité n et où chaque ti (1<=i<=n) est un terme (variable ou constante)

3

Faiblesses de ProPlog

ProPlog permet d'exprimer paul_en_tp_CDI :- paul_a_CDL, paul_a_Syst . john_ en_tp_CDI :- john_a_CDL, john_a _Syst. ... mais pas ‘pour toutétudiant quelconque’ étudiant__en_ tp_CDI :-étudiant__a_ CDL ,étudiant__a_ Syst . où, le Domaine d'intérêt étant les étudiants, représentés par l'ensemble des constantesXÎ{ paul, john,...} "X :Xen_tp_CDI :- X a_CDL, X a_Syst. où , plus proche de la syntaxe fonctionnelle ‘classique’ : "X en_tp_CDI(X) :- a_CDL (X), a_Syst (X) . Cette règle doit avoir même sémantique que le programme ProPlog obtenu par les clauses propositionnelles construites avec tous les noms d'étudiants ci-dessus.

Nouvelle Syntaxe(informelle) 2

2

Domaine :(univers du discours)D = {a , b , c , ... } Variables, ... }, X2 = {X1 : V Prédicats, ... }{p , q : P =

constante::=élément de D variable::=élément de V symb_préd::=élément de P Définitions : terme ::= constante | variable atome ::= symb_préd'(' terme1','...',' termen')' clause ::= fait | règle fait ::= atome '.' règle ::= tête ':-' queue '.' tête ::= atome queue ::= atome | atome ',' queue

4

Syntaxe abstraite

(1) Catégories syntaxiques progr ,... : PROGRAMME a,b,c,... : D (Domaine du discours) X,Y,Z,... : V (Variables) t,t1,t2,... : T = D U V (Termes) p,q,r,... : P (Symboles de Prédicat) at,at1, ... : A (Atomes) cl,cl1, ... : Clause q,q1,q2, ... : Queue lt,lt1, ... : LT (Liste de Termes) (2) Définitions progr ::= cl | cl progr cl ::= at ‘.’ | at ‘:-’ q ‘.’ q ::= at | at ‘,’ q at ::= p’(’ lt ’)’ | a lt ::= t | t ‘,’ lt t ::= a | x

Attention notation post fixée

5

ATTENTION :notation post-fixée: = µ {X1 -> a, X2 -> b} µ (r(X1,X2) :- p(X1), r(X2,X3)) = (r(X1,X2)) :- (p(X1)) , (r(X2,X3)) µ µ µ = µ µ µ = r(X1,X2) :- p(X1) , r(X2,X3) r(a,b) :- p(a), r(b,X3)

Instance close par l’ instanciation µ q(a,b) :- p(a),p(b). ( pas de variables)

7

Instanciation / Affectation / Liaison

Instanciation des variables (ou état): Fonction de l'ensemble des variables dans l'ensemble des constantes du domaine : : V |-> D µ exemple := µ {X1 -> a, X2 -> b} //liaisons On étend cette notion d'instanciation à : Instanciation d'une formule :

( r(X1,X2) :-

p(X1) = , r(X2,X3) ) µ ( r(a,b) :- p(a), r(b, X3) )

Sémantique du Point Fixe

Sémantique de chaînage Avant

6

8

Sémantique du point fixe

Remarque : notation : q(t) pour q(t1,...,tn) Soit un programmePet calculer DEN (P): pf 1. choisir une règle deP: q(t):- q1(t1) ,..., qn(tn)

2. choisir une instanciation µ donnant une instance close de cette règle

3. si l’ensemble : {q1(t1) , ... , qn(tn }ÍDEN (P) courante µ)µ pf alors ajouter q(t) DEN (P) courante µ pf

4. q(t) est dans l'ensemble dénoté parPmoins un calcul luisi au µ assigne q(t) µ

Sémantique Logique

9

1 1

Sémantique du point fixe 2

exemple: (chaque formule est universellement quantifiée) p(a). p(c). r(b). q(X1,X2) :- p(X1),p(X2).

Sémantique de chaînage avant (ou du point fixe) : DEN (P) ={p(a) , p(c) , r(b) , q(a,a) , q(a,c) , q(c,a) , q(c,c)} pf

Sémantique logique : Interprétations

Soit C la clause DATALOG :p(c,X) :- g(X,n,c). Interprétation du programmeur A: I(c) : le chat a I(n) : : la nourriture a I(p(U,V)) =I: U aime V(p) (U,V) a a I(g(U,V,Z)) =IZ: U donne V à (g) (U,V,Z) a a Interprétation du programmeur B: I(c) : : l'entier 10 b I(n): : l'entier 5 b I(p(U,V)) =I: U est inférieur à V(p) (U,V) b b I(g(U,V,Z))=I(g) (U,V,Z): U + V est supérieur à Z b b

1 0

1 2

Satisfaction

Dans le monde A : Le chat aime toute personne qui lui« C : donne de la nourriture » L'interprétation A semble satisfaire la clause C en effet, l'interprétation A est un modèle de C : |="<- g(X,c,n))|= (l(c,X) X.(l(c,X) <- g(X,c,n)) ssi m pour tout m , instanciation des variables de la clause dans le domaine de I a

Dans le monde B : )»01>X<>5=01(X+X.«C: L'interprétation B ne satisfait pas la clause C: En effet il est possible de trouver une instanciation de X dans le domaine de I telle que la b formule soit fausse dans le monde de B exemple X = 6. Donc C peut être vraie dans certaines interprétations (ex: A) et fausse dans d'autres (ex: B).

Interprétation

Une interprétation I est la donnée • d'une structure algébrique <D, {}, {R1, R2, ...,Rn}> • d'une assignation-fonction i(notée également par abus de langage) I qui a toute constante assigne un elément de D ex:paul -->

claude -->

1 3

qui a tout prédicat d'arité n du langage , assigne une relation n-aire de la structure algébrique

ex: en_tp_CDI/1 --> en_tp_CDI = { , }

(autre définition : à tout symbole de prédicat n-aire on assigne n une fonction de D dans {T , F}(domaine sémantique des Booléens)

1 5

Structure algébrique

Triplet : Domaine + ensemble de fonctions + ensemble de relations exemples: < D = { , , ...} , F = {}, R = {AIME = {( , ), ( , ) , ( , ) }, en_tp_CDI = { , } } > < D = l'ensemble des chats, F = {}, R = { AIME = {...}, DONNE_A = {...} } > < D = N, F = {PLUS = {(0,0)->0, (0,1)->1,...}}, R = {INF ={(0,1),(0,2),...},SUP = {(1,0),...}} >

Sentence - formule close

1 4

Q étant un des quantificateurs{" , $} . la portée de QX dans QX.W est W . On dit que QX quantifie toute occurrence de X dans W qui ne soit déjà derrière un quantificateur de W ou dans sa portée ex : " X.( $ B(X))X. A(X) <- . Une occurrence de X est liée SSI elle est derrière un quantificateur ou dans sa portée . Sinon l'occurrence est libre ex : $ Y. pere(Y,X) <- enfant(X) liée libre . Une sentence (ou formule close) est une formule bien formée (f.b.f.) dont toutes les occurrences de variables sont liées ex : " X.( $ Y.(pere(Y,X) <- enfant(X)) )

1 6

Satisfaction des sentences

une interprétation Soit I |= en_CDL(paul) ssi I (paul) = Î en_CDL(cf. Calcul Propositionnel) I |= ¬ W ssi |¹W I I

|= I

|= I

|= I

W1Ùet |=|= W1 W2 ssi I I

W1 v W2 ssi |= W1 ou |= I I

W1 <- W2 ssi si |= I

W2

W2

W2 alors |= I

Interprétation algébrique

W1

1 7

Interprétation : structure algébrique : domaine d'interprétation, ensemble de fonctions et ensemble de relations

Exemple : Den(P) = < {paul,john,claude}, {}, {ETUDIANT , A_INFO_GENE, A_MATH_GENE ,EN_INFO_PROG } > avec les relations ETUDIANT = { paul, john, claude }, A_INFO_GENE = { paul, john, claude }, A_MATH_GENE = { paul, john }, EN_INFO_PROG = { paul, john } associées à chaque symbole de prédicat.

1 9

Satisfaction des sentences (2)

Quantificateurs :

|= " SSI quelque soit l'instanciation(X) .W m de X (libre I dans W) par un élément du domaine: |= (W) m I

|= $ SSI pour au moins une instanciation(X) .W m de X I (libre dans W) par un élément du domaine: |= (W) m I

Evaluation

Une interprétation :I = < D={a1,a2,...}, {...},{...}>et une instanciationµ = {X1 --> a2,...}( valeur d'état des variables dans le domaine de l'interprétation) étant données :

l'évaluation d'un terme t par une interprétation I et une instanciationµ, (notée val(I,µ)(t) )est définie par val(I,µ)(X) = µ(X) et pour toute constante par val(I, µ)(c) = I(c)

1 8

2 0

Interprétation

Rappel : Interprétation < D, {}, {R1, R2, ..., Rn} >

< D = { , , ...} , F = {}, R = {en_tp_CDI = { }, ETUDIANT = { , } } >

Interprétation de Herbrand (2) Univers de Herbrand Up :Ensemble des constantes du programme (domaine) Up = {paul,john,claude} Base de Herbrand Bp :Ensemble des instances closes des atomes du programme Bp = { etudiant(paul), ..., a_CDL(paul), ..., ... en_tp_CDI(john), en_tp_CDI(claude } Interprétation de Herbrand : Sous-ensemble de Bp par exemple : Bp elle-même ou I ={ etudiant(paul), etudiant(john), a_CDL(paul), a_CDL(john), a_MATH1(paul), a_MATH1(john),

en_tp_CDI(paul) }

Cela revient à assigner la valeur T (true) aux seuls atomes de Den(P)

2 1

2 3

Interprétation de Herbrand

< D = Up= {paul,john,claude}, F = {}, R = {en_tp_CDI = {paul}, ETUDIANT = { paul,john } } > notée également : < D = Up= {paul,john,claude}, F = {}, I = {en_tp_CDI(paul), ..., etudiant(paul), etudiant(john)} >

modèle de Herbrand

2 2

exemple :Pp(a). p(c). r(Y). q(X1,X2) :- p(X1),p(X2). -modèles dep(a) : toute interprétation qui contient p(a) exemples :{ }Bp ou pa) -modèles der(Y) : ( c'est-à-dire de") toute interprétation qui Y.r(Y) contientr(c), ...pour toute constantec de Up -modèles de"x1,x2.q(x1,x2) <- p(x1)Ùp(x2) toute interprétation I telle que pour toute instancem, si p(X1).met p(X2).m, sont dans I alors q(X1,X2).m s'y trouve également exemple :Bp -modèle deP :Interprétation qui est un modèle de toutes les clauses de P exemple :, r(c) , q(a,a) , q(a,c) , q(c,a) ,, r(a) , r(b) Den(P) ={ p(a) , p(c) Bp ou q(c,c) }

2 4

2 7

2 8

T

T

F

F

2 6

F

Si Up = {a,b,c}

Den(P) = { p(a) , p(c), r(a) , r(b) , r(c) , q(a,a) , q(a,c) , q(c,a) , q(c,c) }

T

…

F

T

F

Le plus petit modèle de Herbrand est la sémantique logique et est identique à la sémantique du point fixe

retour sur ProPlog

(SLD)

r(c)

2 5

Sémantique logique : PPM de Herbrand

on peut faire le lien entre interprétation de Herbrand et table de vérité de ProPlog

T

Interprétation de Herbrand et ProPlog

F

F

p(c)

r(a)

T

F

F

F

T

T

…

p(a)

T

q(a,a) q(a,c)

opérationnelle

q(c,a) q(c,c)

T

T

F

T

Sémantique

T

T

r(b)

T

T

p(a). p(c). r(Y). q(X1,X2) :- p(X1),p(X2). Il existe au moins un modèle de Herbrand deP :Bp Bp = { p(a) , p(b), p(c), r(a), r(b) ,r(c), q(a,a), q(a,b), q(a,c), q(b,a), q(b,b), q(b,c), q(c,a), q(c,b) , q(c,c) } Il existe un plus petit modèle de Herbrand deP Den(P)= { p(a) , p(c), r(a), r(b) ,r(c), q(a,a), q(a,c), q(c,a), q(c,c) }

exemple :P p(a). p(c). r(Y). q(X1,X2) :- p(X1),p(X2).

Substitution

Une substitution est une fonction d de l'ensemble des variables dans l'ensemble des termes . Termes = Constantes U Variables Exemple : d = { X-> Z, Y -> b}

Le couple X->Z est appelé "liaison" (binding) de X Exemple : Soit F la clause : p(X) , q(X,Y) :- r(Y,Z) F. d :- p(X), r(Y,Z) ).= (q(X,Y) d = q(X,Y). d :- p(X). d , r(Y,Z). d = q(Z,b) :- p(Z), r(b,Z)

une substitution { Xi-> ti, ... } est dite pure si tous les ti sont des variables ( d : V -> V) une substitution est dite close (fermée) si c'est une instanciation

C :

Exemple

anc(X,Y) :- par(X,Z), anc(Z,Y)

<= {X -> Y, Y -> U, Z -> V} d= {Y ->jean, U -> T, V -> T, X -> rené } <°d= { X -> Y.d, Y -> U.d, Z -> V.d, U -> T, V -> T } <°d= { X -> jean, Y -> T, Z -> T, U -> T, V -> T }

C.<°d :anc(jean,T) :- par(jean,T), anc(T,T) on obtient le même résultat par étape : C.<:- par(Y,V), anc(V,U) : anc(Y,U) puis (C.<).d :anc(jean,T) :- par(jean,T), anc(T,T)

2 9

3 1

Composition de substitutions

Soient<etd 2 substitutions

Leur composition

: (ATTENTION :)opf-tseéxi

<°d

correspond à l'application de<puis ded  : F.<°d= (F.< !&d

<

d

= {X1 -> t1, ..., Xn -> tn}

= {Y1 -> t1', ..., Yp -> tp' }

< ° d

= {X1 -> t1. d , ..., Xn -> tn. d , , Y1 -> t1', ..., Yp -> tp' }

dans laquelle on a supprimé les

Xi -> ti& d & Xi = titels que & d & // / (X -> X) et où ne figurent pas les Yj -> tj' tels que YjÎ{X1, ...,Xn }

Variante

E et F deux expressions sont des variantes l'une de l'autre

s’il existe <,s ,2 substitutions telles que E = F. < et F = E . s

exemple:et E=p(U,V)F= p(X,Y) avec < = {X -> U, Y -> V} et s = {U ->X, V -> Y }

contre-exemple: p(X,Y) et p(U,U)

3 0

3 2

Renommage

Soient E une expression , V l'ensemble de ses variables un renommage de E est une substitution pure {X1 -> Y1, ..., Xn -> Yn} telle que {X1 , ..., Xn } inclu dans V les Yi sont toutes distinctes (V- {X1 , ..., Xn })Ç{Y1 , ..., Yn } =Æ Donc,on ne peut pas projeter les Xi sur d'autres variables de l'expression E, mais rien n'empêche de permuter des Xi

Si E et F sont des variantes, alors il existe des renommages < et s tels que E = F. < et F = E . s

Unification

: une liste d'atomes, q1(t) ,..., qn(t) une substitution < telle que q1(t).<= ... = qn(t).< est appelée unificateur de q1(t) ,..., qn(t)

Si un tel unificateur existe, les atomes sont dits unifiables

exemple: soient les 3 atomes : {p(X,b,Z) , p(Y,W,a) , p(Y, b, Z)} < = { W --> b, X --> c, Y --> c, Z --> a } donne la même instance

3 3

p(c,b,a)

3 5

Substitution plus générale

<etsdeux substitutions : <est dite plus générale ques SSI il existelune substitution telle que : <°l=s (<est "un peu moins instanciée" ques) Cette relation n'est pas anti-symétrique ATTENTION : 2 substitutions<et<peuvent être telles que 1 2 <est plus générale que< 1 2 <est plus générale que< 2 1 à un renommage près (voir variantes)

Unificateur le plus général : mgu

j est l' Unificateur le plus général, le mgu (most general unifier) d'un ensemble d'atomes SSI quelque pour tout autre unificateur < il existe une substitution s telle que j ° s = <

3 4

3 6

Unificateur le plus général : mgu (2)

Exemple précédent : , p(Y, b, Z)}{p(X,b,Z) , p(Y,W,a) < = { W --> b, X --> c, Y --> c, Z --> a}n'est pas un mgu

j = { W --> b, X --> Y,Z --> a }est le mgu En effet s = {Y -> c}est telle que j°s=< :

Si au moins un unificateur existe alors le mgu existe.

Algorithme d'unification

/* entrée: 2 expressions L = g(t1,...tn) et M= g'(t1',...tm') sortie: J= mgu(L,M) v échec */ ¹¹ if (g g' v n m) then return échec; else{J:= {}; i := 1; unif:= true; ¹ repeat if (ti.J ti'.J) then{ if (ti'.J est une variable) then{ J:= J°{ti'.J -> ti.J } }else{ if (ti.J est une variable) then{ J:= J°{ti.J -> ti'.J} }else{ unif := false; i := i+1; } }// sinon (ti.J == ti'.J) until (i > n v NOT unif); if unif then return J else return échec;}

3 7

3 9

Exemples

L = p(X,a,Z) M = p(V,W,b) Les substitutions - unificateurs de L et M sont : < 1 = {X -> a, Z -> b, V-> a, W -> a}

< (

< )

< 4

< +

= {X -> b, Z -> b, V-> a, W -> a}

= {X -> V, Z -> b, W -> a}

= {X -> c, Z -> b, V-> c, W -> a}

= {X -> U, Z -> b, V-> U,W -> a, U-> K}

contre-exemple: unifiables

N = q(X,a,X,b)

et

M = q(Y,a,a,Y)

Exemple d'unification

L = p(X, Z, a, U)

M = p(Y, Y, V, W)

ne sont pas

Calcul de mgu(L, M) : < 1 = {} < ( = {Y -> X } < -> X }°{X -> Z} = {Y -> Z , X -> Z}= {Y ) < 4 -> Z , X -> Z}°{V -> a} = {Y -> Z , X -> Z, V -> a }= {Y < -> Z , X -> Z, V -> a }°{W -> U}= {Y + = {Y -> Z , X -> Z, V -> a, W -> U }

=

mgu(L,M)

3 8

4 0

Rappel : on cherche à résoudre ?- q (t) ,..., q (t). 1 n (iii) Si on arrive à : (?- .)j alors SUCCES

j La restriction de aux seules variables de la question initiale est dite

5

15

i.e. le but initial : ?- q ,...,q . est résolu pour la substitution j (composition de 1 n toutes les substitutions de la branche succès).

5 6 7

4

1 2 3

?- et(paul), en_info_gene(paul), amg(paul)

1 {X --> paul} ?-en_info_prog(paul)

Arbre de recherche

Réponse calculée ou Substitution réponse

4 1

4 4

Exemple

echec

?- et(john), en_info_gene(john), amg(john)

?- en_info_gene(john), amg(john)

echec

echec

echec

SLD-résolution

SLD-résolution (2)

?- m(X), eIP(X) X = paul ; X = john ; No ?- eIP(claude). yes

amg(paul). amg(john). amg(claude).

aig(paul). aig(olivier). aig(john). aig(claude).

et(paul). et(john). et(claude).

succès {X --> paul}

4 2

?- en_info_gene(paul), amg(paul)

m( paul). m( olivier). m( john).

15

8 9 10 11

4 3

10

succès {X --> john}

10

?- amg(john)

?- amg(paul)

13

POUR résoudre?- q (t) ,..., q (t). 1 n (i) Choisir unq (t)(règle d'évaluation ou de sélection du littéral) i si (aucune règle renommée n'a une têteq (t')qui s'unifie avecq (t))alors i i échec ( q (t)n'est pas dans Den(P)); i (ii)sinon choisir une de ces règles et soit :d= mgu(q (t),q (t')) i i (règle de recherche ou de sélection de la clause) si (cette règle est un fait) alors s’efface et la résolvante devient q i (t) d d d d ?- q 1 . ,...,q i-1 . ,q i+1 . ,...,q n . . sinon soit cette règle , et la résolvante devient q i :- r 1 ,...,r m d d d d d d ?-q 1 . ,...,q i-1 . ,r 1 . ,...,r m . ,q i+1 . ,...,q n . ou d ?-(q 1 ,..,q i-1 ,r 1 ,..,r m ,q i+1 ,..,q n .)

8

2 {X --> olivier} ?-en_info_prog(olivier)

?-m(X),en_info_prog(X)

15

?- et(olivier,) en_info_gene(olivier), amg(olivier)

echec

echec

echec

Et donc , Équivalence des sémantiques

P|- (q ,...,q n ). j <==>P|= (q 1 ,...,q n ). j sld1

eIP(X) :- et(X), aig(X), amg(X) .

f( claude).

3 {X --> john} ?-en_info_prog(john)

12 13 14

6

15