Division relationnelle

Calcul relationnel

\(\div(S,T)\), opérateur de l’algèbre relationnelle qui sert à répondre aux questions du type :

• « Trouve-moi les \((X)\) des éléments \((X,Y)\) d’un ensemble \(S\) qui sont en relation avec tous éléments \((Y)\) d’un ensemble \(T\)« 

Exemple :

•  » donne-moi les bars \((id\_bar)\) qui servent \((id\_bar,id\_biere)\) toutes les bières \((id\_biere)\) existantes dans la base de données »

Algèbre relationnelle

La division relationnelle entre l’ensemble \(S(X,Y)\) contenant les groupes d’attributs \((X,Y)\) et l’ensemble \(T(Y)\) contenant le groupe d’attributs \((Y)\) peut s’exprimer à l’aide des opérateurs de base (\(\Pi,\setminus,\times\)) :

\(\div(S,T) = \setminus(\Pi_{(X)}(S),\Pi_{(X)}(\setminus(\times(\Pi_{(X)}(S),T),S)))\)

Qui se décompose de la façon suivante :

• \(R_1=\Pi_{(X)}(S)\) : éléments de l’ensemble \(S\) projetés sur \(X\)
• \(R_2=\times (R_1,T)\) : créer toutes les combinaisons (relations) possibles entre chaque élément (\(X\)) de \(S\) et tous les éléments (\(Y\)) de l’ensemble \(T\)
• \(R_3=\setminus(R_2,S)\) : récupérer les éléments \((X,Y)\) de l’ensemble précédent qui ne seraient pas dans l’ensemble \(S(X,Y)\)
• \(R_4=\Pi_{(X)}(R_3)\) : récupérer seulement les \(X\) de l’ensemble précédent qui ne seraient pas en relation avec ceux de l’ensemble \(S(X,Y)\)
• \(\div(S,T) =\setminus(R_1,R_4)\) : la différence entre les \(X\) de \(S\) et les \(X\) de l’ensemble précédent donnera, s’ils existent, les \(X\) de l’ensemble \(S(X,Y)\) liés à tous les \(Y\) de l’ensemble \(T(Y)\)

On peut également interpréter cette formulation en deux phases :

1. créer un ensemble qui contiendrait les éléments \(X\) associés aux éléments \(T(Y)\) qui ne seraient pas liés aux éléments \(X\) de l’ensemble \(S(X,Y)\) :

   • \(E_1=\Pi_{(X)}(\setminus(\times(\Pi_{(X)}(S),T),S))\)

2. récupérer les \(X\) de l’ensemble \(S\) et faire la différence avec les éléments \(X\) de l’ensemble précédent : on obtient les \(X\) de l’ensemble \(S\) qui sont liés à tous les éléments de l’ensemble \(T\) :

   • \(\div(S,T)=\setminus(\Pi_{(X)}(S),E_1)\)

Formulation SQL

La division relationnelle peut-être représentée de différentes manières en SQL.

• en l’exprimant à l’aide des opérateurs de base (\(\Pi,\times,\setminus\))
• en l’exprimant par des requêtes imbriquées (NOT EXISTS et/ou EXCEPT)
• en utilisant des groupements et fonctions d’agrégat (GROUP BY, HAVING,COUNT)

Mise en œuvre sur le modèle de données des bars qui servent des bières :

• Trouver les bars qui servent toutes les bières …

Mise en œuvre :

SELECT se.X
FROM S se
WHERE NOT EXISTS (
                  (SELECT Y FROM T)
                  EXCEPT
                  (SELECT Y FROM S si WHERE si.X=se.X)
                 );

SELECT  se.X
FROM S se
WHERE NOT EXISTS ( SELECT *
                   FROM T
                   WHERE NOT EXISTS (SELECT *
                                     FROM S si
                                     WHERE si.X=se.X AND T.Y=si.Y)
                  );

Mise en œuvre :

SELECT X
FROM S
GROUP BY X
HAVING COUNT(DISTINCT Y)=(
                          SELECT COUNT(DISTINCT Y)
                          FROM T
                         );

Mise en œuvre :

Exercice récapitulatif