ProLog

Partie 2 : Requête et Réponse

Mathieu Vidal

Université Grenoble Alpes

Année 2016-2017

L2 - MIASHS

Grenoble - France

Plan Prolog et SQL

Unification

Arbre de Recherche

Coupure (Cut)

Négation

Objectif: voir comment Prolog répond à nos

requêtes

Partie 1

-

Prolog et SQL

Bases de données et Prolog

On peut facilement représenter des tuples de

relations par des faits Prolog.

Les diverses opérations de l’algèbre relationnelle

se réalisent facilement par des requêtes en

Prolog.

Algèbre relationnelle : Ensemble d’opérations

logiques permettant de manipuler des relations.

Le résultat de toute opération de l'algèbre est une

relation.

Algèbre relationnelle

Opérations ensemblistes :

l’union notée ,

l’intersection notée ,

la différence notée -

le produit cartésien noté X

Opérations propres aux bases de données :

la sélection notée s

la projection notée P

le produit noté *

Algèbre relationnelle en Prolog

Opérations ensemblistes : l’union

R1 R2 représente l’union des lignes des

relations R1 et R2.

Pour pouvoir effectuer cette opération, les

relations R1 et R2 doivent avoir les mêmes

attributs.r(a,1).

r(b,2).

r(c,3).

s(a,1).

s(e,2).

s(f,1).

union(X,Y) :- r(X,Y) ; s(X,Y).

SQL: select * from r union select * from s;

Algèbre relationnelle en Prolog

Opérations ensemblistes : l’intersection

R1 R2 représente l’intersection des lignes des

relations R1 et R2.

R1 et R2 doivent avoir les mêmes attributs.

intersection(X,Y) :- r(X,Y) , s(X,Y).

SQL: select * from r intersect select * from s;

r(a,1).

r(b,2).

r(c,3).

s(a,1).

s(e,2).

s(f,1).

Algèbre relationnelle en Prolog

Opérations ensemblistes : la différence

R1-R2 représente la différence des relations

R1 et R2 : lignes de R1 qui ne sont pas

présentes dans R2. On a :

R1-R2 = R1 - (R1 R2)

R1 et R2 doivent avoir les mêmes attributs.

difference(X,Y) :- r(X,Y) , \+(s(X,Y)). Rmq: le \+ est le not

SQL: select * from r except select * from s;

r(a,1).

r(b,2).

r(c,3).

s(a,1).

s(e,2).

s(f,1).

Algèbre relationnelle en Prolog

Le produit cartésien

R1 X R2 représente la relation formée des

attributs des relations R1 et R2, construite en

combinant chaque n-uplet de R1 avec tous les

n-uplets de R2.

prodcart(A,B,C,D) :- r(A,B) , s(C,D).

SQL: select * from r, s;

r(a,1).

r(b,2).

r(c,3).

s(a,1).

s(e,2).

s(f,1).

Algèbre relationnelle en Prolog

La sélection :

s(P)(R) représente les lignes de la relation R qui

vérifient la propriété P exprimée sous la forme

d’une expression logique :

s (A2<3)(R)r(a,1).

r(b,2).

r(c,3).

r(d,5).

r(a,3).

select(X,Y) :- r(X,Y) , Y<3.

SQL: select * from r where r.Y<3;

Algèbre relationnelle en Prolog

La projection : sélection de colonnes.

P(A1,..., Ak)(R) représente la sous-table de R

formée uniquement des colonnes dont les

attributs ont été spécifiés (A1,..., Ak).

Si après cette opération plusieurs lignes sont

identiques, les doublons sont éliminés

(pas en Prolog). r(a,1,xxx,12).

r(b,2,c,15).

r(c,3,as,123).

r(d,5,aaa,23).

r(a,3,ddd,7).

projection(X,Y) :- r(X,_,_,Y).

SQL: select X,Y from r;

P (A1,A4)(R)

Algèbre relationnelle en Prolog

La jointure naturelle

R1 R2 représente la relation formée de

l'union des attributs de R1 et de R2, les lignes

de cette relation sont les n-uplets de R1

