Prolog et algèbre relationnelle


précédentsommairesuivant

1. Préambule

Dans cet article, les différents prédicats Prolog nous serviront à traduire des relations ensemblistes. Ainsi le prédicat "personne(pierre)." se traduira par "Pierre est une personne" ou plus exactement "l'élément Pierre appartient à l'ensemble Personne".


Ainsi le prédicat "personne(pierre)." signifiant "l'élément Pierre appartient à l'ensemble des personnes", il nous servira pour:

  • vérifier qu'un élément appartient bien à un ensemble
  • lister un par un les éléments d'un ensemble


Pour avoir l'ensemble 'personne' sous forme d'une liste des éléments qui le composent, on utilisera l'un des prédicats suivants:

  • findall/3: retourne l'ensemble des solutions, dans l'ordre d'apparence, sans suppression de doublons.
    S'il n'y a pas de solution, findall/3 retourne la liste vide.

  • bagof/3: s'apparente à findall/3, sauf que si pas de solution, bagof/3 échoue
    (les autres différences entre findall/3 et bagof/3 feront l'objet d'un prochain article)

  • setof/3: similaire à bagof/3, avec en plus la suppression des doublons et le tri des éléments lorsque possible
    (donc un peu moins rapide que bagof/3)


Le prédicat findall/3 retournera la liste des éléments comme si on parcourait les solutions une à une (et sera donc utilisée systématiquement dans nos exemples d'exécution).

2. Opérations ensemblistes

A titre d'exemple, nous utiliserons les ensembles suivants:

  • e1/1: quelques nombres, la plupart étant des nombres premiers (1 a été ajouté à la liste)
  • e2/1: les premiers éléments d'une suite de Fibonacci.
 
Sélectionnez
e1(1).
e1(2).
e1(3).
e1(5).
e1(7).
e1(11).
e1(13).
e1(17).
e1(19).
 
 
e2(1).
e2(1).
e2(2).
e2(3).
e2(5).
e2(8).
e2(13).
e2(21).
e2(34).

Comme vous pouvez le constater, l'élément 1 apparait 2 fois dans la suite de Fibonacci, ce qui nous permettra de distinguer les comportements des prédicats findall/3 et setof/3 dans nos exemples.

2.1. Intersection

Un élément appartient à l'intersection de e1 et e2 si il appartient à la fois à e1 et à e2.

On traduira cela par:

 
Sélectionnez
intersect_e1_e2(X) :- e1(X), e2(X).
 



Voici la fonction de test et son exécution:

 
Sélectionnez
test :-
  findall(X, intersect_e1_e2(X), Bag),
  setof(Y, intersect_e1_e2(Y), Set),
  write('Bag = '), write(Bag), nl,
  write('Set = '), write(Set), nl.
 
Exécution
Sélectionnez
|?- test.
Bag = [1, 1, 2, 3, 5, 13]
Set = [1, 2, 3, 5, 13]
 
Yes

Avec findall, le 1 est dupliqué car il apparait 2 fois dans e2. L'utilisation d'un setof à la place du findall le fait disparaitre.

2.2. Union

Un élément appartient à l'union de e1 et e2 si il appartient soit à e1, soit à e2.

On traduit cela par :

 
Sélectionnez
union_e1_e2(X) :- e1(X).
union_e1_e2(X) :- e2(X).



Voici la fonction qui va nous permettre de comparer les résultats renvoyés par findall/2 et setof/2 :

 
Sélectionnez
test :-
  findall(X, union_e1_e2(X), Bag),
  setof(Y, union_e1_e2(Y), Set),
  write('Bag = '), write(Bag), nl,
  write('Set = '), write(Set), nl.

Exécution:

Exécution
Sélectionnez
| ?- test.
Bag = [1, 2, 3, 5, 7, 11, 13, 17, 19, 1, 1, 2, 3, 5, 8, 13, 21, 34]
Set = [1, 2, 3, 5, 7, 8, 11, 13, 17, 19, 21, 34]
 
Yes



Une variante pour éliminer certains doublons (tous si aucun doublon dans e1 ni e2) :

 
Sélectionnez
union_e1_e2(X) :- e1(X).
union_e1_e2(X) :- e2(X), \+e1(X).

Exécution:

Exécution
Sélectionnez
| ?- findall(X, union_e1_e2(X), Bag), write(Bag).
[1, 2, 3, 5, 7, 11, 13, 17, 19, 8, 21, 34]
 

2.3. Soustraction

Un élément appartient à e1-e2 si il appartient à e1 mais pas à e2.

On traduit cela par :

 
Sélectionnez
minus_e1_e2(X) :- e1(X), \+e2(X).
 



Exécution:

Exécution
Sélectionnez
| ?- findall(X, minus_e1_e2(X), Bag), write(Bag).
[7, 11, 17, 19]
 

2.4. Disjonction

La disjonction entre e1 et e2, c'est l'union entre e1-e2 et e2-e1 (c'est-à-dire l'ensemble des éléments qui appartiennent soit à e1, soit à e2, mais pas à la intersection de e1 et e2).

On traduit cela par :

 
Sélectionnez
disj_e1_e2(X) :- e1(X), \+e2(X).
disj_e1_e2(X) :- e2(X), \+e1(X).



Voici la fonction de test :

 
Sélectionnez
test :-
  findall(X, disj_e1_e2(X), Bag),
  setof(Y, disj_e1_e2(Y), Set),
  write('Bag = '), write(Bag), nl,
  write('Set = '), write(Set), nl.

Exécution:

Exécution
Sélectionnez
| ?- test.
Bag = [7, 11, 17, 19, 8, 21, 34]
Set = [7, 8, 11, 17, 19, 21, 34]
 
Yes

2.5. Produit cartésien

Le produit cartésien, c'est l'ensemble des combinaisons possibles entre les éléments de e1 et ceux de e2. Le résultat sera donné sous forme de tuples.

On traduit cela par :

 
Sélectionnez
prod_e1_e2( (X,Y) ) :- e1(X), e2(Y).
 



Exécution:

Exécution
Sélectionnez
| ?- findall(X, disj_e1_e2(X), Bag), write(Bag).
[ (1, 1), (1, 1), (1, 2), (1, 3), (1, 5), (1, 8), (1, 13), (1, 21), (1, 34), (2, 1), (2, 1), (2, 2), 
(2, 3), (2, 5), (2, 8), (2, 13), (2, 21), (2, 34), (3, 1), (3, 1), (3, 2), (3, 3), (3, 5), (3, 8), (3, 13), 
(3, 21), (3, 34), (5, 1), (5, 1), (5, 2), (5, 3), (5, 5), (5, 8), (5, 13), (5, 21), (5, 34), (7, 1), (7, 1), 
(7, 2), (7, 3), (7, 5), (7, 8), (7, 13), (7, 21), (7, 34), (11, 1), (11, 1), (11, 2), (11, 3), (11, 5), 
(11, 8), (11, 13), (11, 21), (11, 34), (13, 1), (13, 1), (13, 2), (13, 3), (13, 5), (13, 8), (13, 13), 
(13, 21), (13, 34), (17, 1), (17, 1), (17, 2), (17, 3), (17, 5), (17, 8), (17, 13), (17, 21), (17, 34), 
(19, 1), (19, 1), (19, 2), (19, 3), (19, 5), (19, 8), (19, 13), (19, 21), (19, 34)]
 

2.6. Restriction

La restriction permet de resteindre un ensemble à un sous-ensemble d'éléments répondant à certains critères (condition de restriction).

Dans l'exemple suivant, nous allons restreindre e1 aux éléments supérieurs à 3:

 
Sélectionnez
e1_superior_3(X) :- e1(X), 3<X.
 



Exécution:

Exécution
Sélectionnez
| ?- findall(X, e1_superior_3(X), Bag), write(Bag).
[5, 7, 11, 13, 17, 19]
 

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.