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

Тип работы:
Курсовая
Предмет:
Программирование


Узнать стоимость

Детальная информация о работе

Выдержка из работы

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

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

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

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

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

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

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

В-третьих, при использовании различных видов подзапросов на основе знаний о данных следует учитывать особенности вычисления специальных предикатов и применения операторов теоретико-множественных операций. Например, оператор MINUS может выполняться гораздо быстрее, чем запросы с WHERE NOT IN (SELECT) или WHERE NOT EXISTS.

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

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

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

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

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. Зачастую можно приблизительно угадать значение коэффициентов фильтрации, зная, что представляют таблицы и столбцы. Если доступны распределения реальных данных, можно найти точные значения коэффициентов фильтрации, просто получив и проанализировав эти данные. Необходимо рассматривать каждую фильтрованную таблицу с операторами фильтрации, относящимися только к этой таблице, как однотабличный запрос, и искать селективность условий фильтров.

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

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

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

Детальные коэффициенты соединения могут быть равны любому неотрицательному числу. Они могут быть меньше 1,0, так как некоторые отношения главной и детальной таблиц разрешают существование нуля, одной или многих детальных строк, причем чаще всего встречается случай «один к нулю». В примере для средней строки Employees есть соответствующая строка (с которой она связана) в Departments в 98% случаев, тогда как средняя строка Departments соответствует (связывается с) 20 строкам Employees. Нужно по возможности получать эти значения из полных, реальных распределений данных. Так же, как и с коэффициентами фильтрации, может потребоваться вычисление коэффициентов соединения во время фазы разработки приложения.

Диаграммы запросов полностью исключают любые упоминания списков столбцов и выражений, которые выбирает запрос (то есть все, что находится между SELECT и FROM). Производительность запроса практически полностью определяется тем, какие строки выбираются из базы данных, и каким образом они получаются. Что делается с этими строками, какие столбцы возвращаются, и какие выражения подсчитываются -- это практически несущественно для производительности. Главное, но редкое исключение из этого правила -- когда выбираются так мало столбцов из таблицы, что база данных может выполнить запрос, используя только данные из индекса, совершенно не обращаясь к основной таблице. Иногда доступ только к индексу может существенно сэкономить ресурсы, но он мало влияет на решения, которые принимаются относительно оставшейся части плана исполнения. Решать, нужно ли попробовать только индексный доступ, следует в последний момент процесса настройки и только если наилучший план без применения этой стратегии оказывается слишком медленным.

В диаграмме отсутствуют любые указания на сортировку (ORDER BY), группировку (GROUP BY) и фильтрацию после группировки (HAVING). Эти операции практически никогда не имеют большого значения для производительности запроса. Шаг сортировки, который они обычно включают, может влиять на скорость выполнения, но для изменения его стоимости мало что можно сделать, и эта стоимость обычно не так велика по сравнению с производительностью плохо выполняющегося запроса.

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

Детали условий соединения теряются, когда представляются соединения как простые стрелки с парой чисел, полученных откуда-то за пределами SQL. Если известна статистика соединения, то подробности (например, столбцы соединения и как они между собой связаны) не играют роли.

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

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

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

Ниже перечислены правила создания полной диаграммы запроса.

1. Начать с произвольно выбранного псевдонима таблицы из раздела FROM и поместить его в середину пустой страницы. Эта таблица будет называться центральной таблицей, подразумевая, что она будет текущей точкой, начиная с которой будут добавляться дальнейшие элементы в диаграмму запроса.

2. Найти условия соединения, соответствующие единственному значению первичного ключа центральной таблицы. Для каждого такого соединения нарисовать стрелку, указывающую вниз, на центральную таблицу, пометив начало стрелки псевдонимом на противоположной стороне соединения. Если связь представляет внешнее соединение, добавить посередине связи острие стрелки, направленное на дополнительную таблицу.

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

4. Сместить фокус на другой, пока что не рассмотренный узел в диаграмме и повторять шаги 2 и 3, пока не будут собраны узлы, представляющие все псевдонимы в разделе FROM, и стрелки, представляющие все соединения. Обычно вниз на узел будет указывать только одна стрелка, поэтому придется искать новые указывающие вниз соединения из узлов, уже находящихся на нижнем конце соединения (со стрелкой). Так получается перевернутая древовидная структура, ниспадающая из одной детальной таблицы наверху.

5. Заполнив все узлы и связи, вписать числа для коэффициентов фильтрации и коэффициентов соединения, основываясь, если возможно, на статистике по таблицам для промышленного приложения. Если нет промышленных данных, то постараться представить коэффициенты как можно точнее. Нет необходимости добавлять коэффициенты соединения рядом со связями, представляющими внешние соединения. Практически всегда для дополнительной таблицы внешнего соединения (сразу за ключевыми словами LEFT OUTER) условия фильтрации не указаны, поэтому коэффициент фильтрации равен 1,0, что обозначается просто фактом отсутствия числа на диаграмме.

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

Пример.

Имеется запрос

SELECT C. Phone_Number, C. Honorific, C. First_Name, C. Last_Name,

C. Suffix, C. AddressJD, A. AddressJD, A. Street_Address_Linel,

A. Street_Address_Line2, A. City_Name, A. State_Abbreviation, A. ZIP_Code,

DD. Deferred_Shipment_Date, OD. Item_Count. DOT. Text, OT. Text,

P. Product_Description, S. Shipment_Date

FROM Orders O, Orderjtetails OD, Products P, Customers C, Shipments S,

Addresses A, Code_Translations DOT, Code_Translations OT

WHERE UPPER (C. Last_Name) LIKE: Last_Name||'%'

AND UPPER (C. First_Name) LIKE: First_Name||'%'

AND OD. OrderID = O. Order_ID

AND O. CustomerID = C. Customer_ID

AND OD. Product_ID = P. Product_ID (+)

AND OD. Shipment_ID = S. Shipment_ID (+)

AND S. Address_ID = A. Address_ID (+)

AND O. Status_Code = OT. Code

AND DT. CodeJype = 'ORDER_STATUS'

AND OD. Status_Code = ODT. Code

AND CDT. CodeJype = 'ORDERJIETAILJTATUS

AND O. Order_Date >: Now — 366

ORDER BY C. CustomerID, O. Drder_ID DESC, S. ShipmentID, DD. Order_Detail_ID;

Построенная по вышеперечисленным правилам для данного запроса диаграмма показана на рис. 1.2.

Множество подробностей, присутствующих на полных диаграммах запросов, не обязательны, только для самых редких проблем. Для концентрации на необходимых элементах нужен только скелет диаграммы и приблизительные коэффициенты фильтрации. Изредка требуются коэффициенты соединений, но обычно только когда любой из детальных коэффициентов соединения меньше 1,5 или главный коэффициент соединения меньше 0,9. Это, в свою очередь, значит, что меньшее количество данных требует создания более простых диаграмм соединения. Нет необходимости узнавать количество строк для таблиц без фильтров. На практике в многосторонних соединениях обычно есть фильтры только для 3−5 таблиц, поэтому даже самый сложный запрос легко изобразить на диаграмме, не используя множество запросов для сбора статистики.

Отбросив перечисленные детали, можно упростить рис. 1.1 до рис. 1.3.

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

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

План выполнения запроса для MS SQL Server проще всего просмотреть из SQL Server Management Studio [2]/

Для того чтобы получить информацию об ожидаемом плане выполнения запроса, можно в меню Query (Запрос) выбрать команду Display Estimated Execution Plan (Отобразить ожидаемый план выполнения). Если нужно узнать реальный план выполнения запроса, можно перед его выполнением установить в том же меню параметр Include Actual Execution Plan (Включить реальный план выполнения). В этом случае после выполнения запроса в окне результатов в SQL Server Management Studio появится еще одна вкладка Execution Plan (План выполнения), на которой будет представлен реальный план выполнения запроса. При наведении указателя мыши на любой из этапов можно получить о нем дополнительную информацию (рис. 1. 4).

