Введение в системы БД (542480), страница 101
Текст из файла (страница 101)
Таким образом, с тем же успехом в системе вместо исходного множества функциональных зависимостей Б может использоваться его неприводимое покрытие 1 (здесь следует повторить, что для вычисления неприводимого эквивалентного покрытия 1 необязательно вычислять замыкание Б'). Однако необходимо отметить, что для заданного множества функциональных зависимостей не всегда существует уникальное неприводимое покрытие (см.
упр. 10.12). 10.7. Резюме Функциональная зависимость — это связь типа "многие к одному" между двумя множествами атрибутов заданной переменной-отношения. Для заданной переменной- отношения В зависимость А — э В (где А и В являются подмножествами множества атрибутов переменной-отношения й) выполняется для переменной-отношения В тогда и только тогда, когда любые два кортежа переменной-отношения В с одинаковыми значениями атрибутов множества А имеют одинаковые значения атрибутов множества В. 411 Глава 10.
Функциональные зависимости Каждая переменная-отношение обязательно удовлетворяет некоторым тривиальным функциональным зависимостям; причем функциональная зависимость тривиальна тогда и только тогда, когда ее правая (зависимая) часть является подмножеством ее левой части (детерминанта). Одни функциональные зависимости подразумевают другие зависимости. Для данного множества зависимостей Б замыканием Я называется множество всех функциональных зависимостей, подразумеваемых зависимостями множества Я.
Множество Я обязательно является подмножеством собственного замыкания Б'. Правила логического вывода Армстронга обеспечивают исчерпывающую и полную основу для вычисления замыкания Б для заданного множества Я, хотя несколько дополнительных правил вывода (легко выводимых из правил Армстронга) позволяют упростить практические вычисления. Для данного подмножества 2 множества атрибутов переменной-отношения К и множества функциональных зависимостей Я, которые выполняются в переменной- отношении К, замыканием 2 подмножества 2 для множества Б называется такое множество всех атрибутов А переменной-отношения К, что функциональная зависимость 2 — + й являешься членом замыкания Б'.
Если замыкание 2' состоит из всех атрибутов переменной-отношения К, то подмножество 2 называют суперключом переменной-отношения К (а неприводимый суперключ, в свою очередь, называется потенциальным ключом). В этой главе было дано описание простого алгоритма для получения замыкания 2' на основе 2 и Я и, следовательно, для определения, является ли данная зависимость Х вЂ” э У членом замыкания Б (функциональная зависимость Х вЂ” > Т является членом замыкания Б тогда и только тогда, когда множество У является подмножеством замыкания Х ). Два множества функциональных зависимостей Б1 и Б2 эквивалентны тогда и только тогда, когда они являются покрытиями друг для друга, т.е. Б1 =Б2 .
Каждое множество функциональных зависимостей эквивалентно по крайней мере одному неприводимому множеству. Множество функциональных зависимостей является неприводимым, если, во-первых, каждая функциональная зависимость этого множества имеет однозлементную правую часть; во-вторых, если ни одна функциональная зависимость множества не может быть устранена без изменения замыкания этого множества; в-третьих, если ни один атрибут не может быть устранен из левой части любой функциональной зависимости данного множества без изменения замыкания множества.
Если 1 является неприводимым множеством, которое эквивалентно множеству Б, то проверка выполнения функциональных зависимостей из множества 1 автоматически обеспечит выполнение всех функциональных зависимостей из множества Б. В заключение следует отметить, что многие высказанные выше соображения можно расширить в отношении ограничений целостности вообще, а не только функциональных зависимостей.
Например, в общем случае следующие допущения являются верными. ° Некоторые ограничения целостности являются тривиальными. ° Одни ограничения целостности подразумевают другие ограничения. ° Множество всех ограничений, подразумеваемых заданным множеством, может рассматриваться как замыкание этого заданного множества. 412 Часть Ш. Проектирование базы данньп ° Выяснение вопроса, будет ли некоторое ограничение находиться в некотором замыкании (т.е, будет лн заданное ограничение подразумеваться некоторыми данными ограничениями), является очень интересной практической задачей.
° Не менее интересной практической задачей является поиск неприводимого покрытия для некоторого заданного множества установленных ограничений. Благодаря наличию исчерпывающего и полного множества правил вывода различных функциональных зависимостей, работать с ними удобнее, чем с ограничениями целостности вообще. В списках рекомендуемой литературы в конце этой и главы!2 даны ссылки на работы, в которых описывается несколько других типов ограничений (МЧР, )Р и ПМР); для них также существуют подобные наборы правил вывода.
Однако в данной книге лругие существующие типы ограничений столь же подробно и полно, как функциональные зависимое~и, не рассматриваются. Упражнения 10.1. Пусть В является переменной-отношением степени л. Каково максимальное количество функциональных зависимостей (как тривиальных, так и нетривиальных), которые могут выполняться для переменной-отношения В? 10.2. Что конкретно имеется в виду, когда говорится, что правила Армстронга полны и исчерпывающи? 10.3. Докажите правила рефлексивности, дополнения и транзитивности, используя только определение функциональной зависимости. 10.4.
Докажите, что три предыдуших правила подразумевают правила саиоопределения, декоипоэипии, объединения и котпоэичии. 10.5. Докажите общую теорему объединения, предложенную Дарвеном. Какие из перечисленных выше правил потребуются для этого? Какие правила можно вывести в виде особых случаев этой теоремы? 10.6. Дайте определение для а) замыкания множества функциональных зависимостей; б) замыкания множества атрибутов лля заланного множества функциональных зависимостей.
10.7. Перечислите множество всех функциональных зависимостей, которые всегда выполняются для переменной-отношения поставок БР. 10.8. Ниже приведено множество функциональных зависимостей, имеющих место для переменной-отношения й(А, В, С, О, Е, Р,Б). А — + В ВС вЂ” > ВЕ АЕР†> 0 Вычислите замыкание (А,С) для данного множества функциональных зависимостей. Подразумевается ли зависимость АСР— э 06 одной из функциональных зависимостей этого множества? 10.9. Что означает понятие эквивалентности двух множеств функциональных зависимостей Б1 и Б2? 413 Глава 10, Функциональные зависимости 10,10.Что означает понятие неприводимости множества функциональных зависимостей? 10.11.Определите, эквивалентны ли лва приведенных ниже множества функциональных зависимостей, установленных для переменной-отношения й(А, В, С, О, Е).
!. А — эВ А — >С 0 — эйС 0-эЕ 2. А -э ВС 0 -э АЕ 10.12.Найдите неприводимое покрытие приведенного ниже множества функциональных зависимостей, заданных для переменной-отношения В(А, В, С, О, Е, Р) . йВ -э С С вЂ” э й ВС вЂ” > 0 йС0 -э В ВŠ— э С СЕ -+ Рй СР э В0 0 †> ЕР 10.13.В переменной-отношении Т1НЕТАВЬЕ определены перечисленные ниже атрибуты.
0 День недели (! — 5) Р Период времени в течение дня (1 — 8) С Номер класса Т Имя учителя Ь Название урока Кортеж (О:б, Р:р, С:с, Т:С, 1:1) является элементом этой переменной- отношения то~да и только тогда, когда урок 1 проводится учителем Е в классе с в момент (0:б, Р:р).
Предположим, что длительность всех уроков равна одному периоду времени и, кроме того, каждый урок имеет название, уникальное по отношению ко всем урокам этой недели. Какие функциональные зависимости выполняются для этой переменной-отношения? Какие потенциальные ключи существуют для этой переменной-отношения? 10.14.Пусть задана переменная-отношение Нй00В с атрибутами НАНЕ (уникальное имя), ВТВЕЕТ (улица), С!ТУ (город), ЯТАТЕ (штат) и 81Р (индекс), где каждому инлексу соответствует только один город и штат, а каждой улице, городу и штату соответствует ~олько олин индекс.
Найдите неприводимое множество функциональных зависимостей лля этой переменной-отношения. Какие потенциальные ключи существуют для этой переменной-отношения? 10.15.Пусть дана переменная-отношение В с атрибутами (А,В,С,В,Е,Р,О,Н,1,Ю), для которой выполняется приведенное ниже множество функциональных зависимостей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
