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

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

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

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

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

Ф И О ->Д олжн -> Оклад

Между атрибутами может иметь место многозначная зависимость.

В отношении R атрибут В многозначно зависит от атрибута А, если каждому значению А соответствует множество значений В, не связанных с другими атрибутами из R,

Многозначные зависимости могут быть «один ко многим» (1:М), «многие к одному» (М:1) или «многие ко многим» (М:М), обозначаемые соответственно: А=>Б, А<=Би А<=>Б.

Например, пусть преподаватель ведет несколько предметов, а каждый предмет может вестись несколькими преподавателями, тогда имеет местозависимость ФИО<=>Предмет. Так, из таблицы, приведенной на рис. 4.4, видно, что преподаватель Иванов И.М. ведет занятия по двум предметам, а дисциплина СУБД - читается двумя преподавателями: Ивановым И.М. и Петровым М.И.

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

Взаимно независимые атрибуты. Два или более атрибута называютсявзаимно независимыми, если ни один из этих атрибутов не является функционально зависимым от других атрибутов. В случае двух атрибутов отсутствие зависимости атрибута А от атрибута В можно обозначить так: A¬->B. Случай, когда A¬->В и B¬->A, можно обо­значить А¬<->В.

4.3.3 Аксиомы Армстронга

Чтобы определить ключи и понять логические следствия функциональных зависимостей в общем случае, необходимо вычислить замыкание F + изF или по крайней мере знать для заданногоF и функциональной зависимостиX Y , содержится лиX Y вF + . Для этого необходимо иметь правила вывода, которые указывают, как из одной или более зависимостей выводить другие зависимости.

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

А1: (рефлексивность). ЕслиY ≤ X ≤ М, то X Y логически следует изF . Заметим, что это правило даеттривиальные зависимости, т. е. зависимости, правая часть которых содержится в левой части. Его использование не зависит отF .

А2: (пополнение). ЕслиX Y иZ≤ М , тоX UZ  Y UZ . Важно напомнить, что данная зависимостьX Y либо принадлежитF , либо может быть выведена из принадлежащихF зависимостей с использованием описываемых аксиом.

A3:(транзитивность). ЕслиX Y иY Z, тоX Z .

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

Из аксиом Армстронга выводятся еще 5 аксиом (расширения, продолжения, псевдотранзитивности, объединения и декомпозиции), используемых для построенияполного семейства ФЗ.

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

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

ФИО	Долж	Оклад	Стаж	Надб	Каф	Предм	Группа	ВидЗан
Иванов И.М.	преп					СУБД		Лабор
Иванов И.М.	Преп					Информ		Лабор
Петров М.И.	Ст.преп					СУБД		Лекция
Петров М.И.	Ст.преп					Графика		Лабор
Сидоров Н.Г.	Преп					Информ		Лекция
Сидоров Н.Г.	Преп					Графика		Лекция
Егоров В.В.	Преп					ПЭВМ		Лекция

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

А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НФ.

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

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

Информация > формализация >> данные

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

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

Функциональная зависимость: «правильное решение = программа (программист)» и условие: «непрерывное соответствие задаче» действительны в большинстве случаев, но только совместно. Но это не та математическая основа, которая применяется при создании баз данных.

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

и базы данных

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

Основные варианты хранения, отличающиеся вариантами использования данных:

• файлы;
• базы данных.

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

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

Личный опыт и коллективный разум

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

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

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

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

• солидный Oracle;
• требовательный MS SQL Server;
• популярный MySQL.

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

Особенности программирования и данных

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

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

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

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

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

БД: простая зависимость в данных

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

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

Имя каждой колонки в каждой таблице должно быть уникальным в контексте задачи. Одно и то же данное не может быть в двух таблицах. Знать смысл понятий:

• «определить сущности»;
• «исключить избыточность»;
• «зафиксировать взаимосвязи»;
• «обеспечить достоверность».

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

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

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

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

Не обязательно, но вовсе не помешает представлять функциональную зависимость как:

