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

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

Энциклопедичный YouTube

1 / 5

Лекция 2.5 | Функциональная зависимость. Применение векторной алгебры

Лекция 2.3 | Функциональная зависимость. Векторы и действия с ними

Нормализация в базе данных

02 - Погружение в СУБД. Проектирование схемы, часть I

Как обучиться программированию?

Субтитры

Определения

Функциональная зависимость

Пусть дано отношение r {\displaystyle r} со схемой (заголовком) R {\displaystyle R} , A {\displaystyle A} и B {\displaystyle B} - некоторые подмножества множества атрибутов отношения r {\displaystyle r} . Множество B {\displaystyle B} функционально зависит от A {\displaystyle A} тогда и только тогда, когда каждое значение множества A {\displaystyle A} связано в точности с одним значением множества B {\displaystyle B} . Обозначается .

Другими словами, если два кортежа совпадают по атрибутам A {\displaystyle A} , то они совпадают и по атрибутам B {\displaystyle B} .

В этом случае A {\displaystyle A} - детерминант, B {\displaystyle B} - зависимая часть.

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

Замыкание множества зависимостей

Одни функциональные зависимости могут подразумевать другие функциональные зависимости. Например, транзитивная функциональная зависимость,

Множество всех атрибутов, которые подразумеваются данным множеством функциональных зависимостей S {\displaystyle S} называется замыканием множества S {\displaystyle S} .

Пусть Z {\displaystyle Z} - некоторое множество атрибутов отношения r {\displaystyle r} , а S {\displaystyle S} - множество функциональных зависимостей этого отношения. Замыканием Z + {\displaystyle {{Z}^{+}}} множества атрибутов Z {\displaystyle Z} в пределах S {\displaystyle S} называется такое множество всех атрибутов A i {\displaystyle {{A}_{i}}} отношения r {\displaystyle r} , что функциональная зависимость Z → A i {\displaystyle Z\to {{A}_{i}}} является членом замыкания S + {\displaystyle {{S}^{+}}} .

Неприводимые множества зависимостей

Пусть и - некоторые множества функциональных зависимостей.

• Если любая функциональная зависимость из S 1 {\displaystyle {{S}_{1}}} входит и в S 2 {\displaystyle {{S}_{2}}} , то S 2 {\displaystyle {{S}_{2}}} называют покрытием множества функциональных зависимостей S 1 {\displaystyle {{S}_{1}}} .
• Если S 2 {\displaystyle {{S}_{2}}} - покрытие для S 1 {\displaystyle {{S}_{1}}} , а S 1 {\displaystyle {{S}_{1}}} - для S 2 {\displaystyle {{S}_{2}}} (то есть S 1 + = S 2 + {\displaystyle S_{1}^{+}=S_{2}^{+}} ), то такие множества называются эквивалентными .
• Множество функциональных зависимостей S {\displaystyle S} называется неприводимым тогда и только тогда, когда выполняются следующие условия:
• Для любого множества функциональных зависимостей существует по крайней мере одно эквивалентное множество, которое является неприводимым. Такое эквивалентное множество называется неприводимым покрытием .

Вычисление замыканий

Правила вывода Армстронга

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

Пусть у нас есть отношение r (R) {\displaystyle r\left(R\right)} и множества атрибутов A , B , C , D ⊆ R {\displaystyle A,B,C,D\subseteq R} . Для сокращения записи вместо X ∪ Y {\displaystyle X\cup Y} будем писать просто X Y {\displaystyle XY} .

Правила вывода Армстронга полны (используя их, можно вывести все остальные функциональные зависимости, подразумеваемые данным их множеством) и надежны («лишних» функциональных зависимостей вывести нельзя; выведенная функциональная зависимость справедлива везде, где справедливо то множество функциональных зависимостей, из которого она была выведена).

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

Теорема: Функциональная зависимость A → B {\displaystyle A\to B} выводима из данного множества функциональных зависимостей S {\displaystyle S} по правилам вывода Армстронга тогда и только тогда, когда B ⊆ A + {\displaystyle B\subseteq {{A}^{+}}} .

Замыкание множества атрибутов

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

Применение

Проектирование БД

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

Если I {\displaystyle I} является неприводимым покрытием исходного множества функциональных зависимостей S {\displaystyle S} , то проверка выполнения функциональных зависимостей из I {\displaystyle I} автоматически гарантирует выполнение всех функциональных зависимостей из S {\displaystyle S} . Таким образом, задача поиска минимально необходимого набора сводится к отысканию неприводимого покрытия множества функциональных зависимостей, которое и будет использоваться вместо исходного множества.