concaténés aux n-uplets de R2 si les attributs

communs à R1 et R2 ont la même valeur.

Cette opération n'est possible que si les

schémas de R1 et de R2 ont une intersection

non vide. r(d,3).

r(b,2).

r(c,3).

s(d,3).

s(c,2).

s(a,1).jointure(X,Y,Z) :- r(X,Y), s(X,Z).

SQL: select * from r natural join s;

Algèbre relationnelle

La jointure

R1 R2 [Q] représente la relation formée de

l'union des attributs de R1 et de R2, les lignes

de cette relation sont les n-uplets de R1

concaténés aux n-uplets de R2 pour lesquels la

qualification Q est vérifiée.

Ceci constitue la forme générale d’une jointure.

jointure(A,B,C,D) :- r(A,B), s(C,D), B==D.

Select * from r inner join s on r.B = s.B;

Exercice

Quelle question Prolog permet de représenter la requête

SQL suivante?

select * from CV union select * from Compte

avec les tables CV et Compte ayant 2 colonnes Nom, Age

select * from Compte where Age>18

Partie 2

-

Unification

Unification : Idée de base

Exemple :

Base de connaissance : elfe(galadriel).

Question :?- elfe(X).

Comment fait Prolog pour dire que galadriel est une

valeur possible pour X ?

Unification : procédé par lequel on essaie de rendre

deux formules identiques en donnant des valeurs aux

variables qu’elles contiennent.

Unification réussie : substitution possible

Unification dans les Clauses

L'unification réussie dans la tête se propage aux

clauses

frere(X,Y) :- homme(X), enfant(X,Z), enfant(Y,Z), X\=Y.

frere(patrick,Qui).

homme(patrick)

enfant(patrick,Z)

enfant(Qui,Z)

patrick\=Qui

Unification avec frere(X,Y)

X=patrick et Y=Qui

Définition Précise

Si t1 et t2 sont des constantes, t1 et t2 unifient ssi ils

sont le même atome ou le même nombre.

Si t1 est une variable et t2 quelconque, t1 et t2

unifient ssi t1 est instanciable en t2.

Si t1 et t2 sont des termes complexes, t1 et t2

unifient ssi :

Ils ont le même foncteur et arité

Tous leurs arguments correspondants unifient

Les instanciations de variables sont compatibles

Conséquence

L’unification peut réussir ou échouer. e(X) et e(2) peuvent être unifiés.

e(3) et e(2) ne peuvent être unifiés

Le résultat n’est pas forcément unique :

ensemble de solutions

Prédicat d’unification : « = ». Teste si l'unification

a réussie. Ecriture 1 : =(a,b). Ecriture 2 : a=b.

Unification optimiste : pere(X)=X unifie

Unification pessimiste :n'unifie pas

unify_with_occurs_check(pere(X),X).

Exercice

Dire si les expressions suivantes unifient et comment :

?- sam = sam.

?- sam = lea.

?- 'sam' = sam.

?- '1' = 1

?- X = Y.

?- X = sam, X = lea.

?- k(s(g),Y) = k(X,t(k)).

?- k(s(g), t(k)) = k(X,t(Y)).

?- aime(X,X) = aime(sam,lea).

Partie 3

-

Arbre de Recherche

Démonstration Prolog

Pour répondre à une question, Prolog cherche à

l'unifier, soit avec un fait, soit avec la tête d'une

règle

Si l’unification avec la tête d'une règle réussit :

substitution des variables de la queue par les

valeurs correspondantes dans la tête.

L'algorithme est appelé SLDNF résolution

(Selective Linear Definite Negation as Failure)

Résultat Final

Prolog continue à unifier jusqu'à vérification de la

requête initiale

Si l’unification échoue : Prolog répond faux (false)

Si l’unification réussit : Prolog répond soit vrai

(true), soit donne la valeur des variables (expl :

X=lea) s'il y en avait dans la requête.

On demande à Prolog de chercher d'autres

valeurs en appuyant sur « ; » ou « Espace »

A la fin de la démonstration, Prolog a construit

