View
216
Download
0
Category
Preview:
Citation preview
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é)
Recommended