Нормализация баз данных. Алгоритм приведения к 3-й нормальной форме с помощью кольцевых зависимостей

Кольцевые зависимости.

Пусть дано - множество функциональных зависимостей . Если содержит формулы с одинаковой левой частью: , то заменим на . То есть содержит формулы с разной левой частью. Разобъём на классы эквивалентности. Класс , то есть

Пусть одному классу эквивалентности. Выполняется . По правилу транзитивности .

Любая правая часть выводима из любой левой.

. - выводима из каждой левой части.

Пусть класс эквивалентности содержит формулы . Изображеним его в виде:

…

Классу сопоставляется формула, называемая кольцевой зависимостью:

.

Опишем теперь алгоритм приведения структуры БД к 3 нормальной форме методом кольцевых зависимостей (метод синтеза).

Дано: схема , - множество функциональных зависимостей, выполняющихся в .

Нужно: построить новую схему - где , - множество ключей схемы .

Требования:

Множество ключевых зависимостей () эквивалентно .

Каждая схема находится в 3НФ.

Число разбиений должно быть минимальным.

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

Пример.

= {ФИО, группа, факультет}

= {ФИО, группа} = {группа, факультет}

Алгоритм:

Множество сокращается до неизбыточного покрытия .

редуцируется путем исключения посторонних атрибутов. Получим .

разбивается на классы эквивалентности: .

Для каждого строится кольцевая зависимость . В итоге получаем К кольцевых зависимостей (столько, сколько классов эквивалентности).

Выписываем структуру БД , где :

, ,

Предложение

Если - кольцевая зависимость, то - находится в 3НФ относительно .

Пример

1 шаг (редуцирование).

а) избавляемся от избыточных формул.

б) редуцируем слева, редуцируем справа.

Получаем:

2 шаг (разбиение на классы эквивалентности).

Строим эквивалентное множество кольцевых зависимостей:

-

множество из 5 кольцевых зависимостей.

где - множества ключей.

12. Метод «Entity-Relationship». Проектирование структуры баз данных с помощью ER-диаграмм. Пример.

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

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

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

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

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

5. Представить каждое свойство как поле в базовой таблице, представляющей сущность, которая непосредственно описывается этим свойством.

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

7. Если в процессе нормализации было произведено разделение каких-либо таблиц, то следует модифицировать инфологическую модель базы данных и повторить перечисленные шаги.

8. Указать ограничения целостности проектируемой базы данных и дать (если это необходимо) краткое описание полученных таблиц и их полей.

Для примера приведем описания таблиц "Блюда" и "Состав":

СОЗДАТЬ ТАБЛИЦУ Блюда *(Стержневая сущность) ПЕРВИЧНЫЙ КЛЮЧ (БЛ) ПОЛЯ (БЛ Целое, Блюдо Текст 60, Вид Текст 7) ОГРАНИЧЕНИЯ (1. Значения поля Блюдо должны быть уникальными; при нарушении вывод сообщения "Такое блюдо уже есть". 2. Значения поля Вид должны принадлежать набору: Закуска, Суп, Горячее, Десерт, Напиток; при нарушении вывод сообщения "Можно лишь Закуска, Суп, Горячее, Десерт, Напиток");СОЗДАТЬ ТАБЛИЦУ Состав *(Связывает Блюда и Продукты) ПЕРВИЧНЫЙ КЛЮЧ (БЛ, ПР) ВНЕШНИЙ КЛЮЧ (БЛ ИЗ Блюда NULL-значения НЕ ДОПУСТИМЫ УДАЛЕНИЕ ИЗ Блюда КАСКАДИРУЕТСЯ ОБНОВЛЕНИЕ Блюда.БЛ КАСКАДИРУЕТСЯ) ВНЕШНИЙ КЛЮЧ (ПР ИЗ Продукты NULL-значения НЕ ДОПУСТИМЫ УДАЛЕНИЕ ИЗ Продукты ОГРАНИЧИВАЕТСЯ ОБНОВЛЕНИЕ Продукты.ПР КАСКАДИРУЕТСЯ) ПОЛЯ (БЛ Целое, ПР Целое, Вес Целое) ОГРАНИЧЕНИЯ (1. Значения полей БЛ и ПР должны принадлежать набору значений из соответствующих полей таблиц Блюда и Продукты; при нарушении вывод сообщения "Такого блюда нет" или "Такого продукта нет". 2. Значение поля Вес должно лежать в пределах от 0.1 до 500 г.);

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

Для наиболее распространенных реляционных баз данных можно предложить язык инфологического моделирования "Таблица-связь", пример использования которого приведен на рис. 4.7. В нем все сущности изображаются одностолбцовыми таблицами с заголовками, состоящими из имени и типа сущности. Строки таблицы – это перечень атрибутов сущности, а те из них, которые составляют первичный ключ, распологаются рядом и обводятся рамкой. Связи между сущностями указываются стрелками, направленными от первичных ключей или их составляющих.

Рис. 4.7. Инфологическая модель базы данных "Питание", построенная с помощью языка "Таблицы-связи"

13. Физическая организация баз данных.

Дата добавления: 2014-01-11