Декомпозиция отношений

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

Декомпозицией схемы отношения R = {А1, А2, ...,Аn} называется замена её совокупностью подмножеств R, таких, что их объединение дает R. При этом допускается, чтобы подмножества были пересекающимися.

Алгоритм декомпозиции основан на следующей теореме.

Теорема Хита

Пусть дано отношение r (A , B , C) {\displaystyle r\left(A,B,C\right)} .

Если r {\displaystyle r} удовлетворяет функциональной зависимости A → B {\displaystyle A\to B} , то оно равно соединению его проекций r [ A , B ] {\displaystyle r\left} и r [ A , C ] {\displaystyle r\left} .

Введение

Диалектический подход к изучению природы и общества требует рассмотрения явлений в их взаимосвязи и непрестанном изменении. Понятия корреляции и регрессии появились в середине XIX в. благодаря работам английских статистиков Ф. Гальтона и К. Пирсона. Первый термин произошел от латинского «correlatio» – соотношение, взаимосвязь. Второй термин (от лат. «regressio» - движение назад) введен Ф. Гальтоном, который, изучая зависимость между ростом родителей и их детей, обнаружил явление «регрессии к среднему» – у детей, родившихся у очень высоких родителей, рост имел тенденцию быть ближе к средней величине.

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

Выше сказанным обусловлена актуальность выбора темы курсовой работы. Цель данной работы – исследовать функциональную зависимость между случайными величинами методами корреляционного и регрессионного анализов.

Глава 1 Корреляционный анализ

1.1 Функциональная, статистическая и корреляционная зависимости

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

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

В силу неоднозначности статистической зависимости между Y и Х для исследователя, в частности, представляет интерес усредненная по х схема зависимости, т.е. закономерность в изменении среднего значения - условного математического ожидания (Y) (математического ожидания случайной переменной Y, найденного при условии, что переменная Х приняла значение х) в зависимости от х.

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

Корреляционная зависимость может быть представлена в виде:

Предполагается, что φ(x)≠const и ψ(x)≠const, т.е. если при изменении х или у уcловные математические ожидания(Y) и не изменяются, то говорят, что корреляционная зависимость между переменными Х и У отсутствует. Сравнивая различные виды зависимости между Х иY, можно сказать, что с изменением значений переменной Х при функциональной зависимости однозначно изменяется определенное значение переменной у, при корреляционной – определенное среднее значение (условное математическое ожидание) Y, а при статистической- определенное (условное) распределение переменной Y (Рис.1.1)

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

Уравнения (1.1) и (1.2) называются модельными уравнениями регрессии (или просто уравнениями регрессии) соответственно Y по Х и Х по Y, функции ψ(x) и φ(у) – модельными функциями регрессии (или функциями регрессии), а их графики - модельными линиями регрессии (или линиями регрессии).

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

где – условная (групповая) средняя переменной Y при фиксированном значении переменной Х = х; ,…,- параметры кривой.

Аналогично определяется выборочная линия (кривая) регрессии Х по Y:

где – условная (групповая) средняя переменной Х при фиксированном значении переменной Y= у; -параметры кривой.

Уравнения (1.3), (1.4) называют также выборочными уравнениями регрессии соответственно Yпо Х и Х по Y.

При правильно определенных аппроксимирующих функциях) и с увеличением объема выборки (n) они будуг сходиться по вероятности соответственно к функциям регрессии ψ(x) и φ(у).

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

1.2 Линейная парная регрессия

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

Рассмотрим в качестве примера зависимость между суточной выработкой продукции Y (т) и величиной основных производственных фондов Х (млн руб.) для совокупности 50 однотипных предприятий (табл. 1).
(В таблице черези обозначены середины соответствующих интервалов, а через, и – соответственно их частоты.)

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

где - частоты пар () и; m – число интервалов по переменной Y.

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

Аналогично для каждого значения по формуле

вычислим групповые средние, где, l – число интервалов по переменной X.

По виду ломанной можно определить наличие линейной корреляционной зависимости Y по X между двумя рассматриваемыми переменными, которая выражается тем точнее чем больше объем выборки n:

Поэтому уравнение регрессии(1.3) будем искать в виде:

Отвлечемся на время от рассматриваемого примера и найдем формулы расчета неизвестных параметров уравнения линейной регрессии.

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

На основании необходимого условия экстремума функции двух переменных S=S() приравниваем к нулю ее частные производные, т.е.

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

