Оценка числа кортежей в промежуточной таблице Q

Число кортежей оценивается с помощью следующей формулы:

T(Q) = T(R)·p , (5.7)

где

Q=s_F(R) – промежуточной таблица, соответствующая подзапросу Q,

T(Q) – оценка числа кортежей в промежуточной таблице Q,

T(R) – общее число кортежей в исходной таблице R,

p – вероятность того, что кортеж из R удовлетворяет условию поиска F.

Для расчета вероятности p можно воспользоваться следующими рекурсивными выражениями:

1. Пусть F = f₁ AND f­₂ . Тогда

p = p₁p₂ ,

где p_i – вероятность того, что запись из R удовлетворяет подусловию f_i (i=1,2).

2. Пусть F = f₁ OR f­₂ . Тогда

p = p₁ + p₂ – p₁p₂ .

3. Пусть F = NOT f₁ . В этом случае

p = 1 – p₁ .

Если в приведенных выше случаях 1–3 f_i – подусловие по какому-либо атрибуту "а", то вероятность p_i рассчитывается по следующей формуле:

,

где k – мощность атрибута в подзапросе (см. формулу (5.6)),

I(R,a) – мощность атрибута "а" в таблице R.

Ниже приведён пример расчёта числа кортежей в промежуточной таблице.

Пусть таблица R включает атрибуты (a, b, c). Число кортежей T(R) = 1000. Мощности атрибутов: I(R,a) = 5, I(R,b) = 10, I(R,c) = 2. Для простоты полагаем, что a, b, c – натуральные положительные числа.

Пусть задано условие выбора записей таблицы R:

F = (a < 3 OR b ³ 5) AND c = 2

Требуется оценить число записей, удовлетворяющих условию F.

Решение.

1. f₃ = f₁ OR f­₂

2. F = f₃ AND f­₄

– вероятность того, что запись из R удовлетворяет условию F.

3. T(Q) = T(R)·p = 1000·0,38 = 380 – оценка числа записей, удовлетворяющих условию F.