Kolokvium / KOR_2

НОРМАЛИЗАЦИЯ ОТНОШЕНИЙ

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

корректировка отношений не должна приводить к двусмыс­ленности или потере информации;

перестройка набора отношений при введении новых ти­пов данных должна быть минимальной.

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

Среди зависимостей между реквизитами отношения спе­циально выделяются функциональные зависимости. Реквизит В отношения r функционально зависит от реквизита А, если в каждый момент времени каждому значению А соответствует не более чем одно значение В. В свою очередь А функцио­нально определяет В. Иллюстрирует это понятие рис. 3.1; каждое ребро в графе определяет элемент отношения r(А, В). Функциональная зависимость В от А соответствует понятию однозначной функции B = f(A). Данное определение легко распространяется на случай зависимости между группами рек­визитов. Группу М составим из реквизитов А₁, А₂, ..., А_m, группу N - из реквизитов B₁, В₂, ..., В_n. Кортежи отноше­ний r[M] и r[N] будем считать значениями групп реквизи­тов М и N. С учетом этого к М и N применимо общее опреде­ление функциональной зависимости.

Рис. 3.1. Зависимости между реквизитами:

а - функциональная А®B, б - нефункциональная (кортежи < а₃ , в₁ >,< а₂ , в₂> нарушают свойство функциональности), в - взаимно - однозначная A«B.

Наличие функциональной зависимости реквизита В от реквизита А обозначается r. А® r. В, ее отсутствие r. А® r. B. Если ясно, о каком отношении идет речь, то пишут А®В или А®В. Случай А® В, В®А обозначается A«B и называется взаимно - однозначным соответствием (рис. 3.1, е). Очевидно, что в случае А®В число элементов в реквизите А больше, чем в реквизите В, а при взаимно - ­однозначном соответствии число элементов одинаково.

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

Вероятный ключ К отношения r является ком­бинацией из п реквизитов (возможно n = 1), обладающей сле­дующими двумя свойствами: уникальностью (значения К (понимаемые как строки проекции r[К]) и кортежи отноше­ния r находятся во взаимно - однозначном соответствии); неизбыточностью. Набор реквизитов в K нельзя сократить без нарушения первого свойства.

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

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

Найдем, например, ключи в отношении Q (ПРЕДПРИЯ­ТИЕ, АДРЕС, ПРОДУКЦИЯ, ВЫПУСК).

Различных предприятий, естественно, меньше, чем различ­ных кортежей в Q, так как предприятие может выпускать не­сколько видов продукции. Аналогично данная продукция мо­жет выпускаться несколькими предприятиями. Поэтому ни ПРЕДПРИЯТИЕ, ни ПРОДУКЦИЯ по отдельности вероят­ного ключа не образуют. Вместе они составляют вероятный ключ, поскольку ВЫПУСК и АДРЕС ими однозначно опре­деляются. Если учесть зависимость ПРЕДПРИЯТИЕ«АД­РЕС, то появляется еще один вероятный ключ АДРЕС, ПРО­ДУКЦИЯ.

Легко доказать, что каждый неключевой реквизит из от­ношения r функционально зависит от каждого вероятного ключа из r. При предположении обратного возникаем проти­воречие с понятием вероятного ключа. По той же причине два вероятных ключа всегда находятся во взаимно - однозначном соответствии .

Для отношения Q можно теперь вывести зависимости:

ПРЕДПРИЯТИЕ, ПРОДУКЦИЯ «АДРЕС

ПРЕДПРИЯТИЕ, ПРОДУКЦИЯ«ВЫПУСК

АДРЕС, ПРОДУЩИЯ«ПРЕДПРИЯТИЕ

АДРЕС, ПРОДУКЦИЯ«ВЫПУСК

ПРЕДПРИЯТИЕ, ПРОДУКЦИЯ«АДРЕС, ПРОДУКЦИЯ

