1.5. Проектирование схем реляционных баз данных

1.5.1. Нормализация отношений

Одной из важных и сложных проблем процесса проектирования реляционных схем БД является выбор оптимальной структуры кортежа отношений. Из множества группировок атрибутов необходимо выбрать наиболее рациональную структуру кортежа, устойчивую при изменении как данных, так и связей между ними.

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

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

Рассмотрим процесс нормализации отношения на примере связей между предприятиями-производителями и товарами, используя следующие функциональные зависимости: F1: КПР ~> НПР, ГПР F2: КТ НТ, ЦЕНА, ДАТА F3: КПР, КТ, КПТ -» КОЛ F4: КПТ -» НОТ, ГПТ, РТ

На основании подобных зависимостей можно составить такие схемы отношений:

ПРОИЗВОДИТЕЛЬ (КПР, НПР, ГПР) ТОВАР (КТ, НТ, ЦЕНА, ДАТА) ПОТРЕБИТЕЛЬ (КПТ, НПТ, РП, ГПТ) ПОСТАВКА (КПР, КТ, КПТ, КОЛ)

Рассмотрим схему отношения ПОСТАВ (рис. 1.6) и предположим, что вся информация, касающаяся производителей, товаров и потребителей, вместо того, чтобы находится в отдельных отношениях, содержалась бы в одном отношении ПОСТАВ:

ПОСТАВ (КПР, ГПР, КТ, КПТ, ГПТ, РТ, КОЛ)

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

Первая нормальная форма.

Отношение ПОСТАВ находится в 1НФ, так как имеются в наличии значения всех полей каждого кортежа (записи) отношения.

Отношение ПОСТАВ содержит аномалии по отношению к операциям запоминания (Включение, Удаление, Обновление). Рассмотрим проблемы, возникающие с этими операциями.

Включение. В БД ПОСТАВ невозможно включить никакую информацию, если в ней отсутствует поле первичного ключа, например, ПР4, т.е. до тех пор, пока поставщик не поставит какой-либо товар. Напомним, что в нашей БД поле первичного ключа есть (КПР, КТ, КГТТ).

Удаление. Если поставщик имеет лишь одну запись, то в случае ее удаления, мы удалим информацию не только о товаре, но и о производителе, т.е. РТ и ГПР.

Обновление. Одно и тоже значение города потребителя (ГПТ) повторяется много раз. Эта избыточность вызывает проблемы при обновлении информации, например, при изменении места потребителя.

Решение этих проблем заключается в замене отношения ПОСТАВ тремя отношениями ПОСТ, ПРОИЗВ и ПОТР (табл. 1.6,1.7,1.8).

Вторая нормальная форма. Пусть R - схема отношения (с несколькими ключами). Атрибут А, принадлежащий некоторому ключу из R, называется ключевым (главным) в Л, в противном случае А - неключевой атрибут.

Пусть Х->А - F-зависимость. Атрибут А частично зависит от X, если А функционально зависит от некоторого подмножества YcX, т.е. Y~>A. Атрибут А полностью зависит от X, если он не зависит от любого подмножествах.

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

Отношение, находящееся в 1НФ и не представленное в 2НФ, всегда можно преобразовать в эквивалентную совокупность отношений, представленных в 2НФ.

ПОСТ (КПР, КТ, КПТ, КОЛ)

ПРОИЗВ (КПР, ГПР)

ПОТР (КПТ, ГПТ, РТ)

Таблица 1.6. ПОСТ КПР КТ КПТ КОЛ ПР1 Т1 ІТГ1 100 ПР1 ТІ ПТ2 200 ПР1 Т2 ПТЗ 150 ПР2 ТЗ ПТ2 100 ПР2 ТЗ ПТЗ 50 ПРЗ Т4 ПТ1 200 ПРЗ Т4 ПТ2 500 ПРЗ Т4 ПТЗ 300 Таблица 1.7. ПРОИЗВ

КПР ГПР ПР1 Минск ПР2 Н. Новгород ПРЗ Тольятти Таблица 1.8. ПОТР

КПТ ГПТ РТ ПТ1 Минск 30 ПТ2 Москва 50 ПТЗ Москва 40 ПТ4 Киев 30 ПТ5 С.-Петербург 40 Преобразованная структура и полученные три таблицы разрешают все проблемы, связанные с операциями запоминания: Включение, Удаление и Обновление. Действительно, можно включить нового потребителя в ПОТР, даже если ему не поставляется товар. Можно удалить информацию о поставке товара из ПОСТ, не удаляя при этом информацию о потребителе. И, наконец, значение ГПТ появляется в ПОТР только один раз.

Сравнивая схемы на рис. 1.6 и рис. 1.7, .можно видеть, что результатом нашего преобразования структуры явилось устранение неполной функциональной зависимости и это разрешило все проблемы с операциями запоминания. КПР > ГПР (б) ГПТ

