Algèbre conjonctive

Par algèbre, nous entendons ici simplement un ensemble avec des opérations fermées sur cet ensemble. L'algèbre et ses opérations vont apporter une perspective très différente sur les requêtes des bases de données relationnelles. Nous considérons des opérations unaires et binaires sur des relations. L'application de ces opérations exige certaines contraintes de typage (c'est une algèbre à plusieurs sorts). Nous verrons pour chaque opération les contraintes qu'elle impose à ses arguments.

Dans un premier temps, nous considérons quatre opérations : sélection, projection, jointure et renommage. Nous appellerons algèbre conjonctive l'algèbre obtenue avec ces quatre opérations. Un résultat essentiel est l'équivalence entre le calcul conjonctif et l'algèbre conjonctive.

Commençons par un exemple qui nous permettra d'illustrer deux opérations unaires et une opération binaire :

  • la sélection notée σ qui permet d'éliminer des n-uplets (des lignes de relation),

  • la projection notée π qui permet d'éliminer des attributs (des colonnes de relation),

  • la jointure notée ⋈ qui permet de combiner les informations de plusieurs relations.

Ces opérations seront définies formellement plus loin.

AttentionBase de donnée utilisée

Dans tout ce chapitre, on s'appuie sur la base de données utilisée dans le chapitre sur le calcul relationnel