Opérateurs ensemblistes : ∪ et −

• r₁ ∪ r₂ : Implémentation directe : complexité O(n_r1 + n_r2 ).
• Si l’on désire éliminer les occurences multiples, on peut
  • trier le résultat : O((n_r1 + n_r2) log(n_r1 + n_r2)) ;
  • ou utiliser un index existant, par exemple pour r₁ , et n’ajouter à r₁ que les tuples de r₂ qui ne figurent pas dans r₁ : O(n_r1 + n_r2 log(n_r1 )).
• r₁ − r₂ : on peut
  • trier les deux relations et les parcourir ensuite séquentiellement, en éliminant de r₁ les tuples de r₂ : O(n_r1 log(n_r1) + n_r2 log(n_r2)) ;
  • ou utiliser un index existant pour r₂ : considérer chaque tuple de r₁ , le chercher dans r₂ en utilisant l’index : O(n_r1 log(n_r2)).