Début des années 70, le modèle relationnel fait son apparition [Codd 70]. La recherche se passionne : impossible de nier les progrès apportés concernant la représentation et la manipulation des données par les systèmes. Dix ans passent, les spécialistes déchantent : ce top-model engendre en définitive des systèmes commerciaux bien moins performants que leurs concurrents fondés sur les modèles réseau ou hiérarchique. Deux ans plus tard et voilà que les produits relationnels peuvent prétendre relayer les "vieux" systèmes. Leurs apports sont fondamentaux : les nouvelles fonctionnalités permettent un confort d'utilisation sans précédent. Les systèmes commerciaux s'emparent des concepts de ce nouveau modèle. Celui-ci, désormais, s'impose.

Mais quels sont ces concepts, leurs avantages, leurs limites ? Certains sont déjà bien répandus. Ce sont les notions de base que nous détaillerons dans la première partie : domaine, relation, attribut ; puis la manipulation ensembliste des relations par les opérateurs de l'algèbre relationnelle (deuxième partie) sur lesquels sont construits des langages non procéduraux comme SQL (chapitre 4) ; l'importante base théorique du modèle enfin fournit des méthodes pour la conception des bases de données (chapitre 5). D'autres concepts sont toutefois moins connus qui constituent pourtant un progrès essentiel : les vues relationnelles permettent à chaque utilisateur de personnaliser sa vision des données et les contraintes d'intégrité complètent la description de l'information (chapitre 6). Les chapitres suivants présentent chacun des ressorts qui font du modèle relationnel la référence obligée en matière de gestion de bases de données.

La relation des nageurs :

La relation des baignades :

La notion de domaine

Comme on le voit, si un domaine représente l'ensemble des valeurs possibles d'une manifestation du monde réel (exemples : les cheveux sont blonds, noirs, bruns ou blancs ; les ages sont compris entre 0 et 130, etc.), le monde réel "possible" est constitué par le produit cartésien des domaines et le monde réel "réel" est forcément un sous ensemble du produit cartésien.

La notion de relation

La notion d'attribut

Dans un système relationnel, les informations ne sont pas forcément repérées individuellement ; on sait appliquer le même traitement à un ensemble d'enregistrements caractérisés, non par la liste des identifiants individuels, mais par le critère que vérifie chacun des enregistrements qui composent l'ensemble. On dit que la manipulation est ensembliste.

En particulier, pour rechercher des tuples, il suffit de préciser un critère de sélection ; le système déterminera l'ensemble des tuples satisfaisant ce critère et rendra un résultat. Les tuples de ce résultat, extraits de relations de la base, constituent eux-même une relation qu'il sera ainsi aisé de conserver, si nécessaire, pour le plus grand confort de l'utilisateur.

Par exemple, pour connaître les dates et durées des bains pris par Paul Coule ainsi que les noms des plages, on obtient le résultat suivant, qui est une relation RESULTAT à trois attributs NOMP, DATE, DUREE :

Typiquement, on peut classer les requêtes en deux grandes catégories : la mise à jour de tuples dans une relation et la recherche de tuples vérifiant une certaine condition. Eventuellement, ces deux types de requêtes peuvent être combinés.

La manipulation ensembliste est très utile en mise à jour. Elle permet, par exemple, de modifier directement la qualité de tous les nageurs ayant pris un bain sur la plage de Binic le 14 juillet 1989, sans avoir à déterminer préalablement la liste des nageurs qui présentent cette caractéristique. Cette puissance d'expression explique largement le succès du relationnel.

Les insertions/suppressions sont réalisées à l'aide de relations temporaires internes et d'opérateurs ensemblistes d'union et de différence (détails au paragraphe suivant). La combinaison de ces opérateurs et des opérateurs relationnels de sélection sur des critères de recherche facilite sensiblement les opérations de modification. C'est le cas en particulier des modifications calculées, c'est-à-dire des modifications portant sur un ensemble de tuples résultant eux-mêmes d'une sélection.

Exemples

La division

R Ç S = R - (R - S)

R |x| S (Ai, Bj) = s iqj (R x S)

R ¸ S = pi1,…,i(r-s) (R) - pi1,…,i(r-s) ( (pi1,…,i(r-s) (R) x S) - R)

Les cinq opérateurs de base permettent de répondre à toutes les questions que l'on peut poser avec la logique du premier ordre (c'est à dire sans les fonctions) : on dit que l'algèbre relationnelle est complète.

En réalité, nous n'utiliserons dans nos requêtes que les opérateurs les plus maniables : ce sont l'union et la différence pour l'insertion et la suppression de tuples dans la base et la restriction, la projection et la jointure pour la recherche sélective de tuples.

Un arbre algébrique est un arbre dont :

