Prolog et algèbre relationnelle


précédentsommairesuivant

4. Opérateurs "pour tout", "il existe", division relationnelle

4.1. Opérateur "il existe"

On souhaite écrire un prédicat pour exprimer une expression mathématique du genre: "il existe un x appartiennant à ensemble tel que propriete(x)" et qui serait vrai si une telle expression est vérifiée.

Voici le prédicat Prolog correspondant :

 
Sélectionnez
there_exists(Expr, Prop) :- Expr, Prop, !.
 



Exemple d'exécution :

Exécution
Sélectionnez
| ?- there_exists( e1(X), 2<X ).
 
X = 3 
 
Yes

Ceci se traduit par "il existe un x appartenant à e1 tel que 2<X". La propriété est vérifiée. Par unification, il nous renvoie la première solution. Si on demande d'autres solutions, le prédicat échoue (on veut en effet savoir si l'expression est vérifiée pour au moins un élément, pas la liste de toutes les solutions).

Si on veut spécifier une expression complexe (ex: une conjonction), on utilise des parenthèses :

Exécution
Sélectionnez
| ?-
  there_exists( 
    ( e1(X), e2(Y) )
    ,
    ( 2<X, X<Y )
  ).
 
X = 3
Y = 5 
 
Yes

Traduction: "est-ce qu'il existe x appartenant à e1 et y appartenant à e2 tels que 2<X et X<Y ?". La réponse est "oui" (en l'occurence X=3 et Y=5).

4.2. Opérateur "pour tout"

On souhaite maintenant écrire un prédicat pour exprimer une expression mathématique du genre: "pour tout x appartenant à ensemble, on a propriete(x)".

Ceci est équivalent à: "il n'existe pas de x appartenant à ensemble tel que non( propriete(x) )".

Voici le prédicat Prolog correspondant :

 
Sélectionnez
for_all(Expr, Prop) :- \+there_exists(Expr, \+Prop).
 



Ce prédicat est prédéfini dans Prolog, sous la forme forall/2, c'est donc celui-là que nous alllons utiliser (pas besoin de le réécrire).



Exemple d'exécution :

Exécution
Sélectionnez
| ?-
  forall( 
    ( e1(X), e2(Y) )
  ,
    ( 0<X, 0<Y )
  ).
 
X = _G398
Y = _G400 
 
Yes

Traduction: "est-ce que pour tout x appartenant à e1 et y appartenant à e2, on a 0<X et 0<Y ?". La réponse est "oui". Aucune unification n'est faite.

4.3. Exemple d'application

On veut écrire un prédicat qui nous retournerait l'ensemble des personnes les plus jeunes.

En d'autres termes, on veut écrire un prédicat qui nous retournerait "l'ensemble des x appartenant à Personne tel que pour tout y appartenant à Personne, on ait age(x) =< age(y)".

Voici le prédicat Prolog correspondant :

 
Sélectionnez
plusJeune(X) :-
  personne(X),
  age(X, AgeX),
 
  forall(
    ( personne(Y), age(Y, AgeY) )
  ,
    AgeX =< AgeY
  ).
 



Exécution :

Exécution
Sélectionnez
| ?- findall(X, plusJeune(Y),  Inner), write(Inner).
[noemie]



Solution alternative :

Pour obtenir la liste des personnes les plus jeunes, il est également possible de procéder ainsi :

  • faire la liste des solutions renvoyées par le prédicat age/2 en utilisant le prédicat findall/3
  • écrire un prédicat qui parcourerait cette liste à la recherche des personnes les plus jeunes.

Cette méthode peut être plus rapide que la précédente, cependant elle nécessite la création d'une liste, ce qui est plus gourmand en termes de mémoire, ce qui peut éventuellement poser des problèmes (surtout si on utilisait systématiquement cette technique dans un programme).

4.4. La division relationnelle

La division relationnelle est la grande oubliée des opérations relationnelles. Voici à quoi elle correspond :

Soient les ensembles e1 et e2, liés entre eux par la relations rel(X,Y) (avec x appartient à e1 et x à e2). La division de e1 par e2 selon la relation rel, c'est l'ensemble des x appartenant à e1 tels que pour tout y appartenant à e2, on a (x, y) appartient à la relation couple.

Il est extrêmement facile de traduire la définition précidente en Prolog, notamment grâce aux opérateurs définis précédemment :

 
Sélectionnez
div_e1_e2(X) :-
  e1(X),
  forall( e2(Y), rel(X,Y) ).
 

Cette opération paraît extrêmement simple, en particulier exprimée de cette façon. Cependant elle pose tellement de difficulté qu'elle n'est implémentée dans aucun SGBDR actuel.



Exemple :

On utilise la division relationnelle pour avoir la liste des personnes présentant TOUTES les qualités de répertoriées dans l'ensemble qualite (division de personne par qualite par la relation a_qualite) :

 
Sélectionnez
div_personne_qualite(P) :-
  personne(P),
  forall( qualite(Q), a_qualite(P, Q) ).
 

Exécution :

Exécution
Sélectionnez
| ?- findall(X, div_personne_qualite(Y), Div), write(Div).
[pierre]

précédentsommairesuivant

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+   

  

Copyright © 2006 pcaboche. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.