F(x1, x2, …, xN) = (y1, y2, …, yN).

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

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

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

О старом добром Excel

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

• PHP, Perl, JavaScript, C++, Delphi.
• MySQL, Oracle, Visual FoxPro.

• Word.
• Excel.

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

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

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

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

Что такое функциональная зависимость, с чем, куда, почему… очевидно только автору или коллективу таковых.

О том, куда реляционные отношения идут

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

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

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

Вариантов отношений можно придумать великое множество. Это математика с логикой, и она строгая! Информация - это своя математика, особенная. В ней о формальности можно говорить только с очень большим минусом.

Можно формализовать работу отдела кадров, написать АСУ для добычи нефти или производства молока, хлеба, сделать выборку в огромной базе гугла, яндекса или рамблера, но результат будет всегда статичен и каждый момент времени одинаков!

Если функциональная зависимость = строгая логика и математика = основа для баз данных, то о какой динамике можно вести речь. Любое решение будет формальным, любая формальная модель данных + строгий алгоритм = точное и однозначное решение. Информация и область применения любой программы меняются всегда.

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

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

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

Если сменить тон и прислушаться к пульсу динамики, то все можно расписать на объекты. В первом приближении имя колонки в таблице - это объект, список имен - тоже объект, короче таблица - это объект шапки и в нем имена колонок в шапке. И шапки может вовсе не быть...

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

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

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

Функциональная зависимость описывает связь между атрибутами и является одним из основных понятий нормализации. Предположим, что реляционная схема имеет атрибуты (A, B, C,…, Z) и вся база может быть представлена в виде одного универсального отношения R=(A, B, C,…, Z). Следовательно, каждый атрибут в базе имеет уникальное имя.

Если A и B – атрибуты некоторого отношения R, и каждое значение А связано с одним и только одним значением В (причем каждый из атрибутов может состоять из одного или нескольких атрибутов), то атрибут В функционально зависим от атрибута А (ВàА).

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

Транзитивная зависимость для атрибутов A, B и C некоторого отношения означает следующее: если АàВ и ВàС, то С транзитивно зависит от атрибута А через атрибут В (при условии, что А функционально не зависит от В или С).

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

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

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

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

2) в таблице должны отсутствовать повторяющиеся группы полей;

3) каждое поле должно быть семантически неделимым.

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

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

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

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

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

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

Различие между 3НФ и НФБК заключается в том, что функциональная зависимость АàВ допускается в отношении 3НФ, если атрибут В является первичным ключом, а атрибут А не обязательно является потенциальным ключом. В отношении НФБК эта зависимость допускается только тогда, когда атрибут А является потенциальным ключом. Следовательно, НФБК является более строгой версией 3НФ, поскольку каждое отношение НФБК является 3НФ, но не всякое отношение 3НФ является НФБК.

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

Четвертая нормальная форма (4НФ) – отношение в НФБК, которое не содержит нетривиальных многозначных зависимостей.

Многозначная зависимость представляет такую зависимость между атрибутами отношения (например А, В и С), что каждое значение А представляет собой множество значений для В и множество значений для С. Однако множество значений В и С не зависят друг от друга.

Многозначная зависимость может быть дополнительно определена как тривиальная или нетривиальная. Многозначная зависимость АàВ некоторого отношения R определяется как тривиальная, если атрибут В является подмножеством атрибута А или . И наоборот, многозначная зависимость определяется как нетривиальная, если ни то ни другое условие не выполняется. Тривиальная многозначная зависимость не накладывает никаких ограничений на данное отношение, а нетривиальная – накладывает.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Иванов	100	8.07	10:20
Иванов	102	9.07	13:30
Исаев	90	7.07	6:00
Исаев	100	11.07	10:20
Исаев	103	10.07	19:30
Петров	100	12.07	10:20
Петров	102	11.07	13:30
Фролов	90	8.07	6:00
Фролов	90	12.07	6:00
Фролов	104	14.07	13:30

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

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

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

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

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

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

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

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

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

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

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