Nested loop join: differenze tra le versioni

Versione delle 18:09, 19 mar 2015

Versione attuale delle 19:58, 29 gen 2020

(7 versioni intermedie di 6 utenti non mostrate)

Riga 1:

{{W|informatica|marzo 2015}}

L'algoritmoIl '''nested loop join''' (NLJ), o '''simple nested loop join''', è un algoritmo di join che unisce due set usando due cicli nidificati. Una delle due relazioni viene designata come esterna e l’altral'altra interna.

Questo algoritmo legge righe dalla prima tabella una per volta in un ciclo, passando ogni riga al ciclo nidificato che elabora la tabella successiva nel join. Questo processo viene ripetuto per ogni tabella coinvolta nel join.

Supponendo R esterna e S interna l’algoritmol'algoritmo per ogni tupla di R, che verifica le eventuali altre condizioni su R, accede a S ricercando tutte le tuple di S che soddisfano tutte le eventuali altre condizioni su S e che possono concatenarsi con le tuple di R.

Possiamo schematizzare questo comportamento con

<code>

For each tuple r in R do

For each tuple s in S do

If r and s satisfy the join condition

Then output the tuple <r,s>

</code>

=== Valutazione dei costi ===

Dato che l’algoritmol'algoritmo NLJ passa le righe dal ciclo esterno a quello interno una alla volta, tipicamente le tabelle elaborate nel ciclo più interno vengono lette molte volte.

Il costo di esecuzione è espresso come:

:C(R) x+ TR x C(S)

dove:

:C(R) è il costo di accesso a R

:TR è il numero atteso di tuple residue di R

:C(S) è il costo di accesso a S

=== Varianti ===

Esiste un algoritmo di join, chiamato ''[[block nested loop join]]'', che si differenzia da quello di nested-loop poiché i dati vengono salvati in memoria per ridurre il numero di volte che S viene scansionata.

== Bibliografia ==

* Paolo Ciaccia, Dario Mario, Lezioni di basi di dati, 2013, Editrice Esculapio, ISBN-13: 978-8874887187

* [httphttps://dev.mysql.com/doc/refman/5.6/en/nested-loop-joins.html Nested-Loop Joins] in the MySQL 5.6 Reference Manual.

== Fonti ==

* Paolo Ciaccia, Dario Mario, Lezioni di basi di dati, 2013, Editrice Esculapio, ISBN-13: 978-8874887187

{{Reflist}}

* [http://dev.mysql.com/doc/refman/5.6/en/nested-loop-joins.html Nested-Loop Joins] in the MySQL 5.6 Reference Manual.

{{Portale|informatica|ingegneria}}

[[Categoria:Terminologia informatica]]

[[Categoria:Teoria delle basi di dati]]