Главная » SQL, Базы данных » НЕПРИВОДИМЫЕ МНОЖЕСТВА ЗАВИСИМОСТЕЙ

0

Пусть S1 и S2 — два множества функциональных зависимостей. Если любая функциональная зависимость, которая следует из множества зависимостей si, следует также из множества зависимостей S2 (т.е. если замыкание S1+ является подмножеством замыкания S2+,

то множество S2 называется покрытием4 для множества si. Это означает, что если СУБД обеспечит соблюдение ограничений, представленных зависимостями  множества S2, то автоматически  будут  соблюдены  и все  ограничения,  устанавливаемые  зависимостями множества S1.

Далее, если множество S2 является покрытием для множества S1, а  множество S1 одновременно является покрытием для множества S2 (т.е. если S1+=S2+), то множества S1 и S2 эквивалентны. Ясно, что если множества S1 и S2 эквивалентны, то соблюдение СУБД ограничений, представленных зависимостями множества S2, автоматически обеспечит соблюдение ограничений, представленных зависимостями множества S1, и наоборот.

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

16.    Правая (зависимая) часть каждой функциональной зависимости из множества S

содержит только один атрибут (т.е. является одноэлементным множеством).

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

18.    Ни одна функциональная зависимость из множества S не может быть удалена из множества s без изменения его замыкания S+ (т.е. без преобразования множества s в некоторое иное множество, не эквивалентное множеству S).

В отношении пп. 2 и 3 следует отметить, что не обязательно иметь полную информацию о составе замыкания S+ для получения ответа на вопрос, изменится ли это замыкание при удалении из исходного множества какой-либо функциональной зависимости. В качестве примера рассмотрим уже знакомую переменную отношения деталей Р. В ней соблюдаются, кроме всех прочих, функциональные зависимости, перечисленные ниже.

Р# →  PNAME

Р# →  COLOR

Р# →  WEIGHT

Р# →  CITY

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

1.     Р#  →   {  PNAME,   COLOR  }

Р#   →  WEIGHT

Р#   →   CITY

4  Некоторые авторы используют термин "покрытие" для обозначения эквивалентного множества

(это понятие также будет скоро определено в данной книге).

5  В литературе подобное множество часто называется минимальным.

(Правая часть первой ФЗ не является одноэлементным множеством.)

2.     { Р#, PNAME } →   COLOR

Р# →   PNAME

Р# →   WEIGHT

Р# →   CITY

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

3.     р# →  р# Р# →   PNAME Р# →   COLOR Р# →   WEIGHT Р# →   CITY

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

Теперь можно сформулировать утверждение, что для любого множества  функциональных зависимостей существует по крайней мере одно  эквивалентное множество, которое является неприводимым. Это можно  доказать  достаточно легко. Пусть дано исходное множество зависимостей s.  Тогда в силу того, что существует правило декомпозиции, можно без утраты  общности предположить, что каждая функциональная зависимость в этом множестве s имеет одноэлементную правую часть. Далее для каждой зависимости f из этого множества S следует проверить каждый атрибут А в левой части зависимости f. Если удаление атрибута А из левой части зависимости f не приводит к изменению замыкания S+, то этот атрибут следует удалить. Затем  для каждой зависимости f, оставшейся в множестве s, необходимо проверить, приводит ли ее удаление из множества S к изменению замыкания S+; в случае отрицательного ответа следует удалить зависимость f из множества S. Получившееся в результате таких действий множество S является неприводимым и эквивалентным исходному множеству S.

Пример. Пусть дана переменная отношения R с атрибутами А, в, с, D и следующими функциональными зависимостями.

А                                        →   ВС В     →  С

А     →   В АВ   →  С АС   →   D

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

эквивалентное данному множеству.

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

А                                        →    В

А     →     С

В                                        →    С

А     →     В АВ    →   С АС   →    D

Нетрудно заметить, что зависимость А→  в встречается дважды, так что одну из них можно удалить.

2.    Затем в левой части зависимости АС → D может быть исключен атрибут с, по скольку дана зависимость А → С, из которой по правилу дополнения можно по лучить зависимость А →АС. Кроме того, дана зависимость АС → D, из которой

по правилу транзитивности можно получить зависимость А → D. Таким образом,

атрибут с в левой части исходной зависимости АС → D является избыточным.

3.    Также заметим, что может быть исключена зависимость АВ → С, поскольку дана зависимость А→ C, из которой по правилу дополнения можно получить зависи мость АВ → CB, а затем по правилу декомпозиции—зависимость АВ → С.

4.    Наконец, зависимость А→ с следует из зависимостей А → B и B → C, так что она также может быть отброшена. В результате получено следующее неприводи мое множество зависимостей.

А →   В

В →  С

А  →  D

Множество функциональных зависимостей I, которое неприводимо и эквивалентно другому множеству функциональных зависимостей s, называется неприводимым эквивалентом множества S. Таким образом, в системе вместо исходного множества функциональных зависимостей S с тем же успехом может использоваться его неприводимый эквивалент I (здесь следует повторить, что для вычисления неприводимого эквивалента I не обязательно вычислять замыкание s+). Однако необходимо отметить, что для любого заданного множества  функциональных зависимостей не всегда существует уникальный неприводимый эквивалент (см. упр. 11.12).

11.2. РЕЗЮМЕ

Функциональная зависимость— это связь типа "многие к однбму" между двумя множествами атрибутов заданной переменной отношения (она представляет собой наиболее широко распространенный и важный вид ограничения целостности). Для заданной переменной отношения R зависимость А → В (где А и в являются подмножествами множества атрибутов переменной отношения R) выполняется для переменной отношения R тогда и только тогда, когда любые два кортежа переменной отношения R с одинаковыми значениями атрибутов множества А имеют одинаковые значения атрибутов множества в. Каждая  переменная  отношения  обязательно  удовлетворяет  некоторым  тривиальным функциональным зависимостям; причем функциональная зависимость тривиальна тогда и только тогда, когда ее правая (зависимая) часть является подмножеством ее левой части (детерминанта).

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

для заданного множества s (но в действительности обычно проведение этих вычислений не требуется). На основании правил Армстронга можно легко  получить несколько дополнительных удобных правил.

Для данного подмножества z множества атрибутов переменной отношения R и множества функциональных зависимостей S, которые выполняются в переменной отношения R, замыканием z+ подмножества Z для множества S называется такое множество всех атрибутов А переменной отношения R, что функциональная зависимость Z → А является членом замыкания S+. Если  замыкание z+  состоит из всех атрибутов переменной отношения R, то подмножество Z называют суперключом переменной отношения R (а неприводимый суперключ, в свою очередь, называется потенциальным ключом). В этой главе было дано описание простого алгоритма для получения замыкания z+ на основе z и s и, следовательно, для определения того, является ли данная  зависимость х →  Y членом замыкания s+ (функциональная зависимость X → У является членом замыкания S+ тогда и только тогда, когда множество Y является подмножеством замыкания х+).

Два множества функциональных зависимостей s1 и S2 эквивалентны тогда и только

тогда, когда они являются покрытиями друг для друга, т.е. S1+=S2+. Каждое  множество функциональных зависимостей эквивалентно по крайней мере одному  неприводимому множеству. Множество функциональных зависимостей является  неприводимым, если, во-первых, каждая функциональная зависимость этого  множества имеет одноэлементную правую часть; во-вторых, если ни одна функциональная зависимость множества не может быть удалена без изменения замыкания этого множества; в-третьих, если ни один атрибут не может быть удален из левой части любой функциональной зависимости данного множества  без изменения замыкания множества. Если I является неприводимым множеством, которое эквивалентно множеству S, то проверка выполнения  функциональных зависимостей из множества I автоматически обеспечит выполнение всех функциональных зависимостей из множества S.

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

■     Некоторые ограничения целостности являются тривиальными.

■     Из одних ограничений целостности следуют другие ограничения.

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

■     Выяснение вопроса, будет ли некоторое ограничение находиться в некотором за мыкании (т.е. будет ли заданное ограничение следовать из некоторых заданных ограничений), является очень интересной практической задачей.

Не менее интересной практической задачей является поиск неприводимого эквивалента для некоторого заданного множества установленных ограничений.

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

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

Источник: Дейт К. Дж., Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — 1328 с.: ил. — Парал. тит. англ.

По теме:

  • Комментарии