Accueil🇫🇷Chercher

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[1].

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[2] 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[3] - [4].

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[5]. 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[6].

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[7]. 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(x1, ...xarité(R))


On construit la formule avec le symbole de prédicat R et on utilise les variables x1, ...xarité(R) pour parler de tous les tuples de la relation R.

{u1, ..., um} où les ui sont des tuples de même arité α (x1 = u1(1) ∧ ... ∧ xα = u1(α)) ∨ .... (x1 = um(1) ∧ ... ∧ xα = um(α))


On dit que les variables x1, ...xα désigne l'un des tuples de {u1, ..., um}

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 xi


On exprime que l'on parle de tuple de E mais qui en plus satisfont F'

Projection de E sur {i1, ... in} : πi1,...in(E) ∃yi1...∃yin (x1=yi1 ∧ ... xn = yin) ∧ ∃yj1...∃yjl φE(y1, ...yarité(E)) où j1, ..., jl = [1, arité(E)] \ {i1, ... in}


Les variables libres x1, ... xn désigne les coordonnées les éléments de coordonnées i1, ... in d'un tuple de E. Les autres coordonnées sont oubliées et quantifiées avec ∃yj1...∃yjl.

Produit cartésien : E1 × E2 φE1 ∧ φE2(xarité(E1)+1, ... xarité(E1)+arité(E2))


Le produit cartésien est simulé par une conjonction et un décalage des indices de arité(E1).

Union : E1 ∪ E2 φE1 ∨ φE2


L'union correspond à une disjonction.

Différence : E1 - E2 φE1 ∧ ¬φE2


Être dans la différence E1 - E2 c'est être dans E1 mais pas dans E2.

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[8] (et donc en particulier toute requête du calcul relationnel qui est indépendante au domaine s'écrit en algèbre relationnelle).

Notes et références
  1. E. F. Codd, « Relational completeness of data base sublanguages », Database Systems, Prentice-Hall,‎ , p. 65–98 (lire en ligne, consulté le )
  2. J. L. Kuhns, « Logical Aspects of Question-Answering by Computer », dans SEN Report Series Software Engineering, vol. 2, Elsevier, coll. « Computer and Information Sciences–1969 », (lire en ligne), p. 89–104
  3. E. F. Codd, « A Relational Model of Data for Large Shared Data Banks », Commun. ACM, vol. 13, no 6,‎ , p. 377–387 (ISSN 0001-0782, DOI 10.1145/362384.362685, lire en ligne, consulté le )
  4. E. F. Codd, « A Data Base Sublanguage Founded on the Relational Calculus », Proceedings of the 1971 ACM SIGFIDET (Now SIGMOD) Workshop on Data Description, Access and Control, ACM, sIGFIDET '71,‎ , p. 35–68 (DOI 10.1145/1734714.1734718, lire en ligne, consulté le )
  5. (en) Foundations of Databases : The Logical Level, Addison-Wesley Longman Publishing Co., Inc., , 685 p. (ISBN 978-0-201-53771-0, lire en ligne), p. 77 Paragraphe "Relativized interpretations"
  6. Foundations of Databases : The Logical Level, Addison-Wesley Longman Publishing Co., Inc., , 685 p. (ISBN 978-0-201-53771-0, lire en ligne), p. 60 Th. 4.4.8
  7. (en) Foundations of Databases : The Logical Level, Addison-Wesley Longman Publishing Co., Inc., , 685 p. (ISBN 978-0-201-53771-0, lire en ligne), p. 80 (Lemma 5.3.11)
  8. (en) Foundations of Databases : The Logical Level, Addison-Wesley Longman Publishing Co., Inc., , 685 p. (ISBN 978-0-201-53771-0, lire en ligne), p. 80, (Lemma (5.3.12)

Bibliographie
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.