Ficha de revisão: Introduction à l'algèbre relationnelle

📋 Plan du Cours

1. Introduction à l'algèbre relationnelle
2. Principes fondamentaux
3. Opérations ensemblistes
4. Opérations relationnelles
5. Opérations spécifiques
6. Calcul relationnel
7. Optimisation des requêtes

📖 1. Introduction à l'algèbre relationnelle

🔑 Notions clés & Définitions

• Langages procéduraux : Ce sont des langages qui décrivent comment manipuler les données, en précisant la procédure ou l’algorithme à suivre pour obtenir le résultat souhaité. Ils indiquent "comment" réaliser une opération sur les données.

• Langages assertionnels : Aussi appelés langages déclaratifs, ils se concentrent sur ce que l’utilisateur souhaite obtenir, sans préciser la méthode pour y parvenir. Ils décrivent "quoi" manipuler ou rechercher.

• Algèbre relationnelle : Introduite par Codd en 1970, c’est un langage basé sur des opérations mathématiques appliquées aux relations (ensembles de n-uplets). Le résultat de chaque opération est une nouvelle relation, et ces opérations s’appliquent à l’ensemble des n-uplets des relations.

• Calcul relationnel : C’est un langage assertionnel qui permet de décrire la requête en précisant simplement "ce que" on veut, sans donner la procédure pour l’obtenir.

📝 Points essentiels

L’algèbre relationnelle, introduite par Codd en 1970, repose sur des données stockées sous forme de relations. Elle se distingue par deux types d’opérations : les opérations ensemblistes et les opérations relationnelles. Les opérations ensemblistes incluent l’union, l’intersection, la différence et le produit cartésien, qui manipulent des relations de même schéma. Le résultat de chaque opération est une nouvelle relation, ce qui permet de construire des requêtes complexes en combinant ces opérations. La généralisation à l’algèbre d’objets complexes étend ces principes à des structures plus sophistiquées.

💡 À retenir

L’algèbre relationnelle, introduite par Codd en 1970, constitue une approche formelle et mathématique pour manipuler des données relationnelles, en utilisant des opérations ensemblistes et relationnelles. Elle occupe une place centrale dans l’histoire des bases de données, en complément des langages assertionnels qui décrivent "ce que" l’on souhaite obtenir.

📖 2. Principes fondamentaux

🔑 Notions clés & Définitions

Relation
AUTEUR (date) : La relation est une structure de données composée d’un ensemble de n-uplets, où chaque n-uplet est une ligne ou un enregistrement. Elle représente un ensemble de données organisé selon un schéma défini par des attributs.

N-uplet
AUTEUR (date) : Un n-uplet est une séquence ordonnée de n éléments, correspondant à une ligne dans une relation. Chaque n-uplet appartient à une relation et partage le même schéma.

Opérations ensemblistes
AUTEUR (date) : Ce sont des opérations appliquées à des relations, qui produisent de nouvelles relations en combinant ou en comparant des ensembles de n-uplets. Elles incluent notamment l’union, l’intersection, la différence et le produit cartésien.

Opérations relationnelles
AUTEUR (date) : Ce sont des opérations spécifiques appliquées aux relations, permettant de manipuler, filtrer, ou transformer ces relations pour obtenir de nouvelles relations. Elles incluent la projection, la sélection, le renommage, la division, et la θ-jointure.

📝 Points essentiels

Les données sont stockées sous forme de relations composées de n-uplets. Le résultat de toute opération est une nouvelle relation, ce qui garantit la cohérence et la modularité des manipulations. Les opérations s’appliquent à l’ensemble des n-uplets d’une relation, c’est-à-dire qu’elles opèrent sur l’intégralité de l’ensemble de données, en respectant le schéma de la relation. Par exemple, l’opération d’intersection entre deux relations R et S donne une nouvelle relation contenant uniquement les n-uplets présents dans R et S. De même, le produit cartésien combine tous les n-uplets de deux relations pour former une relation plus large, en concaténant leurs attributs respectifs.

💡 À retenir

Les données relationnelles sont structurées en relations de n-uplets, et toutes les opérations fondamentales produisent des nouvelles relations en manipulant ces ensembles de n-uplets, permettant une gestion cohérente et systématique des données.

📖 3. Opérations ensemblistes

🔑 Notions clés & Définitions

Union
L'union de deux relations R et S, notée R ∪ S, consiste à rassembler tous les n-uplets appartenant à R ou à S, en évitant les doublons. Elle ne s'applique qu'à des relations ayant le même schéma, c’est-à-dire le même ensemble d’attributs.

Intersection
L'intersection de R et S, notée R ∩ S, correspond à l’ensemble des n-uplets présents à la fois dans R et dans S. Cette opération nécessite que R et S aient le même schéma.

