Des langages de définition et de manipulation sont associés au modèle relationnel. De façon formelle on trouve deux classes de langages. Les langages algébriques et les langages prédicatifs. Ces langages sont strictement équivalents sur le plan de la puissance d'expression (n'importe quelle requête qui peut s'exprimer dans un de ces langages peut s'exprimer dans l'autre). Sur un plan industriel, les langages algébriques ont dérivé SQL (Structured Query Language, défini par IBM et qui s'impose comme la norme supportée par tout SGBD du commerce) et les langages prédicatifs QBE (Query By Example).
L'algèbre relationnelle se compose d'un ensemble d'opérateurs opérant sur des relations et produisant de nouvelles relations. Il est donc possible de construire de nouvelles informations à partir des relations de départ et d'une composition séquentielle d'opérateurs.
De nombreux opérateurs relationnels ont été proposés, on peut cependant présenter ici les plus courants. On peut classifier les opérateurs relationnels en trois catégories :
La présentation des opérateurs est illustrée par un exemple de gestion d'une base d'invitations. Cette base de données décrit les personnes invitées et les plats qui ont été servis. Elle est composée de trois relations :
N.B : les attributs "personne" et "invité" ont même domaine et les clés sont en soulignéees.
L'affectation permet de sauvegarder le résultat d'une expression de recherche, ou bien de renommer une relation et ses attributs.
Exemple : Q1
La sélection prend en entrée une relation R définie sur un schéma SR et produit en sortie une nouvelle relation de même schéma SR ayant comme nuplets ceux de R satisfaisant à l'expression de sélection. Une expresion de sélection est une condition booléenne construite à partir des connecteurs logiques et, ou, non et de conditions simples (attribut de R - opérateur de comparaison - constante ou attribut de R - opérateur de comparaison - attribut de R)
Exemples : Q1, Q2
La projection prend en entrée une relation R définie sur un schéma SR et produit en sortie une nouvelle relation de schéma A1, ..., An (schéma inclus dans SR) ayant comme nuplets ceux de R restreints au sous-schéma A1, ..., An. Il faut noter que la cardinalité de la nouvelle relation est inférieure ou égale à celle de R, puisque des doublons ont pu être produits par la projection et sont donc supprimés (une relation est toujours un ensemble).
Exemples : Q1, Q2, Q3, Q5, Q6
Les trois opérateurs ensemblistes opèrent sur des relations R et S de même schéma SRS.
produit une nouvelle relation de schéma SRS ayant les nuplets de R et ceux de S (les doublons sont supprimés).
produit une nouvelle relation de schéma SRS ayant les nuplets présents dans R et dans S.
produit une nouvelle relation de schéma SRS ayant les nuplets de R qui ne sont pas dans S. Attention, la différence n'est pas commutative.
Exemple : Q5
Soient R et S deux relations définies sur les schémas SR et SS.
Il faut que les schémas SR et SS aient une intersection SRS non vide. La relation produite a un schéma qui est l'union des schémas SR et SS et dont les nuplets sont la concaténation des nuplets de R avec ceux de S s'ils ont même valeur pour tous les attributs communs (c'est à dire ceux de SRS). On parle également de jointure naturelle ou équi-jointure.
Exemple : Q2
Il faut que les deux schémas SR et SS soient disjoints. La relation produite a un schéma qui est l'union des schémas SR et SS et dont les nuplets sont la concaténation des nuplets de R avec ceux de S. Attention le nombre d'éléments du produit cartésien est le produit des cardinalités des relations R et S!
Exemple : Q4
Cette opération non canonique est équivalente à un produit cartésien suivi d'une opération de sélection.
R * (condition) S = SELECTION condition (R X S)
Exemple : Q3
R est définie sur un schéma SR composé des ensembles d'attributs X,Y (SR = X UNION Y) et S est définie sur un schéma SS composé de l'ensemble d'attributs Y (SS = Y). La relation produite est définie sur le schéma Sres (Sres = SR - SS = Y) et comprend tous les nuplets dont la concaténation avec tous les nuplets de S appartient à R (résultat X S inclus-ou-egal R).
La division peut se définir à l'aide du produit cartésien, de la différence et de la projection :
R(A1, .., Ap, Ap+1, ..., An)
S(Ap+1, ..., An)
R / S = R1 - R2 avec
R1 = PROJECTION A1, ..., Ap (R)
R2 = PROJECTION A1, ..., Ap ((R1 X S) - R)
Exemple : Q6
Un des grands intérets de l'algebre relationnelle est l'ensemble de propriétés des opérateurs ce qui permet l'optimisation des requetes.
Soient R(X) et S(Y) deux relations de schémas distincts, T(V,W), U(W,Z) deux relations ayant un ensemble d'attributs communs, Q1(X), Q2(X) deux relations de même schéma et P(W).
| sélection | SELECTION condition (R) | select *from R
where condition |
| projection | PROJECTION A1, ..., An (R) | select distinct A1, ..., An from R |
| opérateurs ensemblistes | Q1 UNION Q2, Q1 | select * from Q1 |
| jointure | T * U | select V, W, Z from T, U where T.W=U.W (en réalité égalité sur tous les attributs communs) |
| produit cartésien | R X S | select R.*, S.* |
| théta-jointure | R* (condition) S | select X, Y from R, S where condition |
| division | T / P avec P partie de T | select V
from T group by V having count(distinct W) >= (select count(distinct W) from P) |
Deux approches sont possibles pour établir un lien entre la logique du premier ordre et les bases de données :
Les faits élémentaires (données) et les propriétés générales (schéma ainsi que les règles d'intégrité et d'inférences) sont représentés par des axiomes d'une théorie du premier ordre. Répondre à une question revient donc à démontrer un théorême dans cette théorie.
Avantages : une question est résolue en dehors de toute interprétation et on peut utiliser des règles d'intégrité ou d'inférences (qui permettent de déduire des informations non stockées).
Inconvénients : problème de performances (il faut intégrer un démonstrateur de théorêmes) et représentation de l'information négative. La plupart du temps on utilise l'hypothèse du monde fermé ("Closed World Assumption") avec une méta-règle de négation par l'échec ("negation as failure"). Toute information manquante est considérée comme fausse et une information qu'on ne peut dériver est également considérée comme fausse.
Les propriétés générales (schéma seulement) sont considérées comme les axiomes d'une théorie du premier ordre, alors que les faits élémentaires (données) sont perçus comme une interprétation de cette théorie. Si cette interprétation vérifie tous les axiomes, elle constitue un modèle. Répondre à une question revient à chercher la valeur de vérité d'une formule relativement à l'interprétation. On distingue alors entre question fermée (sans variable libre) pour laquelle la réponse est vrai ou faux, et question ouverte (avec variable libre) pour laquelle la réponse sont les valeurs de l'interprétation pour lesquelles la question est vraie.
Avantages : on retrouve la théorie relationnelle classique
Inconvénients : pas de puissance supplémentaire
Nous présentons dans la suite cette deuxième approche, les BD déductives étant étudiées dans le cadre du cours de 3ème année. On rencontre deux classes de langages prédicatifs, ceux à variable nuplet (le domaine d'interprétation d'une variable est le nuplet) et ceux à variable domaine (le domaine d'interprétation d'une variable est le domaine).
Une expression générale du calcul relationnel à variable nuplet est de la forme :
avec ti (de 1 à n+m) variables nuplets non nécessairement distinctes deux à deux, Ai sont des attributs de relations associées aux ti et COND est une formule du calcul relationnel à variable nuplet. L'expression de la forme ti[Aj] exprime la valeur du nuplet ti suivant l'attribut de nom Aj (terme de projection).{t1[A1], t2[A2], ..., tn[An] / COND(t1, t2, ..., tn, tn+1, tn+2, ..., tn+m)}
Une formule est construite à partir de prédicats atomiques (atomes) qui sont d'une des formes suivantes :
NB : une variable est dite libre si elle n'est pas quantifiée dans sa portée, liée sinon.
Une expression générale du calcul relationnel à variable domaine est de la forme :
{x1, x2, ..., xn / COND(x1, x2, ..., xn, xn+1, xn+2, ..., xn+m)}
avec xi variables domaines (non nécessairement distinctes) d'attributs et COND est une formule du calcul relationnel à variable domaine.
Une formule est construite à partir d'atomes. Un atome peut être d'une des formes suivantes :
Une formule est construite à partir des mêmes règles que celles définies pour le calcul relationnel à variable nuplet.