İç içe döngü birleştirme - Nested loop join - Wikipedia

Bir iç içe döngü birleştirme saf algoritma iç içe iki kullanarak iki kümeyi birleştiren döngüler.[1] Birleştirme işlemleri aşağıdakiler için önemlidir: veri tabanı yönetimi.

Algoritma

İki ilişki ve aşağıdaki gibi birleştirilir:

algoritma nested_loop_join dır-dir    her biri için demet r içinde R yapmak        her biri için demet s içinde S yapmak            Eğer r ve s birleştirme koşulunu sağla sonra                Yol ver tuple <r,s>

Bu algoritma n içerecektirr* bs+ br blok transferleri ve nr+ br arar, nerede br ve Bs sırasıyla R ve S ilişkilerindeki blok sayısıdır ve nr R ile ilgili tuple sayısıdır.

Algoritma çalışır I / O'lar, nerede ve içerdiği tuple sayısı ve sırasıyla ve herhangi bir sayıda ilişkiye katılmak için kolayca genelleştirilebilir ...

iç içe döngüyü engelle algoritmaya katıl[2] ek avantajlardan yararlanan basit iç içe döngüler algoritmasının bir genellemesidir. hafıza sayısını azaltmak için ilişki taranır. Ana belleğe R ilişkisinin büyük parçalarını yükler. Her parça için, S'yi tarar ve şu anda bellekte bulunan tüm tuple çiftlerindeki birleştirme koşulunu değerlendirir. Bu, yığın başına bir S'nin taranma sayısını azaltır.

Dizin birleştirme varyasyonu

İç ilişki birleşimde kullanılan özniteliklerde bir dizine sahipse, naif iç içe döngü birleşimi bir dizin birleşimiyle değiştirilebilir.

algoritma index_join dır-dir    her biri için demet r içinde R yapmak        her biri için demet s içinde S dizin aramasında yapmak            Yol ver tuple <r,s>

Bu varyasyon için zaman karmaşıklığı O (M * N) O (M * günlük N).

Ayrıca bakınız

Referanslar