Учитывая (1.5) преобразуем выражение и с учетом (1.7), разделив обе части уравнений (1.10) на n, получим систему нормальных уравнений в виде:

где соответствующие средние определяются по формулам:

Подставляя значение из первого уравнения системы(1.11) в уравнение регрессии (1.8), получаем

Коэффициент b 1 в уравнении регрессии, называемый выборочным коэффициентом регрессии (или просто коэффициентом регрессии) Y по Х, будем обозначать символом. Теперь уравнение регрессии Y по Х запишется так:

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

Решая систему (1.11), найдем

где - выборочная дисперсия переменной X

µ - выборочный корреляционный момент:

Рассуждая аналогично и полагая уравнение регрессии (1.4) линейным, можно привести его к виду:

выборочный коэффициент регрессии (или просто коэффициент регрессии) Х по Y, показывающий, на сколько единиц в среднем изменяется переменная Х при увеличении переменной Y на одну единицу= – (–выборочная дисперсия переменной Y. зависимость . При этом все наблюдения располагаются... Линия тренда (рис. 2); 3) выбрать вид зависимости регрессии . Для нашего примера тип тренда...

Метод нормальных форм

Преподаватель

Рис. 6.4. Исходное отношение ПРЕПОДАВАТЕЛЬ

Неявная избыточность проявляется в одинаковых окладах у всех преподавателей и в одинаковых надбавках к окладу за одинаковый стаж. Если оклад изменится с 500 руб. до 510руб., то это значение надо изменить у всех преподавателей. Если при этом будет пропущен Сидоров, то база станет противоречивой. Это пример аномалии редактирования отношения с неявной избыточностью.

Исключение избыточности состоит в нормализации отношений.

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

Атрибут В функционально зависит от атрибута А, если каждому значению А соответствует в точности одно значение В. Математически функциональная зависимость В от А обозначается записью А ® В. Это означает, что во всех кортежах с одинаковым значением атрибута а АТРИБУТ в БУДЕТ ИМЕТЬ ТАКЖЕ ОДНО И ТО ЖЕ ЗНАЧЕНИЕ. Атрибуты А и В могут быть составными – состоять из двух и более атрибутов. В отношении Преподаватель Функциональные зависимости следующие: ФИО ® Каф, ФИО ® Долж, Долж ® Оклад и др.

Функциональная взаимозависимость. Если существует функциональная зависимость вида А ® В и В ® А, то между А и В имеется взаимно однозначное соответствие, или функциональная взаимозависимость. Математически взаимозависимость обозначается как А « В или В « А.

Пример. Атрибут N (серия и номер паспорта) находится в функциональной взаимозависимости с атрибутом ФИО (фамилия, имя и отчество), если предполагается, что ситуация наличия в отношении полного совпадения фамилий, имен и отчеств у двух людей исключена.

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

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

Атрибут С зависит от атрибута А транзитивно (существует транзитивная зависимость ), если для атрибутов А, В, С выполняются условия А ® В и В ® С, но обратная зависимость отсутствует. В примере транзитивной зависимостью связаны атрибуты:

ФИО ® Долж ® Оклад

В отношении R атрибут В многозначно зависит от атрибута А, если каждому значению А соответствует множество значений В, не связанных с другими атрибутами из R. Многозначные зависимости могут быть «один ко многим» (1:М), «многие к одному» (М:1) или «многие ко многим» (М:М), Обозначаемые соответственно: А Þ В, А Ü В и А Û В.

В рассматриваемом примере имеется многозначная зависимость М:М между атрибутами ФИО Û Предмет (один преподаватель может вести несколько предметов и один предмет могут вести несколько преподавателей).

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

Взаимно независимые атрибуты. Два или более атрибутов называются взаимно независимыми, если ни один из этих атрибутов не является функционально зависимым от других атрибутов. Математически отсутствие зависимости атрибута А от атрибута В обозначается как А Ø® В. Если имеет место А Ø® В и В Ø® А, то взаимная независимость обозначается А Ø= В.

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

Пример. Пусть задано отношение R со схемой R(А1, А2, А3) вида:

Априори известно, сто существуют функциональные зависимости:

А1®А2 и А2®А3.

Из анализа видно, что в отношении существуют еще зависимости:

А1®А3, А1А2®А3, А1А2А3®А1А2, А1А2®А2А3 и т.п..

В отношении отсутствует функциональная зависимость атрибута А1 от атрибута А2 и от атрибута А3, т.е.

