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

Энциклопедичный 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} .

r (R) , A ⊆ R , B ⊆ R {\displaystyle r\left(R\right),\ A\subseteq R,\ B\subseteq R} (A → B) ⇔ ((∀ t 1 , t 2 ∈ r: t 1 (A) = t 2 (A)) ⇒ (t 1 (B) = t 2 (B))) {\displaystyle \left(A\to B\right)\Leftrightarrow \left(\left(\forall {{t}_{1}},{{t}_{2}}\in r:{{t}_{1}}\left(A\right)={{t}_{2}}\left(A\right)\right)\Rightarrow \left({{t}_{1}}\left(B\right)={{t}_{2}}\left(B\right)\right)\right)}

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

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

(B ⊆ A) ⇒ (A → B) {\displaystyle \left(B\subseteq A\right)\Rightarrow \left(A\to B\right)}

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

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

(A → B) ∧ (B → C) ⇒ (A → C) {\displaystyle \left(A\to B\right)\wedge \left(B\to C\right)\Rightarrow \left(A\to C\right)} .

Множество всех атрибутов, которые подразумеваются данным множеством функциональных зависимостей 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}^{+}}} .

r (R) , S , Z ⊆ R , A i ⊆ R , i = 1 , n ¯ {\displaystyle r\left(R\right),\ S,\ Z\subseteq R,\ {{A}_{i}}\subseteq R,\ i={\overline {1,n}}} Z + = { A i: (Z → A i) ∈ S + } {\displaystyle {{Z}^{+}}=\left\{{{A}_{i}}:\left(Z\to {{A}_{i}}\right)\in {{S}^{+}}\right\}}

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

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

• Если любая функциональная зависимость из 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} .

(A → B) ⇒ (r (A , B , C) = r [ A , B ] JOIN r [ A , C ]) {\displaystyle \left(A\to B\right)\Rightarrow \left(r\left(A,B,C\right)=r\left\ {\text{JOIN}}\ r\left\right)}

Лекция 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, сдвинутая по оси ОХ на величину

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 удовлетворяет условию

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

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

Линейной функцией называется функция, которую можно задать формулой вида y=kx+b, где x – независимая переменная, k и b – заданные числа. Для построения графика линейной функции достаточно найти координаты двух точек графика, отметить эти точки в координатной плоскости и провести через них прямую. Прямая пропорциональность – функция вида у=кх, где х – независимая переменная, к – не равное нулю число. Графиком прямой пропорциональности является прямая, проходящая через начало координат.

Построение графика линейной функции Для построения графика линейной функции необходимо: - выбрать любые два значения переменной х (аргумента), например 0 и 1; - вычислить соответствующие значения переменной y (функции). Полученные результаты удобно записывать в таблицу x01 y - полученные точки А и В изображаем в системе координат; - соединяем по линейке точки А и В. Пример. Построим график линейной функции y = -3·x+6. x01 y63

Обратной пропорциональностью называется функция, которую можно задать формулой вида у=k/х, где х - независимая переменная и k - не равное нулю число. Областью определения такой функции является множество всех чисел, отличных от нуля. Если величины x и y обратно пропорциональны, то функциональная зависимость между ними выражается уравнением y = k / x, где k есть некоторая постоянная величина. График обратной пропорциональности есть кривая линия, состоящая из двух ветвей. Этот график называют гиперболой. В зависимости от знака k ветви гиперболы расположены либо в 1 и 3 координатных четвертях (k положительно), либо во 2 и 4 координатных четвертях (k отрицательно). На рисунке изображен график функции y = k/х, где k – отрицательное число.