Еще одно интерактивное графическое средство, которое позволяет администратору базы данных или разработчику писать запросы, выполнять различные запросы одновременно, просматривать результаты, анализировать план запроса и получать поддержку для улучшения плана выполнения — SQL Query Analyzer. Опция просмотра плана выполнения графически показывает методы получения данных, используемые оптимизатором запроса Microsoft SQL Server. В графическом исполнении плана используются иконки для представления специфичных действий и запросов в SQL Server, а не изображения в виде таблиц, созданных инструкциями SET SNOWPLAN_ALL или SET SNOWPLAN_TEXT. Это очень полезно для понимания скоростных показателей запроса. Кроме того, SQL Query Analyzer показывает советы по дополнительным индексам и статистическим данным в неиндексируемых колонках, что улучшит возможности оптимизатора запроса рационально обработать запрос. В частности, SQL Query Analyzer показывает какие статистические данные пропущены, тем самым, заставляя оптимизатор запроса давать оценку по селективности, а затем дает возможность создать пропущенные статистические данные.

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

Пример

Запрос

SELECT DISTINCT t. date AS c0,

c. prefijoext AS c1,

c. numeroext AS c2,

c. checkbook AS c3

FROM Transac t (nolock)

JOIN cmpasociados c (nolock)

ON t. nrotrans = c. nrotrans

JOIN tiposcmp you (nolock)

ON c. codcmp = you. codcmp

JOIN checkbooks so (nolock)

ON c. checkbook = so. checkbook

AND t. codemp = so. codemp

WHERE T. Nrotranselim is null

AND

(

CASE

WHEN T. Codcmp

IN (

' CA', ' CC', ' CB', ' CE'

,' LR', ' LO', ' LP', ' CZ'

,' VA', ' VB', ' VC', ' YOU'

,' VZ'

)

THEN T. Nrotransaut

WHEN T. Codcmp

IN (' I', ' E', ' RD')

THEN T. Nrotransctrl

ELSE T. Nrotrans END

)

IS NOT NULL

AND (t. CodEmp IS NULL OR t. codemp = 1)

AND c. checkbook = 25

AND t. codsuc = 1

ORDER BY C2 DESC

имел следующий план исполнения в Query Analyzer (см. рис. 1. 5).

После применения индексов, получился план исполнения, показанный на рис. 1.6.

1.6 Выводы

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

В настоящее время отсутствуют обучающие программы работе с реляционной алгеброй.

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

· изучить особенности работы всех реляционных операций;

· разработать структуру данных для хранения необходимой информации;

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

· разработать удобный интерфейс для формирования процедурного плана запроса;

· разработать обучающий и контролирующий компоненты программы.

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

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

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

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

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

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

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

Программа «Обучающая программа построению запросов в процедурном виде» должна обеспечивать автоматизацию следующих функций:

1) формирование вопросов для обучаемых;

а) соединение с внутренней БД программы;

б) подключение БД, к которой формируются учебные запросы;

в) запись текста запроса;

г) доступ к метаданным учебной БД;

д) подключение схемы данных учебной БД в виде графического файла;

е) формирование множества операций ответа на запрос;

ж) формирование различных верных последовательностей операций;

2) прием ответа от обучаемого;

а) возможность выбора операции из заданного множества;

б) формирование списка таблиц учебной БД;

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

г) определение списка столбцов заданной таблицы;

д) подключение операндов выбранной операции;

е) изменение последовательности введенных операций;

ж) сравнение введенного ответа с эталонным множеством последовательностей операций;

з) формирование сообщений о неправильных действиях пользователя;

3) обучающая часть;

а) возможность просмотра результата промежуточной операции запроса;

б) возможность просмотра результата запроса;

в) просмотр правильного ответа;