А2 Ø® А1, А3 Ø® А1.

Отсутствие зависимости А1 от А2 объясняется тем, что одному и тому же значению атрибута А2 (21) соответствуют разные значения атрибута А1 (12 и 17).

Все существующие функциональные зависимости в отношении составляют полное множество функциональных зависимостей , которое обозначим F + . Полное множество функциональных зависимостей может быть выведено на основе 8 аксиом вывода: рефлективности, пополнения, транзитивности, расширения, продолжения, псевдотранзитивности, объединения и декомпозиции.

В отношении Преподаватель можно вывести следующие функциональные зависимости:

ФИО ® Оклад

ФИО ® Долж

ФИО ® Стаж

ФИО ® Надб

ФИО ® Каф

Стаж ® Надб

Долж ® Оклад

Оклад ® Долж

ФИО. Предм. Группа ® Оклад

Рис. 6.5. Зависимости между атрибутами.

Предполагается, что один преподаватель в одной группе может проводить один вид занятий (лекции или лабораторные работы). ФИО – уникальны. Имеется зависимость ФИО ® Стаж, а обратное утверждение не верно, т.к. одинаковый стаж имеют несколько преподавателей. Относительно других зависимостей рассуждения аналогичны. Между должностью и окладом устанавливается взаимно однозначная зависимость.

Один преподаватель в одной группе по разным предметам может проводить разные виды занятий. Определение ВидаЗанятий связано с указанием ФИО, Предмета и Группы. Действительно, Петров М.И. в 256-й группе читает лекции и проводит лабораторные занятия, но лекции читает по СУБД, а лабораторные работы по Графике.

Зависимости между атрибутами ФИО, Предмет и Группа не выведены, т.к. они образуют составной ключ и не учитываются в процессе нормализации отношения (таблицы).

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

Выделяют следующую последовательность нормальных форм:

° Первая нормальная форма (1НФ);

° Вторая нормальная форма (2НФ);

° Третья нормальная форма (3НФ);

° Усиленная третья нормальная форма, или нормальная форма Бойса-Кодда (БКНФ);

° Четвертая нормальная форма (4НФ);

° Пятая нормальная форма (5НФ).

Первая нормальная форма Отношение находится в 1НФ, если все его атрибуты являются простыми (имеют единственное значение). Исходное отношение строится таким образом, чтобы оно было в 1НФ.

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

Основной операцией метода декомпозиции является операция проекции.

Пример. Пусть в отношении R(A,B,C,D,E,…) имеется функциональная зависимость С ® D. Декомпозиция отношения R на два новых отношения R1(A, B,C,E,…) и R2(C,D) устранит функциональную зависимость атрибутов и переведет отношение R в следующую нормальную форму. Отношение R2 является проекцией отношения R на атрибуты C и D.

Исходное отношение Преподаватель имеет составной ключ ФИО, Предм, Группа и находится в 1НФ. Атрибуты Стаж, Надб, Каф, Долж, Оклад находятся в функциональной зависимости от части составного ключа – атрибута ФИО . Эта частичная зависимость приводит к явной и неявной избыточности данных, что создает проблемы их редактирования. Часть избыточности устраняется при переводе отношения во 2НФ.

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

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

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

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

Переведем отношение Преподаватель во 2НФ. В результате получим два отношения R1 и R2.

R1

Рис. 6.6. Отношения базы данных ПРЕПОДАВАТЕЛЬ во 2 НФ

В отношении R1 первичный ключ составной ФИО, Предм, Группа , в отношении R2 ключ – ФИО. В результате исключена явная избыточность данных о преподавателях. В R2 по-прежнему имеет место неявное дублирование данных.

Для дальнейшего совершенствования переведем отношения в 3НФ.

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

Информация, данные, информационные системы

Понятие функциональной зависимости в данных

Оставим пока в стороне ответ на вопрос, почему проекты реляционных баз данных бывают плохими, т.е. зачем нужно проектировать реляционную базу данных. Попытаемся сначала ответить на вопросы "В чем заключается проектирование реляционных баз данных ? и "Что лежит в основе процедур ?"

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

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

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

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

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

Вспомним определение функции как соответствия множества аргументов определенным значениям из множества определения функции и способы задания функций: формула, график и перечисление (таблица). Нетрудно понять, что функциональную зависимость (ФЗ) можно определить на довольно широком классе объектов. Определение функции не накладывает никаких ограничений на множество аргументов и множество значений функции, кроме их существования и наличия соответствия между их элементами. Поскольку ФЗ можно задать таблично, а таблица есть форма представления отношения, то становится очевидной связь между ФЗ и отношением. Отношение может задавать ФЗ. Это утверждение является первой (1) конструктивной идеей, которая положена в основу теории проектирования реляционных баз данных .

