Лекция № 9. Функциональные зависимости

1. Ограничение функциональной зависимости

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

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

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

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

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

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

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

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

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

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

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

Inv<X → Y> r(S) = t₁, t₂ ∈ r(t₁[X] = t₂[X] ⇒ t₁[Y] = t₂ [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₁, t₂ ∈ r(t₁[K] = t₂ [K] → t₁(S) = t₂(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. Приведем формулярную запись этого правила:

X →Y, Y → Z ├X → Z.

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

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

Правило вывода 2. inv <X → Y> r(S) ⇒ inv <X ∪ Z → Y> r(S);

Правило вывода 3. inv <X → Y> r(S) & inv <Y ∪ W → Z> r(S) ⇒ inv<X ∪ W → Z> r(S);

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

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

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

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

Inv <X → 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) имеем далее: X ∪ Z → 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 <X → Y> r(S)].

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

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

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

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

Правило вывода 2. inv <X → Y> r(S) ⇒ inv <X ∪ Z → Y> r(S);

Правило вывода 3. inv <X → Y> r(S) & inv <Y ∪ W → Z> r(S) ⇒ inv <X ∪ 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 <X → Y> r(S)];

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

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

<< Назад: Создание базовых отношений (Металингвистические символы. Пример создания базового отношения в записи на псевдокоде. Ограничение целостности по состоянию. Ограничения ссылочной целостности. Понятие индексов. Модификация базовых отношений)

>> Вперед: Нормальные формы (Смысл нормализации схем баз данных. Первая нормальная форма (1NF). Вторая нормальная форма (2NF). Третья нормальная форма (3NF). Нормальная форма Бойса - Кодда (NFBC). Вложенность нормальных форм)

Рекомендуем интересные статьи раздела Конспекты лекций, шпаргалки:

▪ Логистика. Конспект лекций

▪ Психология труда. Конспект лекций

▪ Гражданское процессуальное право. Шпаргалка

Смотрите другие статьи раздела Конспекты лекций, шпаргалки.

Читайте и пишите полезные комментарии к этой статье.

<< Назад

Последние новости науки и техники, новинки электроники:

Атомный секрет вечного блеска золота 20.06.2026

Золото издавна считается символом вечности и благородства не только из-за своей редкости, но и благодаря удивительной химической стойкости. В отличие от большинства металлов, оно не окисляется на воздухе, не тускнеет и не покрывается ржавчиной даже спустя тысячелетия. Эта уникальная инертность позволила золотым артефактам сохранять первозданный блеск с древних времен. Однако точный механизм такой защиты долго оставался загадкой для ученых. Недавнее исследование американских химиков-вычислителей раскрыло, что дело не просто в слабом взаимодействии с кислородом, а в особой атомной структуре поверхности металла. Сотрудники Тулейнского университета Санту Бисвас и Мэтью М. Монтемор провели детальное компьютерное моделирование, чтобы понять, как молекулы кислорода взаимодействуют с поверхностью золота. Ученые сравнили два основных типа атомных структур: "реконструированные" и "нереконструированные" поверхности. Было доказано, что природная способность золота к перестройке атомов играет кл ...>>

Смарфон Realme 16T 5G 20.06.2026

В сегменте доступных смартфонов с акцентом на длительную работу без подзарядки компания Realme представила интересную новинку - модель Realme 16T 5G. Главным преимуществом устройства стала по-настоящему впечатляющая батарея емкостью 8000 мАч, которая способна обеспечить до трех дней автономной работы при умеренном использовании. При этом инженерам удалось сохранить относительно компактный корпус толщиной менее 9 мм и вес всего 224 грамма, что делает смартфон удобным для повседневного ношения несмотря на внушительный аккумулятор. Смартфон оснащен большим 6,8-дюймовым LCD-дисплеем с высокой частотой обновления 144 Гц и пиковой яркостью до 1200 нит. Такое сочетание обеспечивает плавную картинку в динамичных сценах и комфортное восприятие контента даже под прямыми солнечными лучами. За производительность отвечает энергоэффективный процессор MediaTek Dimensity 6300, дополненный оперативной памятью LPDDR4X и накопителем UFS 2.2. Для эффективного отвода тепла во время продолжительных нагру ...>>

Проблема набора веса после 40 19.06.2026

С возрастом многие люди замечают, что поддерживать привычный вес становится все сложнее, даже если рацион и уровень активности существенно не меняются. Ученые из Каролинского института в Швеции раскрыли одну из ключевых биологических причин этого явления. Они показали, что с годами в жировой ткани замедляется процесс обновления липидов, из-за чего организм постепенно накапливает жир. Это естественное возрастное изменение объясняет, почему после 40 лет тело начинает "работать" иначе, способствуя набору веса. В долгосрочном исследовании специалисты наблюдали за жировой тканью 54 мужчин и женщин на протяжении в среднем 13 лет. Независимо от того, набирали участники вес или, наоборот, худели, у всех без исключения скорость липидного обмена в жировых клетках заметно снижалась. Жир в клетках обновляется все медленнее, и этот процесс происходит автоматически с течением времени. Те, кто не компенсировал замедление уменьшением калорийности питания, в среднем набирали около 20% от исходного в ...>>

Случайная новость из Архива Самосвал, работающий на водороде 16.10.2022 Классический карьерный самосвал высотой в три этажа при полной загрузке является одним из крупнейших транспортных средств на планете. Горнодобывающая промышленность ежегодно дает до 7% мировых выбросов углерода. Около 50% этого объема приходится на самосвалы для перевозки тяжелых пород. Поэтому компания First Mode из Сиэтла хочет заменить мощный дизель двигателем водорода. First Mode создала крупнейшую в мире мобильную водородную электростанцию-гибрид, сочетающий водородные топливные элементы с питанием от аккумуляторов. Она весит как пять слонов и способна перевозить груз, равный весу 100 слонов. В мае этого года водородный самосвал официально дебютировал на шахте Могалаквена в Южной Африке, принадлежащей компании Anglo American. По оценкам транснациональной горнодобывающей компании, средний карьерный самосвал в ее парке потребляет 900 000 литров дизельного топлива в год. В последнее время все большее число отраслей - от наземного транспорта до авиации - рассматривают водород как источник энергии. В августе Германия представила 14 пассажирских водородных поездов. Airbus также объявил о планах опробовать самолеты с водородным двигателем в 2026 году. Инженер-исследователь в области энергетики Гленн Рамбах отмечает, что водородная технология в конечном счете может превзойти электрические батареи. Но создание инфраструктуры для получения водородного топлива, необходимого для поддержки парка самосвалов, добавляет он, является одной из основных задач, стоящих перед проектом такого масштаба. Гибридные автомобили, работающие на комбинации водородных и электрических батарей, могут смягчить проблему любого несоответствия в электрической или водородной инфраструктуре. Однако выбросы углерода при использовании водорода в качестве топлива зависят от того, как производится водород. "Зеленый" водород создается с использованием возобновляемых источников энергии, а для создания "голубого" водорода используется ископаемое топливо. First Mode заявляет, что их самосвал был разработан для работы на зеленом водороде, и компания работает над созданием устойчивой цепочки поставок для поддержки грузовиков.

Другие интересные новости:

▪ Подводное фото станет четким

▪ Компас голубя

▪ Дирижабли тушат пожары

▪ Отголоски древнего землетрясения

▪ Процессоры Samsung с нейросетью

Лента новостей науки и техники, новинок электроники

Интересные материалы Бесплатной технической библиотеки:

▪ раздел сайта Телефония. Подборка статей

▪ статья Эндокринология. Шпаргалка

▪ статья Когда появились первые картины? Подробный ответ

▪ статья Эстрагон. Легенды, выращивание, способы применения

▪ статья Импульсный блок питания с регулятором напряжения 1е.32 V мощностью 200 W. Энциклопедия радиоэлектроники и электротехники

▪ статья Фонтан из вазы и руки. Секрет фокуса

Оставьте свой комментарий к этой статье:

www.diagram.com.ua
2000-2026