4) контролирующая часть;

а) формирование вопросника из имеющихся во внутренней БД запросов;

б) выставление баллов за ответ;

в) формирование итоговой оценки;

г) сохранение результатов теста;

д) сохранение введенных ответов.

5) работа с отчетами;

а) формирование сообщений о результатах теста;

б) печать списка вопросов и списка ответов.

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

Входными данными должны быть:

информация для соединения с учебной БД;

структура таблиц учебной БД;

соединение с внутренней БД.

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

Выходными данными являются:

а) множество вопросов в виде текста запроса к учебной БД;

б) множество последовательностей операций для реализации запросов;

в) последовательности операций для реализации запросов к учебной БД, введенные пользователем;

7) оценки за введенные ответы при использовании программы в контролирующем режиме.

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

Надежность и устойчивость функционирования программы должны обеспечиваться:

— продуманной технологией обработки информации;

— контролем правильности ввода входной информации;

— системой диагностических сообщений;

— минимизацией операций, осуществляемых пользователем;

— соблюдением требований эксплуатационной документации.

При функционировании программы «Обучающая программа построению запросов в процедурном виде» должно обеспечиваться:

— решение задачи за приемлемое время;

— вывод результатов работы программы в виде выходных отчетов на принтере и отображения их на экране монитора.

Сохранность программ должна обеспечиваться наличием дубликатов программы и хранением программного обеспечения на внешних носителях.

Программа «Обучающая программа построению запросов в процедурном виде» требует для своего функционирования компьютер типа IBM PC под управлением операционной системы Windows 2000 и выше.

Минимальный состав технических средств:

— процессор с оперативным запоминающим устройством емкостью не менее 512 Мб;

— накопитель на магнитных дисках типа «винчестер» емкостью не менее 30 Гб;

— CD-ROM для чтения информации с компакт-диска;

— монитор;

— принтер.

Программа «Обучающая программа построению запросов в процедурном виде» реализована в виде исполняемого файла и множества БД (внутренняя и учебные).

Язык программирования — Visual Basic 6.0.

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

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

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

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

Состав программной документации программы «Обучающая программа построению запросов в процедурном виде» должен быть следующим:

— описание программы;

— руководство пользователя;

— функциональное описание.

Состав документов может уточняться в процессе разработки.

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

Стадии и этапы разработки, содержание работ и сроки выполнения приведены в таблице 2.1.

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

В процессе разработки программы «Обучающая программа построению запросов в процедурном виде» должны проводиться: 1) проектирование и отладка программы; 2) предварительные испытания; 3) опытная эксплуатация; 4) ввод в действие.

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

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

Продолжительность опытной эксплуатации составляет 2 недели.

Таблица 2.1 Стадии и этапы разработки

Стадии разработки

Этапы работ

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

Сроки выполнения

Изучение предметной области

Изучение особенностей реляционных операций

Исследование основных составляющих запросов и способов их реализации в виде последовательности реляционных операций

31. 01. 10

Техническое задание

Разработка технического задания

Разработка технического задания, экономическое обоснование

01. 03. 10

Эскизный проект

Эскизное проектирование

Разработка функционального описания

15. 03. 10

Рабочий проект

Разработка прикладных программ

Реализация и отладка программ

Разработка программной документации

15. 04. 10

Испытания программы

Проведение предварительных испытаний

07. 05. 10

Проведение опытной эксплуатации

21. 05. 10

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

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

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

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

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

Объединением двух совместимых таблиц R1 и R2 называется таблица R, состоящая из всех строк, принадлежащих хотя бы одной из таблиц R1, R2.

Пересечением двух совместимых таблиц R1 и R2 называется таблица R, состоящая из всех строк, являющихся общими для таблиц R1, R2.

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

Декартовым произведением двух таблиц R1 и R2 (необязательно совместимых) называется таблица R, состоящая из всех таких строк, каждая из которых есть конкатенация двух строк, по одной из таблиц R1 и R2, причем на первом месте должна быть строка из R1.

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

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

