8.7.5. Группирование и агрегирование

Предположим, что необходимо оценить размер отношения, возвращаемого при вычислении оператора группирования (grouping) γ_L(R). Если статистическая характери­стика вида V(R, (g₁, g₂,…, g_k)), где g_i, i = 1,2,..., k, — группирующие атрибуты из списка L, доступна, в качестве оценки следует использовать именно это значение. Однако в реальной ситуации уповать на такую возможность довольно трудно, поэтому необ­ходимо изыскивать альтернативный способ прогнозирования. Количество кортежей в γ_L(R)совпадает с числом групп k. В одном "крайнем" случае итоговое отношение способно содержать единственную группу, а в другом — по группе на каждый кортеж R. Как и в случае с оператором удаления кортежей-дубликатов S, в качестве верхней границы количества групп правомочно использовать произведение значений V(R,g_i), отвечающих группирующим атрибутам из списка L, а искомую оценку вычислять как минимум из T(R) /2 и произведения всех V(R, gi).

8.8. Свод формул для сравнительного расчета количества записей результата выполнения операций реляционной алгебры

1.Выборка.

,

где

, (1)

N-количество отношений в конъюнкции.

Для

A=a. k_i=V(r, A) ,

A > a, k_i=3,

A=B, k_i = max(V(r,A), V(r,B)),

A ≠ a, k_i = V(r,A) / (V(r,A)+1),

A ≠ B, k_i = max(V(r, A),V(r,B)) / (V(r,A)+1),

,

,

.

k_j считается по формуле (1).

2. Проекция.

T(π_x(r))=T(r).

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

.

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

.

5. Разность.

.

6. Декартово произведение.

.

7. Естественное соединение.

,

где N – количество одноименных атрибутов в естественном соединении,

l – одноименные атрибуты.

8. Тетта-соединение.

,

N – количество отношений в формуле D,

k_i берется из формулы (1).

9. Удаление дубликатов.

,

где К – количество атрибутов в r.

10. Агрегирование по атрибутам из списка L.

,

где L – список индексов атрибутов, по которым осуществляется группировка.

11.

,

S(A) – отношение из одного атрибута А.

8.9. Тождественные преобразования для операций реляционной алгебры

1) .

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

Рис. 8.5 – Дерево запроса

T(g₁)+T(g₂)>0.

2) .

Рис. 8.6 – Дерево запроса

3) .

Рис. 8.7 – Дерево запроса

Рис. 8.8 – Дерево запроса

T(g₁)=T(r s)=max(T(r), T(s))+ min(T(r),T(s))=T(r)+ T(s) или T(r)+T(s),

,

,

а) T(r)+ T(s)> .

б) .

4) .

Рис. 8.9 – Дерево запроса

Рис. 8.10 – Дерево запроса

T(g₁)=T(r s)= min(T(r),T(s))= T(r) или T(s).

.

5) .

6) .

7) .

8) .

8.10. Алгебраические законы и планы запросов

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