Différence
La différence R \ S désigne l’ensemble des n-uplets qui appartiennent à R mais pas à S. Elle s'applique uniquement à des relations partageant le même schéma.

Produit cartésien
Le produit cartésien de R et S, noté R × S, concatène chaque n-uplet de R avec chaque n-uplet de S, formant ainsi des n-uplets plus longs. Il ne requiert pas que R et S aient le même schéma, mais le résultat est une relation avec un schéma combiné.

📝 Points essentiels

Les opérations ensemblistes (union, intersection, différence) s'appliquent uniquement à des relations ayant le même schéma, c’est-à-dire le même ensemble d’attributs. Cela garantit que chaque n-uplet comparé ou combiné possède une correspondance cohérente.

Le produit cartésien consiste à concaténer tous les n-uplets de deux relations, indépendamment de leur schéma initial. Il produit une nouvelle relation dont le schéma est la concaténation des schémas originaux.

Les opérations ensemblistes manipulent des ensembles de n-uplets, ce qui implique que chaque relation est vue comme un ensemble d’éléments (n-uplets) sans ordre ni duplication.

💡 À retenir

Maîtriser les opérations classiques d'ensembles adaptées aux relations permet de manipuler efficacement des ensembles de n-uplets tout en respectant leurs contraintes de schéma. La cohérence des schémas est essentielle pour l’application des opérations ensemblistes.

📖 4. Opérations relationnelles

🔑 Notions clés & Définitions

Projection : La projection est une opération qui consiste à restreindre les colonnes d'une relation en ne conservant qu'un sous-ensemble d'attributs. Elle permet d'obtenir un ensemble de n-uplets contenant uniquement les attributs sélectionnés, en supprimant les autres.

Sélection : La sélection est une opération qui restreint les lignes d'une relation selon une condition spécifique. Elle filtre les n-uplets pour ne conserver que ceux qui vérifient cette condition.

Renommage : Le renommage permet de modifier les noms d'attributs d'une relation. Il est utilisé pour éviter les ambiguïtés ou pour rendre les noms plus explicites dans des opérations combinées.

Division : La division extrait des n-uplets d'une relation qui répondent à une condition d'inclusion. Elle consiste à trouver tous les n-uplets d'une relation qui, lorsqu'ils sont combinés avec un autre ensemble, couvrent l'ensemble complet de cet autre.

θ-jointure : La θ-jointure combine deux relations selon une condition θ. Elle crée une nouvelle relation en associant les n-uplets des deux relations qui vérifient la condition θ, permettant de relier des données selon des critères précis.

📝 Points essentiels

• La projection restreint les colonnes d'une relation en ne conservant qu'un sous-ensemble d'attributs, facilitant la réduction de la dimension des données.
• La sélection restreint les lignes selon une condition, permettant d'isoler les n-uplets pertinents pour une requête ou une analyse.
• Le renommage permet de modifier les noms d'attributs, ce qui est utile pour clarifier ou différencier des relations lors de jointures ou opérations complexes.
• La division extrait des n-uplets répondant à une condition d'inclusion, en identifiant ceux qui, combinés avec un autre ensemble, couvrent entièrement cet ensemble.
• La θ-jointure combine deux relations selon une condition θ, en associant les n-uplets qui la vérifient, ce qui permet de relier des données en fonction de critères précis.

💡 À retenir

Les opérations de projection, sélection, renommage, division et θ-jointure sont essentielles pour manipuler efficacement les données relationnelles, en permettant de sélectionner, filtrer, modifier ou combiner les données selon des critères précis.

📖 5. Opérations spécifiques

🔑 Notions clés & Définitions

Jointure naturelle : La jointure naturelle concatène les n-uplets de deux relations en fusionnant ceux qui ont des valeurs identiques sur leurs attributs communs, sans répétition de ces attributs. Elle ne conserve que les attributs communs une seule fois.

• Auteur : voir section 2

Jointure externe gauche : La jointure externe gauche conserve tous les n-uplets de la relation de gauche, même s'il n'existe pas de correspondance en relation de droite. En cas d'absence de correspondance, les attributs de la relation de droite sont complétés par des valeurs indéterminées (_).
Auteur : GABRIELA MONTOYA (2025-2026) : jointure externe gauche.

Jointure externe généralisée : La jointure externe généralisée combine la jointure interne et la jointure externe. Elle inclut tous les n-uplets de deux relations, en complétant par des valeurs indéterminées lorsque aucune correspondance n’est trouvée, et en conservant tous les n-uplets même sans correspondance.
Auteur : GABRIELA MONTOYA (2025-2026) : jointure externe généralisée.