КПТ

РТ (в)

(а) Рис. 1.7. Функциональные зависимости в отношениях ПОСТ (а), ПРОИЗВ (б) и ПОТР (в)

Отношения ПОСТ, ПРОИЗВ и ПОТР находятся в 2НФ, первичными ключами для которых соответственно являются: КПР, КТ, КПТ; КПР и КПТ.

Из полученных трех отношений два отношения ПОСТ и ПРОИЗВ вполне удовлетворяют нас, поскольку значение последнего ключа (реквизита) полностью зависит от значений впереди стоящих полей, т.е. ключей. Что касается отношения ПОТР, то зависимость РТ от КПТ, хотя и функционально, все же являются транзитивной:

КПТ-»ГПТ->РТ

Эта транзитивность приводит к трудностям выполнения операций запоминания, аналогичным вышерассмотренным.

Включение.

Удаление. При исключении некоторого города мы потеряем как информацию о потребителе, так и о рейтинге города.

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

Решение перечисленных проблем состоит в преобразовании отношения в 2НФ в отношение в ЗНФ.

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

Процесс преобразования обратим и, следовательно, никакая информация в процессе преобразования не теряется. Однако отношение в ЗНФ может содержать информацию, которую нельзя представить в отношении, находящемся в 2НФ.

В нашем примере преобразование отношения ПОТР (КПТ, ГПТ, РТ), находящегося в 2НФ, в отношение, находящееся в ЗНФ, состоит в замене этого отношения двумя отношениями (проекциями) со схемами ПОТРГ(КПТ, ГПТ) и ПОТРР (ГПТ, РТ) (рис. 1.8).

I КПТ |—»| гпт| | гпт|—»[ РТ |

(а) (б)

Рис. 1.8. Функциональные зависимости в отношениях ПОТРГ (а) и ПОТРР (б)

Отношения, соответствующие этим схемам, представлены в табл. 1.9 и табл. 1.10.

Таблица 1.9.ПОТРГ КПТ ГПТ ПТ1 Минск ПТ2 Москва ПТЗ Москва ПТ4 Киев ІТГ5 С.-Петербург Таблицаі.10. ПОТРР

ГПТ РТ Минск 30 Москва 50 Киев 30 С.-Петербург 40 Отношение ПОТРГ и ПОТРР находится в ЗНФ, а отношение ПОТР - нет. Первичными ключами этих отношений являются соответственно КПТ и ГПТ.

Проблемы, связанные с вышеуказанными операциями запоминания, исчезли.

В результате вышепроведенных преобразований исходного ненормализованного отношения ПОСТАВ мы получили четыре нормализованных отношения как минимум в ЗНФ: ПОСТ, ПРОИЗВ, ПОТРГ и ПОТРР.

1.5.2.

Процесс построения схемы БД заключается в разложении схемы отношения R, не находящейся в ЗНФ, относительно множества F- зависимостей F. Это означает разбиение схемы отношения R на две схемы отношений R} и R2 (возможно пересекающиеся) таким образом, чтобы любое отношение г со схемой R, удовлетворяющее F, разлагалось без потерь на Я, и R2. Другими словами тгд, (г) ВД-Яд (г).

Возможно потребуется повторить процесс разложения отношений Rx и

R2, если одно из них не окажется в ЗНФ. Процесс декомпозиции продолжается до тех пор, пока все полученные отношения не окажутся в ЗНФ относительно F. Предположим, что существует транзитивная зависимость от ключа в R. Имеются ключ К сД , множество Y ей и непервичный атрибут А в R такие, что К -> F , Y К , Y А относительно F и A g KY . Пусть RX=R-A и R2=YA . Если для нашей схемы отношения имеются выделенные ключи, скажем R = (S, К), то пусть {К} {У} - множества выделенных ключей для Я, и R2 соответственно. Не исключено, что какой-нибудь выделенный ключ К из {?} содержит А. В этом случае К является суперключом для R. Пусть К' = К-А . Если К' остается суперключом для R, то А не может быть частью никакого ключа для R. Подставим К' вместо К в {?}. Таким образом, одну транзитивную зависимость удалили.

Если остались какие-нибудь транзитивные зависимости в Rx или R 2, то декомпозицию можно повторить. Процесс декомпозиции схемы не бесконечен, поскольку получаемые на каждом шаге схемы отношений содержат все меньшее количество атрибутов и, наконец, два атрибута не вызывают транзитивной зависимости.

Процесс декомпозиции можно ускорить, проверяя наличие каких-либо непервичных атрибутов в R - (KY), зависящих от Y. При наличии таких атрибутов они также зависят от К и их можно одновременно удалить.