ЧАСТНЫЕ СЛУЧАИ ЛИНЕЙНОЙ ФУНКЦИИ. y=kx, k0, b=0 - прямая пропорциональность,. График - прямая, проходящая через начало координат; y=b, k=0, b0. (b>0, выше оси OX; b 0, выше оси OX; b"> 0, выше оси OX; b"> 0, выше оси OX; b" title="ЧАСТНЫЕ СЛУЧАИ ЛИНЕЙНОЙ ФУНКЦИИ. y=kx, k0, b=0 - прямая пропорциональность,. График - прямая, проходящая через начало координат; y=b, k=0, b0. (b>0, выше оси OX; b"> title="ЧАСТНЫЕ СЛУЧАИ ЛИНЕЙНОЙ ФУНКЦИИ. y=kx, k0, b=0 - прямая пропорциональность,. График - прямая, проходящая через начало координат; y=b, k=0, b0. (b>0, выше оси OX; b">

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

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

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

Ограничения, которые зависят от семантики элементов домена. Эти ограничения основаны на понимании того, что означают компоненты кортежей. Например, рост человека не может быть равен 6 метрам, как и ни один человек со стажем работы 37 лет не может иметь возраст 25 лет.

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

Пусть R (A 1 , A 2 ,…, А n ) - схема отношения, аXиY- подмножества { A 1 , A 2 , ... , А п }. Говорят, что « X функционально определяет Y» или «Yфункционально зависит отX», и обозначают это какX Y , если в любом отношении r , являющемся текущим значением R , не могут содержаться два кортежа, компоненты которых совпадают по всем атрибутам, принадлежащим множеству X , но не совпадают по одному или более атрибутам, принадлежащим множеству Y . Возможна более простая формулировка. Атрибут В функционально зависит от атрибута А, т.е. А->В, если каждому значению А соответствует в точности одно значение В. Это означает, что во всех кортежах с одинаковым значением атрибута А атрибут В будет иметь также одно и то же значение. Здесь А и В могут быть составными - состоять из двух и более атрибутов.

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

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

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

Пусть, вообще, F есть множество функциональных зависимостей для схемы отношения R и X  Y - некоторая функциональная зависимость. Говорят, что зависимость X  Y логически следует из F , если для каждого отношения r со схемой R , удовлетворяющего зависимостям из F , удовлетворяется также X  Y . Пусть F + обозначает замыкание F - множество функциональных зависимостей, которые логически следуют из F . Если F = F + , то говорят, что F - полное семейство зависимостей.

Рассматривая наборы объектов, мы предполагали, что существует ключ - множество атрибутов, которое уникально определяет объект. Аналогичное понятие существует и для отношений с функциональными зависимостями. Если R - схема отношения с атрибутами A 1 , A 2 ,…, А n и функциональными зависимостями F , а X - подмножество A 1 , A 2 ,…, А n , то X называется ключом R , если:

X  A 1 A 2 … А n принадлежит F + .

Ни для какого собственного подмножества Y ≤ X зависимость Y  A 1 A 2 …А n не принадлежит F + .

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

Помимо этого используется термин детерминант . Атрибут (или группа атрибутов) называется детерминантом , если от него функционально зависит какой-либо другой атрибут. Другими словами, если имеется функциональная зависимость A → B, то A – детерминант.

ния системы или анализа мнений пользователей о работе системы.

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

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

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

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

По сути, функциональная зависимость является связью типа «многие к одному» между множествами атрибутов внутри данного отношения.

Пусть R - семейство всевозможных отношений с одинаковым заголовкомH R (можно называть

переменной типа отношения, а всякое r P R - значением этой переменной(или допустимым отношением)). Пусть A Ď H R и B Ď H R - некоторые подмножества атрибутов заголовка переменной отношения R .

Определение 1. Множество атрибутовB функционально зависимо отA (и обозначаютA Ñ B ) тогда и только тогда, когда каждое значение атрибутовA любого допустимого отношенияr связано ровно с одним значением атрибутовB отношенияr , т. е. если два кортежа совпадают по значению атрибутовA , то они совпадают и по значению атрибутовB . Формально:

pA ÑB q ô @r HR ; Br P R @T 1 ;T 2 P Br p@a PA T 1 :aT 2 :aq Ñ p@b PB T 1 :bT 2 :bq:

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

Определение 2. ЕслиA Ñ B , то множество атрибутовA называютдетерминантом , аB -зави-

симой частью.

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

циональных зависимостей до некоторых допустимых размеров. Почему эта цель важна? Одна из причин состоит в том, что многие функциональные зависимости являются ограничениями целостности , поэтому желательно, чтобы СУБД обеспечивала их соблюдение. Следовательно, для каждого заданного множества функциональных зависимостей S желательно найти такое множество T , которое(в идеальной ситуации) было бы существенно меньше множества S по мощности и при этом каждая функциональная зависимость в множестве S могла бы быть заменена функциональной зависимостью из множества T . Если бы такое множество T было найдено, то СУБД достаточно было бы контролировать выполнение функциональных зависимостей из множества T , что автоматически обеспечивало бы соблюдение всех функциональных зависимостей из множества S . Именно поэтому задача поиска подходящего множества T представляет большой практический интерес.

Тривиальные и нетривиальные зависимости

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

Определение 3’. Функциональная зависимостьA Ñ B называетсятривиальной тогда и только тогда, когдаB Ď A , иначе она называетсянетривиальной .

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

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

Из одних функциональных зависимостей могут следовать другие функциональные зависимости. Пусть есть переменная отношения R , аA Ď H R ,B Ď H R иC Ď H R - некоторые подмножества

его атрибутов.

Определение 4. Функциональная зависимостьA Ñ C называетсятранзитивной (илипроходящей через B ), если существуют функциональные зависимостиA Ñ B иB Ñ C .

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

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

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

Пусть A Ď H R ,B Ď H R ,C Ď H R - некоторые подмножества атрибутов переменной отношенияR .

Базовые аксиомы Армстронга:

1. Правило рефлексивности (reflexivity) : если B Ď A , то A Ñ B .

2. Правило дополнения (augmentation) : если A Ñ B , то A Y C Ñ B Y C .

3. Правило транзитивности (transitivity) : если A Ñ B и B Ñ C , то A Ñ C .

Доказательство: Первая аксиома справедлива, т. к.A Ñ B приB Ď A является тривиальной функ-

циональной зависимостью по определению.
Докажем аксиому дополнения от противного. Предположим, что при A		Ñ B неверно
A Y C Ñ B Y C . Это значит, что найдутся два кортежаT 1 P B r иT 2 P B r (B r		Тело некото-
рого допустимого отношения r ) такие, что
T 1 :acT 2 :ac	@ac P A YC ;
но при этом
Dbc P B YC :T 1 :bcT 2 :bc
Так как A Ď A Y C , то по аксиоме рефлексивностиA Y C Ñ A , а значит, из (7.1) следует, что
T 1 :aT 2 :a	@a P A :
Поскольку задано A Ñ B , то из (7.3) следует
T 1 :bT :b	@b P B :
Но тогда из неравенства (7.2) и (7.4) следует, что упоминаемый bc (7.2) принадлежитC , т. е.
Dc P C: T 1 :cT 2 :c
С другой стороны, в силу наличия тривиальной зависимости A Y C Ñ C и (7.1) получаем
T 1 :cT 2 :c @c PC
что противоречит (7.5). Следовательно, исходное предположение было неверным.

1 Но справедливость «аксиом» Армстронга доказывается с помощью определения функциональной зависимости.

Аксиому транзитивности тоже докажем от противного. Предположим, что A Ñ B иB Ñ C , ноA ­Ñ C . ТогдаDr P R: D T 1 ; T 2 P B r такие, что

T 1 :aT 2 :a @a PA

Данная система правил является:

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

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

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

В целях упрощения нахождения S можно ввестидополнительные правила вывода (D Ď H R ):

4. Правило самоопределения : A Ñ A .

5. Правило декомпозиции : если A Ñ B Y C , то A Ñ B и A Ñ C .

6. Правило объединения : если A Ñ B и A Ñ C , то A Ñ B Y C .

7. Правило композиции : если A Ñ B и C Ñ D , то A Y C Ñ B Y D .

8. Общая теорема объединения (Дарвен): если A Ñ B и C Ñ D , то A Y p C z B q Ñ B Y D .

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

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

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

Определение 6. МножествоS 2 называетсяпокрытием для множестваS 1 , если любая функциональная зависимость, которая следует из множества зависимостейS 1 , следует также из множества зависимостейS 2 , т. е.S 1 Ď S 2 .

Замечание. Это означает, что если СУБД обеспечит соблюдение ограничений, представленных зависимостями множестваS 2 , то автоматически будут соблюдены и все ограничения, устанавливаемые зависимостями множестваS 1 .

Определение 7. Множества зависимостейS 1 иS 2 называютсяэквивалентными , еслиS 1 является покрытием дляS 2 иS 2 является покрытием дляS 1 , т. е.S 1 S 2 .

Определение 8. Множество функциональных зависимостейS называетсянеприводимым (минимальным) тогда и только тогда, когда оно обладает всеми тремя свойствами:

1. Зависимая часть каждой функциональной зависимости из S содержит только один атрибут.

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

терминанта не может быть опущен без изменения замыкания S 1 (т. е. без преобразованияS

в неэквивалентное множество зависимостей).

3. Ни одна функциональная зависимость из множества S не может быть удалена без изменения его замыканияS (т. е. без преобразования множестваS в неэквивалентное множество зависимостей).

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

Иначе называется приводимым .

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

Доказательство: Пусть дано исходное множество зависимостейS .

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

2. Далее для каждой зависимости f P S следует проверить каждый атрибутa в детерминанте зависимостиf : если удаление атрибутаa из левой части зависимостиf не приводит к изменению замыканияS , то этот атрибут следует удалить.

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

Получившееся в результате таких действий множество S 1 является неприводимым и эквивалентным исходному множествуS .l

Определение 9. Множество функциональных зависимостейT , которое неприводимо и эквивалентно другому множеству функциональных зависимостейS , называетсянеприводимым эквивалентом множестваS .

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

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

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

Одним из способов декомпозиции является использование проекции, для которой обратной будет

операция соединения, что показывается теоремой Хита:

Теорема (Хит; Heath) . Пусть задана переменная отношенияR с заголовкомH R A Y B Y C , гдеA ; B ; C - попарно непересекающиеся множества атрибутов переменной отношенияR . ЕслиR удовлетворяет функциональной зависимостиA Ñ B , то можно провести декомпозицию без потерь в виде

R1 A Y B pRq; R2 A Y C pRq;

которая обратима с помощью естественного соединения: R R 1 " R 2 .

В качестве следствия-обобщения можно (неформально) отметить, что декомпозиция переменной отношенияR на проекцииR l ; R 2 ; : : : ; R n выполняетсябез потерь , еслиR R l " R 2 " : : : " R n .

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

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

стей:

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

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

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