Определение функциональной зависимости лежит в основе. Простейшие функциональные зависимости. Линейная парная регрессия

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

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

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

• Описание концептуальной схемы БД в терминах выбранной СУБД.
• Описание внешних моделей в терминах выбранной СУБД.
• Описание декларативных правил поддержки целостности базы данных.
• Описание процедур поддержки семантической целостности базы данных.

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

ОПРЕДЕЛЕНИЕ

Корректной назовем схему БД, в которой отсутствуют нежелательные зависимости между атрибутами отношений.

Процесс разработки корректной схемы реляционной БД называется логическим проектированием БД.

Проектирование схемы БД может быть выполнено двумя путями:

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

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

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

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

В теории реляционных БД обычно выделяется следующая последовательность нормальных форм:

• первая нормальная форма (1НФ);
• вторая нормальная форма (2НФ);
• третья нормальная форма (3НФ);
• нормальная форма Бойса-Кодда (НФБК);
• четвертая нормальная форма (4НФ);
• пятая нормальная форма, или форма проекции-соединения (5НФ).

Основные свойства нормальных форм:

• каждая следующая нормальная форма в некотором смысле улучшает свойства предыдущей;
• при переходе к следующей нормальной форме свойства предыдущих нормальных форм сохраняются.

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

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

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

Функциональные зависимости определяют не текущее состояние БД, а все возможные ее состояния, то есть они отражают те связи между атрибутами, которые присущи реальному объекту, который моделируется с помощью БД.

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

Приведем ряд основных определений.

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

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

Левая и правая части ФЗ называются детерминантом и зависимой частью соответственно.

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

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

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

Очевидным способом сокращения множества ФЗ является исключение тривиальных ФЗ.

Функциональная зависимость тривиальна , если ее правая часть является подмножеством левой части. Например, для БД поставщиков и деталей тривиальная ФЗ:

(PNUM, DNUM)®PNUM

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

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

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

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

Существует несколько способов задания функции: 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">

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

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

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

Пусть нам дано отношение, содержащее данные о результатах какой-то одной конкретной сессии. Схема этого отношения выглядит следующим образом:

Сессия (№ зачетной книжки , Фамилия, Имя, Отчество, Предмет , Оценка);

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

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

Если у нас имеется следующий фрагмент какой-то определенной базы данных студентов учебного заведения после какой-то сессии, то в кортежах с номером зачетной книжки 100, атрибуты «Фамилия», «Имя» и «Отчество» совпадают, а атрибуты «Предмет» и «Оценка» – не совпадают (что и понятно, ведь в них речь идет о разных предметах и успеваемости по ним). Это значит, что атрибуты «Фамилия», «Имя» и «Отчество» функционально зависят от атрибута «№ зачетной книжки», а атрибуты «Предмет» и «Оценка» функционально не зависят.

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

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

Определение : пусть X, Y – подсхемы схемы отношения S, определяющие над схемой S схему функциональной зависимости X > Y (читается «X стрелка Y»). Определим ограничения функциональной зависимости inv > Y> как утверждение о том, что в отношении со схемой S любые два кортежа, совпадающие в проекции на подсхему X, должны совпадать и в проекции на подсхему Y.

Запишем это же определение в формулярном виде:

Inv > Y> r (S ) = t 1 , t 2 ? r (t 1 [X ] = t 2 [X ] ? t 1 [Y ] = t 2 [Y ]), X , Y ? S;

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

Интересно заметить, что в случае функциональной зависимости Y от X, говорят также, что X функционально определяет Y или что Y функционально зависит от X. В схеме функциональной зависимости X > Y подсхема X называется левой частью, а подсхема Y – правой частью.

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

Конец определения .

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

Inv <K > S > r (S ) = ? t 1 , t 2 ? r (t 1 [K ] = t 2 [K ] > t 1 (S ) = t 2 (S )), K ? S ;

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

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