Важное свойство составного (многореквизитного) вероят­ного ключа состоит в том, что никакие два входящих в него реквизита не могут быть связаны функциональной зависимостью. Рассмотрим отношение R с составным ключом ABC и зависимостью В®С. Докажем, что в отношении R`, полученном из R отбрасыванием реквизита С, столько же кортежей, что и в самом R. Допустим обратное. Тогда в R найдетcя стро­ка аb (аÎА, bÎВ), которой в R соответствуют по крайней мере две строки аbc₁ и аbс₂ (с₁ , с₂ ÎС), а это противоречит функциональной зависимости В®С. Отсюда следует, что ключ АВС является избыточным.

Следовательно, в отношении Q

ПРЕД ПРИМ ТИЕ®ПРОДУКЦИЯ

ПРОДУКЦИЯ ®ПРЕДПРИЯТИЕ

АДРЕС ®ПРОДУКЦИЯ

ПРОДУКЦИЯ®АДРЕС

Следующие три свойства функциональных зависимостей справедливы как для отдельных реквизитов, так и для групп реквизитов. Поэтому условимся, что реквизиты А_i ( i =), В_j (j =) и С_k () принадлежат одному отношению R. Могут быть сформулированы следующие теоремы, принадлежащие Армстронгу:

1 ) А₁ А₂ . . . А_m, А_i , для i = .

2) А₁ А₂ . . .А_m ® B₁ B₂ ... В_r тогда и только тогда, когда А₁ А₂ . . . А_m ®В_j для любого j = .

3. Если А₁ А₂ . . .А_m ® B₁ B₂ ... В_r и B₁ B₂ ... В_r® С₁С₂ . . . С_р , то А₁ А₂ .А_m ® С₁С₂ . . . С_р.

В отношении Q можно выделить следующие зависимости, вытекающие из теорем Армстронга:

ПРЕДПРИЯТИЕ, ПРОДУКЦИЯ®ПРЕДПРИЯТИЕ

ПРЕДПРИЯТИЕ, ПРОДУКЦИЯ®ПРОДУКЦИЯ

АДРЕС, ПРОДУКЦИЯ®АДРЕС

АДРЕС, ПРОДУКЦИЯ®ПРОДУКЦИЯ

ПРЕДПРИЯТИЕ, ПРОДУКЦИЯ®АДРЕС, ВЫПУСК

АДРЕС, ПРОДУКЦИЯ®ПРЕДПРИЯТИЕ, ВЫПУСК

Приведенные теоремы о функциональных зависимостях (список их может быть расширен) позволяют формализовать и автоматизировать процесс установления таких зависимостей.

Совокупность функциональных зависимостей может быть изображена графически в виде диаграммы. Вершинами диа­граммы функциональных зависимостей являются различные группы имен реквизитов. Дуга от вершины к вершине означает наличие функциональной зависимости между соответствующими группами реквизитов. Зависимости, которые следуют из теорем Армстронга, на диаграмме, как правило, не показы­ваются. Диаграмма функциональных зависимостей отношения Q приведена на рис. 3.2. Вероятные ключи на любой диаграм­ме функциональных зависимостей соответствуют вершинами которые не заходит ни одна дуга. Многореквизитный ключ об­водится рамкой.

Функциональные зависимости и вероятные ключи отноше­ний должны учитываться при выполнении операций реляци­онной алгебры. В качестве примера рассмотрим реализацию эквисоединения. Пусть отношение R (A, B, С) с помощью опе­рации проекции разделено на R₁ (A, В) и R₂ (B, С). Таблицы значений отношений R и Т = совпадают только тогда, когда реквизит В является вероятным ключом в R₁ или R₂ А, В и С можно рассматривать и как группы реквизитов.

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

Первая нормальная форма отношения (сокращенно1НФ) определяется условием - среди значений реквизитов не должно быть кортежей. Ненормализованные СЕИ не соответст­вуют условиям 1НФ, а нормализованные СЕИ находятся в 1НФ. Если предполагается для обработки извлекать только часть реквизита (например, из даты только год), то отношение, содержащее такой реквизит, не находится в 1НФ.

Условия, определяющие 1НФ отношения, не содержат ни­каких ограничений на возможные варианты функциональных зависимостей. Поэтому создание и корректировка значений в отношении, находящемся в 1НФ, часто бывают затруднены. В рассмотренное ранее отношение Q, в котором соблюдаются условия 1НФ, невозможно включить сведения о предприятии и его адресе, пока предприятие не выпустит какую-то продук­цию. Если предприятие, производящее единственный вид про­дукции, прекращает его выпуск, то необходимое при этом уда­ление кортежа разрушает сведения об адресе предприятия. Далее, одинаковое значение адреса встречается во многих кортежах, если предприятие выпускает большой ассортимент продукции.

Любая замена адреса предприятия становится при этом очень трудоемкой операцией. Указанные факты объяс­няются функциональной зависимостью адреса от предприя­тия. Подобные функциональные зависимости называются не­полными.

Выделим в отношении R два различных подмножества рек­визитов F и E, связанных условием F®Е. Если Е функцио­нально не зависит от любого подмножества F, то функциональ­ная зависимость F®Е, называется полной. Если существует группа реквизитов G, такая, что FÌG и G®E, то функциональная зависимость называется полной.

Отношение R находится во второй нормальной форме (2НФ), если оно находятся в 1НФ и каждыми рек­визит функционально полно зависит от каждого вероятного ключа. Если вероятный ключ однореквизитный, то условия 2НФ соблюдаются автоматически. Отсюда, например, следует, что бинарное отношение всегда находится в 2НФ.

Для отношения в 2НФ не характерны аномалии про­цессов формирования и корректировки, которые были рас­смотрены выше на примере отношения. Поэтому отношение, не находящееся в 2НФ, целесообразно разделить на части, каждая из которых находится в 2НФ.

Выделим в отношении R вероятный ключ F и неключевые реквизиты А, B, ..., Е. Допустим, что FÌG и G®E, следовательно, R находится в 1НФ, но не в 2НФ. С помощью операции проекции создадим два отношения R₁ (G,Е) и R₂ (F, A, B) , каждое из которых находится в 2НФ. R₂ содержит вероятный ключ и те неключевые реквизиты, которые не участвуют в неполной зависимости. R₁ содержит неключевой реквизит, участвующий в неполной зависимости, и под­множество вероятного ключа, которое функционально опре­деляет этот реквизит.

В рассматриваемом примере АДРЕС функционально за­висит от части первичного ключа - реквизита ПРЕДПРИЯ­ТИЕ. Поэтому отношение Q не удовлетворяет условиям 2НФ. Надо разделить его на две проекции Q₁ (ПРЕДПРИЯТИЕ, АДРЕС) и Q₂ (ПРЕДПРИЯТИЕ, ПРОДУКЦИЯ, ВЫПУСК), каждая из которых находится в 2НФ. При необходимости мож­но создать исходное отношение Q с помощью эквисоединения

Q = Q₁ < >О₂.

Правильность эквисоединения подтверждается тем, что ПРЕДПРИЯТИЕ - вероятный ключ в Q₁.

В отношении, удовлетворяющем 2НФ, остаются транзи­тивные функциональные зависимости между реквизитами. Реквизит АÎU транзитивно зависит от множества реквизи­тов XÎU, если существует группа реквизитов YÎU , та­кая, что Х®Y, Y®Х, Y®А.

Наличие транзитивных зависимостей может создавать не­желательные эффекты при корректировке. Например, для ис­ключения какого-то значения реквизита А требуется удаление значительного числа строк.

Назовем некоторый реквизит (возможно, набор реквизи­тов), от которого какой-то другой реквизит функционально (полностью функционально) зависит, детерминантой. Тогда можно определить третью нормальную форму отношения (ЗНФ) условием - каждая детерминанта должна являться вероятным ключом. Еcли вероятный ключ единственный, то 3НФ определяется как отношение в 2НФ, в котором каждый неключевой реквизит нетранзитивно зависит от первичного ключа. Сформулированное определение не запрещает транзитивной зависимости реквизитов, входящих в первичный ключ от других вероятных ключей, что недопустимо соглас­но первому определению. Поэтому первое определение содержит более сильные условия и соответствующая форма отношения часто называется усиленной ЗНФ. Надо отметить, что бинарное отношение обязательно находится в ЗНФ, по­скольку для наличия транзитивной функциональной зависи­мости в отношении должны быть минимально три реквизита.

Рис. 3.2. Диаграмма функциональ­ных зависимостей отношения Q

Рис. 3.3. Функциональные зависимости отношения СПИСОК (НС, ФИО, Г, КС, ВК)

Отношение в ЗНФ обладает простейшим набором функцио­нальных зависимостей - первичный ключ функционально определяет каждый неключевой реквизит н других функциональ­ных зависимостей в отношении нет. Отношение в ЗНФ не со­здает аномалий при корректировке, о которых упоминалось выше. Поэтому отношение, находящееся в 2НФ, но не в ЗНФ, целесообразно разделить (с помощью операции проекции) на части, не содержащие транзитивных зависимостей.

Рассмотрим отношение СПИСОК (НС, ФИО, Г, КС. ВК), где НС - номер зачетной книжки студента, ФИО - его фа­милия, имя, отчество, Г - номер группы, КС - код специаль­ности, ВК - выпускающая кафедра. Функциональные за­висимости этого отношения приводятся на рис. 3.3. Обоснование зависимостей очень простое: каждый студент имеет одну зачетную книжку, учится в одной группе, по одной специаль­ности, на одной выпускающей кафедре; студенты каждой груп­пы обучаются по одной специальности, на одной выпускающей кафедре.

Соответствие СПИСОК находится в 2НФ и содер­жит две транзитивные за­висимости НСГКС и НСГВК. Разде­лить СПИСОК на проек­ции, удовлетворяющие ЗНФ, можно несколькими способами. Некоторые из них показаны в табл. 3.3.

Таблица 3.3

Имеются две возмож­ности при ликвидации це­почки зависимостей А®В®С. Либо связь А®В принадлежит первой проекции, а связь В®С - второй проекции, либо А®В относится к пер­вой проекции, а А®С - ко второй. В последнем случае очень трудно следить за соблюдением соотношения В®С, так как реквизиты В и С принадлежат разным отношениям. Поэтому практически ре­комендуется первый способ. Нежелательным с этой точки зрения является вариант №4 (табл. 3.3).

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

Рассмотрим пример выполнения алгоритма. На рис. 3.4 приведена диаграмма функциональных зависимостей отношения с реквизитами СЛУЖ - служащий, ДОЛЖ - долж­ность, ОКЛАД, ДАТА изменения должности и/или оклада; ТЕМА, по которой служащий работает в отделе НИИ; ОТДЕЛ, НИИ, ФИН - объем финансирования работ по теме. Зависи­мость (СЛУЖ, ДАТА) ® СЛУЖ и все транзитивные зависи­мости следуют из теорем Армстронга. Транзитивные зависи­мости из диаграммы удалены. В начальном положении вероятным ключом является (СЛУЖ, ДАТА), что позволяет выделить отношение в ЗНФ

R1 (СЛУЖ, ДАТА, ДОЛЖ, ОКЛАД)

Затем вероятным ключом становится СЛУЖ, что соответст­вует отношению

R2 (СЛУЖ, ТЕМА)

Следующий вероятный ключ - ТЕМА и следующее отношение в ЗНФ

R3 (ТЕМА, ФИН, ОТДЕЛ)

И наконец, R4 (ОТДЕЛ, НИИ)

Рис. 3.4. Диаграмма функциональных зависимостей отношения RT

Отношение, удовлетворяющее ЗНФ, может содержать еще одно, нежелательное с точки зрения корректировки, свойст­во, а именно многозначную зависимость реквизитов. Введем определение такой зависимости.

Выделим в отношении R три реквизита X, Y, Z. В R име­ется многозначная зависимость между X и Y (обозначается X ®®Y), если при наличии в R двух строк со значениями (x₁ ,y₁ ,z₁) и (x₂ ,y₂ ,z₂) обязательно (содержатся строки со значения (x₁ ,y₁ ,z₂) и (x₁ ,y₂ ,z₁). Здесь x₁ ÎX, y₁ ,y₂ ÎY, z₁ ,z₂ ÎZ.

При корректировке отношения, содержащего многозначно зависимые реквизиты, изменение значения одного из таких реквизитов приводит к корректировке большого числа корте­жей. Поэтому целесообразно иметь дело с отношениями, не содержащими многозначно зависимых реквизитов. Это усло­вие фиксируется в определении четвертой нормальной формы (4НФ) отношения.

Отношение находится в 4НФ, если при наличии многозначной зависимости Х®®Y либо ХY содержит все реквизиты R либо вероятный ключ R содержится в X. Приведе­ние отношения R (Х, Y, Z) к 4НФ (если оно не обладает этим свойством) сводится к его разделению на две проекции R1(X,Y), и R2(X,Z). На рис. 3.5 и табл. 3.4 представлено отношение R с реквизитами ЦЕХ, ПРОДУКЦИЯ, СЫРЬЕ, не удовлетворяющее 4НФ из-за многозначной зависимости реквизитов ЦЕХ и ПРОДУКЦИЯ.

Рис. 3.5. Графическая интерпретация отношения R

Таблица 3.4

Проекции R1 и R2 отношения R со свойствами 4НФ содержат следующие значения:

Обратное преобразование сводится к выполнению эквисоединения по атрибуту ЦЕХ.

При нормализации отношений происходит снижение их порядка. Этот процесс можно искусственно довести до логиче­ского конца и получить набор отношений с минимально воз­можным порядком - два. Соответствующая модель данных на­зывается бинарной реляционной моделью. Если исходное от­ношение в реляционной модели данных имеет однореквизитный первичный ключ (допустим, А) и структуру

R (А, В, С, D . . . ),

то его бинарные проекция получаются по следующему просто­му правилу:

R1(A,B)

R2(A,C)

R3(A,D)

Если первичный ключ исходного отношения состоит из не­скольких реквизитов, в отношение вводится дополнительный реквизит НОМЕР КОРТЕЖА, значения которого являются порядковыми номерами кортежей (строк) отношения. Значе­ния реквизита НОМЕР КОРТЕЖА находятся во взаимно­ - однозначном соответствии со строками отношения, поэтому он может стать первичным ключом отношения. Таким образом, произвольное отношение приводится к частному случаю с однореквизитным ключом, преобразование которого в набор би­нарных отношений уже известно. Возможны и другие вари­анты получения бинарных отношений из парного, однако всегда должна обеспечиваться возможность восстановления исходного отношения по его бинарным проекциям с помощью операции эквисоединения. Имена бинарных отношений обыч­но формируются из пары имен реквизитов, входящих в отно­шение.

Рассмотрим пример преобразования произвольного отно­шения в набор бинарных отношений. Отношение РЕЙСЫ описывает морские порты и заходящие в них суда. Диаграмма функциональных зависимостей отношения РЕЙСЫ показана на рис. 3.6.

R1(КОД СУДНА ,КОД ПОРТА ,НАЗНАЧЕНИЯ)

R2(КОД СУДНА ,КОД ПОРТА ПРИПИСКИ)

R3(КОД ПОРТА ПРИПИСКИ, ПАРОХОДСТВО)

R4 (КОД ПОРТА НАЗНАЧЕНИЯ, ПАРОХОДСТВО)

R5 (КОД СУДНА, ВОДОИЗМЕЩЕНИЕ)

Рис. 3.6. Переход от диаграммы функциональных зави­симостей к бинарным отношениям

Значения в бинарной реляционной модели данных груп­пируются в триплеты. Триплетом называется набор из имени неключевого реквизита значения первичного ключа из какого-то кортежа и значения неключевого реквизита из того же кортежа. Например,

ВОДОИЗМЕЩЕНИЕ, Лисичанск, 35000

ПАРОХОДСТВО, Баку, Каспийское

Обозначим элементы триплета следующим образом: А - имя неключевого реквизита, V - одно из его значений, Е - соответствующее значение первичного ключа. Сам триплет по­лучит выражение А (Е)qY. Через q обозначено одно из отно­шений =, <>, <, >, <=, >=. Один или два компонента триплета в запросах пользователей могут объявляться неизвестными (обозначаются знаком «?»), и поэтому возможны шесть типов запросов (табл. 3.5). Более сложные запросы могут быть образованы за счет логических связок между запросами ти­пов 1, 2, 3.

Для обработки бинарных отношений используются все операторы реляционной алгебры.

К преимуществам бинарной реляционной модели следует отнести хорошую обозримость модели из-за простоты бинарных отношений и соответствие всех отношений ЗНФ и даже 4НФ. Недостаток этой модели заключается в дублировании значе­ний первичных ключей, следовательно, бинарная модель данных занимает больший объем памяти, чем обычная реляционная модель.