48329 ullman106 (2)

Wyrażenia równoważne i optymalizacja zapytań

W wielu systemach baz danych korzysta się z systemów zapytań, które zawieraj.*} języki zapytań zbliżone, w zakresie mocy obliczeniowej, do algebry relacji. A zatem zapytanie utworzone przez użytkownika można przekształcać w sposób równoważny i otrzymać w ten sposób wiele równoważnych wyrażeń (tzn. wyrażeń, które dają ten sam wynik, jeśli operują na tych samych relacjach), różniących się czasem przetwarzania. \V' punkcie 1.2.3 omawialiśmy pokrótce „optymalizator zapytań ’, którego główne zadanie polega na zastąpieniu wyrażenia algebry relacji wyrażeniem równoważnym. które można przetwórz) ć w sposób bardziej efektywny.

PRZYKLAD4.il

Ważnym zastosowaniem operacji złączenia naturalnego jest rekonstrukcja ory ginalnej relacji z relacji otrzymanych w^j wyniku jej dekompozycji do postaci BCNF Przypomnijmy sobie, jak wyglądał) relacje otrzymane w wyniku przekształceń w przykładzie 3.32*:

Fiiml o schemacie {tytuł, rok, długość, -.ypFilmu, nazwaStu-

dia)

fi lm2 O schemacie {tytuł, rok, nawiskoGwiazdył

Spróbujmy teraz zapisać zapytanie „Wyszukać gwiazdy tych filmów, które trwają dłużej niż 100 minut”. W tym zapytaniu powiązano atrybut nazw -skoGwiazdy z relacji Filml Z atrybutem długość z relacji Fł im2. Można połączyć te atrybuty przez wykonanie złączenia tych dwóch relacji. W złączeniu naturalnym /.ostaną powiązane ze sobą te krotki, które dotyczą tego samego (limu, a zatem w których wartości atrybutów tytu- i rok mają takie same wartości w obu relacjach. Czyli wyrażenie z algebr)^- relacji Fi: ir. 1 tx Film2 daje w wyniku relację, którą w przykładzie 3.32 nazywaliśmy Filtr.. Nie ma ona postaci BCNF, ponieważ zawiera wszystkie sześć atrybutów ora/ występują w niej krotki opisujące ten sam film, jeśli wystąpiło w tym filmie kilka gwiazd.

Teraz do złączenia relacji Filml i Fi lm2 zastosujemy operator wyboru, który wymusza wybór tylko tych filmów, które trwają nie krócej niż 100 minut. Potem trzeba wykonać rzutowanie na określony w zapytaniu zbiór atrybutów: tytuł i ; ok Poniżej przedstawiamy wyrażenie algebry relacyjnej, opisujące zadane zapytanie:

ftiyiut, n/Ji((TjtuftiMzioo (Filml txa F Im.-))

□

Relacja Fi Lr. w tamtym przykładzie różniła się od relacji Film. opisanej w podrozdziale 3 i z której korzystaliśmy w przykładach 4.2.4 J i 4 4.

4.1.8. Przemianowanie

Aby nazwy atrybutów wchodzących w skład relacji nic doprowadzały dc nieporozumień w przypadku tworzenia złożonych wyrażeń algebr)' relacji w których występuje wiele relacji i wiele operatorów, często bywa wygodni* utworzyć nowe nazwy dla pewnych atrybutów lub dla relacji. Symbolcrr PsiA^A). a„)(R) oznaczymy przemianowanie relacji R. W wyniku otrzymuje się relację, do której należą te same krotki co do relacji R< ale nazwą nowe

relacji jest S. Atrybuty otrzymują nazwy: A\_%Ai-.....A„, a ich porządek jes

zachowany z relacji oryginalnej. Jeśli zmiana ma dotyczyć tylko nazwy rela cji, a nazwy atry butów mają pozostać bez zmian, to stosujemy zapis p^R).

PRZYKŁAD 4.12

Przy tworzeniu iloczynu kartezjańskiego relacji R i S w' przykładzie 4.5 sto suwaliśmy konwencję pozwalającą odróżniać tak samo nazywane atrybut} z różnych relacji przez dopisywanie przed nimi nazw relacji, z który ch t< atrybuty pochodzą. Na rysunku 4.8 przedstawiono ponownie relacje R i S.

A	B
1	2
3	4
Relacja R
B	C	D
Z	5	6
4	7	8
9	10	11

Relacja S

A	B	X	C	D
1	2	2	5	6
1	2	4	7	8
1	2	9	10	11
3	4	2	b	6
3	4	4	7	8
3	4	9	10	11

RYSUNEK 4.K

Dwie relacje i ich iloczyn kartezjański

Wynik R x pxx.c.i>ł^s)

Może się jednak okazać, że oznaczanie atrybutu B odpowiednio prze R B i S.B jest niewygodne, a lepiej w dalszym ciągu nazywać atrybut B z rela cji R jako B. natomiast atrybut B z relacji S nazwać inaczej, np. X. Możem