Операция естественного соединения (операция 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
Один и тот же результат запроса может быть получен СУБД различными способами (планами выполнения запросов), которые могут существенно отличаться как по затратам ресурсов, так и по времени выполнения. Задача оптимизации заключается в нахождении оптимального способа.
Обычно, говоря про оптимизацию в реляционных СУБД, имеют в виду аспект оптимизации запросов, т.е. такой способ выполнения запросов, когда по начальному представлению запроса путем его синтаксических и семантических преобразований вырабатывается процедурный план выполнения запроса, наиболее оптимальный при существующих в базе данных управляющих структурах. Соответствующие преобразования начального представления запроса выполняются специальным компонентом СУБД - оптимизатором, и оптимальность производимого им плана запроса носит достаточно условный характер: план оптимален в соответствии с критериями, заложенными в оптимизатор; при этом, конечно, возможны отклонения от реальной оптимальности.
Оптимизатор по правилам (rule-based) — оптимизатор, основанный на анализе жестко заданных правил. Этот оптимизатор выбирает методы доступа на основе предположения о статичности базы данных и в соответствии с заданной системой правил выбора методов доступа.
Оптимизатор по стоимости (cost-based optimizer) — оптимизатор, основанный на анализе накладных затрат системы. Для этого оптимизатора выбор метода доступа основан на хранимой внутренней статистике. Под статистикой понимаются точные или аппроксимированные сведения о распределении значений данных в таблицах. СУБД может собирать статистику двумя способами: путем оценки, основанной на произвольной выборке данных и путем точных вычислений.
Под методом доступа (access path) подразумевается вариант алгоритма доступа, а под планом выполнения (execution plan) — последовательность выполняемых действий, которые обеспечивают выбранные методы доступа. Существует два основных вида оптимизаторов:
В реляционной СУБД оптимальный план выполнения запроса - это такая перестановка всех исходных выбираемых таблиц, реляционное соединение которых в выбранной последовательности, представленное в процедурном виде, может быть выполнено за минимальное число операций.
В связи с оптимизацией запросов существует достаточное количество проблем: проблемы преобразований запроса к более эффективному непроцедурному представлению (логическая оптимизация), проблемы выбора набора альтернативных процедурных планов выполнения запроса, проблемы оценок стоимости выполнения запроса по выбранному плану и т.д.
Изменение SQL-выражений на основе знаний о данных, индексах, связях таблиц для повышения эффективности их выполнения, называется коррекцией запросов (query rewriting). Изменение предложений SQL отличается от написания новых предложений. Для того чтобы эффективно переписывать запросы, необходимо в течение некоторого времени накопить знания о системе. Сюда относятся сведения о том, какие предложения SQL нуждаются в переписывании в связи с их частым использованием или использованием ими значительных ресурсов, какие данные ими обрабатываются, каковы характеристики и распределение этих данных, какие логические условия в выражениях можно убрать или трансформировать в связи с логикой функционирования системы. При решении задач оптимизации проблемных запросов необходимо следовать следующим рекомендациям:
Во-первых, при необходимости доступа к значительной части строк какой-либо таблицы полное сканирование (full scan) является более эффективным, чем использование индексов. Граница применения данных методов доступа в общем случае составляет 5-10% записей таблицы, к которым обращается запрос. Дело в том, что для сканирования индекса и извлечения строки требуются, по крайней мере, две операции чтения для каждой строки (одна — для чтения индекса, другая для чтения данных из таблицы). А при полном сканировании таблицы для извлечения строки требуется только одна операция чтения. При доступе к большому количеству строк становится очевидной неэффективность использования индекса по сравнению с полным сканированием таблицы, при котором строки считываются непосредственно из таблицы. Для небольших таблиц полное сканирование практически всегда оказывается эффективнее использования индекса.
Во-вторых, на различных этапах выполнения запросов следует максимально использовать результаты предыдущих этапов. Например, если результирующий набор данных требуется отсортировать по значениям некоторого столбца, то при выполнении операции соединения таблиц можно указать способ выполнения этой операции, при котором будет проведена сортировка этих значений. Полученные результаты будут использованы при окончательной сортировке.
В-третьих, при использовании различных видов подзапросов на основе знаний о данных следует учитывать особенности вычисления специальных предикатов и применения операторов теоретико-множественных операций. Например, оператор MINUS может выполняться гораздо быстрее, чем запросы с WHERE NOT IN (SELECT) или WHERE NOT EXISTS.
Помимо таких, достаточно очевидных способов улучшения качества запросов, можно использовать другие. Как правило, на основе опыта работы с конкретной базой данных у каждого пользователя формируется свой стиль написания оптимальных SQL-выражений.
Можно представить два стиля диаграмм запросов — полные и упрощенные. Полные диаграммы включают все данные, которые потенциально могут относиться к проблеме настройки. Упрощенные диаграммы более качественные и не содержат данных, которые обычно не требуются [Дэн Тоу].
Ниже показан простой запрос с одним соединением, иллюстрирующий все значимые элементы диаграммы запроса.
SELECT D.DepartmentJIame. E.LastJIame. E.Firstjlame FROM Employees E. Departments 0 WHERE E.Department_Id=D.Departmentjd
AND E.Exempt_Flag='Y'
AND D.US_Based_Flag='Y';
В математических терминах то, что показано на рис. 1.Х, является направленным графом. Это набор узлов и связей, причем связей часто обозначаются стрелками, указывающие направление. Узлы на этой диаграмме представлены буквами Е и D. Рядом с узлами и обоими концами каждой связи есть числа, которые указывают дополнительные свойства узлов и связей. В терминах запроса можно интерпретировать эти элементы диаграммы следующим образом.
Узлы
Узлы представляют таблицы или псевдонимы таблиц в разделе FROM — в примере это псевдонимы Е и D. Для удобства можно сокращать названия таблиц или псевдонимов, если это не вызывает двусмысленности или недопонимания.
Связи
Связи представляют соединения между таблицами, а направленная связь обозначает, что соединение гарантированно получит уникальные значения в той таблице, на которую указывает связь. В данном случае DepartmentId — первичный (уникальный) ключ в таблице Departments, поэтому у связи есть стрелка на конце, указывающем на узел D. Так как Departments не уникален в таблице Employees, на другом конце связи стрелки нет. Хотя вы можете догадаться, что DepartmentId — это первичный ключ для Departments, SQL не объявляет явно, какая сторона соединения является первичным ключом, а какая — внешним. Необходимо проверить индексы или объявленные ключи, чтобы удостовериться, что Departments гарантированно уникален в таблице Departments.
Подчеркнутые числа
Подчеркнутые числа рядом с узлами обозначают долю строк каждой таблицы, удовлетворяющих условиям фильтрации для этой таблицы. Здесь под условиями понимаются не условия соединения, а условия, относящиеся только к конкретной таблице на диаграмме SQL. На рис. 1.X 10 % строк таблицы Employees удовлетворяют условию Exempt_Flag='Y', и 50 % строк таблицы Departments удовлетворяют условию US_Based_Flag='Y'. Эти доли называются коэффициентами фильтрации.
Часто для одной или нескольких таблиц вообще не указаны условия фильтрации. В этом случае для коэффициента фильтрации (К) используется значение 1,0, так как 100 % строк удовлетворяют (несуществующим) условиям фильтрации для этой таблицы. В подобных случаях обычно вообще не указываются коэффициенты фильтрации на диаграмме. Отсутствие этого числа обозначает К = 1,0 для данной таблицы. Коэффициент фильтрации не может быть больше 1,0. Зачастую можно приблизительно угадать значение коэффициентов фильтрации, зная, что представляют таблицы и столбцы. Если доступны распределения реальных данных, можно найти точные значения коэффициентов фильтрации, просто получив и проанализировав эти данные. Необходимо рассматривать каждую фильтрованную таблицу с операторами фильтрации, относящимися только к этой таблице, как однотабличный запрос, и искать селективность условий фильтров.