Jointure externe naturelle gauche : Variante de la jointure externe gauche utilisant la jointure naturelle. Elle conserve tous les n-uplets de la relation de gauche, en complétant avec des valeurs indéterminées pour la relation de droite lorsque aucune correspondance n’est présente, en utilisant la logique de la jointure naturelle.
Auteur : GABRIELA MONTOYA (2025-2026) : jointure externe naturelle gauche.

📝 Points essentiels

• La jointure naturelle concatène les n-uplets sans répétition sur les attributs communs, en fusionnant ceux qui ont des valeurs identiques sur ces attributs. Elle ne duplique pas les attributs communs.
• Les jointures externes (gauche, droite, généralisée) conservent tous les n-uplets de la relation du côté spécifié, même en l’absence de correspondance. En cas de non-correspondance, elles complètent avec des valeurs indéterminées (_).
• La jointure externe gauche conserve tous les n-uplets de la relation de gauche, en complétant avec des valeurs indéterminées pour la relation de droite si aucune correspondance n’est trouvée.
• La jointure externe généralisée combine la jointure interne et la jointure externe, en conservant tous les n-uplets de deux relations, même sans correspondance, en complétant par des valeurs indéterminées.
• La jointure externe naturelle gauche est une variante qui utilise la jointure naturelle pour conserver tous les n-uplets de la relation de gauche, en complétant avec des valeurs indéterminées pour la relation de droite lorsque nécessaire.

💡 À retenir

Les différentes jointures externes permettent de gérer les correspondances partielles entre relations en conservant tous les n-uplets d’un côté, tout en complétant par des valeurs indéterminées en l’absence de correspondance. La jointure externe généralisée offre une flexibilité combinée, intégrant à la fois la jointure interne et externe.

📖 6. Calcul relationnel

🔑 Notions clés & Définitions

Prédicat : Un prédicat est une relation ou une propriété qui peut être vraie ou fausse pour des objets donnés. En logique du premier ordre, il sert à exprimer des conditions ou des relations entre éléments.

Atome : Une formule atomique est une expression simple composée d’un prédicat appliqué à un ou plusieurs termes (constantes ou variables). Elle constitue la plus petite unité d’une formule logique.

Connecteur logique : Un connecteur logique relie des formules ou des prédicats pour former des expressions plus complexes. Il inclut notamment la conjonction (∧), la disjonction (∨), la négation (¬), etc. (bien que non explicitement mentionnés dans le contenu source, ils sont implicites dans la composition des formules).

Quantificateur : Un quantificateur indique l’étendue de validité d’une formule. Les principaux sont le quantificateur existentiel (∃) et le quantificateur universel (∀), permettant d’affirmer qu’une propriété est vraie pour certains ou tous les éléments d’un domaine.

Formule atomique : C’est une expression de base composée d’un prédicat appliqué à des termes, sans connecteur ni quantificateur. Exemple : Couleur(voiture).

Formule libre : Une formule construite à partir de formules atomiques, de connecteurs logiques et de quantificateurs, sans liaison de variables (libre ou liée). Elle sert à exprimer des conditions complexes sur les données.

📝 Points essentiels

Le calcul relationnel basé sur la logique du premier ordre utilise des expressions formelles pour décrire des conditions sur les données. Ces expressions combinent des prédicats, des constantes, des variables, des connecteurs logiques et des quantificateurs.

Les prédicats représentent les relations ou propriétés sur les données, tandis que les formules atomiques en sont les éléments de base. La formule atomique est une expression simple, par exemple, un prédicat appliqué à des termes.

Les formules plus complexes, appelées formules libres, sont construites en combinant ces formules atomiques à l’aide de connecteurs logiques et de quantificateurs, permettant de décrire des conditions précises et élaborées.

Le calcul relationnel permet d’écrire des requêtes sous une forme déclarative, où l’on décrit ce que l’on veut obtenir plutôt que comment l’obtenir, en utilisant ces expressions formelles.

Il existe une équivalence de puissance d’expression entre le calcul relationnel et l’algèbre relationnelle, ce qui signifie que toute requête formulée dans l’un peut être traduite dans l’autre.

L’utilisation de constantes, variables, connecteurs et quantificateurs dans ces expressions permet de formuler des requêtes précises, notamment en exprimant des conditions sur des ensembles d’objets ou des relations.

💡 À retenir

Le calcul relationnel, basé sur la logique du premier ordre, permet d’écrire des requêtes déclaratives en utilisant des formules atomiques et complexes, combinant prédicats, variables, connecteurs et quantificateurs pour décrire précisément les conditions sur les données.

📖 7. Optimisation des requêtes

🔑 Notions clés & Définitions

Règles de transformation : Ensemble de règles formelles permettant de réécrire une expression relationnelle en une autre équivalente, dans le but d’améliorer son efficacité ou sa simplicité. (source : contenu source)

