Курсовая работа: Разработка программы запросов

A ´ B

Отношение с тем же заголовком, что и у отношения A, и телом, состоящим из кортежей, значения атрибутов которых при подстановке в условие C дают значение ИСТИНА, называется выборкой. С представляет собой логическое выражение, в которое могут входить атрибуты отношения A и/или скалярные выражения.

Синтаксис:

s (A, C )

Отношение с заголовком (X, Y, …, Z) и телом, содержащим множество кортежей вида (x, y, …, z), таких, для которых в отношении A найдутся кортежи со значением атрибута X равным x, значением атрибута Y равным y, …, значением атрибута Z равным z, называется проекций отношения А. При выполнении проекции выделяется «вертикальная» вырезка отношения-операнда с естественным уничтожением потенциально возникающих кортежей-дубликатов.

Синтаксис:

A [X, Y, …, Z]

или

p _A {x, y, …, z}

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

Синтаксис:

s ((A ´B) , C)

Важными с практической точки зрения частными случаями соединения являются эквисоединение и естественное соединение.

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

Операция естественного соединения (операция NATURE JOIN) применяется к двум отношениям, имеющим общий атрибут (простой или составной). Этот атрибут в отношениях имеет одно и то же имя (совокупность имен) и определен на одном и том же домене (доменах).

Результатом операции естественного соединения является отношение R, которое представляет собой проекцию эквисоединения отношений R1 и R2 по общему атрибуту на объединенную совокупность атрибутов обоих отношений.

Внешнее соединение - расширяет естественное соединение, гарантируя, что каждая запись из обеих исходных таблиц будет представлена в результирующей таблице хотя бы один раз. Внешнее соединение выполняется в два этапа. Сначала выполняется естественное соединение. Затем, если какая-либо строка одной из исходных таблиц не подходит ни к какой строке второй таблицы, она включается в таблицу соединения, а все дополнительные столбцы заполняются пустыми значениями. Обозначение: OUTER JOIN(A,B). Возможно также левое и правое соединения, при которых в результирующую таблицу включаются только строки из одной таблицы.

Отношение с заголовком (X1, X2, …, Xn) и телом, содержащим множество кортежей (x1, x2, …, xn), таких, что для всех кортежей (y1, y2, …, ym) Î B в отношении A(X1, X2, …, Xn, Y1, Y2, …, Ym) найдется кортеж (x1, x2, …, xn, y1, y2, …, ym), называется делением отношений.

Синтаксис:

A / B

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

Один и тот же результат запроса может быть получен СУБД различными способами (планами выполнения запросов), которые могут существенно отличаться как по затратам ресурсов, так и по времени выполнения. Задача оптимизации заключается в нахождении оптимального способа.

Обычно, говоря про оптимизацию в реляционных СУБД, имеют в виду аспект оптимизации запросов, т.е. такой способ выполнения запросов, когда по начальному представлению запроса путем его синтаксических и семантических преобразований вырабатывается процедурный план выполнения запроса, наиболее оптимальный при существующих в базе данных управляющих структурах. Соответствующие преобразования начального представления запроса выполняются специальным компонентом СУБД - оптимизатором, и оптимальность производимого им плана запроса носит достаточно условный характер: план оптимален в соответствии с критериями, заложенными в оптимизатор; при этом, конечно, возможны отклонения от реальной оптимальности.

Оптимизатор по правилам (rule-based) — оптимизатор, основанный на анализе жестко заданных правил. Этот оптимизатор выбирает методы доступа на основе предположения о статичности базы данных и в соответствии с заданной системой правил выбора методов доступа.

Оптимизатор по стоимости (cost-based optimizer) — оптимизатор, основанный на анализе накладных затрат системы. Для этого оптимизатора выбор метода доступа основан на хранимой внутренней статистике. Под статистикой понимаются точные или аппроксимированные сведения о распределении значений данных в таблицах. СУБД может собирать статистику двумя способами: путем оценки, основанной на произвольной выборке данных и путем точных вычислений.

Под методом доступа (access path) подразумевается вариант алгоритма доступа, а под планом выполнения (execution plan) — последовательность выполняемых действий, которые обеспечивают выбранные методы доступа. Существует два основных вида оптимизаторов:

В реляционной СУБД оптимальный план выполнения запроса - это такая перестановка всех исходных выбираемых таблиц, реляционное соединение которых в выбранной последовательности, представленное в процедурном виде, может быть выполнено за минимальное число операций.

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

Изменение SQL-выражений на основе знаний о данных, индексах, связях таблиц для повышения эффективности их выполнения, называется коррекцией запросов (query rewriting). Изменение предложений SQL отличается от написания новых предложений. Для того чтобы эффективно переписывать запросы, необходимо в течение некоторого времени накопить знания о системе. Сюда относятся сведения о том, какие предложения SQL нуждаются в переписывании в связи с их частым использованием или использованием ими значительных ресурсов, какие данные ими обрабатываются, каковы характеристики и распределение этих данных, какие логические условия в выражениях можно убрать или трансформировать в связи с логикой функционирования системы. При решении задач оптимизации проблемных запросов необходимо следовать следующим рекомендациям:

Во-первых, при необходимости доступа к значительной части строк какой-либо таблицы полное сканирование (full scan) является более эффективным, чем использование индексов. Граница применения данных методов доступа в общем случае составляет 5-10% записей таблицы, к которым обращается запрос. Дело в том, что для сканирования индекса и извлечения строки требуются, по крайней мере, две операции чтения для каждой строки (одна — для чтения индекса, другая для чтения данных из таблицы). А при полном сканировании таблицы для извлечения строки требуется только одна операция чтения. При доступе к большому количеству строк становится очевидной неэффективность использования индекса по сравнению с полным сканированием таблицы, при котором строки считываются непосредственно из таблицы. Для небольших таблиц полное сканирование практически всегда оказывается эффективнее использования индекса.