Workshop - Algèbre et arbres relationnels

1. σ_{prix > 40}(Produit)

   → La sélection filtre les lignes : seules celles vérifiant la condition sont conservées.
   → Le schéma (colonnes) reste identique.

2. Résultat :
| idProduit | nom     | prix |
|-----------|---------|------|
| 1         | Clavier | 45   |
| 3         | Écran   | 220  |

   → La Souris (30 €) est exclue car 30 ≤ 40.

3. σ_{prix ≤ 100}(Produit)

   Résultat :
| idProduit | nom     | prix |
|-----------|---------|------|
| 1         | Clavier | 45   |
| 2         | Souris  | 30   |

   → L'Écran (220 €) est exclu car 220 > 100.

1. π_{nom, prix}(Produit)

   Résultat :
| nom     | prix |
|---------|------|
| Clavier | 45   |
| Souris  | 30   |
| Écran   | 220  |

   → On n'a plus la colonne idProduit. Les trois lignes sont conservées.

2. Oui, si plusieurs lignes ont exactement les mêmes valeurs sur les colonnes projetées,
   elles sont fusionnées en une seule (le modèle relationnel ne conserve pas les doublons).

   Exemple : si deux produits avaient nom = "Souris" et prix = 30,
   π_{nom, prix} n'en afficherait qu'une.

3. π_{idProduit}(Produit)

   Résultat :
| idProduit |
|-----------|
| 1         |
| 2         |
| 3         |

1. Client ∪ Prospect

2. Résultat :
| nom     |
|---------|
| Alice   |
| Bernard |
| Camille |

   → Bernard apparaissait dans les deux relations mais n'est affiché qu'une fois :
     l'union supprime automatiquement les doublons.

3. L'union est une opération d'ensemble : elle n'est possible que si les deux relations
   ont le même nombre de colonnes, dans le même ordre, avec des types compatibles
   (on dit qu'elles ont le même "schéma").
   Si ce n'est pas le cas, l'opération est invalide et le SGBD retourne une erreur.

1. Client − Prospect

2. Résultat :
| nom   |
|-------|
| Alice |

   → Alice est cliente mais pas prospecte. Bernard est les deux, il est donc exclu.

3. Non, la différence n'est PAS symétrique :

   Client − Prospect = { Alice }       → clients qui ne sont pas prospects
   Prospect − Client = { Camille }     → prospects qui ne sont pas clients

   → L'ordre des opérandes change complètement le résultat.
     C'est une différence fondamentale avec l'union, qui elle est symétrique (A ∪ B = B ∪ A).

1. Auteurs × Livres

2. 2 × 3 = 6 lignes.
   Toutes les combinaisons possibles sont générées :
   (Auteur1, Livre1), (Auteur1, Livre2), (Auteur1, Livre3),
   (Auteur2, Livre1), (Auteur2, Livre2), (Auteur2, Livre3)

3. Le produit cartésien seul n'a pas de signification métier : il associe tout à tout,
   y compris des paires qui n'ont aucun lien réel.

   En appliquant une sélection dessus (ex : σ_{idAuteur = auteur_du_livre}),
   on ne garde que les paires ayant une vraie correspondance.
   C'est exactement ce que fait une jointure : produit cartésien + sélection.

   Jointure = σ_{condition}(R1 × R2)

1. Employe ⨝_{Employe.idDept = Departement.idDept} Departement

   → La jointure associe chaque ligne d'Employe à la ligne de Departement
     dont le idDept correspond.

2. Une union exige que les deux relations aient le même schéma (mêmes colonnes).
   Employe et Departement n'ont pas les mêmes colonnes : l'union est impossible.
   La jointure, elle, fusionne des relations de schémas différents sur un champ commun.

3. π_{nom, nomDept}(Employe ⨝_{Employe.idDept = Departement.idDept} Departement)

   → On applique la projection après la jointure, car nomDept n'existe que
     dans Departement et n'est accessible qu'après la jointure.

1. π_{nom}(σ_{nomDept = "RH"}(Employe ⨝_{Employe.idDept = Departement.idDept} Departement))

   Ordre de lecture (intérieur → extérieur) :
   a) Jointure entre Employe et Departement
   b) Sélection des lignes où nomDept = "RH"
   c) Projection du champ "nom" uniquement

2. Le champ "nomDept" n'existe que dans Departement.
   Il n'est pas présent dans Employe. Impossible de filtrer dessus
   tant qu'on n'a pas fait la jointure pour enrichir chaque ligne avec ce champ.

3. On peut inverser partiellement : on peut filtrer Departement AVANT la jointure.
   σ_{nomDept = "RH"}(Departement) renvoie uniquement la ligne du département RH.
   On peut ensuite faire la jointure sur ce résultat réduit :

   π_{nom}(Employe ⨝ σ_{nomDept = "RH"}(Departement))

   → C'est même plus efficace : on filtre d'abord une petite table,
     puis on joint sur un ensemble réduit. C'est le principe de l'optimisation par poussée de sélection.

1. EmployeCompetence ÷ Competence

2. La division exprime une quantification universelle : "pour tous les éléments de B,
   il existe un lien dans A". Ni la sélection, ni la jointure ne permettent
   d'exprimer cette contrainte de manière directe.

   En SQL, on traduit souvent la division par une double négation :
   "les employés pour lesquels il n'existe pas de compétence qu'ils n'ont pas."

3. Si Competence = {A, B, C} :

   EmployeCompetence :
   | employe | competence |
   |---------|------------|
   | Alice   | A          |
   | Alice   | B          |
   | Alice   | C          |   → Alice a TOUT → elle est dans le résultat
   | Paul    | A          |
   | Paul    | B          |   → Paul n'a pas C → il est exclu

   EmployeCompetence ÷ Competence = { Alice }

1. Étape 1 : trouver les idEtudiant inscrits à tous les cours
   π_{idEtudiant}(Inscription) ÷ π_{idCours}(Cours)

   Étape 2 : récupérer leur nom via une jointure
   π_{nom}(Etudiant ⨝ (π_{idEtudiant}(Inscription) ÷ π_{idCours}(Cours)))

   → On projette d'abord les colonnes utiles avant la division,
     pour s'assurer que les schémas sont compatibles (même colonne de chaque côté).

2. La division est indispensable ici.
   Une jointure seule donnerait tous les étudiants qui ont AU MOINS une inscription,
   pas ceux qui ont TOUTES les inscriptions. La division filtre les individus
   qui couvrent l'intégralité de l'ensemble diviseur.

3. On peut ajouter une relation intermédiaire :
   Enseignement(idCours, idProf)
   Professeur(idProf, nom, prenom)

   → Cela permettrait d'associer chaque cours à un professeur,
     et d'interroger (ex : "tous les cours enseignés par Dupont") via une jointure.

1. Lecture de bas en haut :
   a) Client → on part de la relation Client complète
   b) σ_{ville = 'Paris'} → on ne garde que les clients parisiens
   c) π_{nom, prenom} → on ne conserve que les colonnes nom et prenom

2. Si on inverse (projection avant sélection) :
   σ_{ville = 'Paris'}(π_{nom, prenom}(Client))

   → Après la projection, la colonne "ville" a disparu.
   → La sélection σ_{ville = 'Paris'} ne peut plus s'appliquer : erreur.

3. Conclusion : l'ordre projection/sélection n'est pas interchangeable librement.
   On doit toujours s'assurer que les colonnes nécessaires aux filtres
   sont encore présentes au moment où on filtre.

   En revanche, si on projette une colonne inutile juste avant une sélection
   qui n'en a pas besoin, on peut le faire plus tôt pour alléger les données.

1. π_{nom, prenom}(Client ⨝_{Client.idClient = Commande.idClient} Commande)

2. Arbre :

        π_{nom, prenom}
               |
   ⨝_{Client.idClient = Commande.idClient}
          /           \
       Client       Commande

   → Deux feuilles (Client, Commande) reliées par une jointure,
     puis on projette les colonnes souhaitées.

3. L'opération centrale est la jointure.
   Sans elle, on ne peut pas "croiser" les informations des deux tables :
   Commande ne contient pas le nom du client, et Client ne contient pas les commandes.
   La jointure sur idClient permet de fusionner ces informations.

1. π_{nom}(Etudiant ⨝ Inscription ⨝ σ_{nomCours = "Maths"}(Cours))

2. Arbre non optimisé (jointures d'abord, filtre ensuite) :

          π_{nom}
             |
     σ_{nomCours = "Maths"}
             |
   ⨝_{Inscription.idCours = Cours.idCours}
             /                \
⨝_{Etudiant.id = Inscription.idEtudiant}   Cours
         /          \
    Etudiant    Inscription

3. Arbre optimisé (filtre appliqué le plus tôt possible) :

          π_{nom}
             |
   ⨝_{Etudiant.id = Inscription.idEtudiant}
         /                      \
    Etudiant      ⨝_{Inscription.idCours = Cours.idCours}
                         /                   \
                   Inscription        σ_{nomCours = "Maths"}
                                               |
                                             Cours

   Pourquoi c'est meilleur ?
   → On filtre d'abord Cours pour ne garder que la ligne "Maths" (1 ligne au lieu de N).
   → La jointure suivante porte sur un ensemble réduit : moins de données à traiter.
   → Résultat identique, mais performance améliorée.

1. Feuilles (relations de départ) : Etudiant, Classe
   Nœuds internes (opérations) : jointure, sélection (σ), projection (π)
   Racine (résultat final) : π_{nom}

2. Modifier la projection pour inclure prenom :
   π_{nom, prenom}(...)

   → Aucune autre modification nécessaire, car prenom est déjà présent
     dans Etudiant, qui est déjà dans l'arbre.

3. Remplacer la sélection :
   σ_{nomClasse = '2A'} → σ_{prenom = 'Marie'} (par exemple)

   → Mais attention : prenom est dans Etudiant, pas dans Classe.
     La sélection doit donc se faire APRÈS la jointure (pour avoir accès aux deux tables),
     ou directement sur Etudiant AVANT la jointure (optimisation possible ici).

   Version optimisée :
   π_{nom}(σ_{prenom = 'Marie'}(Etudiant) ⨝ Classe)

1. Opérations nécessaires (ordre logique) :
   a) Filtrer les clients habitant Lyon → σ_{ville = "Lyon"}(Client)
   b) Filtrer les commandes > 1000 → σ_{montant > 1000}(Commande)
   c) Joindre les deux résultats sur idClient → ⨝
   d) Projeter uniquement le nom → π_{nom}

2. Expression complète (optimisée) :
   π_{nom}(σ_{ville = "Lyon"}(Client) ⨝_{Client.id = Commande.idClient} σ_{montant > 1000}(Commande))

3. Arbre optimisé :

              π_{nom}
                 |
       ⨝ (Client.id = Commande.idClient)
           /                        \
σ_{ville = "Lyon"}          σ_{montant > 1000}
        |                               |
     Client                         Commande

   → Les deux sélections sont appliquées en premier, directement sur les feuilles.
   → La jointure porte sur des ensembles déjà réduits.
   → La projection est la dernière opération : on ne garde que "nom" dans le résultat final.