Операция деления отношений

Эта операция наименее очевидна из всех операций реляционной алгебры и поэтому нуждается в более подробном объяснении. Пусть заданы два отношения - A с заголовком {a1, a2,..., an, b1, b2,..., bm} и B с заголовком {b1, b2,..., bm}. Будем считать, что атрибут bi отношения A и атрибут bi отношения B не только обладают одним и тем же именем, но и определены на одном и том же домене. Назовем множество атрибутов {aj} составным атрибутом a, а множество атрибутов {bj} - составным атрибутом b. После этого будем говорить о реляционном делении бинарного отношения A(a, b) на унарное отношение B(b).

Результатом деления A на B является унарное отношение C(a), состоящее из кортежей v таких, что в отношении A имеются кортежи < v, w> такие, что множество значений {w} включает множество значений атрибута b в отношении B.

Предположим, что в базе данных сотрудников поддерживаются два отношения: СОТРУДНИКИ (ИМЯ, ОТД_НОМЕР) и ИМЕНА (ИМЯ), причем унарное отношение ИМЕНА содержит все фамилии, которыми обладают сотрудники организации. Тогда после выполнения операции реляционного деления отношения СОТРУДНИКИ на отношение ИМЕНА будет получено унарное отношение, содержащее номера отделов, сотрудники которых обладают всеми возможными в этой организации именами.

10. Понятие функциональной зависимости для отношения. Основные определения. Способ определения Ф.З. Тривиальные и нетривиальные зависимости.

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

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

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

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

Некоторые функциональные зависимости могут быть нежелательны.

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

Функциональная зависимость X -> Y называется транзитивной, если существует такой атрибут Z, что имеются функциональные зависимости X -> Z, Z -> Y и отсутствует функциональная зависимость Z-> X. (При отсутствии последнего требования мы имели бы " неинтересные" транзитивные зависимости в любом отношении, обладающем несколькими ключами.)

Два атрибута взаимно зависимы, если один из них функционально зависит от другого и наоборот. Обозначают: A< -> B.

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

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

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

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

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

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

Аксиомы:

1. Свойство рефлексивности, если множество В является подмножеством множества А, то А -> В.

2. Свойство пополнения, если A -> B, то АС -> ВС.

3. Свойство транзитивности, если A -> B и B -> C, то A -> C.

Каждое из этих трех правил может быть непосредственно доказано на основе определения ФЗ (первое из них – просто определение тривиальной зависимости).

Типы функциональных зависимостей:

1. Частичная, если неключевой атрибут зависит только от части ключа.

2. Функциональная зависимость X Y называется полной, если атрибут Y не зависит функционально от любого точного подмножества X. т.е. Существует функциональная зависимость X+Z Y, и нет функциональных зависимостей X Y, Z Y.