Heuristique d’optimisation : Méthode ou stratégie empirique guidant la réorganisation des opérations dans une requête pour réduire sa complexité ou son coût d’exécution, en appliquant notamment des règles de transformation. (source : contenu source)

Commutativité : Propriété selon laquelle l’ordre de certaines opérations, comme la projection avec les unions ou les jointures, peut être échangé sans changer le résultat. (source : contenu source)

Associativité : Propriété permettant de regrouper différemment des opérations successives (ex : jointures, projections) sans modifier le résultat, facilitant leur réorganisation. (source : contenu source)

Descente des sélections et projections : Technique d’optimisation consistant à appliquer précocement ces opérations, dès que possible dans la requête, afin de réduire la taille des relations intermédiaires et améliorer l’efficacité globale. (source : contenu source)

📝 Points essentiels

L’ordre des opérations dans une requête influence directement son efficacité. En appliquant des règles formelles de transformation, il est possible de réécrire une expression pour la rendre plus performante. Notamment, les sélections et projections doivent être effectuées dès que possible, idéalement en amont, pour réduire la taille des relations intermédiaires et limiter le coût des opérations suivantes. La propriété de commutativité permet d’échanger l’ordre de certaines opérations, comme la projection avec les unions ou les jointures, sans changer le résultat. De même, l’associativité facilite la réorganisation des opérations successives, permettant de regrouper ou de dissocier des opérations pour optimiser leur exécution. L’heuristique d’optimisation recommande de grouper et de descendre ces opérations dès la phase initiale de la requête, en particulier en dégroupant les sélections et en les appliquant aux relations de base, puis en descendant les projections pour limiter la taille des relations intermédiaires.

💡 À retenir

L’optimisation des requêtes relationnelles repose sur l’application de règles formelles et d’heuristiques permettant de réorganiser les opérations. En appliquant précocement les sélections et projections, et en utilisant la commutativité et l’associativité, on peut significativement améliorer les performances en réduisant la taille des relations intermédiaires et en simplifiant l’exécution.

📊 Tableaux de Synthèse

Opération	Type	Description	Condition d'application	Auteur / Référence
Union	Ensembliste	Rassemble tous les n-uplets de R et S, sans doublons	Même schéma (même attributs)	—
Intersection	Ensembliste	N-uplets commun à R et S	Même schéma	—
Différence	Ensembliste	N-uplets dans R mais pas dans S	Même schéma	—
Produit cartésien	Ensembliste	Concatène tous les n-uplets de R avec ceux de S	—	—
Projection	Relationnelle	Limite les attributs conservés dans une relation	—	—
Sélection	Relationnelle	Filtre les n-uplets selon une condition	Condition sur attributs	—
Renommage	Relationnelle	Modifie les noms d’attributs	—	—
Division	Relationnelle	Extrait des n-uplets qui, combinés avec un autre ensemble, couvrent un ensemble donné	—	—
θ-jointure	Relationnelle	Combine deux relations selon une condition θ	Condition θ sur attributs	—

⚠️ Pièges & Confusions Fréquentes

1. Confondre union et union avec des relations de schémas différents.
2. Appliquer la différence ou l’intersection sur des relations ayant des schémas incompatibles.
3. Oublier que le produit cartésien ne nécessite pas de même schéma, mais produit un schéma combiné.
4. Confondre projection (limitation des attributs) avec la suppression de lignes.
5. Mal utiliser la sélection en ne précisant pas correctement la condition.
6. Oublier que le renommage est nécessaire pour éviter ambiguïtés lors de jointures.
7. Confondre division avec une opération de filtrage simple.
8. Négliger la différence entre opérations ensemblistes et opérations relationnelles.

✅ Checklist Examen

1. Connaître la définition d’une relation selon l’auteur (relation = ensemble de n-uplets).
2. Maîtriser la différence entre opérations ensemblistes (union, intersection, différence, produit cartésien).
3. Savoir appliquer la règle d’unicité et de compatibilité des schémas pour les opérations ensemblistes.
4. Connaître la définition et l’usage de la projection pour limiter les attributs d’une relation.
5. Maîtriser la sélection pour filtrer les n-uplets selon une condition spécifique.
6. Comprendre le rôle du renommage dans la gestion des noms d’attributs.
7. Savoir réaliser une opération de division et ses applications.
8. Comprendre le concept de θ-jointure et ses conditions d’application.
9. Identifier les différences entre opérations relationnelles et opérations ensemblistes.
10. Connaître l’origine et l’introduction de l’algèbre relationnelle par Codd en 1970.
11. Assimiler que toutes les opérations produisent des relations, garantissant la cohérence du modèle.
12. Vérifier la maîtrise du vocabulaire spécifique : relation, n-uplet, schéma, opération ensembliste, opération relationnelle.