Összekapcsolás N táblával
Tip
Gyors recap, a csokornyakkendő(\(\Join\)) kommutatív és asszociatív
\[
(A\Join B)\Join C = A \Join (B\Join C) \qquad A\Join B = B \Join A
\]
- Válassz olyan sorrendet, hogy a köztes eredmények mérete minimális legyen
- I/O és számolásban legyen hatékony
- Ha \(A\Join B\) kissebb, mint \(B\Join C\), akkor \((A\Join B)\Join C\) legyen a sorrend
Alternatív kritériumok
- Háttértár hozzáférés
- CPU
- Válaszidő
- Hálózat
Válaszd meg az összekapcsolási fa alakját
Asszociativitás
- Egyenértékű az összekapcsolások lehetséges zárójelezési permutációjával
- \(T(1) = 1\)
- \(T(n) = \underset{i}{\overset{n}{\sum}}~T(i)\,T(n-i)\)
- pl.: \(T(6) = 42 (=T(1)*T(5)+T(2)*T(4)+T(3)*T(3)+T(4)*T(2)+T(5)*T(1))\)
Permutáld a relációkat
- \(n!\) permutáció
Quick math, akkor ha 6 táblát akarunk összekapcsolni, annak a fának 42 féle alakja lehet, és 30240 sorrendben lehet kapcsolni, happy huntin'
Főbb alakok
No D2?
Kotlin was eeby and sleepy when this note happened, text Kotlin if you miss a D2 diagram for this section
The secret code is "GT egy cukrász", he'll know what to do
Left-deep Tree
- \(((A\Join B)\Join C) \Join D\)
- Jobboldal mindig reláció, nem előző kapcsolás eredménye
- Általában a bal-mély fák "elég jók"
- Kissebb a keresési tér
- Egyes kapcsolási algoritmusoknál hatékonyabbank bizonyul
- ha a relációk méretben rendezettek
- Pipeline elvégezhető
- Kerüli a köztes számítások materializálását (többet tud a memóriában dolgozni)
jobbra is működik
Bushy Tree
- \((A\Join B)\Join (C\Join D)\)
- Párhuzamosítható
- Sem jobbra, sem balra nem mély
Legjobb kapcsolási terv keresése
- Lássuk be, hogy a faktoriális lehetőséget egyesével nem tudjuk megnézni
- Dinamikus programozás ✨
- Számold ki a legjobb tervet
(k-1)magas összekapcsolási fára, hogy megtudd akmagas fa legjobb tervét
- Számold ki a legjobb tervet
- Mohó heurisztikus algó
- Iteratív dinamikus programozás ✨✨
Dynamic my asspirin
\(\text{BestPlan}(A,B,C,D,E) = \min\{\\ \quad\text{BestPlan}(A,B,C,D) \Join E,\\ \quad\text{BestPlan}(A,B,C,E) \Join D,\\ \quad\text{BestPlan}(A,B,D,E) \Join C,\\ \quad\text{BestPlan}(A,C,D,E) \Join B,\\ \quad\text{BestPlan}(B,C,D,E) \Join A\\ \}\)
Komplexitás
- Hát, visszaadja a legjobb sorrendet, de ahhoz tudnunk kell az összes [1..n] magas fáét is...
- Idő: \(O(n\times 2^n)\)
- Tár: \(O(2^n)\)
- Exponenciális méretű, de 10 táblát meghaladó összekapcsolás ritka
Selinger algo
Jelölések
OPT({R1, R2, R3})- Optimális terv \(R_1\Join R_2\Join R_3\) elvégzésére
T({R1, R2, R3})- Rekordok száma \(R_1\Join R_2\Join R_3\) eredményében
Actual algo
\[
\text{OPT}(\{R_1, R_2, R_3\}) = \min\begin{cases}\text{OPT}(\{R_1, R_2\}) + \text{T}(\{R_1, R_2\}) + \text{T}(R_3) \\ \text{OPT}(\{R_2, R_3\}) + \text{T}(\{R_2, R_3\}) + \text{T}(R_1) \\ \text{OPT}(\{R_1, R_3\}) + \text{T}(\{R_1, R_3\}) + \text{T}(R_2) \\ \end{cases}
\]
Ez csak az egyszerű költségmodellel működik