8.6. Соединение нескольких отношений

Рассмотрим, наконец, общий случай естественного соединения:

S = R₁ R₂ … R_n.

Предположим, что атрибут А присутствует в схемах k отношений R, и количества раз­личных значений компонентов А в этих k отношениях — т.е. величины V(R₁, A), где i=1,2,..., k, — равны v₁ ≤v₂≤ …≤v_k в порядке от меньшего к большему. Допустим, что в каждом из к отношений выбрано по одному кортежу. Какова вероятность того, что все эти кортежи совпадают в атрибуте А?

Для получения ответа на вопрос рассмотрим кортеж t₁, выбранный из отношения с наименьшим количеством v₁ различных значений атрибута А. В соответствии с допущением о принадлежности одного множества значений совпадающего атрибута другому, каждое из v₁ значений можно найти в компонентах А кортежей всех других k-1 отношений. Обратимся к отношению, содержащему v_i различ­ных значений атрибута А. Выбранный из этого отношения кортеж t_i совпадает с кортежем t₁ в атрибуте А с вероятностью 1 / v₁. Поскольку подобное утверждение верно для всех

i=2,3,...,k, вероятность того, что все k кортежей совпадут в атрибуте А, равна 1 / (v₂ v₃ … v_k).

Теперь мы можем сформулировать правило прогнозирования размера итогового отноше­ния, возвращаемого оператором соединения с произвольным числом аргументов:

• перемножить количества кортежей во всех отношениях-операндах R_i, и поделить полученное произведение на все величины V(R_i, А), кроме наименьшей, для каждого атрибута А, присутствующего, как минимум, в двух отношениях.

Аналогичным образом можно оценить количество различных значений атрибута А в отношении, полученном в результате соединения: согласно допущению о принадлежности одного множества значений совпадающего атрибута другому, эта величина равна минимальному из значений V(R_i, A).

Пример. Рассмотрим операцию соединения R(a, b, с) S(b, с, d) U(b, e) при ус­ловии, что отношения-операнды обладают статистическими характеристиками, приве­денными в таблице ниже. Для получения оценки количества кортежей в итоговом отно­шении вначале перемножим размеры отношений R, S и U: 1000 * 2000 * 5000. Затем отыщем атрибуты, присутствующие в схемах нескольких отношений: это b, объявлен­ный в схемах всех трех отношений, и с, содержащийся в двух. Разделим полученное выше произведение на два самых крупных значения из числа V(R, b), V(S, b) и V(U, b), т.е. на 50 и 200, и на более крупное из двух значений, V(R, с) и V(S, с), т.е. на 200. Оценка, таким образом, примет вид

1000 * 2000 * 5000 / (50 * 200 * 200) = 5000.

Таблица 8.3 – Характеристики отношений

R(a, b, с)	S(b, ,с d)	U(b, e)
T(R) = 1000	T(S) = 2000	T(U) = 5000
V(R, a) = 100
V(R, b) - 20	V(S, b) = 50	V(U, b) = 200
V(R, c) = 200	V(S,c)= 100
	V(S, d) = 400
		V(U, e) = 500

Наконец, в качестве оценок количеств различных значений каждого из атрибутов итогового отношения можно использовать минимальные из величин таких количеств по каждому отношению-операнду: для атрибутов а, b, с, d и е эти оценки равны 100, 20, 100, 400 и 500 соответственно.

Принимая во внимание два допущения — о принадлежности одного множества зна­чений совпадающего атрибута другому и о сохранности множеств значений несовпа­дающих атрибутов, можно сформулиро­вать любопытное и полезное свойство рассмотренного выше правила прогнозирования.

• Независимо от способа группирования и упорядочения аргументов выражения естественного соединения п отношений, правило, применяемое к каждому частному соединению отдельно, дает в сумме тот же результат, что и в случае применения к соединению всех n отношений.

Приведенные примеры содержат образцы практического ис­пользования этого правила с привлечением трех вариантов группирования для соеди­нения трех отношений, включая случай, когда соединение по существу сводится к декартову произведению.