Az optimalizáció algoritmusa

A szabályokat paragrafusként hivatkozom, evvan :P

Heurisztikák

1. Szelektálni minél hamarabb

Minél hamarabb csökkentjük a relációk méretét, annál kevesebbszer kell iterálni rajta, (p str8 forward)

2. Hozzunk ki \(\Join\)-t, ahol lehet

A szorzás utáni kiválasztás jellemzően csokornyakkendő szagú, és ne felejtsük el, hogy összekapcsolás közben szűrni hatékonyabb, mint egyszer egybe gyúrmázni az egészet, majd mégegyszer átmenni rajta, csak hogy szűrjük. meh

3. Láncolt unárisokat vonjuk össze

Ne vetítsünk 10x, ha megtehetjük egyszer is. Ugyanez a szűréssel

(nem beszélve arról, hogy egy szigorúbb szűrés kissebb relációt eredményezhet)

Bónusz, inkább szűrjünk először, majd vetítünk a maradékon

4. Keressünk közös részkifejezéseket

A közös részt elég csak egyszer kiszámolni kiértékeléskor

Az algoritmus (now rly)

A lépéseket sorba, plz:

A kiválasztásokat bontsuk fel a §4 segítségével

A kiválasztásokat a §4 §5 §6 §7 §8 §9 segítségével vigyük olyan mélyre a kifejezésfában, amilyen mélyre csak lehet

A vetítéseket a §3 §5 §10 §11 segítségével vigyük olyan mélyre a kifejezésfában, amilyen mélyre csak lehet

Hagyjuk el a triviális vetítéseket , tehát amikben az argumentum reláció összes oszlopa megtalálható

Ha egy relációra vagy konstans relációra egymás után kiválasztásokat és/vagy vetítéseket alkalmaznánk, azokat vonjuk össze §3 §4 §5 segítségével egy \(\Pi.(\sigma.())\) alakra, amennyire lehet

Optimalizált kifejezésfa it is

A gráfot a bináris műveletek mentén részgráfokra bontjuk. Minden részgráf csúcsai a felbontásban szerplő műveletek (\(\cup,\;-,\;\times\))

Ha bináris művelet szorzás(\(\times\)), és az eredmény Equi-Join-nak megfelel, valamint a szorzás valamelyik ágán nincs bináris művelet, vegyüók azt is fel

az előző lépésben kapott részgráfok is fák. A kiértékelés akkor optimális, ha lentről felfelé hatjuk végre a műveleteket, azon belül tetszőleges sorrendben.