L'union :
 

La différence :

Nous pouvons dès lors facilement représenter la requête :

"Sur quelle plage (NOMP) Jean Plouf a-t-il pris des bains de plus de deux minutes ? "

Remarquons que cette requête peut s'exécuter de diverses façons :
 
 

Première méthode

Une première méthode d'exécution de requête peut minimiser le nombre d'opérations à effectuer. C'est ce que nous faisons ici en exécutant les jointures dans un premier temps, puis en repoussant à la fin la restriction et la projection qui permettent d'obtenir le résultat désiré. On minimise ainsi le nombre d'opérations à effectuer, mais on réalise des jointures sur des relations très volumineuses. ce qui augmente considérablement les tailles des relations intermédiaires et donc le coût global d'exécution de la requête.

Deuxième méthode
 

Quelle que soit l'heuristique choisie pour exécuter la requête. Déterminer dans quel ordre l'exécution des jointures entraîne un coût minimum est intéressant. Suivant la taille des relations mises en jeu, la différence de coût Correspondant à une inversion dans l'ordre des jointures peut être considérable.

Troisième méthode

Toutefois, compte tenu du coût très important des jointures et de l'importance de la taille des relations mises en jeu, il vaut mieux rajouter des étapes intermédiaires qui diminuent la taille des relations à l'entrée des jointures. Le coût supplémentaire est compensé par une baisse sensible du coût des jointures. C'est ce que nous faisons ici : les opérations de jointure agissent sur des relations réduites au maximum par des restrictions et des projections.

Quatrième méthode

Nous pouvons affiner cette méthode en éliminant après chaque jointure les attributs devenus inutiles pour l'obtention du résultat final.

Cinquième méthode
 

Enfin, nous pouvons également être amenés à rechercher les critères de variation du coût entre la méthode décrite ci-dessous et la précédente. Nous rajoutons ici une première étape de projection avant la première restriction.

A partir de cet exemple, nous constatons qu'à une même requête correspond de multiples plans d'exécution. Le choix d'un plan par rapport à un autre a de nombreuses implications quant à la durée d'exécution de la requête.

Enfin, si la vérification que l'ordre des opérateurs permet de réaliser la question initialement posée, choisir parmi les nombreuses solutions qui n'affectent pas le résultat, mais seulement la rapidité d'exécution de la requête est plus délicat .

En effet, se préoccuper activement du coût d'exécution d'une requête est nécessaire : un SGBD est jugé sur sa rapidité.

Une heuristique simple consiste à restreindre le plus vite possible la taille des relations intermédiaires pour diminuer le coût . Pour ce faire, nous utilisons les propriétés des différents opérateurs :

De façon générale ; il est indispensable de disposer :

Par exemple, tous les SGBD offrent aujourd'hui un langage assertionnel de requêtes, SQL. Un langage assertionnel permet de poser la requête sous la forme d'une ou de plusieurs conditions (assertions) à remplir sans se préoccuper de l'ordre des différentes opérations à effectuer au niveau du système. C'est au SGBD d'analyser la condition et de la décomposer en une requête de l'algèbre relationnelle.

L'optimiseur de requêtes est un composant très important d'un SGBD relationnel. L'étape fondamentale est la construction d'un arbre algébrique optimisé, en déterminant le meilleur ordre d'exécution des diverses opérations. Cependant, les SGBD utilisent d'autres critères (contraintes d'intégrité, taille des relations candidates, méthodes de placement…) soit pour aider à la construction de l'arbre optimisé, soit pour réfuter logiquement une requête et pour choisir l'algorithme adéquat à la réalisation d'une opération particulière (une même opération dispose couramment de différents algorithmes dont les performances varient suivant les caractéristiques des relations mises en jeu).

L'opération de jointure ou la prise en compte des temps de transit de données dans des systèmes répartis sont un bon exemple de la multiplicité des algorithmes existants.

Les améliorations sur le marché suivent de près les progrès de la recherche et les produits évoluent vite : les premières versions de nombreux produits offraient des algorithmes peu performants, mais la situation a bien changé depuis. Les SGBD demeurent toutefois des produits délicats à évaluer, comme c'est souvent le cas des produits informatiques. L'utilisation d'un algorithme ne suffit pas à garantir sa bonne utilisation. Notez en particulier l'importance essentielle des méthodes de stockage et des primitives de bas niveau offertes par le système d'exploitation pour l'efficacité des SGBD. Pour toutes ces raisons, le modèle relationnel, malgré sa "beauté conceptuelle", a mis beaucoup de temps à s'imposer sur le marché.

[Codd 70] E.F. CODD, "A Relational Model of Data for Large Shared Data Banks", Communications ACM, V13, N6, Juin 1970, pp 377-387.