Функциональная зависимость на отношениях, нормальные формы отношений. Оптимизация запросов.

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

Если даны два атрибута X и Y некоторого отношения, то говорят, что Y функционально зависит от X, если в любой момент времени каждому значению X соответствует ровно одно значение Y. Функциональная зависимость обозначается X -> Y. Отметим, что X и Y могут представлять собой не только единичные атрибуты, но и группы, составленные из нескольких атрибутов одного отношения. Можно сказать, что функциональные зависимости представляют собой связи типа " один ко многим", существующие внутри отношения.

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

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

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

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

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

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

Пример приведения таблицы к первой нормальной форме:

Исходная, ненормализованная, таблица: Таблица, приведённая к 1NF:

Сотрудник Номер телефона Сотрудник Номер телефона

Иванов И. И. 283-56-82 Иванов И. И. 283-56-82

390-57-34 Иванов И. И. 390-57-34

Петров П. Ю. 708-62-34 Петров П. Ю. 708-62-34

Атомарность атрибутов

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

Одно и то же значение может быть атомарным или неатомарным в зависимости от смысла этого значения. Например, значение «4286» является

* атомарным, если его смысл — «пин-код кредитной карты» (при разбиении на части или переупорядочивании смысл теряется)

* неатомарным, если его смысл — «четные цифры» (при разбиении на части или переупорядочивании смысл не теряется)

Хорошим способом принятия решения о необходимости разбиения атрибута на части является вопрос: «будут ли части атрибута использоваться по отдельности?». Если да, то атрибут следует разделить (но так, чтобы сохранились осмысленные части атрибута). Далее необходимо снова задаться тем же вопросом для новой структуры и так до тех пор, пока не останется атрибутов, допускающих разбиение.

Отношение находится во второй нормальной форме, если оно находится в первой нормальной форме, и при этом любой его неключевой атрибут функционально полно зависит от атрибутов первичного ключа. Функционально полная зависимость означает, что атрибут функционально зависит от всего составного ключа, но при этом не находится в функциональной зависимости от какой-либо из входящих в него атрибутов (частей). Или другими словами: в 2NF нет неключевых атрибутов, зависящих от части составного ключа (плюс выполняются условия 1NF), все неключевые атрибуты зависят полностью от всего составного ключа.

Пример приведения таблицы ко второй нормальной форме

Пусть Сотрудник и Должность вместе образуют первичный ключ в такой таблице:

Сотрудник Должность Зарплата Наличие компьютера

Гришин Кладовщик 20000 Нет

Васильев Программист 40000 Есть

Васильев Кладовщик 25000 Нет

Зарплату сотруднику каждый начальник устанавливает сам, но её границы зависят от должности. Наличие же компьютера у сотрудника зависит только от должности, то есть зависимость от первичного ключа неполная.

В результате приведения к 2NF получаются две таблицы:

Сотрудник Должность Зарплата Должность Наличие компьютера

Гришин Кладовщик 20000 Кладовщик Нет

Васильев Программист 40000 Программист Есть

Васильев Кладовщик 25000

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

Отношение находится в 3НФ тогда и только тогда, когда выполняются следующие условия:

* Отношение R (таблица) находится во второй нормальной форме;

* Каждый непервичный атрибут R находится в нетранзитивной (то есть прямой) зависимости от каждого ключа R.

Транзитивная зависимость — это функциональная зависимость, при которой X → Z (X определяет Z) не напрямую, а посредством отношения X → Y и Y → Z (отношение Y → X не является обязательным условием).

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

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

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

План выполне́ ния запро́ са — последовательность операций, необходимых для получения результата SQL-запроса в реляционной СУБД.

План в целом разделяется на две стадии:

* Выборка результатов;

* Сортировка и группировка, выполнение агрегаций.

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

