15. Алгоритмы реализации соединений отношений в SQL

Для того, чтобы обеспечить целостность, мы будем заниматься денормализацией (создавать множество связанных таблиц).

Это приводит к снижению производительности.

WARNING

Соединение таблиц - это дорого!

TIP

Говорить об эффективности этих алгоритмов - сложно. Хоть 2-ой потенциально и работает за O(n), но все может изменится из-за сортировки (а может и не изменится, зависит от исходных данных). Современные СУБД сами принимают решения, какой алгоритм использовать для достижения эффективности

1. Вложенные циклы

for (int i = 0; i < R.Count; ++i)
{
    for (int j = 0; j < S.Count; ++j)
    {
        if (R[i].atr != S[j].atr) continue;
        Console.WriteLine(r + s);
    }
}

for r in R
    for s in S
        if (r.atr == s.atr)
            print(r + s)

2. Через слияние

R.sort(atr)
S.sort(atr)

while not EndOF(S) and not EndOF(R)
    if (r.atr < s.atr)
        next(R)
    if (r.atr = s.atr)
        print(r + s)
        next(R)
    if (r.atr > s.atr)
        next(S)