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

Страницы работы

2 страницы (Word-файл)

Содержание работы

3.3.3.

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

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

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

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

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

3.3.4

Дано

R1 (A1, A2); R1 имеет мощность = 10x103 кортежей. Причем A2=11-15 кортежей.

            R2 (A3, A4); R2 имеет мощность = 20х103 кортежей и A3=55-50 кортежей

Найти: 1) R3 = R1(A1,A2) (X) R2(A3,A4)

            2)Все кортежи R3, которые имеют А2=11 и А3=55

R3

А1

А2

А3

А4

11

55

11

55

            Мощность декартова произведения R3= 10x103x20x103 = 200x106 – кортежей, т.е для реализации запроса необходимо просмотреть 200х106 кортежей.

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

σА2=11˄А3=55 (R3) необходимо выполнить 200х106 обращений к отношению R3 для просмотра всех кортежей.

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

σA2=11 ˄ A3=55 (R3)  =  σA2=11 (R1) (X) σA3=55 (R2)

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

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

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

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

4)  Общее количество обращений для реализации выражения R(A1,A2,A3,A4)=  σA2=11 (R1) (X) σA3=55 (R2)  =  20Х103+10Х103+750 ≈ 30Х103 обращений.

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

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

Похожие материалы

Информация о работе