Оптимизатору даётся времени очень мало и он не успевает перебрать всё, поэтому вы должны ему помочь и давать такие запросы, чтобы они были ближе к идеалу. Ульман писал, что оптимизация — не очень хорошее слово, здесь это только приближение к хорошему варианту, никакая функция не строится и не изучается. Желательно знать какие оптимизации есть и написать, если вам не затратно, эффективный запрос. Иногда лучше сделать несколько небольших подзапросов, а потом объединить их в UNION, а их лучше оптимизировать уже. К тому же, если кэшировать запросы, СУБД быстро всё найдёт.

Желательно ещё LIKE не писать, у которого в начале стоит %, это почти наверняка отключит оптимизацию (% означает неопределённое количество неопределённых символов). Из соображений, что неравенство гораздо менее определённое, чем ограничение вроде 2 < s < 3, если можете, лучше всего использовать равенство или > =, чем > (так как в первом случае индексы сразу начинаются с нужной цифры). Величина NULL не является значением, поэтому старайтесь не писать IS NULL (а так же по тем же причинам ANY, EXISTS без NOT, так получается отсутствие оптимизации всякой), старайтесь использовать — это так называемые объявленные курсоры, чтобы его открыть, надо как можно меньше их.

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

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

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

3)Для подсчета кол-ва строк используйте функцию COUNT(*), c указанием " звездочки" в качестве аргумента.

Почему COUNT(*) обычно быстрее COUNT(id), поясню на примере:

Есть таблица message: id | user_id | text

с индексом PRIMARY(id), INDEX(user_id)

Нам надо подсчитать сообщения пользователя с заданым $user_id

Сравним 2 запроса:

SELECT COUNT(*) FROM message WHERE user_id = $user_id

и

SELECT COUNT(id) FROM message WHERE user_id = $user_id

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

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

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

16. Сетевая модель: основные понятия, описание данных

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

Сетевая модель данных определяется в тех же терминах, что и иерархическая. Она состоит из множества записей, которые могут быть владельцами или членами групповых отношений. Связь между между записью-владельцем и записью-членом также имеет вид 1: N.

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

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

* древья (a) и (b), показанные на рис. 17.1, заменяются одной сетевой структурой, в которой запись СОТРУДНИК входит в два групповых отношения;

* для отображения типа M: N вводится запись СОТРУДНИК_КОНТРАКТ, которая не имеет полей и служит только для связи записей КОНТРАКТ и СОТРУДНИК, см. рис. 16.1.(Отметим, что в этой записи может храниться и полезная информация, например, доля данного сотрудника в общем вознаграждении по данному контракту).

Каждый экземпляр группового отношения характеризуется следующими признаками:

* способ упорядочения подчиненных записей:

-произвольный,

-хронологический /очередь/,

-обратный хронологический /стек/,

-сортированный.

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

* режим включения подчиненных записей:

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

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

* режим исключения. Принято выделять три класса членства подчиненных записей в групповых отношениях:

1. Фиксированное. Подчиненная запись жестко связана с записью владельцем и ее можно исключить из группового отношения только удалив. При удалении записи-владельца все подчиненные записи автоматически тоже удаляются. В рассмотренном выше примере фиксированное членство предполагает групповое отношение " ЗАКЛЮЧАЕТ" между записями " КОНТРАКТ" и " ЗАКАЗЧИК", поскольку контракт не может существовать без заказчика.

2. Обязательное. Допускается переключение подчиненной записи на другого владельца, но невозможно ее существование без владельца. Для удаления записи-владельца необходимо, чтобы она не имела подчиненных записей с обязательным членством. Таким отношением связаны записи " СОТРУДНИК" и " ОТДЕЛ". Если отдел расформировывается, все его сорудники должны быть либо переведены в другие отделы, либо уволены.

3. Необязательное. Можно исключить запись из группового отношения, но сохранить ее в базе данных не прикрепляя к другому владельцу. При удалении записи-владельца ее подчиненные записи - необязательные члены сохраняются в базе, не участвуя более в групповом отношении такого типа. Примером такого группового отношения может служить " ВЫПОЛНЯЕТ" между " СОТРУДНИКИ" и " КОНТРАКТ", поскольку в организации могут существовать работники, чья деятельность не связана с выполненинем каких-либо договорных обязательств перед заказчиками.