Théorème de Codd
# Théorème de Codd

En théorie des bases de données, le théorème de Codd affirme l'équivalence entre l'algèbre relationnelle et le calcul relationnel (restreint aux requêtes indépendantes du domaine). Ce théorème est important pour les bases de données relationnelle, car il assure que toute requête « naturelle » (i.e. du calcul relationnel) peut se traduire en algèbre relationnelle, et donc en un langage de requêtes intelligible par un ordinateur (en particulier le SQL). Ce théorème a été démontré par Edgar Frank Codd en 1971.

## Introduction

Dans le modèle de la base de données relationnelle, une table (ou relation) contient plusieurs attributs ou champs (les colonnes) et plusieurs lignes, appelées tuples. Une table est vue comme un ensemble (ou multi-ensemble dans la plupart des implémentations) de tuples. Par exemple, une table avec deux champs (Titre et Réalisateur) et trois tuples.

Films :

| Titre | Réalisateur |
| - | - |
| Whiplash | Damien Chazelle |
| Lalaland | Damien Chazelle |
| Didier | Alain Chabat |

Il existe deux modélisations mathématiques de requêtes.

* Dans le calcul relationnel, les requêtes sont déclaratives. Par exemple, la requête "Donner l'ensemble des titres de films qui sont réalisés par Damien Chazelle" s'écrit {<x> | Films(x, 'Damien Chazelle') } en calcul relationnel. Elles sont basées sur des ensembles, quantificateurs et variables et donc proches de la logique du premier ordre.
* En algèbre relationnelle, les requêtes sont impératives, c’est-à-dire que l'on décrit comment construire le résultat. Par exemple, "Garder uniquement les lignes de la table où la deuxième colonne est 'Damien Chazelle'".

## Calcul relationnel

Le calcul relationnel correspond à la logique du premier ordre sans symbole de fonction, mais avec des adaptations propres aux bases de données relationnelles. Selon Serge Abiteboul et al., son introduction remonte à un rapport technique de J.L. Kuhns de 1969 où il utilise des formules logiques pour faire des requêtes. Mais l'importance du calcul relationnel s'est développé avec $Codd^,.$

Certaines requêtes dépendent du domaine. Par exemple, "donner l'ensemble des titres des films qui ne sont pas dans la relation Films" est une requête pour laquelle il faut spécifier le domaine. Par exemple, avec le domaine {Whiplash, Lalaland, Didier, Damien Chazelle, Alain, Chabat}, la réponse est vide. Mais, avec le domaine {Whiplash, Lalaland, Didier, Damien Chazelle, Alain, Chabat, Star Wars}, la réponse est {Star Wars}. On étend la sémantique d'une formule en explicitant précisément le domaine dans lequel on travaille. On parle d’interprétation relativisé : une requête est évaluée dans une base de données muni d'un domaine.

Le domaine actif d'une base de données est l'ensemble des éléments qui apparaissent dans la base de données. Dans l'exemple, ci-dessus, il s'agit de {Whiplash, Lalaland, Didier, Damien Chazelle, Alain, Chabat}.

Une requête est indépendante du domaine si sa solution ne dépend pas du domaine et dépend uniquement de la base de données. Par exemple, "Donner l'ensemble des titres de films qui sont réalisés par Damien Chazelle" est indépendante du domaine. Par contre, "donner l'ensemble des titres des films qui ne sont pas dans la relation Films", elle, dépend du domaine.

Pour les requêtes indépendantes du domaine, il suffit alors de réaliser la requête sur une base de données en utilisant le domaine actif.

## Algèbre relationnelle

L'algèbre relationnelle décrit des opérations sur des relations. Dans cet article, on s'intéresse aux opérations suivantes :

* Prendre une relation R
* Prendre m tuples de même arité
* Sélection (ne garder que les tuples qui vérifient une certaine propriété)
* Projection (oublier des champs)
* Produit cartésien de deux relations
* Union de deux relations
* Différence de deux relations

## Énoncés

Une première version du théorème de Codd énonce l'équivalence entre le calcul conjonctif (on n'utilise que des conjonctions dans les requêtes du calcul relationnel) et l'algèbre SPC (prendre une relation R, prendre m tuples, sélections, projections, produits cartésien) satisfiable.

Une seconde version du théorème de Codd énonce l'équivalence entre l'algèbre relationnelle (entière) et le calcul relationnel restreint aux requêtes indépendantes du domaine.

## Démonstration

### Algèbre relationnelle vers calcul relationnel

La table ci-dessous montre comment transformer une requête de l'algèbre relationnelle non nommé en une requête équivalente du calcul relationnel, qui est indépendante du domaine. La construction se fait par induction sur la requête de l'algèbre relationnelle. On rappelle que le symbole ∨ désigne la disjonction (ou), le symbole ∧ désigne la conjonction (et), le symbole ¬ désigne la négation (non).

| Requête de l'algèbre relationnelle | Requête correspondante en calcul relationnel, indépendante du domaine |
| - | - |
| Une relation R | $R(x_1,$ $...x_{arité(R)})$ On construit la formule avec le symbole de prédicat R et on utilise les variables $x_1,$ $...x_{arité(R)}$ pour parler de tous les tuples de la relation R. |
| ${u_1,$ ..., $u_m}$ où les $u_i$ sont des tuples de même arité α | $(x_1$ = $u_1(1)$ ∧ ... ∧ $x_α$ = $u_1(α))$ ∨ .... $(x_1$ = $u_m(1)$ ∧ ... ∧ $x_α$ = $u_m(α))$ On dit que les variables $x_1,$ $...x_α$ désigne l'un des tuples de ${u_1,$ ..., $u_m}$ |
| Une sélection de E par une formule F : $σ_F(E)$ | $φ_E$ ∧ F' où F' est la formule obtenue en remplaçant l'identifiant de la coordonnée i par $x_i$ On exprime que l'on parle de tuple de E mais qui en plus satisfont F' |
| Projection de E sur ${i_1,$ ... $i_n}$ : $π_{i1,...in}(E)$ | $∃y_{i1}...∃y_{in}$ $(x_1=y_{i1}$ ∧ ... $x_n$ = $y_{in})$ ∧ $∃y_{j1}...∃y_{jl}$ $φ_E(y_1,$ $...y_{arité(E)})$ où $j_1,$ ..., $j_l$ = [1, arité(E)] \ ${i_1,$ ... $i_n}$ Les variables libres $x_1,$ ... $x_n$ désigne les coordonnées les éléments de coordonnées $i_1,$ ... $i_n$ d'un tuple de E. Les autres coordonnées sont oubliées et quantifiées avec $∃y_{j1}...∃y_{jl}.$ |
| Produit cartésien : $E_1$ × $E_2$ | $φ_{E1}$ ∧ $φ_{E2}(x_{arité(E1)+1},$ ... $x_{arité(E1)+arité(E2)})$ Le produit cartésien est simulé par une conjonction et un décalage des indices de $arité(E_1).$ |
| Union : $E_1$ ∪ $E_2$ | $φ_{E1}$ ∨ $φ_{E2}$ L'union correspond à une disjonction. |
| Différence : $E_1$ - $E_2$ | $φ_{E1}$ ∧ $¬φ_{E2}$ Être dans la différence $E_1$ - $E_2$ c'est être dans $E_1$ mais pas dans $E_2.$ |

### Calcul relationnel vers algèbre relationnelle

Toute requête en calcul relationnel, il existe une requête en algèbre relationnelle qui est lui est équivalente sous domaine actif (et donc en particulier toute requête du calcul relationnel qui est indépendante au domaine s'écrit en algèbre relationnelle).

