BD-2st-1.2-w13.tresc-1.1-Slajd14
Szacowanie rozmiarów Selection (3)
Do oszacowania rozmiaru liczby różnych wartości atrybut B w wyniku selekcji S (c= val(B[S])) stosuje się tak zwaną aproksymację Yao przedstawioną na slajdzie. Dla ilustracji rozważmy ponownie rozważany wcześniej przykład relacji Pracownicy. Niech card(Pracownicy) = 1000. Relacja Pracownicy zawiera, m. in. atrybuty miasto i stanowisko . Załóżmy, że liczba różnych wartości atrybut miasto w relacji Pracownicy wynosi 5 (val(miasto[Pracownicy]) = 5) i val(stanowisko[Pracownicy]) = 10. Ile różnych wartości atrybutu stanowisko znajdzie się w wyniku zapytania S:
Select nazwisko, stanowisko
From Pracownicy
Where miasto=’Konin’
Dane: n=1000 (krotek relacji Pracownicy), m=10 (różnych stanowisk), r =200 = card(S) (rozmiar wyniku zapytania). Stąd, zgodnie z aproksymacją Yao, val(stanowisko[S]) = m = 10.