Создание проекций — операция реляционной алгебры, создающая новую таблицу путем исключения столбцов из существующей таблицы.

Проекция — реляционная таблица, полученная в результате создания проекций.

Соединение — операция реляционной алгебры, связывающая таблицы. У нее есть несколько версий:

Естественное соединение — операция соединения, связывающая таблицы, когда общие столбцы имеют равные значения.

Тета-соединение — это соединение с определенным условием, в котором участвуют столбцы из каждой таблицы. Оператор сравнения может быть любой:

JOIN (A, B: X Y), где обозначает операцию сравнения.

Если используется операция «=», то соединение также называется эквисоединением.

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

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

Программа может работать в двух режимах: обучающем и контролирующем.

В обоих режимах необходимо наличие множества вопросов. Таким образом, необходим еще один компонент программы — формирования вопросов.

Каждый вопрос представляет собой текст запроса к учебной БД. Пользователю для ввода ответа на вопрос необходимо представить текст запроса и информацию о БД, к которой направляется запрос. Удобно представлять информацию о БД в виде графической схемы данных.

Ответ на вопрос должен вводиться в виде последовательности операций реляционной алгебры.

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

Например, пусть БД состоит из таблиц Товар (Идентификатор, Название) и Продажа (Дата, Идентификатор товара, Количество, Цена).

Необходимо получить результат запроса «Какой товар продавали в количестве более 100». Ответ можно представить в виде следующих последовательностей.

Первая последовательность:

R1=JOIN (Товар, Продажа, Идентификатор товара=Товар)

R2= (R1, Количество> 100)

R3= (R2, Название)

Вторая последовательность:

R1= (Продажа, Количество> 100)

R2=JOIN (Товар, R1, Идентификатор товара=Товар)

R3= (R2, Название)

Необходимо получить результат запроса «Какой товар ни разу не продавали». Ответ можно представить в виде следующих последовательностей.

Первая последовательность:

R1= LEFT JOIN (Товар, Продажа, Идентификатор товара=Товар)

R2= (R1, Идентификатор товара=NULL)

R3= (R2, Название)

Вторая последовательность:

R1= (Продажа, Идентификатор товара)

R2= (Товар, Идентификатор)

R3=R2-R1

R4=JOIN (Товар, R3, Товар. Идентификатор = R3. Идентификатор)

R5= (R4, Название)

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

Проверка правильности введенного ответа может выполняться двумя способами.

Первый способ предполагает сравнение ответа с эталонным множеством ответов. При этом важное значениек5 имеет полнота введенных ответов, то есть качество заполнения внутренней БД.

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

Таким образом, администратор программы должен обеспечить следующее.

Должна быть учебная БД с заполненными таблицами. Таблицы должны быть заполнены такими данными, чтобы можно было проверить правильность выполнения запроса в любом случае.

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

Учебных БД может быть несколько.

К каждой БД может быть составлено множество запросов, на каждый запрос может быть множество ответов.

Пользователь должен иметь удобный интерфейс для ввода последовательности операций.

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

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

При вводе условий необходимо предоставить возможность выбора операции сравнения и множества стандартных констант типа TRUE, FALSE, NULL.

При проверке правильности ответа необходимо учесть зависимость и независимость порядка операндов.

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

R1= LEFT JOIN (A, B, условие соединения)

и

R1= RIGHT JOIN (B, A, условие соединения).

Таким образом, проверка правильности введенного ответа не может выполняться простым сравнением эталона и введенного текста.

Необходимы алгоритмы интеллектуального сравнения с учетом особенностей предметной области.

При вводе очередной n-й операции последовательности ее результату присваивается стандартное имя Rn. Это имя добавляется в список возможных операндов следующей операции.

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

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

Для этого программа должна уметь преобразовывать операцию (последовательность операций) в запрос к БД.

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

ПоказатьСвернуть
Заполнить форму текущей работой