Исследование ациклической модели данных

Тема 6

ЛАБОРАТОРНАЯ РАБОТА № 4

ИССЛЕДОВАНИЕ АЦИКЛИЧЕСКОЙ МОДЕЛИ ДАННЫХ

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

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

В отношении К(А, В,С) имеется многозначная зависимость А ->—» В, если для любого а, являющегося значением реквизита А

iт(ВС)а = i1т(В)а ° iт(С)а,

где iт(В)а - множество значений реквизита В, связанных с заданным значением реквизита а; ° - знак декартова произведения множеств.

Положение реквизитов В и С равноценно, поэтому одновременно справедливо А —.>—> С, т. е. многозначные зависимости всегда встречаются парами.

Отношение R (А, В, С) с многозначной зависимостью А —»—» В содержит избыточную информацию, хотя и несколько другого рода, чем отношение в 1НФ. Оказывается, что отношения R1=R[А, В] и R=R2[А, С] вместе представляют всю информацию из R. Справедливо соотношение R=R1*R2, которое можно считать равноценным определению многозначной зависимости.

Рассмотрим отношение Z(Завод, Изделие, Компл, План), где Компл - название комплектующего изделия для данного Изделия, а План - план выпуска Изделий. Справедлива функциональная зависимость Завод, Изделие —> План и мы имеем следующие отношения в ЗНФ:

Z1 (Завод, Изделие, План),

Z2(Завод, Изделие, Компл).

Отношение Z1 содержит двухреквизитный ключ и в нем не может быть многозначной зависимости (МЗ). В Z2 существует МЗ вида Изделие —>—> Завод (и, следовательно, Изделие —>—> Компл), поскольку каждое изделие комплектуется одним и тем же набором комплектующих изделий, на каком бы заводе оно ни производилось. Отношение Z2 необходимо разделить на два отношения Z11 (Завод, Изделие) и Z12(Изделие, Компл). Вся информация из Z11 содержится в Z1, поэтому окончательный список отношений состоит из Z1 и Z12.

Операция соединения позволяет получить Z2 = Z11*Z12.

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

Для определения понятия «ациклическая схема базы данных» вводится граф соединений на множестве отношений. Если граф можно превратить в дерево с помощью исключения некоторых дуг при сохранении определенного требования, то база данных с отношениями {51,52,..., 5к} является ациклической.

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

Алгоритм проверки структуры БД на ацикличность

Исходные данные - список отношений с указанием реквизитного состава каждого отношения.

Метод - последовательное выполнение указанных ниже ша - 1 гов.

Шаг 1. Если некоторый реквизит встречается только в од-1 ном отношении, то необходимо вычеркнуть данный реквизит из I этого отношения.

Ш а г 2. Если все реквизиты некоторого отношения находятся среди реквизитов другого отношения, то первое отношение вычеркивается из списка.

Шаги 1 и 2 можно применять в любой последовательности.

Если в результате будут вычеркнуты все отношения, то база данных является ациклической. Если будут вычеркнуты не все отношения - база данных циклическая.

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

Рассмотрим простой пример графа соединений (рис. 2.2).

Наличие цикла очевидно. Отношение Т(Служащий, Отдел, Заказчик) может быть вычислено либо как T=R1 * R2, либо в виде:

Т= (R1 * R3)[Служащий, Отдел, Заказчик].

В первом случае будет справедлива функциональная зависимость Служащий —> Отдел, а во втором случае - нет, так как с заказчиками могут работать служащие, не являющиеся сотрудниками каких-то отделов.

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

1. Добавление в базу данных нового отношения с реквизитами, равными объединению весов дуг, образующих цикл. В этом

случае придется допустить существование неопределенных значений в новом отношении.

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

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

Учитывая высокую трудоемкость приведения отношений к ЗНФ при достаточно большом числе реквизитов (в качестве границы назовем 1-14 реквизитов), можно рекомендовать следующие действия при проектировании структуры реляционной БД:

• каждый входной документ привести к ЗНФ и установить первичный ключ в каждом случае;

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

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

ЗАДАНИЯ