{№ зачетной книжки} > {Фамилия, Имя, Отчество};

{№ зачетной книжки, Предмет} > {Оценка};

2. Правила вывода Армстронга

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

Хорошим примером таких специальных правил являются правила вывода Армстронга.

Но прежде чем приступать к анализу самих правил вывода Армстронга, введем в рассмотрение новый металингвистический символ «+», который называется символом метаутверждения о выводимости . Этот символ при формулировании правил записывается между двумя синтаксическими выражениями и свидетельствует о том, что из формулы, стоящей слева от него, выводится формула, стоящая справа от него.

Сформулируем теперь сами правила вывода Армстронга в виде следующей теоремы.

Теорема. Справедливы следующие правила, называемые правилами вывода Армстронга.

Правило вывода 1. + X > X;

Правило вывода 2. X > Y+ X ? Z > Y;

Правило вывода 3. X > Y, Y ? W > Z + X ? W > Z;

Здесь X, Y, Z, W – произвольные подсхемы схемы отношения S. Символ метаутверждения о выводимости разделяет списки посылок и списки утверждений (заключений).

1. Первое правило вывода называется «рефлексивность » и читается следующим образом: «выводится правило: “X функционально влечет за собой X”». Это самое простое из правил вывода Армстронга. Оно выводится буквально из воздуха.

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

2. Второе правило вывода называется «пополнение » и читается таким образом: «если X функционально определяет Y, то выводится правило: “объединение подсхем X и Z функционально влечет за собой Y”». Правило пополнения позволяет расширять левую часть ограничения функциональных зависимостей.

3. Третье правило вывода называется «псевдотранзитивность » и читается следующим образом: “если подсхема X функционально влечет за собой подсхему Y и объединение подсхем Y и W функционально влекут за собой Z, то выводится правило: «объединение подсхем X и W функционально определяют подсхему Z»”.

Правило псевдотранзитивности обобщает правило транзитивности, соответствующее частному случаю W: = 0. Приведем формулярную запись этого правила:

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

Правило вывода 1. inv X> r(S);

Правило вывода 2. inv Y> r(S) ? inv Y> r(S);

Правило вывода 3. inv Y> r(S) & inv Z> r(S) ? inv Z> r(S);

Проведем доказательства этих правил вывода.

1. Доказательство правила рефлексивности следует непосредственно из определения ограничения функциональной зависимости при подстановке вместо подсхемы Y – подсхемы X.

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

Inv Y> r(S) и подставим в него X вместо Y, получим:

Inv X> r(S), а это и есть правило рефлексивности.

Правило рефлексивности доказано.

2. Доказательство правила пополнения проиллюстрируем на диаграммах функциональной зависимости.

Первая диаграмма – это диаграмма посылки:

посылка: X > Y

Вторая диаграмма:

заключение: X ? Z > Y

Пусть кортежи равны на X ? Z. Тогда они равны на X. Согласно посылке они будут равны и на Y.

Правило пополнения доказано.

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

Первая диаграмма – первая посылка:

посылка 1: X > Y

посылка 2: Y ? W > Z

И, наконец, третья диаграмма – диаграмма заключения:

заключение: X ? W > Z

Пусть кортежи равны на X ? W. Тогда они равны и на X, и на W. Согласно Посылке 1, они будут равны и на Y. Отсюда, согласно Посылке 2, они будут равны и на Z.

Правило псевдотранзитивности доказано.

Все правила доказаны.

3. Производные правила вывода

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

Что это за правила, как они получаются?

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

Необходимо специально отметить, что эти самые произвольные правила являются «производными» именно от пройденных нами ранее правил вывода Армстронга.

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

Теорема.

Следующие правила являются производными от правил вывода Армстронга.

Правило вывода 1. + X ? Z > X;

Правило вывода 2. X > Y, X > Z + X ? Y > Z;

Правило вывода 3. X > Y ? Z + X > Y, X > Z;