une liste de couples valeur-variable

Parcours

Parcours de la base du haut vers le bas

Parcours des clauses de gauche à droite

Quand il y a plusieurs manières d'unifier, on a un

point de choix. Cas possibles :

Différentes règles définissant un même

prédicat

Disjonction de prédicats dans une queue

Instanciation d'une variable

Arbre de recherche

Pour résoudre une question, Prolog construit

l’arbre de recherche de la question

Construction de l'arbre

Racine : la question initiale

Nœud : point de choix

Passage d’un nœud vers son fils en effectuant

une unification

Stratégie de Prolog

Parcours en profondeur d’abord

nœud de succès : c’est une solution, Prolog

l’affiche et peut chercher d’autres solutions

nœud d'échec : remontée dans l’arbre jusqu'à un

point de choix possédant des branches non

explorées

Puis parcours de gauche à droite dans l'ordre

des conditions

Backtracking

Remontée dans l'arbre jusqu'au point de choix :

backtrack. Si un tel nœud de choix n’existe pas,

la démonstration est terminée, il n’y a pas d’autre

solution.

Bactrack : toutes les unifications faites depuis le

dernier point de choix sont défaites

Possibilité de branche infinie et donc de

recherche sans terminaison… Attention à :

L’ordre des littéraux dans la queue de clause

L’ordre des clauses

Exemple d'Arbre de recherche

Exemple de programme:pere(charlie, david). (p1)pere(henri, charlie). (p2)papi(X,Y) :- pere(X,Z), pere(Z,Y). (p3)

Question :?- papi(X,Y).

Résolution versus SLDNF

Résolution

Théorie Mathématique

Clauses de Horn

SLDNF

Algorithme effectif

Unification

Expl : Base = {p, q si p} et Question = {q?}

Base = {p,q v ¬p}. Qu. = {¬q}

[p] [q, ¬p] [¬q]

[q] [¬q]

[]

Base = {p. q:- p}. Qu. = {q}

?- q

?- p

OK

Equivalent

Exercice

rectangle(a).

rectangle(b).

losange(b).

carre(X) :- rectangle(X),losange(X).

?- carre(X).

Soit la base de connaissance et la requête suivante.

Construire l'arbre de recherche Prolog

Partie 4

-

Coupure

Notion de coupure (1)

La recherche systématique de toutes les

solutions possibles est une caractéristique

importante de Prolog.

Mais elle constitue également son talon d’Achille

car elle conduit parfois à une explosion

combinatoire qu’il est nécessaire de couper si

l’on veut voir son programme se terminer.

Notion de coupure (2)

Différents noms utilisés: coupure, cut ou coupe choix

Introduit un contrôle du programmeur sur l'exécution de ses programmes en élaguant les branches de l’arbre de recherche

rend les programmes plus simples et efficaces

Notation: !

Le coupe choix est un prédicat prédéfini qui réussit toujours.

Notion de coupure (3)

Le coupe choix permet de signifier à Prolog qu’on

ne désire pas conserver les points de choix en

attente

Les autres solutions possibles à l'unification ne

sont donc pas examinées

Coupure dans une règle

Le coupe-choix ne conserve que les unifications faites avant la suppression des points de choix.

a(1). b(1). a(2). b(2).

p(X):- a(X),b(X).

?- p(X).

X =1 ;

X=2.

a(1). b(1). a(2). b(2).

p(X):- a(X), !,b(X).

?- p(X).

X =1.

Arbre de Recherche

Sans Coupure Avec Coupure

Exemples d'utilisation

Pour prouver que x est un élément d’une liste, on peut s'arrêter dès que la première occurrence de x a été trouvée.

Pour calculer min(a,b) :

min(A, B, A) :- A=<B. min(A, B, A) :- A=<B, !.

min(A, B, B) :- A >B. min(A, B, B) :- A =B.

Exprimer des clauses exclusives :humain(X) :- homme(X). humain(X) :- homme(X), !.

humain(X) :- femme(X). humain(X) :- femme(X), !.

Danger

