48648 (Разработка программы запросов)

Курсовая работа

Одесса 2010

Содержание

Введение

1 Анализ существующих решений

1.1 Операции реляционной алгебры

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

1.3 Диаграмма запроса

1.4 Создание диаграммы запроса

1.5 Программы построения плана выполнения запроса

1.6 Выводы

2 Техническое задание на разработку обучающей программы построению запросов с использованием реляционных операций

2.1 Основание для разработки

2.2 Назначение разработки

2.3 Требования к программе

2.4 Требования к программной документации

2.5 Стадии и этапы разработки

2.6 Порядок контроля и приемки

3 Проектирование программы обучения реляционной алгебре

3.1 Анализ предметной области

3.2 Структура данных

Список литературы

Введение

Реляционная алгебра описывает выполняемые над отношениями действия. Языки запросов, построенные на основе реляционной алгебры, в современных СУБД широкого распространения не получили. Однако знание реляционной алгебры необходимо для понимания сути действий, происходящих при выполнении любых запросов к реляционным базам данных.

Значительным фактором, влияющим на производительность бизнес-приложений, является скорость выполнения их SQL-запросов. SQL-серверы предоставляют достаточно широкие возможности улучшений. SQL-код, значительно влияющий на загрузку системы и производительность конечных пользователей, обычно можно улучшить как минимум в два раза. Однако можно найти немного советов по настройке SQL-запросов.

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

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

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

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

В редких случаях задачи настройки SQL нельзя решить за счет ускорения выполнения одного запроса. Запрос может возвращать слишком много строк, или выполняться слишком часто, чтобы достигнуть максимальной скорости, будь он даже абсолютно оптимизированным. Для таких проблем существуют систематические решения на уровне приложения, изменяющие модель применения SQL-запроса.

Настройка SQL состоит из трех основных этапов:

1) понять, какой план выполнения (путь к данным, запрашиваемым вашим оператором) имеется;

2) изменить SQL или базу данных, чтобы получить выбранный план выполнения;

3) выбрать оптимальный план выполнения.

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

В первой главе приведено описание операций реляционной алгебры. Представлены принципы оптимизации запросов. Описано представление запроса в виде диаграммы. А также приведено описание графических сред для просмотра плана выполнения запроса.

Во второй главе описано назначение разработанной программы, представлены ее основные функции.

1 Анализ существующих решений

В начале 70-х годов двадцатого века Кодд опубликовал две статьи, в которых ввел реляционную модель данных (РМД) и реляционные языки обработки данных.

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

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

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

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

1.1 Операции реляционной алгебры

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

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

Реляционные операторы объединения, пересечения и взятия разности требуют, чтобы отношения имели одинаковые заголовки. Действительно, отношения состоят из заголовка и тела. Операция объединения двух отношений есть просто объединение двух множеств кортежей, взятых из тел соответствующих отношений [1].

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

Некоторые отношения не являются совместимыми по объединению, но становятся таковыми после некоторого переименования атрибутов.

Оператор присваивания (:=) позволяет сохранить результат вычисления реляционного выражения в существующем отношении.

Отношение с тем же заголовком, что и у совместимых по типу отношений A и B, и телом, состоящим из кортежей, принадлежащих или A, или B, или обоим отношениям, называется объединением отношений A и B.

Синтаксис:

A U B

Отношение с тем же заголовком, что и у отношений A и B, и телом, состоящим из кортежей, принадлежащих одновременно обоим отношениям A и B, называется пересечением отношений A и B.

Синтаксис:

A ∩ B

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

Синтаксис:

A - B

Отношение (A1, A2, …, Am, B1, B2, …, Bm), заголовок которого является сцеплением заголовков отношений A(A1, A2, …, Am) и B(B1, B2, …, Bm), а тело состоит из кортежей, являющихся сцеплением кортежей отношений A и B:

(a1, a2, …, am, b1, b2, …, bm)

таких, что (a1, a2, …, am) A, (b1, b2, …, bm) B,

называется декартовым произведением отношений А и В.

Синтаксис:

A B

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

Синтаксис:

(A, C)

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

Синтаксис:

A [X, Y, …, Z]

или

_A {x, y, …, z}

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

Синтаксис:

((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) — последовательность выполняемых действий, которые обеспечивают выбранные методы доступа. Существует два основных вида оптимизаторов:

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