8.3. Выборка с условием равенства двух атрибутов

Рассмотрим отношение R(ABCD).

σ_A=B(r),

T(σ_A=B(r))=?,

V(r,A)=3, {a,b,c},

V(r,B)=4, {a,b,c ,d}.

A	B	C	D
a	a	…	…
a	b	…	…
a	c	…	…
a	d	…	…
b	a	…	…
b	b	…	…
b	c	…	…
b	d	…	…
c	a	…	…
c	b	…	…
c	c	…	…
c	d	…	…

T(r)

+ =

Рис. 8.3 – Выборка при условии равенства двух атрибутов

σ_A=B=C(r)=σ_{A=B & B=C}.

T(σ_A=B=C(r))=T(r) .

8.4. Выборка при условии неравенства двух атрибутов

T(σ_{A B}(r))=T(r)(1- ).

Количество строк при декартовом произведении двух отношений

T(r s) = T(r) T(s).

Пусть имеем два отношения R(ABCD), S(FBCDE).

Операция естественного соединения примет вид:

.

Следовательно

.

T(r) T(s)

Рис. 8.4 – Схема отношения

V(r,A), V(r,B), V(s,A),

T(r)=V(r,A), V(s,C),

V(s,D).

.

Пример. Рассмотрим три отношения со следующими статистическими характе­ристиками:

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

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

Предположим, что необходимо вычислить естественное соединение вида R S U. Один из вариантов выполнения оператора состоит в группировании (R S) U. На основании указанного выше правила T(R S) = T(R)T(S) / max (V(R, b), V(S, b)) получим 1000 * 2000 / 50, или 40000.

Далее результат R S подлежит соединению с U. Выражение оценки размера ито­гового отношения можно записать как T(R S)T(U) / max (V(R S, с), V(U, с)). В соот­ветствии с предположением о сохранности множеств значений несовпадающих атри­бутов V(R S, с) = V(S, с) = 100, т.е. при выполнении соединения ни одно из значений атрибута с не "пропадает". В этом случае прогнозируемым значением количества кор­тежей в R S U будет 40000 * 5000 / mах(100, 500) = 400000.

Выполнение операции R S U можно начать и с соединения S с U. В этом случае оценкой размера S U окажется T(S)T(U)/max(V(S,c), V(U,c)), или 2000*5000/500=20000.

Ожидаемый размер итогового отношения равен T(R)T(S U)/max (V(R,b), V(S U,b)), и с учетом допущения о сохранности множеств значений несовпадающих атрибутов, V(S U,b)= V(S, b) = 50, получим 1000 * 20000 / 50, или 400000.

8.5. Естественное соединение отношений с несколькими общими атрибутами

Теперь исследуем случай, когда Y представляет не один, а несколько атрибутов, общих для отношений R и S, подлежащих естественному соединению, R(X, Y) S(Y, Z). Для простоты рассмотрим оператор R(x, у₁, у₂) S(y₁, y₂, z). Пусть r является одним из кортежей R. Вероятность того, что r удастся соединить с определенным кортежем s от­ношения S, может быть подсчитана следующим образом.

Прежде всего зададимся вопросом, какова вероятность совпадения r и s в атрибуте y₁. Предположим, что V(R, y₁) ≥ V(S, у₁). Тогда с учетом допущения о принадлежности одного множества значений совпадающих атрибутов другому можно утверждать, что любое значение атрибута y₁ отношения S определенно присутствует в наборе значений атрибута у₁ отношения R. Следовательно, вероятность того, что кортеж s обладает тем же значением компонента у₁, что и кортеж s, равна 1/ V(R, y₁). Аналогично, если V(R,y₁)< V(S,y₁), тогда значение у₁ кортежа r должно наличествовать в S, причем веро­ятность совпадения содержимого компонентов y₁ кортежей r и s равна 1 /V(S, у₁). Ве­роятность того, что кортежи r и s согласуются в атрибуте у₁ в общем случае оценива­ется величиной 1 / max (V(R, у₁), V(S, у₁)).

Те же доводы позволяют заключить, что вероятность совпадения кортежей r и s в ком­понентах атрибута у₂ равна 1 / max (V(R, y₂), V(S, y₂)). Поскольку значения атрибутов у₁ и у₂ независимы, вероятность одновременного равенства обоих компонентов кортежей r и s представляет собой произведение двух указанных дробей. Поэтому с учетом об­щего количества различных пар кортежей R и S, равного T(R)T(S), прогнозируемое число пар кортежей, совпадающих одновременно в компонентах у₁ и у₂, равно

T(R)T(S) / (max (V(R, у₁), V(S, у₁)) * max (V(R, y₂), V(S, y₂))).

Для получения оценки размера итогового отношения, возвращаемого оператором естественного соединения в случае, когда отношения-операнды обладают произволь­ным количеством общих атрибутов, используется следующее правило:

• прогнозируемый размер отношения RsxS равен произведению значений T(R) и T(S), деленному на произведение максимумов из величин V(R, у) и V(S, у) для каждого атрибута у, общего для отношений R и S.

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

R(a, b, с) S(d, e, f),

R.b=S.d & R.c=S.e

обладают следующими статистическими характеристиками:

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

R(a, b, с)	S{d, e,J)
T(R) = 1000	T(S) = 2000
V{R, b) = 20	V(S, d) = 50
V(R, c)= 100	V(S, e) = 50

Подобный вариант соединения можно интерпретировать как естественное соеди­нение, если воспринимать атрибуты пары R.b, S.d и пары R.c, S.e как одноименные.

Тогда в соответствии с указанным выше правилом для получения оценки размера итогового отношения следует перемножить значения 1000 и 2000 и поделить произве­дение на большее из чисел 20 и 50, а затем — на большее из чисел 100 и 50, т.е. 1000 * 2000 / (50 * 100) = 400.

Пример. Вновь обратимся к предыдущему примеру, но рассмотрим третий из возможных вариантов порядка соединения, в соответствии с которым вначале выпол­няется операция R(a, b) U(c, d). Такое соединение по существу представляет собой декартово произведение, и количество кортежей в возвращаемом им отношении равно T(R)T(U)= 1000 * 5000 = 5000000. Заметим, что количество различных значений в компо­нентах атрибутов b и с этого отношения по-прежнему равно V(R,b) = 20 и V(U, с) = 500 соответственно. Для получения оценки размера отношения, получаемого при даль­нейшем соединении промежуточного результата с S(b, с), следует перемножить коли­чества кортежей в отношениях-операндах и поделить произведение как на max (V(R, b), 1/(S, b)), так и на max (V(U, с), V(S, с)), т.е. 2000 * 5000000 / (50 * 500) = 400000. Нетрудно убедиться, что и для третьего варианта соединения остается справедливой та же оценка, которая получена в примере для двух других.