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▲
À 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.
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 s’il appartient à la fois à e1 et à e2.
On traduira cela par :
intersect_e1_e2(X) :- e1(X), e2(X).Voici la fonction de test et son exécution :
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.|?- test.
Bag = [1, 1, 2, 3, 5, 13]
Set = [1, 2, 3, 5, 13]
YesAvec 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 s’il appartient soit à e1, soit à e2.
On traduit cela par :
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 :
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 :
| ?- 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]
YesUne variante pour éliminer certains doublons (tous si aucun doublon dans e1 ni e2) :
union_e1_e2(X) :- e1(X).
union_e1_e2(X) :- e2(X), \+e1(X).Exécution :
| ?- 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 s’il appartient à e1, mais pas à e2.
On traduit cela par :
minus_e1_e2(X) :- e1(X), \+e2(X).Exécution :
| ?- 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 à l’intersection de e1 et e2).
On traduit cela par :
disj_e1_e2(X) :- e1(X), \+e2(X).
disj_e1_e2(X) :- e2(X), \+e1(X).Voici la fonction de test :
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 :
| ?- test.
Bag = [7, 11, 17, 19, 8, 21, 34]
Set = [7, 8, 11, 17, 19, 21, 34]
Yes2-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 :
prod_e1_e2( (X,Y) ) :- e1(X), e2(Y).Exécution :
| ?- 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 restreindre 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 :
e1_superior_3(X) :- e1(X), 3<X.Exécution :
| ?- findall(X, e1_superior_3(X), Bag), write(Bag).
[5, 7, 11, 13, 17, 19]3. Jointures▲
Pour illustrer cette section à propos des jointures, nous allons prendre comme exemple les ensembles et relations suivants :
- homme : l'ensemble des hommes ;
- femme : l'ensemble des femmes ;
- personne : l'union entre les ensembles disjoints homme et femme ;
- qualite : l'ensemble des qualités que peut avoir une personne (ex. : beau, intelligent, gentil) ;
- couple : une relation entre les ensembles homme et femme ;
- age : une relation entre l'ensemble personne et l'ensemble des entiers naturels ;
- a_qualite : une relation entre l'ensemble personne et l'ensemble qualite.
Pour des raisons de simplicité (et pour illustrer les jointures), nous ne nous intéresserons qu'aux couples hétérosexuels.
Voici notre fichier d'exemple :
personne(P) :- homme(P).
personne(P) :- femme(P).
homme(denis).
homme(jacques).
homme(pierre).
homme(sylvain).
homme(edouard).
femme(amelie).
femme(julie).
femme(henriette).
femme(sylvie).
femme(noemie).
age(denis, 27).
age(jacques, 35).
age(pierre, 25).
age(sylvain, 28).
age(edouard, 65).
age(noemie, 18).
age(amelie, 21).
age(augustine, 27).
age(stephanie, 32).
age(christine, 34).
age(henriette, 61).
couple(edouard, henriette).
couple(jacques, christine).
couple(denis, amelie).
qualite(beau).
qualite(intelligent).
qualite(gentil).
a_qualite(denis, beau).
a_qualite(denis, gentil).
a_qualite(jacques, intelligent).
a_qualite(pierre, beau).
a_qualite(pierre, intelligent).
a_qualite(pierre, gentil).
a_qualite(sylvain, beau).
a_qualite(sylvain, intelligent).
a_qualite(edouard, intelligent).
a_qualite(edouard, gentil).3-1. Interne/Externe▲
3-1-1. Jointure interne▲
Une jointure interne traduit la relation entre deux ensembles.
Il s'agit donc de la relation elle-même :
inner_join( (H,F) ) :-
couple(H,F).Exemple d'exécution :
| ?- findall(X, inner_join(X), Inner), write(Inner).
[ (edouard, henriette), (jacques, christine), (denis, amelie)]3-1-2. Jointure externe▲
Dans une jointure externe, on retrouve les mêmes éléments que pour la jointure interne, sauf qu'en plus on ajoute les éléments n'ayant pas de correspondance dans la relation. Il est alors possible de leur spécifier une valeur par défaut (null, inconnu, 'N/A', une valeur arbitraire) ou pas de valeur du tout.
Il existe plusieurs types de jointures externes, suivant le sens de la jointure (gauche, droite, complète).
3-1-2-1. Jointure externe gauche▲
Pour la jointure gauche, on part de l'ensemble de départ et on cherche les correspondances dans la relation. S'il n'y a pas de correspondance, on spécifie une valeur par défaut (ici null, comme en SQL).
Il est possible d'effectuer la jointure de plusieurs manières, suivant comment on souhaite que soient classés les éléments null (entrelacés ou non entrelacés).
Voici la manière entrelacée :
left_join_interleaved( (H,F) ) :-
homme(H),
lji(H,F).
lji(H,F) :- couple(H,F), !.
lji(_,null).Voici la manière non entrelacée :
left_join_noninterleaved( (H,F) ) :-
couple(H,F).
left_join_noninterleaved( (H,null) ) :-
homme(H),
\+couple(H,_).Voici la fonction de test et son exécution :
test :-
findall(X, left_join_interleaved(X), LeftInter),
findall(Y, left_join_noninterleaved(Y), LeftNonInter),
write('LeftInter = '), write(LeftInter), nl,
write('LeftNonInter = '), write(LeftNonInter), nl.| ?- test.
LeftInter = [ (denis, amelie), (jacques, christine), (pierre, null), (sylvain, null), (edouard, henriette)]
LeftNonInter = [ (edouard, henriette), (jacques, christine), (denis, amelie), (pierre, null), (sylvain, null)]
YesComme on peut le remarquer, pour la manière non entrelacée, on a choisi de mettre les null à la fin. On aurait pu choisir de les mettre au début. La manière non entrelacée est en fait une union de deux ensembles (ceux ayant une correspondance dans la relation et les autres).
3-1-2-2. Jointure externe droite▲
Le principe est le même pour une jointure droite que pour une jointure gauche, seul le sens de la jointure change.
3-1-2-3. Jointure externe complète▲
Une jointure externe complète, c'est l'union d'une jointure gauche et d'une jointure droite, sans doublons.
Comme pour les jointures externes gauches ou droites, il est possible de spécifier si l'on souhaite que les résultats soient entrelacés ou non.
full_outer_join( (H,F) ) :-
couple(H,F).
full_outer_join( (H,null) ) :-
homme(H),
\+couple(H,_).
full_outer_join( (null, F) ) :-
femme(F),
\+couple(_, F).Exemple d'exécution :
| ?- findall(X, full_outer_join(X), Full), write(Full).
[ (edouard, henriette), (jacques, christine), (denis, amelie), (pierre, null), (sylvain, null), (null, julie),
(null, sylvie), (null, noemie)]3-2. Autojointure▲
Une autojointure est une jointure liant un ensemble à lui-même, directement ou au moyen de jointures successives.
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 appartenant à ensemble tel que propriete(x) » et qui serait vrai si une telle expression est vérifiée.
Voici le prédicat Prolog correspondant :
there_exists(Expr, Prop) :- Expr, Prop, !.Exemple d'exécution :
| ?- there_exists( e1(X), 2<X ).
X = 3
YesCeci 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 :
| ?-
there_exists(
( e1(X), e2(Y) )
,
( 2<X, X<Y )
).
X = 3
Y = 5
YesTraduction : « 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'occurrence 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 :
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 allons utiliser (pas besoin de le réécrire).
Exemple d'exécution :
| ?-
forall(
( e1(X), e2(Y) )
,
( 0<X, 0<Y )
).
X = _G398
Y = _G400
YesTraduction : « 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 :
plusJeune(X) :-
personne(X),
age(X, AgeX),
forall(
( personne(Y), age(Y, AgeY) )
,
AgeX =< AgeY
).Exécution :
| ?- findall(X, plusJeune(Y), Inner), write(Inner).
[noemie]Autre solution
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 parcourrait 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.
Soit les ensembles e1 et e2, liés entre eux par la relation 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écédente en Prolog, notamment grâce aux opérateurs définis précédemment :
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 répertoriées dans l'ensemble qualite (division de personne par qualite par la relation a_qualite) :
div_personne_qualite(P) :-
personne(P),
forall( qualite(Q), a_qualite(P, Q) ).Exécution :
| ?- findall(X, div_personne_qualite(Y), Div), write(Div).
[pierre]5. Résumé▲
Dans les sections précédentes, nous avons illustré les différentes opérations de l'algèbre relationnelle en Prolog grâce à des prédicats « statiques ». Il est toutefois possible de redéfinir des prédicats (et donc les ensembles et relations de l'algèbre relationnelle) de manière « dynamique » grâce notamment à asserta/1, assertz/1, retract/1. Ceci permet de faire de notre programme Prolog une « base de faits » dynamique.
Grâce aux différentes opérations de l'algèbre relationnelle (notamment les restrictions, unions, intersections, jointures), il est tout à fait possible de créer des sous-ensembles à partir des ensembles de base pour obtenir ce que l'on pourrait appeler des « vues » (en référence aux vues du langage SQL).
Par ailleurs, ces vues peuvent être combinées entre elles pour obtenir d'autres vues. Enfin il est tout à fait possible de paramétrer ces vues de manière, par exemple, à spécifier les conditions de restriction.
Dans cet article, nous avons également vu qu'il était possible d'utiliser les prédicats Prolog de 2 manières :
- soit tel quel pour retourner 1 à 1 les éléments d'un ensemble, lors de l'énumération de solutions ;
- soit retourner l'ensemble au complet, sous forme de liste, grâce aux prédicats findall/3, bagof/3 ou setof/3.
Tout ceci offre une très grande souplesse d'utilisation.
6. Conclusion▲
Dans cet article, nous avons fait le lien entre Prolog et l'algèbre relationnelle (qui est notamment à la base de données relationnelles et donc du langage SQL). En faisant ce lien, nous espérons avoir facilité la compréhension du langage Prolog en capitalisant sur des connaissances déjà acquises (bons nombres de gens sont familiers avec les concepts liés aux bases de données et donc à l'algèbre relationnelle).
Par ailleurs, cet article a montré une manière de traduire des opérations de l'algèbre relationnelle en Prolog, le tout illustré de nombreux exemples. On a notamment défini les opérations « il existe » et « pour tout ». Les prédicats définis dans cet article peuvent donc servir de référence pour une consultation ultérieure.
Enfin cet article montre combien en Prolog il est simple de représenter des ensembles, des relations, et d'effectuer des opérations sur ces ensembles, le tout sans avoir recours à des fonctions d'une grande complexité.