Задание 1. Выполните декомпозиции и соединения с отношениями

Z1 (Завод, Изделие, План),

Z2(Завод, Изделие, Компл) средствами СУБД. Значения в отношениях выберите таким образом, чтобы соблюдалась многозначная зависимость Изделие -»—» Компл. Убедитесь, что после декомпозиции избыточность данных сократилась.

Задание 2. Определите первичные ключи в каждом отношении. Установите, является ли база данных в целом ациклической. Если база данных циклическая, то приведите ее к ациклическому виду.

R1 (Служащий, Организация, Должность).

R2(Организация, Расчетный_счет, Адрес).

R3(Служащий, Автомобиль).

R4(Автомобиль, Цена, Регистрационный_номер).

Задание 3. Определите первичные ключи в каждом отношении. Установите, является ли база данных в целом ациклической. Если база данных циклическая, то приведите ее к ациклическому виду.

R1 (Деталь, Станок).

R2(Деталь, Производитель).

R3(Производитель, Станок, Количество).

R4(Станок, Вес, Год_выпуска).

Задание 4. Определите первичные ключи в каждом отношении. Установите, является ли база данных в целом ациклической. Если база данных циклическая, то приведите ее к ациклическому виду.

R1(ФИО, Подразделение).

R2(ФИО, Должность).

RЗ(Подразделение, Должность, Зарплата).

R4(Должность, Вид_работы).

R5(Подразделение, Номер).

Задание 5. Определите первичные ключи в каждом отношении. Установите, является ли база данных в целом ациклической. Если база данных циклическая, то приведите ее к ациклическому виду.

R1 (Товар, Поставщик).

R2(Поставщик, Склад).

RЗ(Товар, Магазин).

R4(Магазин, Склад, Адрес_магазина).

Задание 6. Определите первичные ключи в каждом отношении. Установите, является ли база данных в целом ациклической. Если база данных циклическая, то приведите ее к ациклическому виду.

R1 (СУБД, Тип_подключения, Размер).

R2(Тип_подключения, Сетевой_протокол, Клиент).

R 3 (СУБД, Фирма, Срок_использования).

R4(Фирма, Клиент, Срок_контракта).

R5(Клиент, Телефон).

Задание 7. Определите первичные ключи в каждом отношении. Установите, является ли база данных в целом ациклической. Если база данных циклическая, то приведите ее к ациклическому виду.

R1 (Статья, Автор, Тема).

R2(Журнал, Тема).

R3(Раздел, Количество_статей, Количество_авторов).

R4(Автор, Должность).

Задание 8. Определите первичные ключи в каждом отношении. Установите, является ли база данных в целом ациклической. Если база данных циклическая, то приведите ее к ациклическому виду.

R1 (Студент, Секция, День_посещения).

R2(Секция, Вид_спорта, Преподаватель).

R3(Студент, Группа, Дисциплина).

R4(Дисциплина, Преподаватель).

Задание 9. Определите первичные ключи в каждом отношении. Установите, является ли база данных в целом ациклической. Если база данных циклическая, то приведите ее к ациклическому виду.

R1 (Кинотеатр, Фильм).

R2(Кинотеатр, Сеанс).

RЗ(Фильм, Сеанс, Стоимость_билета).

R4(Сеанс, Время).

R5(Фильм, Продолжительность).

Задание 10. Определите первичные ключи в каждом отношении. Установите, является ли база данных в целом ациклической. Если база данных циклическая, то приведите ее к ациклическому виду.

R1 (Кафедра, Студент, Специализация).

R2(Кафедра, Преподаватель).

RЗ(Студент, Группа, Успеваемость).

R4(Преподаватель, Телефон).

R5(Студент, Дисциплина, Преподаватель).

Задание 11. Определите первичные ключи в каждом отношении. Установите, является ли база данных в целом ациклической. Если база данных циклическая, то приведите ее к ациклическому виду.

R1 (Программист, Страна, Возраст).

R2(Страна, Язык).

RЗ(Программист, Проект, Страна).

R4(Проект, Язык_программирования).