Séquence 3/6 : Algèbre relationnelle

Pour simplifier la présentation, nous utilisons ici une algèbre basée sur les numéros de colonnes au lieu des noms d'attributs. Soit q une requête algébrique d'arité n. Nous construisons q′ = {x1,...,xn∣φ_q} équivalente à q par induction sur les “sous-requêtes” de q. (Une requête est construite en appliquant une opération à une ou deux sous-requêtes.) En particulier, pour une sous-requête q′ de q, on définit φ_q′ par :

1. si q′ est R pour R ∈ R : φ_q′ est R(x1,...,xm) où m = arité(R).

2. si q′ est {u1,...,um} où chaque uj est un nuplet d'arité α : φ_q′ est

   (x1 = u1(1)∧ ⋅⋅⋅∧ xα = u1(α)) ∨ ... ∨ (x1 = um (1)∧ ⋅⋅⋅∧ xα = um(α )).

3. si q′ est σ_F (q1) : φ_q′ est φ_q1∧ψ_F , où ψ_F est la formule obtenue à partir de F en remplaçant chaque numéro de colonne i par une nouvelle variable xi.

4. si q′ est π_i1,...,in(q1) : φ_q′ est

   ∃yi1 ...yin((x1 = yi1 ∧ ⋅⋅⋅∧ xn = yin) ∧ ∃yj1 ...∃yjlφ_q1(y1,...,ym)) où m=arite(q′).

   où j1,...,jl est une liste de [1,arite(q′)] -{i1,...,in}.

5. si q′ est q1 × q2 : φ_q′ est φ_q1 ∧ φ_q2(x_m1+1,...,x_m1+m2) où m1=arite(q1) et m2=arite(q2).

6. si q′ est q1 ∪ q2 : φ_q′ est φ_q1 ∨ φ_q2.

7. si q′ est q1 - q2 : φ_q′ est φ_q1 ∧¬φ_q2.

Vous pouvez vérifier vous même les détails de cette construction.