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

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

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

2-аянормальная форма (2НФ) отношения. Определение полной функциональной зависимости и 2НФ. Характеристика отношения во 2НФ. Алгоритм приведения ко 2НФ. Теорема Хита. Примеры.

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

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

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

2NF - вторая нормальная форма.

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

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

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

1)не должны появляться ранее отсутствовавшие кортежи;

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

Теорема Хита

Пусть дано отношение .

Если r удовлетворяет функциональной зависимости , то оно равно соединению его проекцийи

3-я нормальная форма (3НФ) отношения. Определение транзитивной зависимости и 3НФ.Алгоритм приведения к 3НФ.Нормальная форма Бойса-Кодда (НФБК).Определение и алгоритм приведения к НФБК. Характеристика отношения в 3НФ и в НФБК. Примеры.

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

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

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

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

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

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

2-аянормальная форма (2НФ) отношения. Определение полной функциональной зависимости и 2НФ. Характеристика отношения во 2НФ. Алгоритм приведения ко 2НФ. Теорема Хита. Примеры.

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

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

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

2NF - вторая нормальная форма.

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

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

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

1)не должны появляться ранее отсутствовавшие кортежи;

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

Теорема Хита

Пусть дано отношение .

Если r удовлетворяет функциональной зависимости , то оно равно соединению его проекцийи

3-я нормальная форма (3НФ) отношения. Определение транзитивной зависимости и 3НФ.Алгоритм приведения к 3НФ.Нормальная форма Бойса-Кодда (НФБК).Определение и алгоритм приведения к НФБК. Характеристика отношения в 3НФ и в НФБК. Примеры.

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

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

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

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

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

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

c. Если мы желаем записать математически, что переменная у зависит от , то будем употреблять такое обозначение:

Эта запись читается так:

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

Точно так же, если функция U зависит от двух аргументов то эта зависимость обозначается следующим образом:

Здесь буквы f, х и у также не являются сомножителями.

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

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

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

Для того чтобы иметь возможность изучать функцию нужно ее задать.

e. Имеется много способов задать функцию, но все они сводятся к трем основным типам:

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

2) функцию можно задать графически;

3) функцию можно задать математической формулой.

f. Приведем примеры. Известно, что при вращении махового колеса возникают напряжения, которые стремятся разорвать его обод. Если обод колеса сделан из однородного материала, то напряжения зависят только от скорости вращения. Обозначая скорость через v, а напряжение в ободе через , мы можем записать что

Теория сопротивления материалов дает такую таблицу для значений функции (4), если обод сделан из литой стали:

Здесь v измеряется в метрах в секунду - в ньютонах на квадратный сантиметр.

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

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

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

h. От первых двух недостатков свободен графический способ задания функции.

Чтобы пояснить графический способ рассмотрим такой пример.

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

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

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

Для мягкой стали мы получим следующую кривую (рис. 31):

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

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

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

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

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

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

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

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

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

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

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

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

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

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