Здесь X, Y, Z, W, так же как и в предыдущем случае, – произвольные подсхемы схемы отношения S.

1. Первое производное правило называется правилом тривиальности и читается следующим образом:

«Выводится правило: “объединение подсхем X и Z функционально влечет за собой X”».

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

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

2. Второе производное правило называется правилом аддитивности и читается следующим образом: «Если подсхема X функционально определяет подсхему Y, и X одновременно функционально определяет Z, то из этих правил выводится следующее правило: “X функционально определяет объединение подсхем Y и Z”».

3. Третье производное правило называется правилом проективности или правилом «обращение аддитивности ». Оно читается следующим образом: «Если подсхема X функционально определяет объединение подсхем Y и Z, то из этого правила выводится правило: “X функционально определяет подсхему Y и одновременно X функционально определяет подсхему Z”», т. е., действительно, это производное правило является обращенным правилом аддитивности.

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

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

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

1. Доказательство правила тривиальности .

Проведем его, как и все последующие доказательства, по шагам:

1) имеем: X > X (из правила рефлексивности вывода Армстронга);

Правило тривиальности доказано.

2. Проведем пошаговое доказательство правила аддитивности :

1) имеем: X > Y (это посылка 1);

2) имеем: X > Z (это посылка 2);

3) имеем: Y ? Z > Y ? Z (из правила рефлексивности вывода Армстронга);

4) имеем: X ? Z > Y ? Z (получаем при помощи применения правила псевдотранзитивности вывода Армстронга, а потом как следствие первого и третьего шагов доказательства);

5) имеем: X ? X > Y ? Z (получаем, применяя правило псевдотранзитивности вывода Армстронга, а после следует из второго и четвертого шагов);

6) имеем X > Y ? Z (следует из пятого шага).

Правило аддитивности доказано.

3. И, наконец, проведем построение доказательства правила проективности :

1) имеем: X > Y ? Z, X > Y ? Z (это посылка);

2) имеем: Y > Y, Z > Z (выводится при помощи правила рефлексивности вывода Армстронга);

3) имеем: Y ? z > y, Y ? z > Z (получается из правила пополнения вывода Армстронга и следствием из второго шага доказательства);

4) имеем: X > Y, X > Z (получается, применением правила псевдотранзитивности вывода Армстронга, а затем как следствие из первого и третьего шагов доказательства).

Правило проективности доказано.

Все производные правила вывода доказаны.

4. Полнота системы правил Армстронга

Пусть F (S ) - заданное множество функциональных зависимостей, заданных над схемой отношения S.

Обозначим через inv <F (S )> ограничение, накладываемое этим множеством функциональных зависимостей. Распишем его:

Inv <F (S )> r (S ) = ?X > Y ?F (S ) [inv Y> r (S )].

Итак, это множество ограничений, накладываемое функциональными зависимостями, расшифровывается следующим образом: для любого правила из системы функциональных зависимостей X > Y, принадлежащего множеству функциональных зависимостей F (S ), действует ограничение функциональных зависимостей inv Y> r (S ), определенных над множеством отношения r (S ).

Пусть какое-то отношение r (S ) удовлетворяет этому ограничению.

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

Правило вывода 1. inv < X > X > r (S );

Правило вывода 2. inv Y> r (S ) ? inv ? Z > Y> r (S );

Правило вывода 3. inv Y> r (S ) & inv ? W > Z> r (S ) ? inv ? W > Z>;

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

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

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

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

Если записать только что сказанное в формулярном виде, то получим:

F (S ) ? F + (S ), [F + (S )] + = F + (S );

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

X > Y ? F + (S ) ? ?r (S ) [inv <F (S )> r (S ) ? inv Y> r (S )];

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

(Доказательство этой теоремы мы рассматривать не будем, так как сам процесс доказательства не столь важен в нашем конкретном курсе лекций.)

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

Определение: Если даны два атрибута 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НФ и в НФБК. Примеры.