Théorème d'équivalence
Fondamental :
Une requête est exprimable en calcul conjonctif si et seulement si elle est exprimable en algèbre conjonctive.
Éléments de preuve
Toute requête du calcul conjonctif peut facilement être exprimée dans l'algèbre conjonctive : ∃ est simulé par une restriction, et ∧ par la jointure. Pour la simulation de l'algèbre par les requêtes conjonctives, on remarque dans un premier temps que cela est évident pour des requêtes de la forme :
(*) πU ( σγ ( σγ1(ρ|f1(R1)) ⋈ ⋅⋅⋅ ⋈ σγn(ρ|fn(Rn ))))
où chaque γi est une condition de sélection, chaque fi un renommage, et chaque Ri une relation de la base de données (voir l'exemple plus loin.) Pour des requêtes algébriques plus complexes, on se ramène à la forme (*) en utilisant des équivalences algébriques telles que :
σF (σF′(q)) ↔ σF′(σF(q)) | |
πX (πY (q)) ↔ πX ∩Y(q) | |
σF (πX (q)) ↔ πX (σF (q)) | si F porte sur des attributs de X |
q1 ⋈ q2 ↔ q2 ⋈ q1 | |
σF(q1 ⋈ q2) → σF(q1) ⋈ q2 | si F porte sur des attributs de sort (q1) |
πX (q1 ⋈ q2) → πX (q1) ⋈ πX (q2) | si X ⊆ sort(q1) ∩ sort(q2) |