Функциональная зависимость X Y называется транзитивной, если существует такой атрибут Z, что имеются функциональные зависимости X Z и Z Y и отсутствует функциональная зависимость Z X. Зависимость называется тривиальной, если она не может не выполняться. Зависимость является тривиальной тогда и только тогда, когда правая часть ее правой записи является подмножеством левой части. (S#, P#) -> S#. Нетривиальные зависимости являются реальными ограничениями целостности.

11. Замыкание множества зависимостей. Аксиомы Армстронга.

Замыканием множества FD S является множество FD S⁺, включающее все FD, логически выводимые из FD множества S.

Для начала приведем два примера FD, из которых следуют (или выводятся) другие FD. Будем снова пользоваться отношением СЛУЖАЩИЕ_ПРОЕКТЫ. Для этого отношения выполняется, например, FD СЛУ_НОМ {СЛУ_ЗАРП, ОТД_НОМ}. Из этой FD выводятся FD СЛУ_НОМ СЛУ_ЗАРП и СЛУ_НОМ ОТД_НОМ.

В отношении СЛУЖАЩИЕ_ПРОЕКТЫ имеется также пара FD СЛУ_НОМ ОТД_НОМ и ОТД_НОМ ПРОЕКТ_РУК. Из них выводится FD СЛУ_НОМ ПРОЕКТ_РУК. Заметим, что FD вида СЛУ_НОМ ПРОЕКТ_РУК называются транзитивными, поскольку ПРОЕКТ_РУК зависит от СЛУ_НОМ «транзитивно», через ПРО_НОМ.

FD A C называется транзитивной, если существует такой атрибут B, что имеются функциональные зависимости A B и B C и отсутствует функциональная зависимость C A.

Подход к решению проблемы поиска замыкания S⁺ множества FD S впервые предложил Вильям Армстронг²⁸⁾. Им был предложен набор правил вывода новых FD из существующих (эти правила обычно называют аксиомами Армстронга, хотя справедливость правил доказывается на основе определения FD). Обычно принято формулировать эти правила вывода в следующей форме. Пусть A, B и C являются (в общем случае, составными) атрибутами отношения R. Множества A, B и C могут иметь непустое пересечение. Для краткости будем обозначать через AB A UNION B. Тогда:

1. если B A, то A B (рефлексивность);

2. если A B, то AC BC (пополнение);

3. если A B и B C, то A C (транзитивность).

Истинность первой аксиомы Армстронга следует из того, что при B A FD A B является тривиальной.

Справедливость второй аксиомы докажем от противного. Предположим, что FD AC BC не соблюдается. Это означает, что в некотором допустимом теле отношения найдутся два кортежа t₁ и t₂, такие, что t₁ {AC} = t₂ {AC} (a), но t₁ {BC} t₂ {BC} (b) (здесь t {A} обозначает проекцию кортежа t на множество атрибутов A). По аксиоме рефлексивности из равенства (a) следует, что t₁ {A} = t₂ {A}. Поскольку имеется FD A B, должно соблюдаться равенство t₁ {B} = t₂ {B}. Тогда из неравенства (b) следует, что t₁ {C} t₂ {C}, что противоречит наличию тривиальной FD AC C. Следовательно, предположение об отсутствии FD AC BC не является верным, и справедливость второй аксиомы доказана.

Аналогично докажем истинность третьей аксиомы Армстронга. Предположим, что FD A C не соблюдается. Это означает, что в некотором допустимом теле отношения найдутся два кортежа t₁ и t₂, такие, что t₁ {A} = t₂ {A}, но t₁ {C} t₂ {C}. Но из наличия FD A B следует, что t₁ {B} = t₂ {B}, а потому из наличия FD B C следует, что t₁ {C} = t₂ {C}. Следовательно, предположение об отсутствии FD A C не является верным, и справедливость третьей аксиомы доказана.

Можно доказать, что система правил вывода Армстронга полна и совершенна (sound and complete) в том смысле, что для данного множества FD S любая FD, потенциально выводимая из S, может быть выведена на основе аксиом Армстронга, и применение этих аксиом не может привести к выводу лишней FD. Тем не менее Дейт по практическим соображениям предложил расширить базовый набор правил вывода еще пятью правилами:

4. A A (самодетерминированность) – прямо следует из правила (1);

5. если A BC, то A B и A C (декомпозиция) – из правила (1) следует, что BC B; по правилу (3) A B; аналогично, из BC С и правила (3) следует A C;

6. если A B и A C, то A BC (объединение) – из правила (2) следует, что A AB и AB BC; из правила (3) следует, что A BC;

7. если A B и C D, то AC BD (композиция) – из правила (2) следует, что AС BС и BC BD; из правила (3) следует, что AC BD;

8. если A BC и B D, то A BCD (накопление) – из правила (2) следует, что BС BCD; из правила (3) следует, что A BCD.

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

Правила вывода ФЗ (правила Армстронга): позволяют вывести базовые правила:

рефлексивность -

если Y является подмножеством Х то Х определяет У

дополнения

если Х-> У то XZ-> YZ где XYZ- элементы отношения

транзитивность –

если X-> Y и Y-> Z то X-> Z

Позволяют вывести дополнительные правила

декомпозиция

если A-> BC A-> B A-> C

объединение

если A-> B и A-> C то A-> BC

композиция если A-> Bи C-> D то AC-> BD

теорема всеобщего объединения

Если А-> В и С-> D, то А U (С-> В)-> ВD

Задача определения замыкания S+ является так называемой NP - полной задачей это означает, его определения зависит экспоненциально от кол-ва исходных зависимостей (еN) это означает что даже при малых N вычисления почти не возможны