Séquence 3/6 : Algèbre relationnelle

Soit q = {x1,...,xn∣φ} une requête du calcul. Il est facile de construire une requête algébrique construisant le domaine actif :

q_adom(I) = {⟨a⟩ | a ∈ adom (q,I)}

Ensuite, par induction, on associe à chaque sous-formule ψ une requête algébrique q_ψ telle que :

{y1,...,ym | ψ} (I) = q_ψ (I)

On illustre cette construction avec quelques cas. Supposons que ψ est une sous formule de φ. Alors q_ψ est construit de la manière suivante :

1. ψ(y1,...,ym) est R(t1,...,tl), où chaque ti est une constante ou appartient à y1,...,ym Alors q_ψ ≡ π⃗_k1,... ;kl(σ_F (R)), où ⃗kj et F sont choisis en accord avec y1,...,ym,t1,...,tl .

2. ψ(y1,y2) est y1≠y2 : q_ψ est σ_1≠2(q_adom × q_adom).

3. ψ(y1,y2,y3) est ψ′(y1,y2) ∨ ψ′′(y2,y3) : q_ψ est (q_ψ′× q_adom) ∪ (q_adom × q_ψ′′).

4. ψ(y1,...,ym) est ¬ψ′(y1,...,ym) : qψ est (q_adom ×⋅⋅⋅× q_adom) - q_ψ′.