Kihagyás

Relációs algebra optimalizációja

Példa: Lócsi SZ01-es számláján mennyi pénz van?

számla(név, szamla_azon, összeg)

név szamla_azon összeg
Lócsi SZ01 100000
Szakáll SZ02 999999
Lócsi SZ03 0.001
\[ \Pi_{\text{összeg}}(\sigma_{\text{név='Lócsi'}\land\text{szamla\_azon='SZ01'}}(Számla)) \]

Fő cél az adatok elérésének optimalizációja

  • I/O műveletek minimalizálása
    • Relációk méretének csökkentése
  • Az optimalizáció során relációs algebrai azonosságok alkalmazása
    • Az eredetivel ekvivalens, de I/O szempontjából optimálisabb lekérdezés készítése
    • A \(q, q'\) relációs algebrai lekérdezések ekvivalensek, ha tetszőleges \(I\) előfordulás esetén \(q(I)=q'(I)\) fennál
      • Jelölés: \(q\equiv q'\)

Optimalizáció - Példa

\(F = \text{Film(Cím, Év, Hossz)}\)

\(S = \text{Szerepel(Filmcím, Év, Színész)}\)

\(\Pi_{\text{Hossz}}(\sigma_{\text{Cím=Filmcím}\,\land\,\text{F.Év = Sz.Év}\,\land\,\text{Színész='Edus'}}(F\times S))\)

Ekvivalens a

\(\Pi_{\text{Hossz}}(\sigma_{\text{Cím=Filmcím}\,\land\,\text{F.Év = Sz.Év}}(F\times (\sigma_{\text{Színész='Edus'}}(S))))\)

Lekérdezéssel

Az pedig érezhető, hogy az összefűzés előtti szűrés sokszor kevesebb összehasonlítást eredményezhet az összekapcsolás után (a nem 'Edus'-ok elsőre kikerülnek)...

Tulajdonságok - Descartes szorzat és Összekapcsolás

Asszociativitás

Descartes és természetes kapcsolás

\[ (E_1 \circ E_2) \circ E_3 \equiv E_1 \circ (E_2 \circ E_3)\quad(\circ\in\{\times,\;\Join\}) \]

A Descartes ugye minden sort minden sorral párosít, a feltétel nélküli Join pedig csak azonos nevű attribútumok szerint, ezért nem kell plusz megkötés

Theta összekapcsolás

\[ (E_1 \Join_{F_1} E_2) \Join_{F_2} E_3 \equiv E_1 \Join_{F_1} (E_2 \Join_{F_2} E_3) \]
\[ \text{attr}(F_1)\subseteq\text{attr}(E_1)\cup\text{attr}(E_2)~~\land~~\text{attr}(F_2)\subseteq \text{attr}(E_2)\cup\text{attr}(E_3) \]

Na ugye itt most a feltételeket \((F_1,\;F_2)\) mi adjuk, így biztosak kell legyünk abban, hogy nem csak a közös relációra, de a részekre is valid mind a két feltétel

Kommutativitás

\[ E_1\circ E_2\equiv E_2\circ E_1\quad(\circ\in\{\times,\;\Join,\;\Join_F\}) \]

Trivi 💣

Tulajdonságok - Projekció és Szelekció

Halmazműveletek

Projekció sorozat

\[ \Pi_X(\Pi_Y(E))\equiv\Pi_X(E)\quad(X\subseteq Y) \]

A kezdő rejációból ha kiemelünk először Y(a,b,c,d)-r, majd abból X(b,d)-t, az eredmény ugyanaz lesz, mintha egyből csak X-et emelnél ki.

Kiválasztás és feltételek konjunkciója

\[ \sigma_{F_1\land F_2}(E)\equiv\sigma_{F_1}(\sigma_{F_2}(E)) \]

Ugye a feltételek láncban alkalmazását ha elvégeznénk is úgy hangzana, hogy: Fogjuk az \(F_2\)-nek, és azokból az \(F_1\)-nek megfelelő sorokat (az \(\land\) meg felcserélhető, so don't you worry)

Kiválasztás és feltételek diszjunkciója

\[ \sigma_{F_1\lor F_2}(E)\equiv\sigma_{F_1}(E)\cup\sigma_{F_2}(E) \]

Ugyanaz az elv, csak "kifordítva"

Kiválasztás elé projekció beillesztése

\[ \Pi_X(\sigma_F(E))\equiv\Pi_X(\sigma_F(\Pi_Y(E)))\quad(Y = \text{attr}(F)\cup X) \]

Ez kicsit a subquery-k tétele, ha közben már szűkíteni akarsz az attribútumokon, mielőtt végül kiválasztasz, go ahead

SELECT name, id FROM users WHERE name='Johny'

\(\equiv\)

SELECT name, id FROM (SELECT name, id, age FROM users) WHERE name='Johny'

Magában ez a tétel csak azt mondja ki, hogy a felesleges al-kiválasztásokat el lehet hagyni, viszont ennek segítségére később még szükség lehet

Felcserélhetőség kiválasztás felett (Descartes / Join)

\[ \sigma_F(E_1 \circ E_2)\equiv \sigma_F(E_1)\circ E_2\qquad(attr(F)\subseteq attr(E_1),~~\circ\in\{\times,\Join\}) \]

Itt érdemes visszaemlékezni arra, hogy a Descartes és a Join hogyan is működik, ha az egyik oldalt végzel egy szűrést, az összes hozzá tartozó párosítást is eldobtad így.

Általános alak

\[ \sigma_F(E_1 \circ E_2)\equiv \sigma_{F_1}(E_1)\circ \sigma_{F_2}(E_2) \]

Ahol \(\quad attr(F_i)\subseteq attr(E_i)\;(i=(1,2))\quad F=F_1\land F_2\quad\circ\in\{\times,\Join\}\)

Ez ugye a kibővítés, itt arról van szó, hogy a feltételt ha fel tudod bontani külön az E_1-re és külön az E_2-re vonatkozóan, akkor azt a kapcsolás előtt elvégezheted rajtuk

Don't forget that Join is expensive

Ebből levezetve

\[ \sigma_F(E_1 \circ E_2)\equiv \sigma_{F_2}(\sigma_{F_1}(E_1)\circ E_2) \]

Ahol \(\quad attr(F_i)\subseteq attr(E_i)\;(i=(1,2))\quad F=F_1\land F_2\quad\circ\in\{\times,\Join\}\)

Hasonló megközelítés, itt csak az egyik feltételt emeljük ki a kapcsolás utánra

Felcserélhetőség projekció felett (Descartes, Join)

\[ \Pi_X(E_1 \circ E_2)\equiv \Pi_Y(E_1)\circ \Pi_Z(E_2) \]

Ahol $ \quad X=Y\cup Z,\;Y\subseteq attr(E_1),\;Z\subseteq attr(E_2),\quad \circ\in{\times, \Join}$

Kotlin reminder:

Itt a lényeg csak annyi, hogy tök mindegy, előbb sorolod fel Y(a,b,c),t majd fűzöd össze Z(c,d,e)-vel, minthogy először összefűzöl, majd felsorolod egybe X(a,b,c,d,e)-t (yes, the overlap is intentional)

Halmazműveletek - Projekció

Felcserélhető halmazműveletek - Kiválasztás

\[ \sigma_F(E_1\circ E_2)\equiv\sigma_F(E_1)\circ\sigma_F(E_2)\quad(\circ\in\{\cap,\;\cup,\;-\}) \]

Felcserélhető unió - Projekció

\[ \Pi_X(E_1\cup E_2)\equiv\Pi_X(E_1)\cup\Pi_X(E_2) \]

Sajnos a metszet nem minden esetben működik, így arra nincs általános szabály (a metszet ha belül üres halmazt alkot, kívül még nem feltétlen)

Példa: (Üres halmazzról minden kiválasztás üres halmaz)

\(\Pi_A(\{\left<A=a,B=b\right>\cap\left<A=a,B=b'\right>\}) = \emptyset\)

Míg

\(\Pi_A(\{\left<A=a,B=b\right>\})\cap\Pi_A(\{\left<A=a,B=b'\right>\}) = \{\left<A=a\right>\}\cap\{\left<A=a\right>\} =\{\left<A=a\right>\}\)

Mert ha már csak egy attribútum marad, szűkebb halmazon nagyobb átfedés lehet (a példában lett is)

Optimalizáció - Feladat

Táblák

  • Személy(név, kor, város, ISBN)
  • Könyv(cím, író, ISBN, ár)
  • Kiad(k_cím, k_író, város, ország)

Feladat

Kik azok, akik 20 évesek és moszkvai kiadású könyvet kölcsönöztek ki?

\[ \Pi_N(\sigma_{Sz\text{.ISBN}=Kö\text{.ISBN}\,\land\,\text{cím=k\_cím}\,\land\,\text{író=k\_író}\,\land\,\text{kor}=20\,\land\,\text{k\_város='Moszkva'}}(Sz\times Kö\times K)) \]

Lekérdezésfa

Csúcsok műveletek, levelek pedig Relációk

Lépésenként alulról a csúcsokat a kiértékelés eredményével helyettesítjük, amíg a gyökeret elérve megkapjuk az egész lekérdezéshez tartozó relációt.

Előző feladat lekérdezésfája

Naiv lekérdezésfa

Lekérdezésfa - Lépések

Lépések - Kiválasztás

  • A kiválasztások konjunkciós feltételeinek szétdarabolása
    • \(\sigma_{F_1\land F_2}(E)\equiv\sigma_{F_1}(\sigma_{F_2}(E))\)
  • Kiválasztást halmazműveletekkel, Descartes-al és természetes összekapcsolással helyettesíteni
  • Célunk a kiválasztásokat minél hamarabb végrehajtani
  • Theta összekapcsolást érdemesebb Descartes-en végzett kiválasztással helyettesíteni
    • \(R \Join_F S \equiv \sigma_F(R\times S)\)

Darabolás utáni fa

Darabolás utáni állapot

Letolás utáni fa

Letolás után

Lépések - Projekciók

They call it: "Projekciók beírása"

  • Célunk csak azokat az oszlopokat megtartani a köztes relációkban, amikre később szükség is lesz
    • Jellemzően ez nem nagy nyereség
      • Mert a projekciók is költségesek
  • A projekciókra vonatkozó szabályok érvényesülnek

Projekciók beírása után

Projekciókkal

Lépések - Kapcsolások

  • \(\Pi_L(\sigma_C(R \times S))\) és \(\sigma_C(R\times S)\) helyettesíteése Természetes és Theta összekapcsolással

Kapcsolásokkal

Diszjunkció megjelenésével az optimalizációs algoritmus már nem egyértelmű...

Lépések - Felemelés

They call it "Feljebb csúsztatás"

Példa lekérdezés

CREATE VIEW film04 AS
(SELECT *
FROM film
WHERE év = 2004);
\[ \sigma_{\text{év}=2004}(\text{Film}) \]

Kezdeti fa

Kezdeti fa

Második lépés

Második lépés

Eredmény

Eredmény

Leginkább azért, mert a kezdeti szelekció adhat előnyt a másik táblában is