modif algo euclide

[cours-maths-dis.git] / ensembles / relnaire.tex

\section{Définitions}

\subsection{Relations orientées et non orientées}

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$.

\begin{Def}[Relation $n$-aire]
Cette partie définit une relation $n$-aire\index{relation n-aire} entre ces ensembles. 
\end{Def}



\begin{Notation}
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$.
\end{Notation}





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
$(x_i,y_j)$ est considéré comme différent du couple $(y_j,x_i)$ lorsque $x_i\neq y_j$. 



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
$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.




\subsubsection{Exemple de relation ternaire orientée}


Soient

\begin{itemize}
 \item $E_1=\{1,2,3,4,5,6,7,8,9\}$,
 \item $E_2=\{1988, 1989, 1990, 1991, 1992, 1993, 1994\}$
 \item $E_3=\{\hbox{Alsace}, \hbox{Beaujolais}, \hbox{Côtes du Rhône}\}$.
\end{itemize}

 et soit

\begin{center}
$G=\{$ (3,1988,\hbox{Alsace}), (4,1991,\hbox{Alsace}), (8,1989,\hbox{Beaujolais}), (4,1989,\hbox{Côtes du Rhône}) $\}$. 
\end{center}




$G$ est le graphe d'une relation ternaire orientée qui représente une cave à vins.\\




On peut la représenter par le tableau :\\


\centerline{$\begin{array}{c|c|l}
3 & 1988 & \hbox{Alsace} \\
4 & 1991 & \hbox{Alsace} \\
8 & 1989 & \hbox{Beaujolais} \\
4 & 1989 & \hbox{Côtes du Rhône} \\ \end{array}$}

\bigskip


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.


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\\



\centerline{$\begin{array}{l|l|l}
\hbox{Alsace} & 1988 & 3 \cr
\hbox{Alsace} & 1991 & 4 \cr
\hbox{Beaujolais} & 1989 & 8 \cr
\hbox{Côtes du Rhône} & 1989 & 4 \cr\end{array}$}




\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
$\{$Nombre, Année, Région$\}$.


On obtiendrait\\

\centerline{$\begin{array}{c|c|l}
\hbox{Nombre} & \hbox{Année} & \hbox{Région} \cr
\noalign{\hrule}
3 & 1988 & \hbox{Alsace} \cr
4 & 1991 & \hbox{Alsace} \cr
8 & 1989 & \hbox{Beaujolais} \cr
4 & 1989 & \hbox{Côtes du Rhône} \cr\end{array}$}

\bigskip

Cette relation ternaire ne sera pas considérée comme différente de la relation représentée par\\


\centerline{$\begin{array}{l|c|c}
\hbox{Région} & \hbox{Année} & \hbox{Nombre} \cr
\noalign{\hrule}
\hbox{Alsace} & 1988 & 3 \cr
\hbox{Alsace} & 1991 & 4 \cr
\hbox{Beaujolais} & 1989 & 8 \cr
\hbox{Côtes du Rhône} & 1989 & 4 \cr\end{array}$}\psaut

\medskip

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$\}$.


\bigskip

Dans la suite, le terme de relation $n$-aire sera réservé aux relations non orientées.


\bigskip


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.


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.


\bigskip

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).


\begin{Notation}
On notera ${\mathcal{R}}[A]$ une relation $n$-aire (non orientée) d'attributs $A$.
\end{Notation}



\subsection{Relations équivalentes, relations égales}

\begin{Def}[Relations $n$-aires équivalentes]
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).
\end{Def}




\begin{Def}[Relations $n$-aires égales]
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. 
\end{Def}



\noindent
\begin{tabular}{ccc}

\begin{tabular}{|c|c|c|}
\noalign{\hrule}
Groupe & Nom & Age \cr
\noalign{\hrule}
1 & A & 18 \cr
\noalign{\hrule}
1 & B & 17 \cr
\noalign{\hrule}
2 & C & 18 \cr
\noalign{\hrule}
\end{tabular} 

&

\begin{tabular}{|c|c|c|}
\noalign{\hrule}
Age & Nom & Groupe \cr
\noalign{\hrule}
18 & A & 1\cr
\noalign{\hrule}
17 & B & 1\cr
\noalign{\hrule}
18 & C & 2\cr
\noalign{\hrule}
\end{tabular}

&

\begin{tabular}{|c|c|c|}
\noalign{\hrule}
Note & Matière & Nombre \cr
\noalign{\hrule}
18 & A & 1\cr
\noalign{\hrule}
17 & B & 1\cr
\noalign{\hrule}
18 & C & 2\cr
\noalign{\hrule}
\end{tabular}

\cr

Une relation ${\mathcal{R}}$

&

Une relation égale à ${\mathcal{R}}$ 

&

