При представлении концептуальной схемы в виде реляционной модели возможны различные варианты выбора схем отношений. Одни варианты выбора рассматривались в предыдущих разделах (п. 6.2.3), другие получаются объединением (или разбиением) некоторых схем отношений. От правильного выбора схем отношений, представляющих концептуальную схему, в значительной степени будет зависеть эффективность функционирования базы данных .
Рассмотрим для примера конкретную схему отношений и проанализируем её недостатки. Предположим, что данные о студентах, факультетах, специальностях, включены в таблицу со следующей схемой отношения: СТУДЕНТ (Код студента, Фамилия, Название факультета, Название специальности).
Эта схема отношений обусловливает следующие недостатки соответствующей базы данных :
- Дублирование информации (избыточность). У студентов, обучающихся на одном факультете, будет повторяться название факультета. Для разных факультетов будут повторяться специальности.
- Потенциальная противоречивость (аномалии обновления ). Если, например, изменится название специальности, то изменяя её в одном кортеже (у одного студента), необходимо изменять и во всех других кортежах, где она присутствует.
- Потенциальная возможность потери сведений (аномалии удаления ). При удалении информации о всех студентах, поступающих на определенную специальность, мы теряем все сведения об этой специальности.
- Потенциальная возможность невключения информации в базу данных (аномалии включения ). В базе данных будут отсутствовать сведения о специальности, если на ней нет обучающихся студентов.
В теории реляционных баз данных существуют формальные методы построения реляционной модели базы данных , в которой отсутствует избыточность и аномалии обновления , удаления и включения.
Нормализация. Первая нормальная форма .
Построение рационального варианта схем отношений (обладающего лучшими свойствами при операциях включения, модификации и удаления данных, чем все остальные наборы схем) осуществляется путем так называемой нормализации схем отношений . Нормализация производится в несколько этапов. На начальном этапе схема отношений должна находиться в первой нормальной форме ( 1НФ ).
Отношение находится в первой нормальной форме , если все атрибуты отношения принимают простые значения (атомарные или неделимые), не являющиеся множеством или кортежем из более элементарных составляющих .
Рассмотрим следующий пример.
Таблица представляет сущность ЭКЗАМЕНАЦИОННАЯ ВЕДОМОСТЬ
| Код студента | Фамилия | Код экзамена | Предмет и дата | Оценка |
|---|---|---|---|---|
| 1 | Сергеев | 1 | Математика 5.06.08 | 4 |
| 2 | Иванов | 1 | Математика 5.06.08 | 5 |
| 1 | Сергеев | 2 | Физика 9.06.08 | 5 |
| 2 | Иванов | 2 | Физика 9.06.08 | 5 |
Теперь на пересечении любой строки и любого столбца находится одно значение и, следовательно, данная таблица находится в первой нормальной форме .
Далее отношение , представленное в первой нормальной форме , последовательно преобразуется во вторую и третью нормальные формы . Процесс построения второй и третьей нормальных форм будет описан в следующих подразделах. При некоторых предположениях о данных третья нормальная форма является искомым наилучшим вариантом.
Если эти предположения не выполняются, то процесс нормализации продолжается и отношение преобразуется в четвертую и пятую нормальные формы . Построение соответствующих форм описано в литературе и в данной книге не рассматривается.
Прежде чем перейти к построению второй нормальной формы , необходимо определить ряд формальных понятий.
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 + .
Полной функциональной зависимостью называется зависимость неключевого атрибута от всего составного ключа .
Частичной функциональной зависимостью будем называть зависимость неключевого атрибута от части составного ключа .
Для вычисления замыкания множества функциональных зависимостей используются следующие правила вывода (
Введение
Диалектический подход к изучению природы и общества требует рассмотрения явлений в их взаимосвязи и непрестанном изменении. Понятия корреляции и регрессии появились в середине XIX в. благодаря работам английских статистиков Ф. Гальтона и К. Пирсона. Первый термин произошел от латинского «correlatio» – соотношение, взаимосвязь. Второй термин (от лат. «regressio» - движение назад) введен Ф. Гальтоном, который, изучая зависимость между ростом родителей и их детей, обнаружил явление «регрессии к среднему» – у детей, родившихся у очень высоких родителей, рост имел тенденцию быть ближе к средней величине.
В практике экономических исследований очень часто имеющиеся данные нельзя считать выборкой из многомерной нормальной совокупности, например, когда одна из рассматриваемых переменных не является случайной или когда линия регрессии явно не прямая и т.п. В этих случаях пытаются определить кривую (поверхность), которая дает наилучшее (в смысле метода наименьших квадратов) приближение к исходным данным. Соответствующие методы приближения получили название регрессионного анализа. Задачами регрессионного анализа являются установление формы зависимости между переменными, оценка функции регрессии, оценка неизвестных значений (прогноз значений) зависимой переменной.
Выше сказанным обусловлена актуальность выбора темы курсовой работы. Цель данной работы – исследовать функциональную зависимость между случайными величинами методами корреляционного и регрессионного анализов.
Глава 1 Корреляционный анализ
1.1 Функциональная, статистическая и корреляционная зависимости
В естественных науках часто речь идет о функциональной зависимости (связи), когда каждому значению одной переменной соответствует вполне определенное значение другой. Функциональная зависимость может иметь место как между детерминированными (неслучайными) переменными (например, зависимость скорости падения в вакууме от времени и т.п.), так и между случайными величинами (например, зависимость стоимости проданных изделий от их числа и т.п.).В экономике в большинстве случаев между переменными величинами существуют зависимости, когда каждому значению одной переменной соответствует не какое-то определенное, а множество возможных значений другой переменной. Иначе говоря, каждому значению одной переменной соответствует определенное (условное) распределение другой переменной. Такая зависимость (связь) получила название статистической (или стохастической, вероятностной).
Возникновение понятия статистической связи обусловливается тем, что зависимая переменная подвержена влиянию ряда неконтролируемых или неучтенных факторов, а также тем, что измерение значений переменных неизбежно сопровождается некоторыми случайными ошибками. Примером статистической связи является зависимость урожайности от количества внесенных удобрений, производительности труда на предприятии от его энерговооруженности и т.п.
В силу неоднозначности статистической зависимости между Y и Х для исследователя, в частности, представляет интерес усредненная по х схема зависимости, т.е. закономерность в изменении среднего значения - условного математического ожидания (Y) (математического ожидания случайной переменной Y, найденного при условии, что переменная Х приняла значение х) в зависимости от х.
Определение : Статистическая зависимость между двумя переменными, при которой каждому значению одной переменной соответствует определенное среднее значение, т.е. условное математическое ожидание другой, называется корреляционной. Иначе, корреляционной зависимостью между двумя переменными величинами называется функциональная зависимость между значениями одной из них и условным математическим ожиданием другой.
Корреляционная зависимость может быть представлена в виде:
Предполагается, что φ(x)≠const и ψ(x)≠const, т.е. если при изменении х или у уcловные математические ожидания(Y) и не изменяются, то говорят, что корреляционная зависимость между переменными Х и У отсутствует. Сравнивая различные виды зависимости между Х иY, можно сказать, что с изменением значений переменной Х при функциональной зависимости однозначно изменяется определенное значение переменной у, при корреляционной – определенное среднее значение (условное математическое ожидание) Y, а при статистической- определенное (условное) распределение переменной Y (Рис.1.1)
Таким образом, из рассмотренных зависимостей наиболее общей выступает статистическая зависимость. Каждая корреляционная зависимость является статистической, но не каждая статистическая зависимость является корреляционной. Функциональная зависимость представляет частный случай корреляционной.
Уравнения (1.1) и (1.2) называются модельными уравнениями регрессии (или просто уравнениями регрессии) соответственно Y по Х и Х по Y, функции ψ(x) и φ(у) – модельными функциями регрессии (или функциями регрессии), а их графики - модельными линиями регрессии (или линиями регрессии).
Для отыскания модельных уравнений регрессии, вообще говоря, необходимо знать закон распределения двумерной случайной величины (Х,Y). На практике исследователь, как правило, располагает лишь выборкой пар значений (,) ограниченного объема. В этом случае речь может идти об оценке (приближенном выражении) по выборке функции регрессии. Такой наилучшей (в смысле метода наименьших квадратов) оценкой является выборочная линия (кривая) регрессии Y по Х
где – условная (групповая) средняя переменной Y при фиксированном значении переменной Х = х; ,…,- параметры кривой.
Аналогично определяется выборочная линия (кривая) регрессии Х по Y:
где – условная (групповая) средняя переменной Х при фиксированном значении переменной Y= у; -параметры кривой.
Уравнения (1.3), (1.4) называют также выборочными уравнениями регрессии соответственно Yпо Х и Х по Y.
При правильно определенных аппроксимирующих функциях) и с увеличением объема выборки (n) они будуг сходиться по вероятности соответственно к функциям регрессии ψ(x) и φ(у).
Статистические связи между переменными можно изучать методами корреляционного и регрессионного анализа. Основной задачей регрессионного анализа является установление формы и изучение зависимости между переменными. Основной задачей корреляционного анализа – выявление связи между случайными переменными и оценка ее тесноты.
1.2 Линейная парная регрессия
Данные о статистической зависимости удобно задавать в виде корреляционной таблицы.
Рассмотрим
в качестве примера зависимость между
суточной выработкой продукции Y
(т) и величиной основных
производственных фондов Х
(млн руб.) для совокупности
50 однотипных предприятий (табл. 1).
(В
таблице черези обозначены
середины соответствующих интервалов,
а через, и –
соответственно их частоты.)
Для каждого значения, т.е. для каждой строки корреляционной таблицы вычислим групповые средние
где - частоты пар () и; m – число интервалов по переменной Y.
Вычисленные групповые средние поместим в последнем столбце корреляционной таблицы и изобразим графически в виде ломаной, называемой эмпирической линией регрессии Y по X
Аналогично для каждого значения по формуле
вычислим групповые средние, где, l – число интервалов по переменной X.
По виду ломанной можно определить наличие линейной корреляционной зависимости Y по X между двумя рассматриваемыми переменными, которая выражается тем точнее чем больше объем выборки n:
Поэтому уравнение регрессии(1.3) будем искать в виде:
Отвлечемся на время от рассматриваемого примера и найдем формулы расчета неизвестных параметров уравнения линейной регрессии.
С этой целью применим метод наименьших квадратов, согласно которому неизвестные параметры и выбираются таким образом, чтобы сумма квадратов отклонений эмпирических групповых средних, вычисленных по формуле (1.5), от значений, найденных по уравнению регрессии (1.8), была минимальной:
На основании необходимого условия экстремума функции двух переменных S=S() приравниваем к нулю ее частные производные, т.е.
Откуда после преобразования получим систему нормальных уравнений для определения параметров линейной регрессии:
Учитывая (1.5) преобразуем выражение и с учетом (1.7), разделив обе части уравнений (1.10) на n, получим систему нормальных уравнений в виде:
где соответствующие средние определяются по формулам:
Подставляя значение из первого уравнения системы(1.11) в уравнение регрессии (1.8), получаем
Коэффициент b 1 в уравнении регрессии, называемый выборочным коэффициентом регрессии (или просто коэффициентом регрессии) Y по Х, будем обозначать символом. Теперь уравнение регрессии Y по Х запишется так:
Коэффициент регрессии Yпо Х показывает, на сколько единиц в среднем изменяется переменная Y при увеличении переменной Х на одну единицу.
Решая систему (1.11), найдем
где - выборочная дисперсия переменной X
µ - выборочный корреляционный момент:
Рассуждая аналогично и полагая уравнение регрессии (1.4) линейным, можно привести его к виду:
выборочный коэффициент регрессии (или просто коэффициент регрессии) Х по Y, показывающий, на сколько единиц в среднем изменяется переменная Х при увеличении переменной Y на одну единицу= – (–выборочная дисперсия переменной Y. зависимость . При этом все наблюдения располагаются... Линия тренда (рис. 2); 3) выбрать вид зависимости регрессии . Для нашего примера тип тренда...
Парная регрессия (3)
Контрольная работа >> МатематикаСмысл регрессионного анализа – построение функциональных зависимостей между двумя группами переменных величин... линейные и нелинейные регрессии . Линейная регрессия :. Нелинейные регрессии делятся на два класса: регрессии , нелинейные относительно...
ния системы или анализа мнений пользователей о работе системы.
Целью этого этапа является оптимизация функционирования существующей системы путем реорганизации базы данных и/или внесения изменений в программное обеспечение.
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 можно визуально представить в видедиаграммы функциональных зависимо-
стей:
Каждый атрибут изображается прямоугольником с именем атрибута в нем.
Каждое множество атрибутов изображается в виде прямоугольника, внутри которого находятся прямоугольники-атрибуты, которые входят в множество атрибутов.
Функциональная связь изображается в виде стрелки от домена (всегда является потенциальным ключом) к множеству атрибутов зависимой части.
Функциональные зависимости
Функциональная зависимость описывает связь между атрибутами и является одним из основных понятий нормализации. Предположим, что реляционная схема имеет атрибуты (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. Например, преподаватель ведет несколько предметов, а каждый предмет может вестись несколькими преподавателями, тогда имеет место зависимость ФИО <=> Предмет.
Рассмотрим следующий пример: Предположим, что для учебной части факультета создается БД о преподавателях, которая включает следующие атрибуты:
ФИО - фамилия и инициалы преподавателя (совпадения фамилий и инициалов исключаются).
Должность - должность, занимаемая преподавателем.
Оклад- оклад преподавателя.
Стаж - преподавательский стаж. Д_Стаж - надбавка за стаж.
Кафедра - номер кафедры, на которой числится преподаватель.
Предмет - название предмета (дисциплины), читаемого преподавателем.
Группа - номер группы, в которой преподаватель проводит занятия.
Вид занятия - вид занятий, проводимых преподавателем в учебной группе.
Исходное отношение ПРЕПОДАВАТЕЛЬ
