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

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

Рассмотрим для примера конкретную схему отношений и проанализируем её недостатки. Предположим, что данные о студентах, факультетах, специальностях, включены в таблицу со следующей схемой отношения: СТУДЕНТ (Код студента, Фамилия, Название факультета, Название специальности).

Эта схема отношений обусловливает следующие недостатки соответствующей базы данных :

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

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

Нормализация. Первая нормальная форма .

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

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

Рассмотрим следующий пример.

Таблица представляет сущность ЭКЗАМЕНАЦИОННАЯ ВЕДОМОСТЬ

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

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

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

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

8.2. Функциональные зависимости (зависимости между атрибутами отношения)

Пусть R(A 1 , A 2 , ..., A n) – схема отношения , а X и Y – подмножества {A 1 , A 2 , ..., A n } .

Функциональная зависимость на отношении R – это утверждение вида "Если два кортежа R совпадают по атрибутам множества (т.е. эти кортежи имеют в соответствующих друг другу компонентах одни и те же значения для каждого атрибута множества X ), то они должны совпадать и по атрибутам множества . Формально эта зависимость записывается выражением X -> Y , причем говорится, что X функционально определяет Y . Часто используется другое утверждение: X функционально определяет Y или Y функционально зависит от X (обозначается X -> Y ) тогда и только тогда, когда каждое значение множества X отношения R связано с одним значением множества Y отношения R . Иначе говоря, если два кортежа R совпадают по значению X , они совпадают и по значению Y .

Замечание. Вообще говоря, под термином " отношение " могут подразумеваться два понятия:

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

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

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

Пример функциональных зависимостей для отношения ЭКЗАМЕНАЦИОННАЯ ВЕДОМОСТЬ

Код студента -> Фамилия Код студента, Код экзамена -> Оценка

Пример функциональных зависимостей для отношения СТУДЕНТ, приведенного в начале настоящей лекции

Код студента -> Фамилия, Код студента -> Факультет

Заметим, что последняя зависимость существует при условии, что один студент не может обучаться на нескольких факультетах.

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

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

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

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

Введенные понятия позволяют формально определить понятие ключа.

Пусть существует некоторая схема R с атрибутами A 1 A 2 ...A n , F – некоторое множество функциональных зависимостей и X – некоторое подмножество R . Тогда X называется ключом, если, во-первых, в F + существует зависимость X -> A 1 A 2 ...A n и, во-вторых, ни для какого подмножества Y , входящего в X , зависимость Y -> A 1 A 2 ...A n не принадлежит F + .

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

Частичной функциональной зависимостью будем называть зависимость неключевого атрибута от части составного ключа .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Лекция 3. Общие понятия и определения. Классификация функций. Предел функции. Бесконечно малые и бесконечно большие функции. Основные теоремы о бесконечно малых функциях.

Функция

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

Определение

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

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

Понятие функции

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

Определение

Переменная величина y называется функцией (однозначной) от переменной величины x, если они связаны между собой так, что каждому рассматриваемому значению x соответствует единственное вполне определенное значение величины y (сформулировал Н.И.Лобачевский).

Обозначение y=f(x) (1)

x – независимая переменная или аргумент;

y – зависимая переменная (функция);

f – характеристика функции.

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

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

2. Функция (2). Функция определена при

Для наглядного представления поведения функции строят график функции.

Определение

Графиком функции y=f(x) называется множество точек M(x,y) плоскости OXY , координаты которых связаны данной функциональной зависимостью. Или график функции – это линия, уравнением которой служит равенство, определяющее функцию.

Например, график функции (2) – полуокружность радиуса 2 с центром в начале координат.

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

Рассмотрим несколько простейших функциональных зависимостей

1. Прямая функциональная зависимость

Определение

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

y=kx , где k – коэффициент пропорциональности.

График функции

1. Линейная зависимость

Определение

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

График функции

1. Обратная пропорциональная зависимость

Определение

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

1. Квадратичная зависимость

Квадратичная зависимость в простейшем случае имеет вид , где k – некоторая постоянная величина. График функции – парабола.

1. Синусоидальная зависимость.

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

- функция называется гармоникой.

A – амплитуда;

Частота;

Начальная фаза.

Функция периодическая с периодом . Значения функции в точках x и x+T , отличающихся на период, одинаковы.

Функцию можно привести к виду , где . Отсюда получаем, что графиком гармоники является деформированная синусоида с амплитудой A периодом T, сдвинутая по оси ОХ на величину

Способы задания функции

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

1. Аналитический способ задания функции

Если функция выражена при помощи формулы, то она задана аналитически.

Например

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

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

1. Табличный способ задания функции

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

Можно ли от табличного задания функции перейти к аналитическому выражению?

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

1. Графический способ задания функции

Аналитический и табличный способы не дают наглядного представления о функции.

Этого недостатка лишен графический способ задания функции y=f(x) , когда соответствие между аргументом x и функцией y устанавливается с помощью графика.

Понятие неявной функции

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

Функция y от аргумента x называется неявной, если она задана уравнением

F(x,y)=0 (1) неразрешенным относительно зависимой переменной.

Понятие обратной функции

Пусть задана функция y=f(x) (1). Задавая значения аргумента х, получаем значения функции y.

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

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

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

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

Функциональная зависимость описывает связь между атрибутами и является одним из основных понятий нормализации. Предположим, что реляционная схема имеет атрибуты (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.

Лекции № 8-9.

Функциональная зависимость. Нормальные формы.

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

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

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

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

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

Вначале вспомним некоторые понятия:

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

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

Определение функциональной зависимости: Пусть X и Y атрибуты некоторого отношения. Если в любой момент времени произвольному значению X соответствует единственное значение Y, то Y функционально зависит от X (X →Y)

Если ключ является составным, то любой атрибут должен зависеть от ключа в целом, но не может находиться в функциональной зависимости от какой-либо части составного ключа, т.е. функциональная зависимость имеет вид (X 1 , X 2 , ..., X) →Y.

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

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

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

Определение транзитивной функциональной зависимости: Пусть X, Y, Z - три атрибута некоторого отношения. При эtom X →Y и Y →Z, но обратное соответствие отсутствует, то есть Y не зависит от Z, а Х не зависит от Y. Тогда говорят, что Z транзитивно зависит от Х.

Определение многозначной зависимости: Пусть Х и Y атрибуты некоторого отношения. Атрибут Y многозначно зависит от атрибута X, если. каждому значению X соответствует множество значений Y, не связанных с другими атрибутами из отношения. Многозначные зависимости могут носить характер «один ко многим» (1:М), «многие к одному» (М:1) или «многие ко многим» (М:М), обозначаемые соответственно: X=>Y, Y<=X и X<=>Y. Например, преподаватель ведет несколько предметов, а каждый предмет может вестись несколькими преподавателями, тогда имеет место зависимость ФИО <=> Предмет.

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

ФИО - фамилия и инициалы преподавателя (совпадения фамилий и инициалов исключаются).

Должность - должность, занимаемая преподавателем.

Оклад- оклад преподавателя.

Стаж - преподавательский стаж. Д_Стаж - надбавка за стаж.

Кафедра - номер кафедры, на которой числится преподаватель.

Предмет - название предмета (дисциплины), читаемого преподавателем.

Группа - номер группы, в которой преподаватель проводит занятия.

Вид занятия - вид занятий, проводимых преподавателем в учебной группе.

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