Une relation équivalente à ${\mathcal{R}}$

\cr

\end{tabular}


\bigskip

\subsection{Interprétation fonctionnelle}

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
D_2\union\cdots\union D_n$.



\begin{Ex}
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.
\end{Ex}



\subsection{SGBD}

\begin{Def}[SGBD]
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).
\end{Def}





Cette application met en général à la disposition de l'utilisateur un langage (le plus souvent, SQL) qui permet 
\begin{itemize}
\item de définir les objets et leurs liens, de les modifier et d'enrichir la base de données,
\item de retrouver l'information contenue dans la base de données par la formulation de requêtes.
\end{itemize}




\section{Projections}

\subsection{Définitions}


Soit ${\mathcal{R}}[A]$ une relation $n$-aire d'attributs $A$, et $a\in A$.

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$.



\begin{Def}[Projection d'une relation]
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 :
$${\mathcal{R}}_a(x_2\vir\ldots\vir x_n)\qquad\Ssi\qquad \exi x_1\in D_1,\ {\mathcal{R}}\famn x.$$ 
\end{Def}


\begin{Rem}
Dans la pratique, on obtient la projection d'une relation :
\begin{itemize}
 \item en supprimant la colonne de l'attribut selon lequel se fait la projection,
 \item et en ne conservant qu'une seule occurrence de lignes qui
seraient devenues identiques.
\end{itemize}
\end{Rem}



\subsection{Théorème des projections}

Soit ${\mathcal{R}}[A]$ une relation $n$-aire d'attributs $A$, $a\in A$, $b\in A$ ($b\neq a$).

\begin{Th}[Théorème des projections]
 $$\left({\mathcal{R}}_a\right)_b=\left({\mathcal{R}}_b\right)_a\ .$$
\end{Th}



\begin{Proof}
(Démonstration immédiate). 
\end{Proof}


\begin{Rem}
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). 
\end{Rem}



\begin{Notation}
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$. 
\end{Notation}





\section{Opérations sur les relations $n$-aires}


\subsection{Somme et produit}

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.

Les relations somme ${\mathcal{R}}+{\cal S}$ et produit ${\mathcal{R}}*{\cal S}$ ont pour attributs $A\union B$.

\bigskip

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
\begin{itemize}
\item les attributs de $A$ qui ne sont pas dans $B$, les domaines sont $D_1\vir\ldots\vir D_p\,$,
\item les attributs communs à $A$ et à $B$, les domaines sont $D_{p+1}\vir\ldots\vir D_q\,$,
\item les attributs de $B$ qui ne sont pas dans $A$, les domaines sont $D_{q+1}\vir\ldots\vir D_n\,$.
\end{itemize}
(l'un de ces sous-ensembles peut être vide).


\begin{Def}
On a alors, par définition
\begin{itemize}
 \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
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)$,
\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).$
\end{itemize}
\end{Def}

 

\begin{Notation}
On note $\left({\mathcal{R}}+{\cal S}\right)[A\union B]$ et $\left({\mathcal{R}}*{\cal S}\right)[A\union B]$. 
\end{Notation}




\begin{Ex}
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\}$. 
\end{Ex}


\noindent
\begin{tabular}{cccc}
\begin{tabular}{c|c}
Groupe & Nom \cr
\noalign{\hrule}
1 & A \cr
1 & B \cr
2 & C \cr
\end{tabular}

&

\begin{tabular}{c|c}
Groupe & Age \cr
\noalign{\hrule}
1 & 20 \cr
1 & 21 \cr
2 & 21 \cr
\end{tabular}

&

\begin{tabular}{c|c|c}
Groupe & Nom & Age \cr
\noalign{\hrule}
1 & A & 20 \cr
1 & A & 21 \cr
1 & B & 20 \cr
1 & B & 21 \cr
2 & C & 21 \cr
\end{tabular}

&

\begin{tabular}{c|c|c}
Groupe & Nom & Age \cr
\noalign{\hrule}
1 & A & 19 \cr
1 & A & 20 \cr
1 & A & 21 \cr
1 & B & 19 \cr
1 & B & 20 \cr
1 & B & 21 \cr
1 & C & 20 \cr
1 & C & 21 \cr
2 & A & 21 \cr
2 & B & 21 \cr
2 & C & 19 \cr
2 & C & 20 \cr
2 & C & 21 \cr
\end{tabular}

\cr

Une relation ${\mathcal{R}}$

&

Une relation ${\cal S}$

&

La relation ${\mathcal{R}}*{\cal S}$

&

La relation ${\mathcal{R}}+{\cal S}$

\cr

\end{tabular}

\subsection{Réunion et intersection}
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$.


Donc, dans le cas où $A=B$, ${\mathcal{R}}\union{\cal S}={\cal
R}+{\cal S}$ et ${\mathcal{R}}\inter{\cal S}={\mathcal{R}}*{\cal S}$.


