Тема_6 (1122348)
Текст из файла
Проектирование РБД:дальнейшая нормализацияС.Д. Кузнецов. Базы данных. Тема 6План (1)ВведениеМногозначные зависимости и четвертаянормальная формаАномалии обновлений при наличиимногозначных зависимостей и возможнаядекомпозицияМногозначные зависимости. ТеоремаФейджина. Четвертая нормальная форма29.10.2009С.Д. Кузнецов. Базы данных.2Проектирование РБДПлан (2)Зависимости проекции/соединения и пятаянормальная формаN-декомпозируемые отношенияЗависимость проекции/соединенияАномалии, вызываемые наличиемзависимости проекции/соединенияУстранение аномалий обновления в 3декомпозицииПятая нормальная формаЗаключение29.10.2009С.Д.
Кузнецов. Базы данных.3Проектирование РБДВведение (1)Функциональные зависимости и нормальные формы,основанные на учете «аномальных» функциональныхзависимостей, являются естественными и легкопонимаемыми, поскольку в их основе лежит интуитивнопонятное понятие функционального отображенияБыло бы замечательно, если бы ликвидация в ходенормализации аномальных функциональных зависимостейгарантировала отсутствие аномалий обновления отношенийК сожалению, эта гарантия в общем случае необеспечиваетсяИногда в переменных отношений требуется поддержкаболее сложных ограничений целостности, для выражениякоторых понятие функции оказывается недостаточным29.10.2009С.Д.
Кузнецов. Базы данных.4Проектирование РБДВведение (2)Класс зависимостей, опирающихся на понятие функционала– обобщение понятия функции, обнаружил в 1970-е гг.Рональд ФейджинОн назвал такие зависимости многозначными, поскольку вних одному значению детерминанта соответствуетмножество значений зависимого атрибутаНаличие в переменной отношения многозначныхзависимостей, не являющихся функциональнымизависимостями от возможного ключа, приводит к аномалиямобновления таких отношенийФейджин показал, что и в этом случае возможнадекомпозиция данных отношений на две проекции, длякоторых подобные аномалии обновления не проявляютсяТакие проекции находятся в четвертой нормальной форме29.10.2009С.Д.
Кузнецов. Базы данных.5Проектирование РБДВведение (3)Позже было установлено, что при наличиинекоторых естественных ограничений,являющихся обобщением ограничениймногозначных зависимостей, и в отношениях,которые находятся в четвертой нормальнойформе, проявляются аномалии обновленияБолее того, эти аномалии невозможно устранитьпутем проецирования отношения на двепроекции, требуется декомпозиция на три илибольшее число отношенийТакие ограничения получили названиезависимостей проекции/соединения.29.10.2009С.Д.
Кузнецов. Базы данных.6Проектирование РБДВведение (4)Отношение, в котором существует нетривиальнаязависимость проекции/соединения, может бытьдекомпозировано на три или большее число проекций, вкоторых зависимости проекции/соединения следуют извозможного ключаТакие проекции находятся в пятой нормальной форме, илинормальной форме проекции/соединенияВ отношениях, находящихся в пятой нормальной форме,отсутствуют аномалии обновления, которые можно было быустранить путем декомпозиции, и поэтому при достижении пятой нормальной формы процесспроектирования реляционной базы данных на основенормализации естественным образом завершается29.10.2009С.Д. Кузнецов. Базы данных.7Проектирование РБДMVD и 4NF (1) Рассмотрим ещеодну возможнуюинтерпретациюпеременной отношенияСЛУЖ_ПРО_ЗАДАН Предположим, чтокаждый сотрудникможет участвовать внескольких проектах,но в каждом проекте, вкотором он участвует,им должнывыполняться одни и теже задания29.10.2009С.Д.
Кузнецов. Базы данных.8Проектирование РБДMVD и 4NF (2)Аномалии обновлений при наличии MVD (1)В новом варианте переменной отношенияединственно возможным ключом являетсязаголовок отношения{СЛУ_НОМ, ПРО_НОМ, СЛУ_ЗАДАН}Кортеж{<СЛУ_НОМ, сн>, <ПРО_НОМ, пн>, <СЛУ_ЗАДАН, сз>}входит в тело отношения в том и только в томслучае,когда служащий с номером сн выполняет в проекте пнзадание сз29.10.2009С.Д. Кузнецов. Базы данных.9Проектирование РБДMVD и 4NF (3)Аномалии обновлений при наличии MVD (2)Поскольку для каждого служащего указываются все проекты, вкоторых он участвует, и все задания, которые он должен выполнятьв этих проектах, для каждого допустимого значения переменнойотношения СЛУЖ_ПРО_ЗАДАН должно выполняться следующееограничение (BСПЗ обозначает тело значения переменнойотношения СЛУЖ_ПРО_ЗАДАН):IF({<СЛУ_НОМ, сн>, <ПРО_НОМ, пн1>, <СЛУ_ЗАДАН, сз1>} ∈ BСПЗAND{<СЛУ_НОМ, сн>, <ПРО_НОМ, пн2>, <СЛУ_ЗАДАН, сз2>} ∈ BСПЗ )THEN({<СЛУ_НОМ, сн>, <ПРО_НОМ, пн1>, <СЛУ_ЗАДАН, сз2>} ∈ BСПЗAND{<СЛУ_НОМ, сн>, <ПРО_НОМ, пн2>, <СЛУ_ЗАДАН, сз1>} ∈ BСПЗ )29.10.2009С.Д.
Кузнецов. Базы данных.10 Проектирование РБДMVD и 4NF (4)Аномалии обновлений при наличии MVD (3)Наличие такого ограничения (оно порождается наличиеммногозначной зависимости) приводит к тому, что при работес отношением СЛУЖ_ПРО_ЗАДАН проявляются следующиеаномалии обновления: Добавление кортежа. Если уже участвующий в проектахслужащий присоединяется к новому проекту, то к телузначения переменной отношения СЛУЖ_ПРО_ЗАДАНтребуется добавить столько кортежей, сколько заданийвыполняет этот служащий Удаление кортежей.
Если служащий прекращает участие впроектах, то отсутствует возможность сохранить данные озаданиях, которые он может выполнять Модификация кортежей. При изменении одного из заданийслужащего необходимо изменить значение атрибутаСЛУ_ЗАДАН в стольких кортежах, в скольких проектахучаствует служащий29.10.2009С.Д. Кузнецов. Базы данных.11 Проектирование РБДMVD и 4NF (5)Аномалии обновлений при наличии MVD (4) Трудности, связанные с обновлениемпеременной отношенияСЛУЖ_ПРО_ЗАДАН, решаются путем егодекомпозиции на две переменныхотношений: СЛУЖ_ПРО_НОМ {СЛУ_НОМ,ПРО_НОМ} и СЛУЖ_ЗАДАНИЕ {СЛУ_НОМ,СЛУ_ЗАДАН}29.10.2009С.Д.
Кузнецов. Базы данных.12 Проектирование РБДMVD и 4NF (6)Аномалии обновлений при наличии MVD (5)Легко видеть, что эта декомпозиция является декомпозициейбез потерь и что она решает перечисленные вышепроблемы с обновлением переменной отношенияСЛУЖ_ПРО_ЗАДАН: Добавление кортежа. Если некоторый уже участвующий впроектах служащий присоединяется к новому проекту, то ктелу значения переменной отношения СЛУЖ_ПРО_НОМтребуется добавить один кортеж, соответствующий новомупроекту Удаление кортежей.
Если служащий прекращает участие впроектах, то данные о заданиях, которые он можетвыполнять, остаются в отношении СЛУЖ_ЗАДАНИЕ Модификация кортежей. При изменении одного из заданийсотрудника достаточно изменить значение атрибутаСЛУ_ЗАДАН в одном кортеже отношения СЛУЖ_ЗАДАНИЕ29.10.2009С.Д. Кузнецов. Базы данных.13 Проектирование РБДMVD и 4NF (7)MVD, теорема Фейджина, 4NF (1)Заметим, что последний вариант переменной отношенияСЛУЖ_ПРО_ЗАДАН находится в BCNF, поскольку все атрибутызаголовка отношения входят в состав единственно возможногоключаВ этом отношении вообще отсутствуют нетривиальные FDПоэтому ранее обсуждавшиеся принципы нормализации здесьнеприменимы, но, тем не менее, мы получили полезнуюдекомпозицию.В случае этого варианта отношения СЛУЖ_ПРО_ЗАДАН мы имеемдело с новым видом зависимости, впервые обнаруженным РономФейджином в 1971 г.Фейджин назвал зависимости этого вида многозначными (multivalued dependency – MVD)Многозначная зависимость атрибута A от атрибута B обозначается,как A →→ BКак мы увидим немного позже, MVD является обобщением понятияFD29.10.2009С.Д.
Кузнецов. Базы данных.14 Проектирование РБДMVD и 4NF (8)MVD, теорема Фейджина, 4NF (2)В отношении СЛУЖ_ПРО_ЗАДАН выполняются две MVD:СЛУ_НОМ →→ ПРО_НОМ иСЛУ_НОМ →→ СЛУ_ЗАДАНПервая MVD означает, что каждому значению атрибута СЛУ_НОМсоответствует определяемое только этим значением множествозначений атрибута ПРО_НОМДругими словами, в результате вычисления алгебраическоговыражения(СЛУЖ_ПРО_ЗАДАНWHERE (СЛУ_НОМ = сн AND СЛУ_ЗАДАН = сз))PROJECT {ПРО_НОМ}для фиксированного допустимого значения сн и любогодопустимого значения сз мы всегда получим одно и то жемножество значений атрибута ПРО_НОМАналогично трактуется вторая MVD29.10.2009С.Д.
Кузнецов. Базы данных.15 Проектирование РБДMVD и 4NF (9)MVD, теорема Фейджина, 4NF (3)Определение 6.1. Многозначная зависимостьВ переменной отношения r с атрибутами A, B, C(в общем случае, составными) имеетсямногозначная зависимость B от A (MVD A →→ B)в том и только в том случае, когда множествозначений атрибута B, соответствующее парезначений атрибутов A и C, зависит от значения Aи не зависит от значения CМногозначные зависимости обладаютинтересным свойством «двойственности»,которое демонстрирует следующая лемма29.10.2009С.Д. Кузнецов. Базы данных.16 Проектирование РБДMVD и 4NF (10)MVD, теорема Фейджина, 4NF (4)Лемма ФейджинаВ отношении r {A, B, C} выполняется MVD A →→ B в том и только в томслучае, когда выполняется MVD A →→ CДокажем достаточность условия леммыПусть выполняется MVD A →→ BПусть R – некоторое значение переменной отношения r, удовлетворяющееэтой зависимостиПусть a обозначает значение атрибута A в некотором кортеже BR, {b} и {c} –множества значений атрибутов B и C соответственно, взятых из всехкортежей тела BR, в которых значением атрибута A является aПредположим, что для этого значения a MVD A →→ C не выполняетсяЭто означает, что существует значение c ∈ {c}, что для него найдется такоезначение b ∈ {b}, что кортеж {<A, a>, <B, b>, <C, c>}∉ BRНо это противоречит наличию MVD A →→ B ({b} зависит только от a)Следовательно, если выполняется MVD A →→ B, то выполняется и MVD A→→ CАналогично можно доказать необходимость условия леммы29.10.2009С.Д.
Кузнецов. Базы данных.17 Проектирование РБДMVD и 4NF (11)MVD, теорема Фейджина, 4NF (5)Таким образом, MVD A →→ B и A →→ C всегда составляютпару Поэтому обычно их представляют вместе в форме A →→ B |CFD является частным случаем MVD, когда множествозначений зависимого атрибута обязательно состоит изодного элемента Таким образом, если выполняется FD A → B, то выполняетсяи MVD A →→ B.Мы видим, что отношения СЛУЖ_ПРО_НОМ иСЛУЖ_ЗАДАНИЕ не содержат MVD, отличных от FD, иименно в этом выигрывает показанная раньше декомпозицияПравомочность этой декомпозиции доказываетсяприведенной ниже теоремой Фейджина, которая являетсяуточнением и обобщением теоремы Хита29.10.2009С.Д.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
