5 \subsection{Relations orientées et non orientées}
7 Exactement comme dans le cas des relations binaires, on considère une partie $G$ de l'ensemble produit cartésien de $n$ ensembles $\famn E$, soit $G\sse E_1\times E_2\times\cdots\times E_n$.
9 \begin{Def}[Relation $n$-aire]
10 Cette partie définit une relation $n$-aire\index{relation n-aire} entre ces ensembles.
16 Pour un $n$-uplet $\famn x$ d'éléments de $E_1\times E_2\times\cdots\times E_n$, on notera $\famn x\in G$ ou ${\mathcal{R}}\famn x$ le fait que ces éléments sont en relation par la relation ${\mathcal{R}}$ de graphe $G$.
23 Comme dans le cas des relations binaires, les $n$-uplets sont ordonnés et, même si deux des ensembles $E_i$ et $E_j$ sont identiques (pour $i\neq j$), le couple d'éléments
24 $(x_i,y_j)$ est considéré comme différent du couple $(y_j,x_i)$ lorsque $x_i\neq y_j$.
28 Cependant, dans la plupart des applications pratiques des relations $n$-aires, et dans toutes celles que nous verrons en tout cas, on \og étiquette les colonnes\fg{}, ce qui permet de s'affranchir de cet ordre, et de considérer ce que l'on appelle des relations
29 $n$-aires {\it non orientées\/}, dont les {\it domaines\/} sont les ensembles $\famn E$, dans un ordre non spécifié, car ils sont nommés.
34 \subsubsection{Exemple de relation ternaire orientée}
40 \item $E_1=\{1,2,3,4,5,6,7,8,9\}$,
41 \item $E_2=\{1988, 1989, 1990, 1991, 1992, 1993, 1994\}$
42 \item $E_3=\{\hbox{Alsace}, \hbox{Beaujolais}, \hbox{Côtes du Rhône}\}$.
48 $G=\{$ (3,1988,\hbox{Alsace}), (4,1991,\hbox{Alsace}), (8,1989,\hbox{Beaujolais}), (4,1989,\hbox{Côtes du Rhône}) $\}$.
54 $G$ est le graphe d'une relation ternaire orientée qui représente une cave à vins.\\
59 On peut la représenter par le tableau :\\
62 \centerline{$\begin{array}{c|c|l}
63 3 & 1988 & \hbox{Alsace} \\
64 4 & 1991 & \hbox{Alsace} \\
65 8 & 1989 & \hbox{Beaujolais} \\
66 4 & 1989 & \hbox{Côtes du Rhône} \\ \end{array}$}
71 Il est évident que l'ordre des éléments du $n$-uplet élément de $G$ a une importance fondamentale, surtout lorsque l'intersection des domaines n'est pas vide.
74 Autrement dit, cette relation doit être considérée comme différente de la relation définie sur $E_3\times E_2\times E_1$ par le graphe $G'$ représenté par le tableau\\
78 \centerline{$\begin{array}{l|l|l}
79 \hbox{Alsace} & 1988 & 3 \cr
80 \hbox{Alsace} & 1991 & 4 \cr
81 \hbox{Beaujolais} & 1989 & 8 \cr
82 \hbox{Côtes du Rhône} & 1989 & 4 \cr\end{array}$}
87 \subsubsection{Exemple de relation ternaire non orientée}\hfill\break Pour s'affranchir de l'ordre en évitant toute ambiguïté, il faut nommer les colonnes du tableau, c'est-à-dire ajouter un ensemble d'{\it attributs\/} (ou clés, ou étiquettes) qui pourraient être ici
88 $\{$Nombre, Année, Région$\}$.
93 \centerline{$\begin{array}{c|c|l}
94 \hbox{Nombre} & \hbox{Année} & \hbox{Région} \cr
96 3 & 1988 & \hbox{Alsace} \cr
97 4 & 1991 & \hbox{Alsace} \cr
98 8 & 1989 & \hbox{Beaujolais} \cr
99 4 & 1989 & \hbox{Côtes du Rhône} \cr\end{array}$}
103 Cette relation ternaire ne sera pas considérée comme différente de la relation représentée par\\
106 \centerline{$\begin{array}{l|c|c}
107 \hbox{Région} & \hbox{Année} & \hbox{Nombre} \cr
109 \hbox{Alsace} & 1988 & 3 \cr
110 \hbox{Alsace} & 1991 & 4 \cr
111 \hbox{Beaujolais} & 1989 & 8 \cr
112 \hbox{Côtes du Rhône} & 1989 & 4 \cr\end{array}$}\psaut
116 En effet, les attributs ne sont pas ordonnés, l'ensemble $\{$Région, Année, Nombre$\}$ est égal à l'ensemble $\{$Nombre, Année, Région$\}$.
121 Dans la suite, le terme de relation $n$-aire sera réservé aux relations non orientées.
127 On peut toujours associer à une relation $n$-aire une relation $n$-aire orientée, définie sur $D_1\times D_2\times\cdots\times D_n$, où les $D_i$ sont les domaines attachés aux attributs de $A$, énoncés dans un certain ordre.
130 Bien entendu, si les attributs sont énoncés dans un ordre différent, la relation $n$-aire orientée associée peut ne pas être la même, mais, pour une même relation $n$-aire, toutes les relations $n$-aires orientées associées se déduisent les unes des autres par une permutation sur les domaines.
135 C'est pourquoi on s'autorisera à utiliser l'abus de notation ${\mathcal{R}}\famn x$, pour exprimer que les $x_i$ sont en relation par la relation $n$-aire (non orientée) ${\mathcal{R}}$, en se référant à l'une quelconque des relations $n$-aires orientées associées (celle qui correspond à l'ordre des domaines $D_i$ lorsque les $x_i$ sont énoncés).
139 On notera ${\mathcal{R}}[A]$ une relation $n$-aire (non orientée) d'attributs $A$.
144 \subsection{Relations équivalentes, relations égales}
146 \begin{Def}[Relations $n$-aires équivalentes]
147 Deux relations $n$-aires (non orientées) sont \emph{équivalentes}\index{relations n-aires!équivalentes} lorsque leurs domaines sont les mêmes et qu'il existe une permutation de ces domaines telle que les relations orientées associées sont égales (au sens de l'égalité des ensembles, puisqu'une relation $n$-aire orientée est définie comme un ensemble).
153 \begin{Def}[Relations $n$-aires égales]
154 Deux relations $n$-aires (non orientées) sont \emph{égales}\index{relations n-aires!égale} lorsqu'elles sont équivalentes et que leurs attributs sont les mêmes.
162 \begin{tabular}{|c|c|c|}
164 Groupe & Nom & Age \cr
176 \begin{tabular}{|c|c|c|}
178 Age & Nom & Groupe \cr
190 \begin{tabular}{|c|c|c|}
192 Note & Matière & Nombre \cr
204 Une relation ${\mathcal{R}}$
208 Une relation égale à ${\mathcal{R}}$
212 Une relation équivalente à ${\mathcal{R}}$
221 \subsection{Interprétation fonctionnelle}
223 Chaque ligne du tableau d'une relation $n$-aire ${\mathcal{R}}[A]$ aux attributs $A$, de domaines $\famn D$, peut être interprétée comme une application de $A$ (l'ensemble des attributs) dans $D_1\union
224 D_2\union\cdots\union D_n$.
229 Par exemple, pour la première relation du paragraphe précédent, on peut considérer les fonctions $f_1$, $f_2$ et $f_3$ définies par $f_1(\hbox{Groupe})=1$, $f_1(\hbox{Nom})=A$, $f_1(\hbox{Age})=18$, $f_2(\hbox{Groupe})=1$, etc.
237 Un Système de Gestion de Base de Données Relationnelles (SGBD) \index{SGBD} est une application informatique de définition et de travail sur des relations $n$-aires (non orientées).
244 Cette application met en général à la disposition de l'utilisateur un langage (le plus souvent, SQL) qui permet
246 \item de définir les objets et leurs liens, de les modifier et d'enrichir la base de données,
247 \item de retrouver l'information contenue dans la base de données par la formulation de requêtes.
253 \section{Projections}
255 \subsection{Définitions}
258 Soit ${\mathcal{R}}[A]$ une relation $n$-aire d'attributs $A$, et $a\in A$.
260 On pose $A=\{a\}\union B$, et on suppose que le domaine de $a$ est $D_1$ et que les domaines des attributs de $B$ sont $D_2 \vir \ldots \vir D_n$.
264 \begin{Def}[Projection d'une relation]
265 La projection de la relation ${\mathcal{R}}$ suivant $a$ sur $B$, notée ${\mathcal{R}}_a$ (on autorise aussi ${\mathcal{R}}[B]$), est définie par :
266 $${\mathcal{R}}_a(x_2\vir\ldots\vir x_n)\qquad\Ssi\qquad \exi x_1\in D_1,\ {\mathcal{R}}\famn x.$$
271 Dans la pratique, on obtient la projection d'une relation :
273 \item en supprimant la colonne de l'attribut selon lequel se fait la projection,
274 \item et en ne conservant qu'une seule occurrence de lignes qui
275 seraient devenues identiques.
281 \subsection{Théorème des projections}
283 Soit ${\mathcal{R}}[A]$ une relation $n$-aire d'attributs $A$, $a\in A$, $b\in A$ ($b\neq a$).
285 \begin{Th}[Théorème des projections]
286 $$\left({\mathcal{R}}_a\right)_b=\left({\mathcal{R}}_b\right)_a\ .$$
292 (Démonstration immédiate).
297 Ce dernier résultat nous autorise à considérer la projection d'une relation suivant un sous-ensemble d'attributs (et sur le complémentaire de ce sous-ensemble d'attributs).
303 On notera cette projection ${\mathcal{R}}_B$ (ou ${\mathcal{R}}[A\moins B]$) (si $B\sse A$, c'est la projection suivant $B$ de ${\mathcal{R}}$ sur $C=A\moins B$.
310 \section{Opérations sur les relations $n$-aires}
313 \subsection{Somme et produit}
315 Soit ${\mathcal{R}}$ une relation d'attributs $A$ et ${\cal S}$ une relation d'attributs $B$, pour lesquelles les attributs de même nom ont même domaine.
317 Les relations somme ${\mathcal{R}}+{\cal S}$ et produit ${\mathcal{R}}*{\cal S}$ ont pour attributs $A\union B$.
321 Pour l'énoncé de la définition, comme l'ordre dans lequel on énonce les attributs est sans importance, on suppose que, dans $A\union B$, les éléments sont énumérés dans l'ordre suivant
323 \item les attributs de $A$ qui ne sont pas dans $B$, les domaines sont $D_1\vir\ldots\vir D_p\,$,
324 \item les attributs communs à $A$ et à $B$, les domaines sont $D_{p+1}\vir\ldots\vir D_q\,$,
325 \item les attributs de $B$ qui ne sont pas dans $A$, les domaines sont $D_{q+1}\vir\ldots\vir D_n\,$.
327 (l'un de ces sous-ensembles peut être vide).
331 On a alors, par définition
333 \item $({\mathcal{R}}+{\cal S}) (x_1\vir\ldots\vir x_p\vir x_{p+1}\vir\ldots\vir x_q \vir\ldots\vir x_{q+1}\vir
334 x_n)$ si et seulement si\\ $ {\mathcal{R}} (x_1\vir\ldots\vir x_q)$ ou ${\cal S} (x_{p+1}\vir\ldots\vir x_n)$,
335 \item $ ({\mathcal{R}}*{\cal S}) (x_1\vir\ldots\vir x_p\vir\ldots\vir x_q\vir\ldots\vir x_n)$ si et seulement si\\ $ {\mathcal{R}} (x_1\vir\ldots\vir x_q)$ et ${\cal S} (x_{p+1}\vir\ldots\vir x_n).$
342 On note $\left({\mathcal{R}}+{\cal S}\right)[A\union B]$ et $\left({\mathcal{R}}*{\cal S}\right)[A\union B]$.
349 Le domaine de l'attribut Groupe est $\{1,2,3\}$, celui de Nom est $\{$A,B,C$\}$ et celui de Age est $\{19,20,21\}$.
354 \begin{tabular}{cccc}
375 \begin{tabular}{c|c|c}
376 Groupe & Nom & Age \cr
387 \begin{tabular}{c|c|c}
388 Groupe & Nom & Age \cr
407 Une relation ${\mathcal{R}}$
411 Une relation ${\cal S}$
415 La relation ${\mathcal{R}}*{\cal S}$
419 La relation ${\mathcal{R}}+{\cal S}$
425 \subsection{Réunion et intersection}
426 C'est le cas particulier de la somme et du produit de deux relations d'attributs $A$ et $B$ dans le cas où $A=B$.
429 Donc, dans le cas où $A=B$, ${\mathcal{R}}\union{\cal S}={\cal
430 R}+{\cal S}$ et ${\mathcal{R}}\inter{\cal S}={\mathcal{R}}*{\cal S}$.
434 On note donc $\left({\mathcal{R}}\union{\cal S}\right)[A]$ et $\left({\mathcal{R}}\inter{\cal S}\right)[A]$
439 \subsection{Produit cartésien}
441 Il s'agit du cas particulier du produit de deux relations dans le cas où $A\inter B=\void$.
444 Donc, dans le cas où $A\inter B=\void$, ${\mathcal{R}}\times{\cal S}={\mathcal{R}}*{\cal S}$.
448 On note donc $\left({\mathcal{R}}\times{\cal S}\right)[A\union B]$.
453 \section{Sélection d'une relation $n$-aire}
455 Soit ${\mathcal{R}}[A]$ une relation $n$-aire d'attributs $A$ et $F$ une formule de logique dans laquelle les variables sont des éléments de $A$ et les constantes des éléments du domaine des attributs.
459 La sélection de ${\mathcal{R}}$ suivant $F$ est une relation ayant les mêmes attributs $A$, notée $\left({\mathcal{R}}:F\right)[A]$
460 et telle que ${\mathcal{R}}\famn x$ et $F\famn x$.
464 Autrement dit, il s'agit des éléments des domaines des attributs qui sont en relation par ${\mathcal{R}}$ et qui satisfont la formule $F$ donnée.
467 Sur une relation d'attributs $\{\hbox{Nom}\vir\hbox{Age}\vir\hbox{Note}\}$ on pourra définir la
468 relation $[(\hbox{Age}\leqslant 19)\ \hbox{et}\ (\hbox{Note}\geqslant 16)]$ pour sélectionner les étudiants admis à s'inscrire au département d'Informatique.
473 \section{Dépendances fonctionnelles et clés}
475 \subsection{Dépendances fonctionnelles}
477 Il s'agit, lorsque c'est possible, de remplacer une relation $n$-aire par une autre, plus simple, et sans perte d'information.\\
480 Soit ${\mathcal{R}}[A]$ une relation d'attributs $A$ telle que $A$ soit de la forme $X\union Y\union Z$.
483 On suppose pour simplifier :
485 \item que les domaines des attributs de $X$ sont $D_1\vir D_2\vir\ldots\vir D_p$,
486 \item que ceux de $Y$ sont $D_{p+1}\vir\ldots\vir D_q$
487 \item que ceux de $Z$ sont $D_{q+1}\vir\ldots\vir D_n$.
491 \begin{Def}[Dépendance fonctionnelle]
492 On dit que $Y$ dépend fonctionnellement de $X$ lorsque l'on a $${\mathcal{R}}(x_1\vir\ldots\vir x_p\vir x_{p+1}\vir\ldots\vir x_q\vir x_{q+1}\vir\ldots\vir x_n)$$ et $${\mathcal{R}}(x_1\vir\ldots\vir x_p\vir x'_{p+1}\vir\ldots\vir x'_q\vir x'_{q+1}\vir\ldots\vir
493 x'_n)$$ si et seulement si $$x_{p+1}=x'_{p+1}\vir\ldots\vir x_q=x'_q\,$$.
504 Dans la suite, et pour une situation du même type, on s'autorisera à utiliser les notations suivantes :
506 \item $D_X$ pour $D_1\vir D_2 \vir\ldots\vir D_p$,
507 \item $D_Y$ pour $D_{p+1}\vir\ldots\vir D_q$,
508 \item $D_Z$ pour $D_{q+1}\vir\ldots\vir D_n$,
509 \item $x$ pour $(x_1\vir\ldots\vir x_p)$,
510 \item $y$ pour $(x_{p+1}\vir\ldots\vir x_q)$
511 \item et $z$ pour $(x_{q+1}\vir\ldots\vir x_n)$.
517 Ainsi, la condition énoncée peut s'écrire plus simplement ${\mathcal{R}}(x,y,z)$ et ${\mathcal{R}}(x,y',z')$ si et seulement si $y=y'$ (cette égalité devant être considérée comme une égalité de $n$-uplets, c'est-à-dire l'égalité composante par composante.
521 Dans la relation suivante,\\
523 \centerline{\begin{tabular}{|c|c|c|c|}
525 Groupe & Nom & Niveau & Age \cr
541 On distingue les dépendances fonctionnelles
543 \item $\{$Nom$\}\imp$ $\{$Age$\}$
544 \item $\{$Groupe , Niveau$\}\imp$ $\{$Age$\}$
550 \subsection{Théorème des dépendances fonctionnelles}
552 \begin{Th}[Théorème des dépendances fonctionnelles]
553 Si la relation ${\mathcal{R}}[A]$ d'attributs $A=X\union Y\union Z$ admet une dépendance fonctionnelle $X\imp Y$, elle est le produit de ses projections sur $X\union Y$ et $X\union Z$.
558 La relation précédente est le produit de ses deux projections ${\cal
559 R}[\{\hbox{Nom}\vir\hbox{Age}\}]$ et ${\mathcal{R}}[\{\hbox{Nom}\vir\hbox{Groupe}\vir\hbox{Niveau}\}]$.
567 Pour une relation ${\mathcal{R}} [A]$ d'attributs $A$, une \emph{clé} \index{clé} est un sous-ensemble minimal $K$ de $A$ tel qu'il existe une dépendance fonctionnelle $C\imp A\moins K$.
570 ($K$ est un sous-ensemble minimal au sens qu'il n'y a pas de partie stricte $K'$ de $K$ pour laquelle il existe une dépendance fonctionnelle $K'\imp A\moins K'$).
574 Cette \og minimalité\fg{} n'entraîne en aucune manière l'unicité de la clé pour une relation donnée.
578 Pour toute relation, il est possible d'introduire un attribut dont les valeurs sont toutes différentes, et qui constitue donc une clé pour la nouvelle relation obtenue (par exemple, une numérotation).
587 \centerline{\x{Fin du Chapitre}}