\begin{Notation}
On note donc $\left({\mathcal{R}}\union{\cal S}\right)[A]$ et $\left({\mathcal{R}}\inter{\cal S}\right)[A]$ 
\end{Notation}



\subsection{Produit cartésien}

Il s'agit du cas particulier du produit de deux relations dans le cas où $A\inter B=\void$.


Donc, dans le cas où $A\inter B=\void$, ${\mathcal{R}}\times{\cal S}={\mathcal{R}}*{\cal S}$.


\begin{Notation}
On note donc $\left({\mathcal{R}}\times{\cal S}\right)[A\union B]$. 
\end{Notation}



\section{Sélection d'une relation $n$-aire}

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.


\begin{Def}
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]$
et telle que  ${\mathcal{R}}\famn x$ et $F\famn x$. 
\end{Def}


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.

\begin{Ex}
Sur une relation d'attributs $\{\hbox{Nom}\vir\hbox{Age}\vir\hbox{Note}\}$ on pourra définir la
relation $[(\hbox{Age}\leqslant 19)\ \hbox{et}\ (\hbox{Note}\geqslant 16)]$ pour sélectionner les étudiants admis à s'inscrire au département d'Informatique. 
\end{Ex}



\section{Dépendances fonctionnelles et clés}

\subsection{Dépendances fonctionnelles}

Il s'agit, lorsque c'est possible, de remplacer une relation $n$-aire par une autre, plus simple, et sans perte d'information.\\


 Soit ${\mathcal{R}}[A]$ une relation d'attributs $A$ telle que $A$ soit de la forme $X\union Y\union Z$.


On suppose pour simplifier  :
\begin{itemize}
 \item que les domaines des attributs de $X$ sont $D_1\vir D_2\vir\ldots\vir D_p$,
 \item que ceux de $Y$ sont $D_{p+1}\vir\ldots\vir D_q$
 \item que ceux de $Z$ sont $D_{q+1}\vir\ldots\vir D_n$.
\end{itemize}


\begin{Def}[Dépendance fonctionnelle]
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
x'_n)$$ si et seulement si $$x_{p+1}=x'_{p+1}\vir\ldots\vir x_q=x'_q\,$$.
\end{Def}








\begin{Notation}
 Dans la suite, et pour une situation du même type, on s'autorisera à utiliser les notations suivantes :
\begin{itemize}
 \item $D_X$ pour $D_1\vir D_2 \vir\ldots\vir D_p$,
 \item $D_Y$ pour $D_{p+1}\vir\ldots\vir D_q$,
 \item $D_Z$ pour $D_{q+1}\vir\ldots\vir D_n$,
 \item $x$ pour $(x_1\vir\ldots\vir x_p)$,
 \item $y$ pour $(x_{p+1}\vir\ldots\vir x_q)$
 \item et $z$ pour $(x_{q+1}\vir\ldots\vir x_n)$.
\end{itemize}
\end{Notation}



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.


\begin{Ex}
Dans la relation suivante,\\

\centerline{\begin{tabular}{|c|c|c|c|}
\noalign{\hrule}
Groupe & Nom & Niveau & Age \cr
\noalign{\hrule}
1 & A & 1 & 20 \cr
2 & B & 3 & 21 \cr
1 & C & 3 & 20 \cr
1 & A & 3 & 20 \cr
3 & B & 1 & 21 \cr
1 & C & 1 & 20 \cr
2 & A & 1 & 20 \cr
3 & B & 2 & 21 \cr
1 & C & 2 & 20 \cr
\noalign{\hrule}
\end{tabular}}

\medskip

On distingue les dépendances fonctionnelles 
\begin{itemize}
\item $\{$Nom$\}\imp$  $\{$Age$\}$
\item $\{$Groupe , Niveau$\}\imp$  $\{$Age$\}$
\end{itemize}
\end{Ex}



\subsection{Théorème des dépendances fonctionnelles}

\begin{Th}[Théorème des dépendances fonctionnelles]
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$.
\end{Th}


\begin{Ex}
La relation précédente est le produit de ses deux projections ${\cal
R}[\{\hbox{Nom}\vir\hbox{Age}\}]$ et ${\mathcal{R}}[\{\hbox{Nom}\vir\hbox{Groupe}\vir\hbox{Niveau}\}]$.
\end{Ex}



\subsection{Clés}

\begin{Def}[Clé]
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$.


($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'$).
\end{Def}

\begin{Rem}
Cette \og minimalité\fg{}   n'entraîne en aucune manière l'unicité de la clé pour une relation donnée. 
\end{Rem}

\begin{Th}
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). 
\end{Th}






\gsaut
\centerline{\x{Fin du Chapitre}}