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

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

Пусть R - ϶ᴛᴏ отношение. С одной стороны, оно имеет конкретное (постоянное) значение в данный момент времени. С другой стороны, это переменная, которая в каждый момент времени может принять неĸᴏᴛᴏᴩᴏᴇ новое значение.

Понятие ФЗ можно применить и к первому, и ко второму случаю. При этом мы будем рассматривать только второй случай, т.к. он больше соответствует реальности.

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

Здесь X называют детерминантом ФЗ, а Y – зависимой частью ФЗ.

Пример : Пусть R - ϶ᴛᴏ отношение Students . X – код студента͵ а Y – множество всœех атрибутов студента. Тогда X → Y , т.к. X представляет собой первичный ключ, который уникально идентифицирует запись в таблице Students .

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

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

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

Пример :

{StudentID , FirstName , LastName , MiddleName } → {BirthDate } – приводимая ФЗ.

{StudentID } → {BirthDate } – неприводимая ФЗ.

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

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

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

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

Рассмотрение множества неприводимых ФЗ важно для нормализации отношений.

Выделяют два вида ФЗ:

1. Тривиальные ФЗ - ϶ᴛᴏ ФЗ, в которых правая часть (Y ) является подмножеством левой части (X ). С практической точки зрения они не представляют значительного интереса, однако с точки зрения формальной теории зависимостей крайне важно учитывать их наличие.

2. Нетривиальные ФЗ . Οʜᴎ действительно являются ограничениями целостности данных, в связи с этим в дальнейшем мы будем рассматривать именно нетривиальные ФЗ.

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

Пусть A , B , C - ϶ᴛᴏ подмножества множества атрибутов отношения R , AB – объединœение этих подмножеств.

1. Правило рефлексивности . В случае если множество B является подмножеством множества А , то А → В . (По сути, это определœение тривиальной зависимости.)

2. Правило дополнения . В случае если А → B , то АС → ВС .

3. Правило транзитивности . В случае если А → B и B→C , то А → С .

Каждое из этих правил должна быть доказано на базе определœения ФЗ.

При этом в целях упрощения получения всœех ФЗ можно вывести еще несколько дополнительных правил (пусть D - ϶ᴛᴏ еще одно произвольное подмножество множества атрибутов R ):

4. Правило самоопределœения . А → А .

5. Правило декомпозиции . В случае если А → ВС , то А → B и A → C .

6. Правило объединœения . В случае если А → В и А → С , то А → ВС .

7. Правило композиции . В случае если А → B и С → D , то АС → BD .

8. Теорема всœеобщего объединœения . В случае если А→ B и C → D , то А(С – В) → BD .

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

При этом следует иметь в виду, что эти правила не обеспечивают чёткого алгоритма получения всœех ФЗ. Более того, такого алгоритма не существует. Единственный путь - ϶ᴛᴏ перебор всœех вариантов.

Понятие функциональной зависимости - понятие и виды. Классификация и особенности категории "Понятие функциональной зависимости" 2017, 2018.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ОПРЕДЕЛЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(PNUM, DNUM)®PNUM

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

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

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