Определение 1. Пусть r (A 1 , A 2 , ..., A n) - схема отношения R , a X и Y - подмножества r . Говорят, что Х функционально определяет Y , если каждому значению атрибутов кортежа отношения из Х соответствует не более одного значения атрибутов того же кортежа отношения из Y . Такая ФЗ обозначается как .

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

Пример. Понятие функциональной зависимости Продемонстрируем понятие функциональной зависимости на примере графика полетов аэропорта. ГРАФИК_ПОЛЕТОВ (Пилот, Рейс, Дата_вылета, Время_вылета)

Известно, что:

• каждому рейсу соответствует определенное время вылета;
• для каждого пилота, даты и времени вылета возможен только один рейс;
• на определенный день и рейс назначается определенный пилот.

Следовательно:

• "Время_вылета" функционально зависим от "Рейс" : "Рейс" -> "Время_{} вылета" ;
• "Рейс" функционально зависим от {"Пилот", "Дата_вылета", "Время_вылета"} : {"Пилот", "Дата_вылета", "Время_вылета"} -> "Рейс" ;
• "Пилот" функционально зависим от {"Рейс", "Дата_вылета"} : {"Рейс", "Дата_вылета"} -> "Пилот" .

Важной задачей при выявлении функциональных зависимостей на атрибутах отношения, которое по определению является множеством, является выяснение, какой из атрибутов выступает как аргумент, а какой - как значение ФЗ. Наиболее подходящими кандидатами в аргументы ФЗ являются возможные ключи , так как кортежи представляют экземпляры сущности , которые идентифицируются значениями атрибутов своего ключа. Нестрого говоря, функциональная зависимость имеет место на отношении, когда значения кортежа на одном множестве атрибутов однозначным образом определяют значения кортежа на другом множестве атрибутов. Это рабочее определение ФЗ не содержит в себе тех формальных элементов, которые позволяют ответить на вопрос "А как проверить наличие ФЗ между атрибутами отношения?" Необходимый для этого формализм дает нам использование реляционных операций . Для получения формального (строгого) определения наличия ФЗ в отношении обратимся к реляционным операциям .

Определение 2. Пусть имеется отношение R со схемой r , X и Y - два подмножества R . ФЗ имеет место на R , если множество имеет не более одного кортежа для каждого значения х . Такая ФЗ называется также F -зависимостью.

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

Алгоритм, который проверяет, удовлетворяет ли отношение R ФЗ , состоит в сортировке отношения по значениям возможного ключа и установления факта однозначности между его значением и значениями других атрибутов. Этот алгоритм полезен, но он носит вспомогательный характер.

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

Функциональные зависимости фактически представляют собой утверждения обо всех отношениях предметной области. Эти отношения могут являться значениями схемы r и, в сущности, не могут быть получены формальными методами. Единственный способ установления функциональных зависимостей для схемы отношения r - это исследование семантики атрибутов сущностей предметной области . Являясь высказываниями о сущностях предметной области , они не могут быть доказаны. Это обстоятельство по существу порождает неединственность представления предметной области отношениями реляционной БД.

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

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

Цель нормализации

Нормализация - метод создания набора отношений с заданными свойствами на основе требований к данным, установленным в некоторой орга­низации.

Нормализация часто выполняется в виде последовательности тестов для некоторого отношения с целью проверки его соответствия (или несоответствия) требованиям заданной нормальной формы.

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

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

Функциональные зависимости

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

Функциональная зависимость - описывает связь между атрибутами отношения. Например, если в отношении. R, содержащем атрибуты А и В, атрибут В функционально зависит от атрибута А (что обозначается как АВ), то каждое значение атрибута А связано только с одним значением атрибута В. (Причем каждый из атрибутов А и В может состоять из одного или нескольких атрибутов.)

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

Зависимость между атрибу­тами А и В можно схематически представить в виде диаграммы, показанной на рисунке 5.

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

Рисунок 5 - Диаграмма функциональной за­висимости

При наличии функциональной зависимости атрибут или группа атрибутов, распо­ложенная на ее диаграмме слева от символа стрелки, называется детерминантом (determinant). Например, на рис. 6.1 атрибут А является детерминантом атрибута В.

Концепция функциональной зависимости является центральным понятием про­цесса нормализации.