Общие понятия реляционного подхода к организации БД (1122811), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

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

FD A B называется тривиальной, если A B (т. е. множество атрибутов A включает множество B или совпадает с множеством B). Очевидно, что любая тривиальная FD всегда выполняется. Частным случаем тривиальной FD является A A. Поскольку тривиальные FD выполняются всегда, их нельзя трактовать как ограничения целостности, и поэтому они не представляют интереса с практической точки зрения. Однако в теоретических рассуждениях их наличие необходимо учитывать.

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

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. Тем не менее Дейт по практическим соображениям предложил расширить базовый набор правил вывода еще пятью правилами:

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

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

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

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

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

Пусть заданы отношение R, множество Z атрибутов этого отношения (подмножество заголовка R, или составной атрибут R) и некоторое множество FD S, выполняемых для R. Тогда замыканием Z над S называется наибольшее множество Z⁺ таких атрибутов Y отношения R, что FD Z Y входит в S⁺.

Алгоритм вычисления Z⁺

Докажем корректность алгоритма по индукции. На нулевом шаге Z[0] = Z, FD Z Z[I], очевидно, принадлежит S⁺ (тривиальная FD «выводится» из любого множества FD). Пусть для некоторого K выполняется FD Z Z[K], и пусть мы нашли в S такую FD A B, что A Z[K]. Тогда можно представить Z[K] в виде AC, и, следовательно, выполняется FD Z AC. Но по правилу (8) мы имеем FD Z ACB, т.е. FD Z (Z[K] UNION B) входит во множество S⁺, что переводит нас на следующий шаг индукции.

Пусть для примера имеется отношение с заголовком {A, B, C, D, E, F} и заданным множеством FD S = {A D, AB E, BF E, CD F, E C}. Пусть требуется найти {AE}⁺ над S. На первом проходе тела цикла DO Z[1] равно AE. В теле цикла FOR EACH будут найдены FD A D и E C, и в конце цикла Z[1] станет равным ACDE. На втором проходе тела цикла DO при Z[2], равном ACDE, в теле цикла FOR EACH будет найдена FD CD F, и в конце цикла Z[2] станет равным ACDEF. Следующий проход тела цикла DO не изменит Z[3], и Z⁺ ({AE}⁺) будет равно ACDEF.

Алгоритм построения замыкания множества атрибутов Z над заданным множеством FD S помогает легко установить, входит ли заданная FD Z B в замыкание S⁺. Очевидно, что необходимым и достаточным условием для этого является B Z⁺, т. е. вхождение составного атрибута B в замыкание Z.

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

Одно из следствий этого определения состоит в том, что подмножество K заголовка отношения R является суперключом тогда и только тогда, когда для любого атрибута A (возможно, составного) заголовка отношения R выполняется FD K A. В терминах замыкания множества атрибутов K является суперключом тогда и только тогда, когда K⁺ совпадает с заголовком R.

Множество FD S2 называется покрытием множества FD S1, если любая FD, выводимая из S1, выводится также из S2.

Легко заметить, что S2 является покрытием S1 тогда и только тогда, когда S1⁺ S2⁺. Два множества FD S1 и S2 называются эквивалентными, если каждое из них является покрытием другого, т. е. S1⁺ = S2⁺.

Множество FD S называется минимальным в том и только в том случае, когда удовлетворяет следующим свойствам:

1. правая часть любой FD из S является множеством из одного атрибута (простым атрибутом);

2. детерминант каждой FD из S обладает свойством минимальности; это означает, что удаление любого атрибута из детерминанта приводит к изменению замыкания S⁺, т. е. порождению множества FD, не эквивалентного S³⁰⁾;

3. удаление любой FD из S приводит к изменению S⁺, т. е. порождению множества FD, не эквивалентного S.

Для любого множества FD S существует (и даже может быть построено) эквивалентное ему минимальное множество S^-.

Приведем общую схему построения S^- по заданному множеству FD S. Во-первых, используя правило (5) (декомпозиции), мы можем привести множество S к эквивалентному множеству FD S1, правые части FD которого содержат только одноэлементные множества (простые атрибуты). Далее, для каждой FD из S1, детерминант D {D₁, D₂, …, D_n} которой содержит более одного атрибута, будем пытаться удалять атрибуты D_i, получая множество FD S2. Если после удаления атрибута D_i S2 эквивалентно S1, то этот атрибут удаляется, и пробуется следующий атрибут. Назовем S3 множество FD, полученное путем допустимого удаления атрибутов из всех детерминантов FD множества S1. Наконец, для каждой FD f из множества S3 будем проверять эквивалентность множеств S3 и S3 MINUS {f}. Если эти множества эквивалентны, удалим f из множества S3, и в заключение получим множество S4, которое минимально и эквивалентно исходному множеству FD S.

Пример (оставил ради понимания что происходит) :

Пусть, например, имеется отношение R {A, B, C, D} и задано множество FD S = {A B, A BC, AB C, AC D, B C}. По правилу декомпозиции S эквивалентно множеству S1 {A B, A C, AB C, AC D, B C}. В детерминанте FD AC D можно удалить атрибут C, поскольку по правилу дополнения из FD A C следует A AC; по правилу транзитивности выводится FD A D, поэтому атрибут C в детерминанте FD AC D является избыточным. FD AB C может быть удалена, поскольку может быть выведена из FD A C (по правилу пополнения из этой FD выводится AB BC, а по правилу декомпозиции далее выводится AB C). Наконец, FD A C тоже выводится по правилу транзитивности из FD A B и B C. Таким образом, мы получаем множество зависимостей {A B, A D, B C}, которое является минимальным и эквивалентно S по построению.

Минимальным покрытием множества FD S называется любое минимальное множество FD S1, эквивалентное S.

Характеристики

Список файлов ответов (шпаргалок)