Стратегии вычислений

3.3.3.

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

            Этот процесс-выбор эффективной стратегии вычислений выполняет оптимизатор на уровне транслятора.

            Оптимизатор использует определенные правила и законы преобразования реляционных выражений

• Правила выборки и проекции
• Распределительный закон
• Законы коммутативности и ассоциативности
• Семантические преобразования.

Рассмотрим пример оптимизации запроса.

3.3.4

Дано

R₁ (A₁, A₂); R₁ имеет мощность = 10x10³ кортежей. Причем A₂=11-15 кортежей.

            R₂ (A₃, A₄); R₂ имеет мощность = 20х10³ кортежей и A₃=55-50 кортежей

Найти: 1) R₃ = R₁(A₁,A₂) (X) R₂(A₃,A₄)

            2)Все кортежи R₃, которые имеют А₂=11 и А₃=55

R3

А1	А2	А3	А4
	11	55
	11
		55

            Мощность декартова произведения R₃= 10x10³x20x10³ = 200x10⁶ – кортежей, т.е для реализации запроса необходимо просмотреть 200х10⁶ кортежей.

            Для реализации селекции

σА₂=11˄А₃=55 (R₃) необходимо выполнить 200х10⁶ обращений к отношению R₃ для просмотра всех кортежей.

Введем эквивалентное преобразование:

σA₂=11 ˄ A₃=55 (R₃)  =  σA₂=11 (R₁) (X) σA₃=55 (R₂)

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

1)  Для реализации σА₂=11 (R₁) – необходимо реализовать 10Х10³ обращений к отношению R₁

2)  Для реализации σА₃=55 (R₂) – необходимо реализовать 20Х10³ обращений к отношению R₂

3)  Для получения декартова произведения необходимо получить еще 15Х50 = 750 обращений

4)  Общее количество обращений для реализации выражения R(A₁,A₂,A₃,A₄)=  σA₂=11 (R₁) (X) σA₃=55 (R₂)  =  20Х10³+10Х10³+750 ≈ 30Х10³ обращений.

А в 1 случае имеем 200х10⁶ обращений, т.е мы получаем за счет оптимизации запросов выигрыш на 4 порядка.

      Этот пример дает представление об оптимизации запросов, которая используется в языке SQL.