Sélection et projection

• σ_F(r₁) (SELECT * FROM r1 WHERE F) :
  • Au pire, considérer chaque tuple de r₁ et tester la condition F : O(n_r1).
  • Une meilleure complexité peut être obtenue s’il y a des index adaptés à la condition de sélection (par exemple, un index sur colonne et une condition telle que colonne = valeur.
• π_X(r₁) (SELECT X FROM r1) :
  • En général : parcours de r₁ avec extraction des composantes nécessaires de chaque tuple : O(n_r1).
  • Si l’élimination des occurences multiples est nécessaire (SELECT DISTINCT X FROM r1), alors il faut trier la relation r₁ : O(n_r1 log(n_r1))