Общий обзор методов обработки запросов

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

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

Оптимизация запросов

Основные методы оптимизации основываются на статических показателях накапливаемых для БД (кардинальность отношений, степень отношений,наличие индексов, их число, размер блоков и др.)

Пример: необходимо определить имена всех менеджеров, которые работают в гродненском отделе компании.

SELECT *

FROM Staff, Branch b

WHERE s.bno=b.bno AND

(s.position= ‘Менеджер’ AND b.city= ‘Гродно’);

этот запрос можно представить в терминах реляционной алгебры в 3-х вариантах.

1. используем выборку:

σ(s.position=‘Менеджер’ Ù b.city= ‘Гродно’) ÙStaff.bno Branch.bno(Staff x Branch)

2.  эквивалентный вариант:

σ position=‘Менеджер’ Ù b.city= ‘Гродно’

3. (Staff join Staff.bno=Branch.bno Branch);

(σ position=‘Менеджер’ (Staff)) join Staff.bno=Branch.bno

(σcity= ‘Гродно’ (Branch));

в таблице Staff – 1000 кортежей, в Branch – 50.

Предположим, что в таблице Staff 1000 кортежей, «Отделение» - 50.

5 из 50 менеджеров находятся в Гродно. Будем считать, что отношение не имеет индексов и никаких ключей сортировки. Сравнение будет производиться с точки зрения количества операции доступа к диску. Операция произведение потребуется 1000+50 операций для чтения исходных отношений. Затем потребуется 1000*50 операций, для того чтобы проверить заданное условие.

Общая стоимость этого захода будет:

(1000+50)+(1000+50)=1050+2*50000=101650

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

1000+2*(1000+50)=3100

и 3-ий вариант идет вначале выборка 1000 операций. Результирующий набор будет состоять не более чем из 50 строк.

Branch – 50 операций.

Результирующая таблица будет состоять из 5 строк.

Для того чтобы сделать операцию соединения надо: 50+5 операций.

1000+2*50+5+50+5=1160 операций.

Наиболее оптимальный 3-ий вариант. Если будет больше число картежей, то будет больше разница между первым и третьим запросом.

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

Общая схема оптимизации запроса можно представить следующим образом.

			запрос

 

Время компиляции

Время выполнения

Сгенерирует код

Выражение реляционной алгебры

Системный каталог

Основная БД

Статистика БД

запрос

План выполнения

Фактическое Выполнение запроса

Генерация кода

Декомпозиция запроса

Оптимизация запроса

 

 

 

Динамическая оптимизация выполнения при каждом вызове запроса статически предусматривает однократное выполнение.

Рассмотрим основные этапы выполнения запроса

48. Декомпозиция запросов.

Назначение: преобразование запроса на языки высокого уровня в выражение реляционной алгебры с последней проверкой его синтаксической и семантической корректности. Т.е. на этом этапе выполняется анализ, нормализация, семантический анализ, упрощение и реструктуризация запроса.

Анализ - проведение лексического и синтаксического анализа. Уточняется присутствуют ли все определения для указанных в запросе отношений и атрибутов.

Например:

 SELECT Staff_no – такого поля нет

FROM Staff

WHERE position>10 – не соответствует тип

Затем строиться дерево запроса для каждого базового отношения создаются листовые узлы. Листовые создаются для каждого промежуточного отношения, которое является результатом выполнения некоторых операций реляционной алгебры. Корень дерева – результат. Результат выполняется от листовых узлов к корню дерева.

Пример:

SELECT *

FROM staff_s, branch_b

WHERE s.sno=b.bno

AND (s.position= ‘Менеджер’ AND b.city = ‘Гродно’) 

Схема

 

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

Стадия нормализации выполняется с целью упрощения манипулирования данными. Здесь предикаты образуются в одну из 2-ух стандартных форм.

1. конъюнктивная. Это последовательность конъюнкции, связанных между собой операциями конъюнкции AND (Ù). Каждая конъюнкция может содержать один или более терма, соединенных операторами дизъюнкции OR (Ú). Например, (position = ‘инспектор’ Ú salary Ю 200000) Ù s.sno=b.bno

2. дизъюнкция. Это последовательность соединений, связанных между собой операциями дизъюнкции. Каждая дизъюнкция может содержать один или 2 терма, соединенных операторами конъюнкции. Пример, (position = ‘Менеджер’ Ù bno = BS) Ú (salary > 200000 bno=33).

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

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

Position = ‘ Инспектор’Ù Position = ‘Менеджер ’

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

Процедура упрощения использует правила эквивалентности реляционной алгебры.

Р Ù р = р

Р Ù false=false

P Ù (-p)=false

P Ù true =p

P Ú p=p

P Ú (-p)=true

P Ú false =p

P Ú true=true

Реструктуризация запроса запрос преобразуется в такую форму, которая позволяет обеспечить наиболее эффективное его выполение.

49. Правила преобразований операций реляционой алгебры

Для обеспечения наибольшей эффективности выполнения рестр запроса выполняется с помощью правил преобразования операций реляционной алгебры. Эти правила используются для реструктуризации дерева реляционной алгебры, которое строилось в процессе декомпозиции запроса. Правила:

1.Операция выборки с коньюктивным предикатом может быть преобразована в последовательносьт операций выборки по членам коньюнкции. Это каскадная выборка.

2.Правило коммутативности выбора

3.Правило коммутативности операций выборки и проекции

4.Правило коммутативности операций тетта – соединения и декартового произведения. Отношения могут меняться местами

5.Правило коммутативности операций выборки и тетта-соединения.

6.Правило коммутативности операций проекции и тетта-соед

7.Правило коммутативности операций объединение и пересечение

8.Правило коммутативности операций выборки и объединения, пересечения, разности.

9.Правило коммутативности операций проекции и объединения

10.Правило ассоциативности операций тетта соед и дек пр

11.Правило ассоциативности операций обединения и пересечения

12.В последовательности выполняются только опреции проекции

 

Основные стратегии эвристической обработки запроса

Во многих СУБД для выбора стратегии обработки запросов используются те

или иные эвристические правила.

1. Выполнение операций выборки на самых ранних этапах обработки. (Сокращается время обработки)

2. Объединение в одну операцию соединения операции декартова произведения и следующей за ней операции выборки, предикат которой представляет условие соединения.

3. Использование свойства ассоциативности бинарных операций для переупорядочения листовых узлов таким образом, что лист-узлы с наиболее ограничительными операциями выборки будут выполняться в первую очередь.

4. Как можно более раннее выполнение операций проекции.

5. Однократное вычисление общих выражений.

 

 

Концепция хранилищ данных

КХД базируется на усовершенствовании технологий БД и предусматривает специальные средства упрощенного процесса хранения хранения информации. Эта технология базируется на инструментах опреций аналитической обработки (OLAP-технология) и инструментах разработки данных (data mining). ХД – это предметно-ориентированный, интегрированный, привязанный ко времени и неизменяемый набор данных, который предназначен для поддержки принятия решений. В этой концепции указываются следующие характеристики данных: