Alăturare buclă imbricată
Îmbinarea buclei imbricate (NLJ), sau simpla îmbinare buclă imbricată , este un algoritm de îmbinare care unește două seturi folosind două bucle imbricate. Una dintre cele două relații este desemnată ca externă, iar cealaltă internă.
Acest algoritm citește rânduri din primul tabel pe rând, într-o buclă, trecând fiecare rând în bucla imbricată care procesează următorul tabel din îmbinare. Acest proces se repetă pentru fiecare tabel implicat în alăturare. Presupunând că R extern și S intern, algoritmul pentru fiecare tupl de R, care verifică orice alte condiții de pe R, accesează S căutând toate tuplele de S care îndeplinesc toate celelalte condiții de pe S și care se pot concatena cu tuplele lui A Putem schematiza acest comportament cu
Pentru fiecare tupl r în R do Pentru fiecare tuplu din S faceți Dacă r și s îndeplinesc condiția de asociere Apoi scoateți tuplul <r, s>
Evaluarea costurilor
Deoarece algoritmul NLJ trece rânduri de la bucla exterioară la bucla interioară unul câte unul, de obicei tabelele procesate în bucla interioară sunt citite de multe ori. Costul de execuție este exprimat ca:
- C (R) + TR x C (S)
unde este:
- C (R) este costul accesării R.
- TR este numărul așteptat de tupluri reziduale de R.
- C (S) este costul accesării S
Variante
Există un algoritm de asociere, numit asociere cu buclă imbricată , care diferă de cel al buclei imbricate prin faptul că datele sunt salvate în memorie pentru a reduce numărul de scanări ale S.
Bibliografie
- Paolo Ciaccia, Dario Mario, Lecții în baze de date, 2013, Editrice Esculapio, ISBN 978-8874887187
- Nested-Loop se alătură în Manualul de referință MySQL 5.6.