8.7. Оценка размеров результатов выполнения других операторов

Мы уже познакомились с двумя операциями, размеры результатов которых можно описать с помощью точных формул:

1) оператор проекции (projection) не изменяет количество кортежей исходного отношения;

2) оператор декартова произведения (Cartesian product) возвращает отноше­ние, размер которого равен произведению количеств кортежей отноше­ний-операндов.

Мы рассмотрели и две другие операции — выбор (selection) и соединение (join), -допускающие возможность относительно точного прогнозирования характеристик результатов. Размеры итоговых отношений, получаемых при выполнении других операторов реляционной алгебры, предсказать сколько-нибудь верно, однако, не столь просто.

8.7.1. Объединение

Размер результата объединения мультимножеств (bag union) определяется точной суммой количеств кортежей отношений-аргументов. Величина объема итогового от­ношения, возвращаемого оператором объединения множеств (set union), заключена в интервале от значения максимума из размеров операндов до суммы этих размеров. Мы предлагаем в качестве оценки использовать среднее арифметическое двух гранич­ных величин, т.е. сумму большего размера и половины меньшего размера.

8.7.2. Пересечение

Объем отношения, получаемого в результате выполнения оператора пересечения (intersection), не зависит от выбора версии оператора ("множественной" или "мультимножественной") и исчисляется значением из интервала от 0 до размера меньшего из аргументов.

Другой подход связан с интерпретацией пересечения как некоего предельного случая естественного соединения. Если подразумевается операция пересечения множеств, формула гарантирует, что ре­зультат по числу кортежей окажется не большим, нежели меньшее из двух отношений-операндов. В случае пересечения мультимножеств, однако, возможно возникновение определенных аномалий, когда оценка результата превышает размер любого из исход­ных отношений. Рассмотрим в качестве иллюстрации оператор

R(a, b) S(a, b).

От­ношения R и S состоят из двух и трех копий кортежа (0,1) соответственно. Тогда

V(R, a) = V(S, a) = V(R, b) = V(S, b)=1,

T(R) = 2 и T(S) = 3. Согласно правилу прогнозирования размера результата соединения, получим 2*3/(mах(1,1)*mах(1, 1)) = 6, хотя совершенно очевидно, что результат не может содержать более min (T(R), T(S)) = 2 кортежей.

8.7.3. Разность

При вычислении оператора разности (difference) R\S размер результата принадле­жит интервалу от T(R) до T(R) - T(S). В качестве оценки рекомендуется использовать среднее арифметическое граничных значений: T(R) - T(S) /2.

8.7.4. Удаление кортежей-дубликатов

Размер итогового отношения, возвращаемого оператором δ(R), который применя­ется к отношению R(a₁ , a₂,...,а_n), составляет V(R, (a₁ , a₂,...,а_n)). Зачастую, однако, по­добная статистическая характеристика просто недоступна, что вынуждает пользоваться приближенными оценками. В экстремальных случаях размер S(R) либо совпадает с количеством кортежей в R (т.е. R не содержит дубликатов), либо равен 1 (все кортежи R одинаковы). В качестве другого варианта значения верхней границы количества кортежей в S(R) уместно использовать максимально допустимое число различных кор­тежей, выраженное в форме произведения множителей V(R, а_i), где i = 1,2,..., п. Эта ве­личина может быть ниже в сравнении с другими оценками T(δ(T)). Существует ряд правил прогнозирования значения T(δ(T)), но мы порекомендуем следующее: вычис­лить минимум из T(R) / 2 и произведения всех V(R, а_i).