Produit cartésien et jointure

• (r₁ × r₂ ) : Par définition, le produit cartésien contient n_r1 × n_r2 tuples et nécessite un temps de calcul O(n_r1 × n_r2 ).
• (r₁ ⋈ r₂ ) : Stratégies différentes en fonction de la présence ou non d'index.
• Jointure sans index avec X les attributs communs de r₁ et r₂.
  • Méthode naive : Examiner toutes les paires de tuples et comparer les valeurs des attributs communs : O(n_r1 × n_r2 ).
  • Tri et fusion : Trier les deux relations par rapport à leurs attributs communs. Fusionner les résultats.
    Complexité : O(n_r1 log(n_r1) + n_r2 log(n_r2)), pour autant que n_ri/nbVal(X,r_i) avec i=1 ou i=2 soit borné pour les attributs communs X.