Calcul du coût d'une requête

Soit deux relations t1(a:char(8),b:integer) et t2(b:integer) de respectivement 100 et 10 lignes.

Soit la requête SELECT * FROM t1 INNER JOIN t2 ON t1.b=t2.b WHERE t2.b=1.

  • Soit n1 le nombre de tuples tels que b=1 dans t1 ; n1 ∈[0..100]

  • Soit n2 le nombre de tuples tels que b=1 dans t2 ; n2 ∈[0..10]

  • Soit n3 le nombre de tuples tels que t1.b=t2.b ;  : n3 ∈[0..1000]

Question

Il existe plusieurs façons de traduire cette requête en algèbre relationnel, proposer quelques exemples.

Question

Calculer le nombre d'instructions de chaque exemple d'expression relationnelle :

  • en considérant que les restrictions sont effectuées par un parcours intégral dans des listes non triées (comme si c'était effectué avec des boucles de type FOR) ;

  • en considérant que chaque opération est effectuée séparément.

Effectuer les calculs pour trois valeurs de n1,n2 et n3 (une valeur minimum, une valeur maximum et une valeur intermédiaire). Donner un intervalle [min..max] indépendant de n1, n2 et n3.

Question

Conclure en indiquant quelle opération nécessite le moins d'instructions.