Kapslad slingkoppling

En kapslad loop-koppling är en naiv algoritm som sammanfogar två uppsättningar genom att använda två kapslade loopar . Join-operationer är viktiga för databashantering .

Algoritm

Två relationer $R$ och $S$ sammanfogas enligt följande:

     
         
             
                 algoritmen  nested_loop_join  är  för varje  tuppel  r  i  R  do  för varje  tuppel  s  i  S  gör  om  r  och  s  uppfyller kopplingsvillkoret  ger  då  tuppel <  r  ,  s  >

Denna algoritm kommer att involvera n _r *b _s + b _r blocköverföringar och n _r + b _r sökningar, där b _r och b _s är antalet block i relationerna R respektive S, och n _r är antalet tuplar i relation R .

Algoritmen körs i $O(|R||S|)$ I/Os, där $|R|$ och $|S|$ är antalet tuplar som finns i $R$ respektive $S$ och kan enkelt generaliseras för att sammanfoga valfritt antal relationer ...

för blockkapslade loop join är en generalisering av den enkla kapslade loops-algoritmen som drar fördel av ytterligare minne för att minska antalet gånger som $S$ -relationen skannas. Den laddar stora bitar av relation R i huvudminnet. För varje bit skannar den S och utvärderar sammanfogningsvillkoret för alla tuppelpar, för närvarande i minnet. Detta minskar antalet gånger S skannas till en gång per bit.

Variation för indexsammanfogning

Om den inre relationen har ett index på attributen som används i joinen kan den naiva nest loop joinen ersättas med en index join.

     
        
             algoritm  index_join  är  för varje  tuppel  r  i  R  do  för varje  tuppel  s  i  S  i indexuppslagningen  ger  ger  tuppel <  r  ,  s  >

Tidskomplexiteten för denna variation förbättras från $O(|R||S|){\text{ till }}O( |R|\log |S|)$

Se även