Dangers du coupe-choix : on peut perdre des

solutions. Expl :achete(helene, journal). achete(helene, journal) :- !.

achete(corinne, timbres). achete(corinne, timbres) :- !.

achete(X, pain). achete(X, pain).

et l’interrogation achete(helene, N).

Sans coupure : N=journal et N=pain

Avec coupure : N=journal

Notion de coupure (fin)

En résumé, les utilités du coupe-choix sont :

éliminer les points de choix menant à des échecs

certains

supprimer certains tests d’exclusion mutuelle dans

les clauses

permettre de n’obtenir que la première solution de

la démonstration

assurer la terminaison de certains programmes

contrôler et diriger la démonstration

Exercice

Etant donné la base de connaissance suivante, quel sera la réponse de Prolog à la question ?

a(1). a(2). b(2). c(3).

p(X):- c(X).

p(X):- a(X), !, b(X).

?- p(X).

Partie 5

-

Négation

La négation

Négation par l'échec Si F est une formule, sa négation est notée \+(F).

Dans d'autres implémentations, notée not(F)

Prolog pratique la négation par l'échec, c’est-à-dire que pour démontrer \+(F) Prolog va tenter de démontrer F. Si la démonstration de F échoue, Prolog considère que \+(F) est démontrée.

Pour Prolog, \+(F) signifie que la formule F n’est pas démontrable, et non que c’est une formule fausse. C’est ce que l’on appelle l'hypothèse du monde clos.

La négation

\+(X) ne veut pas dire que X est faux mais que X

ne peut pas être prouvé.

Elle est utilisée pour vérifier qu’une formule n’est

pas vraie.

La négation par l'échec ne doit être utilisée que

sur des prédicats dont les arguments sont

déterminés et à des fins de vérification.

Son utilisation ne détermine jamais la valeur d’une

variable

La négation

Dangers :

Considérez le programme suivant :

p(a).

Et interrogez Prolog avec :

?- X = b, \+ p(X).

YES { X = b }

Prolog répond positivement car p(b) n’est pas

démontrable.

La négation

Par contre, interrogez le avec :

?- \+ p(X), X=b.

No

Prolog répond négativement car p(X) étant démontrable avec X = a, \+ p(X) est considéré comme faux.

=> Incohérence qui peut être corrigée si l’on applique la règle vue précédemment : n’utiliser la négation que sur des prédicats dont les arguments sont déterminés.

La différence

La différence est définie comme le contraire

de l’unification

Elle est notée : X \= Y. Elle signifie que X et Y ne

sont pas unifiables, et non qu’ils sont différents.

Ex : Z \= 3. Sera faux car Z et 3 sont unifiables.

Elle peut être définie comme :X \= Y :- \+ (X = Y).

Le prédicat fail

fail signale à Prolog l'échec de la branche

courante

Prolog effectue alors un backtrack (retour arrière

jusqu'au dernier point de choix)

Toutes les instanciations de variable faites dans

la branche sont annulées

Combinaison cut-fail

Enchaînement :?- …,!,fail.

Le cut a supprimé tous les points de choix

Le fail retourne au dernier point de choix

Leur combinaison termine donc la démonstration

Permet d'exprimer une exception à une règle : Tout oiseau qui n’est pas une autruche vole

oiseau(X):- autruche(X), !,fail.

oiseau(X) :- vole(X).

Exercice

Définir la base de connaissance décrivant qu'en Europe, les voitures roulent à droite, sauf dans les Iles Britanniques (Irlande et Royaume-Uni).

roule(X) :- rouleADroite(X);rouleAGauche(X).

rouleADroite(X) :- rouleDansIlesBritanniques(X), !, fail.

rouleADroite(X) :- rouleEnEurope(X).

Définition de la négation

La négation se définit par l’enchainement cut,fail.

\+ est définit par les deux clauses suivantes:

\+(X) :- X, !, fail.

\+(_).

1ère ligne : si X est prouvé, cut,fail. (arrêt et false)

2ème ligne: sinon, true (c-à-d qu’il est vrai que X

n’est pas prouvé)