Введение в системы БД (542480), страница 102
Текст из файла (страница 102)
АВ0 — > Е А — э 6  — э Р 414 Часть 1П. Проектирование базы данных с — >з Сг -э 1 6-+й Является ли это множество неприводимым? Какие потенциальные ключи сущест- вуют для данной переменной-отношения? Список литературы АггпкггопЯ%.%. Ререн|!епсу Бгп|сщгек оТ Ра|а Ваке Ке1айопкй~рк // Ргос.
1Р!Р Сопдгекк. — БгоскЬо1ш, Бэчег!еп, ! 974. Здесь впервые изложена формальная теория функциональных зависимостей (т.е. эта работа является первоисточником аксиом Армстронга), а также приведена точ- ная характеристика потенциальных ключей. Сакапоча М.А., Рая!и К., Рараг(!ш!|г!оц С.Н. !пс!цк!оп Ререпг!епс!ек апд ТЬе|г !п|егасбоп |ч!|Ь Рцпсбопа! Ререн|(епс!ек // Ргос. !к| АСМ Б!ОАСТ-Б!ОМОР Бу|прок!шп оп Рппс|р1ек оТ РасаЬаке Букгешк. — Еок Апйе1ек, СаИ., Магсй, 1982.
Зависимости включения (!пс1цкюп г(ерепг(епс!ек — 1Ь!Рк) являются обобщением концепции ограничений целостности. Например, зависимость включения типа 10.1. 10.2. (здесь символическая запись содержит несколько более длинную стрелку, подчеркивающую, что это зависимость другого типа) означает, что множество значений атрибута ЯР.Я1 должно быть подмножеством (необязательно собственным подмножеством) множества значений атрибута Я.Я1. Это, конечно, частный случай ограничения целостности, в общем же случае для зависимости включения не сушествует никаких ограничений на то, что левая часть является внешним ключом, а правая — потенциальным.
Замечание. Зависимости включения имеют некоторое сходство с функциональными зависимостями, поскольку оба эти типа зависимостей представляют связь "многие к одному". Однако зависимости включения обычно покрывают переменные-отношения, тогла как функциональные зависимости не покрывают. Предложено исчерпывающее и полное множество правил вывода для зависимостей включения, которые могут быть (в несколько нестрогой форме) представлены в следующем виде. 1. й — + й.
2. Если й — + СВ, той — + С и  — > О. 3. Еслий — + Ви — э С,то й — + С. Б|ч!гсЬ!пЯ Рцпс|юпк 0 1ВМ й КкР. — Бер|ешЬег, 1973. — 17, № 5. В работе показано, что для данной переменной-отношения множество функциональных зависимостей (которые в этой статье называются функциональными связями) может быть представлено как "булева переключательная функция". Кроме того, отмечено, что эта функция в некотором смысле уникальна, посколь- 415 Глава 10. Функ|(иональные зависимости 10.3.
Сакеу К.О., Ре!оЬе! С. Ресошро|йбоп о( а Раса Ваке апг! гйе ТЬеогу о( Воо1еап 10.4. 10.5. 10.6. ку исходные функциональные зависимости могут быть заданы многими совершенно различными (но эквивалентными) способами, каждый из которых в общем приводит к возникновению существенно разных булевых функций, но все такие функции могут быть сведены к одной той же канонической форме с помо- щью законов булевой алгебры. Показано, что проблема декомпозиг(ии исходной переменной-отношения (т.е. декомпозиция без потерь; подробности приводятся в главе 11) логически эквивалентна хорошо известной в булевой алгебре проблеме поиска "покрывающего множества из простых импликантов" для булевой функции, соответствующей этой переменной-отношению вместе с ее функциональными зависимостями.
Следовательно, исходная проблема может быть пере- формулирована в эквивалентную проблему в булевой алгебре, а для ее решения могут применяться хорошо известные методы. Эта одна из первых работ, посвященных применению теории зависимостей для широкого круга других дисциплин. Этому также посвящена публикация [10.8) и несколько работ, упомянутых в списках литературы в главе 12. Содд Е,Г. ГцгсЬег Хоггпа!сгайоп оТ сйе Васа Ваке Ке!айопа! Моде1 П Васа Ваке Зуксегпк, Соцгапс Сопсрцсег Бссепсе Зушрогда Бепек 6.
— Еп81еиоод С!сТ(к, счС.Л.: Ргепбсе-На!1, 1972. Впервые представлена концепция функциональной зависимости (не считая более раннего упоминания в одном из внутренних документов фирмы!ВМ). Понятие "дальнейшая нормализация" (ГцгсЬег Иоппасскассоп), приведенное в заголовке, относится к некоторому типу специализированного макета базы данных, обсуждаемого в главе 1! (назначение этой статьи заключалось в демонстрации возможности использования идеи функциональной зависимости для решения проблем проектирования базы данных). Действительно, функциональные зависимости представляют собой одну из первых попыток разрешения этой проблемы.
Однако идея ФЗ с тех пор доказала свою полезность и для более широкого практического применения. Содд Е.Г. )чоппа11кед Васа Ваке а!псе!иге; А Впе( Тшопа! // Ргос. 1971 АСМ 5!ОГ1ВЕТ %ог(скЬор оп Васа Оекспрйоп, Ассекк, апд Сои!го!, — Кап Все8о, Сай(., Н очешЬег, ! 97! . Вводное изложение идей, представленных в [! 0.4].
Вапчеп Н. ТЬе Ко!е оТ Гцпсдопас Верепдепсе сп Оцегу Весошрогдйоп П Сди Васе апд Н. Вапчеп. Кесабопа! ВасаЬаке Ссссгсс!пйк 1989-1991. — Кеадспй, Макал Аддскоп-'счек1еу, 1992. Представлен набор правил наследования для функциональных зависимостей, с помощью которых может быть выведена выполнимость функциональных зависимостей для данной произвольной переменной-отношения на основе выполнимости этих зависимостей в переменной-отношении (или нескольких переменных- отношениях), из которой выведена данная переменная-отношение. Выведенное таким образом множество ФЗ может использоваться для определения потенциальных ключей для некоторой выведенной переменной-отношения. В результате можно получить правила наследования для нопсенцнальных ключей, кратко упомянутые в главах 8 и 9 как "наиболее желательные".
В статье показано, как эти правила наследования для функциональных зависимостей и потенциальных ключей 416 Часть ТН. Проектирование базы данных 10.7. 10.8. Показано, что аксиомы Армстронга 110.1) строго эквивалентны системе импликапионных утверждений в логике высказываний. Иначе говоря, задается отображение между функциональными зависимостями и утверждениями в логике высказываний, а затем показывается, что данная зависимость 1 является последовательностью заданного множества зависимостей Я тогда и только тогда, когда высказывание, соответствующее 5, является логическим следствием множества высказываний, соответствующих множеству Я.
ЕнссЬез( СЛ.., ОзЪогп 5.).. СапдЫаге Кеуз !ог Ке1абопз Н й Сошр. апд Яуз. Яс)епсез. — 1978. — 17, № 2. 10.9. Представлен алгоритм поиска всех потенциальных ключей, а также функциональ- ных зависимостей, выполняющихся для заданной переменной-отношения. Ответы к некоторым упражнениям 10.1. Функциональная зависимость — это утверждение типа А — > В, где й и В являются подмножествами множества атрибутов переменной-отношения В. Поскольку множество из и элементов образует 2" возможных подмножеств, каждое из множеств А и В может содержать по 2" возможных значений. Следовательно, общее число возможных функциональных зависимостей равно 2 ".
10.5. (дано) (дано) (зависимость соединения, 1) (самоопределение) н ( С - В ) (композиция,3,4) (упрощение, 5) (транзитивность, 6, 2) (композипия, 1, 7) 1. А — >В 2. С вЂ” )0 3. й-эйлС 4. С- — зС-В 5.йи(С-В) — з(ВгзС) 6. Ан(С-В) — эС 7. й о ( С - В ) -+ В Я.йи(С-В) — эВоп Доказательство завершено.
° Использованные для доказательства правила указаны в скобках. Среди них есть правила, которые являются особыми случаями теоремы Дарвена: объединение, транзитивность, композиция и дополнение. Таким же особым случаем теоремы Дарвена является следующее полезное правило. ° Если А — ч В ий — з С, той — ч С. 417 Глава /О. Функциональные зависимости могут использоваться для значительного повышения производительности СУБД, ее функпиональности и удобства пользования. Рагиеп Н.
ООЬзегчабопз о( а Ке)айова! В)8о! // Ргезепгайоп го ВСЯ Ярес!а) (п!егез! Огопр оп Гоппа! Азрес!з оГСошрпйп8 Бс!епсе. — Ьопг(оп, 1)К, РесешЪег, 1990. Га8)п К. Гппспопа! Ререпдепс(ез !п а Ке!айопа( РагаЬазе апд Ргороьйюпа) Ео81с // 1ВМ АК кР. — ХочешЬег, 1977. — 21, № 6. Ниже приведен полный набор функциональных зависимостей (т.е, замыкание) для 10.7. переменной-отношения ЯР. ( Я», Р», 0ТУ ) -э ( 3$, Р», 0ТУ ) ( Я», Р», 0ТТ ) -+ ( 3$, Р» ) ( 3$, Р», 0ТУ ) -+ ( Р», 0ТУ ) ( 3$, Р», 0ТУ ) -+ ( Б», 0ТУ ) ( 3», Р», 0тт ) -з ( 3$ ) ( 3», Р», 0ТУ ) -+ ( Р$ ( 3$, Р», 0ТТ ) -э ( 0ТТ ) ( 3$, Р$, СТУ ) -+ ( ( 3$, Р» ) -> ( 3$, Р», 0ТУ ) ( 3», Р» ) -э ( 3$, Р$ ) ( 3$, Р» ) - ( Р», 0тт ) ( 3»', Р» ) + ( я»', 0тт ) ( 3», Р» ) — ( 3$ ) ( Я», Р$ ) -+ ( Р» ) ( 3$, Р» ) — ( 0 ) ( Б» Р» ) -+ ( ) ( Р$, 0ТУ ) -+ ( Р$, 0ТУ ) ( Р», ЦТУ ) -э ( Р$ ) ( Р$, 0ТУ ) — э ( 0ТУ ) (Р»',0ТТ) ->() ( я», ()тх ) -+ ( 3», 0тх ) ( 3$, 0тт ) — ( я» ) ( Я$, 0ТУ ) †> ( 0ТУ ) ( 3», 0ту ) -э ( ) ( 3$ ) -+ ( 3$ ) (3$)- () (Р») — >(Р») (Р») - () ( ()ТУ» ) -+ ( 0ТУ» ( 0ТУ» ) -+ ( ()-+() 10 8.
(А,С) = (А,В,С,В,Е). На вторую часть вопроса следует дать утвердительный ответ. 10.11.0ни зквивалентны. Пронумеруем функциональные зависимости из первого множества следующим образом. 1. А — эВ 2. А — >С 418 Часть |11. Проектирование базы данных 3.
0 — эйС 4. 0 — гЕ Тогда строка 3 может быть заменена следующей строкой. 3. 0 — эйи0 — >С Затем с помощью строки 1 можно придать строке 2 такой вид. 2. А-+С Но поскольку теперь 0 -э й и А -э С, по транзитивности это подразумевает 0 э С, а в результате для строки 3 можно получи~ь следующее выражение. 3. 0 — +й Таким образом, первое множество функциональных зависимостей эквивалентно следующему неприводимому множеству.
А — э В А — э С 0 -э й 0 — э Е Приведенное ниже второе множество функциональных зависимостей, очевидно, эквивалентно данному неприводимому множеству. А-+ВС 0 э АЕ Таким образом, эти множества эквивалентны. ° 10.12.Прежде всего, следует переписать данное множество так, чтобы каждая функциональная зависимость имела одноэлементную правую часть. 1. А — > С 2. С вЂ” >А 3. ВС вЂ” э 0 4. АС0 — э В 5. ВŠ— э С 6.
СŠ— +й 7. СŠ— э Р 8. СР— эВ 9, СР— э0 10.0 — э Е 11.0 г Р Тогла получаем следующее. ° Строка 2 подразумевает строку 6, поэтому строку 6 можно опустить. ° Строка 8 подразумевает функциональную зависимость СР— э ВС (по правилу дополнения), которая вместе со строкой 3 подразумевает функциональную зависимость СР— э 0 (по правилу транзитивности), так что строку 9 можно опустить. Глава 10. Функциональные зависимости 419 ° Строка 8 подразумевает функциональную зависимость АСà — з АВ (по дополнению), а строка 11 — функциональную зависимость АСР— + АСГ (по дополнению). Тогда можно записать, что АСР— > АВ (по правилу транзитивности) и АСР— з В (по правилу декомпозиции).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
