Capp (ComputerAided Process Planning) Автоматизированное технологическая подготовка производства (планирование технологических процессов)

• Название: Capp (ComputerAided Process Planning) Автоматизированное технологическая подготовка производства (планирование технологических процессов)
• Дата: 19.10.2021
• Размер: 1.81 Mb.
• Имя файла: CAPP.docx
• Тип: Задача; #251303
• страница: 8 из 11

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

Пример отношения в НФБК: ВыдачаВозврат (Код книги, Код читателя, Дата выдачи, Дата возврата).

Функциональные зависимости, имеющие место в данном отношении:

 Код книги Код книги

Дата выдачи Дата возврата

Код читателя Код читателя

Дата возврата Дата выдачи

Функциональные зависимости определены из следующих соображений: любая книга берется (соответственно возвращается) не один раз и разными читателями (т.е. по любому атрибуту данного отношения нельзя однозначно определить никакой другой атрибут); любой читатель может взять одну книгу дважды (т.е. по коду книги и по коду читателя нельзя однозначно определить дату выдачи книги); в один день читатель может взять (соответственно отдать) несколько книг (т.е. по коду читателя и дате выдачи (дате возврата) книги нельзя однозначно определить код книги). Таким образом, имеем два детерминанта, составные атрибуты: Код книги, Дата выдачи и Код книги, Дата возврата и они же являются возможными ключами отношения.

Может оказаться так, что отношение в 3НФ нельзя будет привести к НФБК без потери зависимостей между атрибутами этого отношения.

Обратимся, например, к отношению ГАИ (город, адрес, индекс), которое не находится в НФБК, так как имеет место зависимость индекс ® город.

Это отношение можно разбить на отношения: ГА (город, адрес) и АИ (адрес, индекс), но тогда зависимость индекс ® город будет утеряна.

Определение второй разновидности четвертой нормальной формы (4НФ): отношение r находится в 4НФ тогда и только тогда, когда при существовании многозначной зависимости в r атрибута Y от атрибута X, все остальные атрибуты r функционально зависят от Х.

Атрибут Х многозначно определяет атрибут Y, если с каждым значением x может использоваться значение y из фиксированного подмножества значений Y. Обозначается: X ↠ Y.

Небольшое отступление: одни авторы считают, что при нормализации отношений вполне можно ограничиться 3НФ; другие говорят о необходимости приведения отношений к 4НФ, как к лучшей НФ, кроме того, существуют НФ высшего порядка.

В качестве примера рассмотрим отношение КПУ (Курс, Преподаватель, Учебник), где Курс – наименование курса, Преподаватель – фамилия преподавателя, Учебник – название учебника. Пусть данному курсу может соответствовать любое число преподавателей и любое количество учебников, и пусть преподаватели и учебники не зависят друг от друга.

Экземпляр отношения КПУ, касающийся только одного курса:

 

Курс	Преподаватель	Учебник
Физика	Иванов	Основы механики
Физика	Иванов	Законы оптики
Физика	Петров	Основы механики
Физика	Петров	Законы оптики

 

Атрибут Курс многозначно определяет атрибут Преподаватель и имеется многозначная зависимость атрибута Учебник от атрибута Курс:

Курс ↠ Преподаватель;

Курс ↠ Учебник.

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

Для устранения недостатков отношения, представленного в 3НФ, выполняют разложение по многозначным зависимостям данного отношения, т. е. отношение r (A, B, C), где A ↠ B и A ↠ C, разбивают на два: r1 (A, B) и r2 (A, C).

Для нашего примера: КП (Курс, Преподаватель), КУ (Курс, Учебник). Каждое из полученных отношений находится в четвертой нормальной форме.

Приведем примеры выявления нормальной формы отношений.

Дана диаграмма функциональных зависимостей для некоторого отношения (варианты а, б):

а) б)



 

 

Необходимо определить, в какой нормальной форме находится данное отношение.

Для варианта а: имеем две функциональные зависимости: А ® С и А, В ® D, т.е. ключом отношения является составной атрибут А, В. Будем считать, что каждый из имеющихся атрибутов имеет атомарное значение. Тогда рассматриваемое отношение находится в 1НФ. Отношение не находится во 2НФ, в силу имеющейся функциональной зависимости неосновного атрибута С от атрибута А – части ключа.

Для варианта б: имеем три функциональные зависимости: D ® A, D ® B и A, B ® C, т.е. ключом отношения является атрибут D. Будем считать, что каждый из имеющихся атрибутов имеет атомарное значение. Тогда рассматриваемое отношение находится в 1НФ. Отношение находится во 2НФ, т.к. все неосновные атрибуты: A, B и С функционально полно зависят от ключа отношения. Отношение не находится в 3НФ, так как неосновной атрибут С транзитивно зависит от ключа D: D ® A, B ® C.

Общий подход к декомпозиции

<9101112131415>

 

 

Этапы проектирования:

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

2) Определяются все функциональные зависимости между атрибутами данного отношения.

3) Определяется, находится ли отношение в нормальной форме Бойса - Кодда. Если да, то проектирование завершается, если нет, то осуществляется декомпозиция, т.е. разбиение отношения.

4) Шаги 2 и 3 повторяются для каждого нового отношения, полученного в результате декомпозиции. Проектирование завершается, когда все отношения будут находиться в НФБК.

Декомпозиция может осуществляться следующим образом:

· Пусть отношение r(A, B, C, D, E,…) не находится в НФБК. Определяется F-зависимость, являющаяся причиной того, что отношение r не находится в НФБК, например, С ® D (атрибут С является детерминантом, но не является возможным ключом).

· Создаются два новых отношения: r1(A, B, С, Е,…) и r2(C, D), где зависимостная часть F-зависимости – атрибут D был выделен из отношения r и опущен при формировании отношения r1, F–зависимость С ® D была полностью использована при формировании отношения r2. Отношения r1 и r2 являются проекциями отношения r.

Такая декомпозиция называется декомпозицией без потерь при естественном соединении (т. е. естественное соединение r1 и r2 даст исходное отношение r).

Например, обратимся к отношению Консультант (№ студента, ФИО студента, № комнаты, № телефона, № курса, Семестр, Оценка), которое является универсальным отношением.

F-зависимости отношения Консультант (были определены нами ранее):

№ студента ® ФИО студента;

№ студента ® № комнаты;

№ студента ® № телефона;

№ комнаты ® № телефона;

№ телефона ® № комнаты;

№ студента, № курса, Семестр ® Оценка.

Возможным и единственным ключом отношения является составной атрибут: № студента, № курса, Семестр. Имеются три детерминанта, не являющиеся возможными ключами: № студента, № комнаты, № телефона. Необходимо выбрать F-зависимость для проведения первой проекции. Для этого отыскивают «цепочку» F-зависимостей вида: А ® В ® С и используют для проекции крайнюю правую зависимость. В нашем случае такими цепочками являются:

№ студента ® № комнаты ® № телефона;

№ студента ® № телефона ® № комнаты.

а) Выбрав F-зависимость № комнаты ® № телефона, получим следующие отношения:

r1(№ студента, № курса, Семестр, Оценка, ФИО студента, № комнаты);

r2(№ комнаты, № телефона).

Отношение r2 находится в НФБК (все его детерминанты являются возможными ключами) и не нуждается больше в декомпозиции.

Отношение r1 не находится в НФБК (детерминант № студента не является возможным ключом) и поэтому разбивается далее.

Детерминант № студента имеет два зависимых атрибута:

№ студента ® ФИО студента

№ студента ® № комнаты

Эти две зависимости в r1 можно рассматривать как одну с составной правой частью:

№ студента ® ФИО студента, № комнаты.

Выбирая данную F-зависимость для проведения второй проекции, получим следующие отношения:

r3(№ студента, ФИО студента, № комнаты);

r4(№ студента, № курса, Семестр, Оценка).

Данные отношения находятся в НФБК. Проектирование завершено: отношения r2, r3, r4 могут быть использованы при формировании БД для консультанта.

б) Выбрав для проведения первой проекции F-зависимость № телефона ® № комнаты, получим следующие отношения:

r1(№ студента, № курса, Семестр, ФИО студента, № телефона, Оценка);

r2(№ телефона, № комнаты).

Отношение r2 находится в НФБК, r1 – нет. Разбиваем r1 на следующие два отношения:

r3(№ студента, ФИО студента, № телефона);

r4(№ студента, № курса, Семестр, Оценка).

Отношения r3 и r4 находятся в НФБК, проектирование завершено.

Таким образом, имеем два различных решения. Какое из двух решений является «лучшим», определяется выбором проектировщика и зависит до некоторой степени от того, как планируется использовать БД.

 

6.2. Некоторые комментарии к декомпозиционному

методу проектирования

 

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

Пусть имеется отношение r(A, B, C) и F-зависимости: А ® В, В ® С.

Выберем для проведения проекции F-зависимость А ® В.

Получим отношения: r1(A, B) и R2(A, С). Оба эти отношения находятся в НФБК, но F-зависимость В ® С утеряна (ни отношение r1, ни r2 автономно не содержат атрибуты, присутствующие в данной функциональной зависимости). С практической точки зрения это означает то, что нельзя будет утверждать, что некорректные связи между В и С не будут привнесены в БД. При использовании правила цепочки такой ситуации не возникает.

Рассмотрим другой случай возможной потери функциональной зависимости при проектировании. Пусть имеется отношение r(A, C, B) и F-зависимости: А ® В, С ® В.

Отношение r не находится в НФБК. Правило цепочки здесь неприложимо по причине их отсутствия. Если же одна из функциональных зависимостей будет выделена обычным способом, то другая будет потеряна:

· при выделении из r зависимости А ® В будут получены отношения: r1(A, B) и r2(A, C) и F-зависимость С ® В будет утеряна;

· при выделении из r зависимости С ® В будут получены отношения: r1(С, B) и r2(A, C) и F-зависимость   А ® В будет утеряна.

Если отношение R разбить на r1(A, B) и r2(C, В), то ни одна из функциональных зависимостей не будет утеряна. Такой путь не соответствует стандартному методу декомпозиции. В его основе (в некоторых литературных источниках данный метод называется методом синтеза) лежит следующее утверждение: все F-зависимости с одинаковыми детерминантами необходимо выделять в группы и каждой группе отводить свое собственное отношение (что мы и сделали).

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

Избыточных зависимостей

<10111213141516>

 

Использование аксиомы пополнения



 

 

Использование аксиомы аддитивности

Если:



 

 

то:

 



 

Использование аксиомы проективности

Если:



 

то:



 

Использование аксиомы транзитивности

Исходный набор F-зависимостей:

 



 

 

исключаем A ® E, так как A ® C и C ® E:



 

исключаем B ® E, так как B ® C и C ® E:



 

исключаем A ® С так как A ® B и B ® C:



 

 

Получили неизбыточный набор функциональных зависимостей. Теперь, применив метод декомпозиции, можно получить набор НФБК – отношений.

Имеем отношение r (A, B, C, E).

Выделяя в отдельное отношение F-зависимость C ® E, разбиваем отношение r на r1 (C, E) и r2 (A, B, C).

Отношение r1 находится в НФБК, r2 – нет. Выделяя в отдельное отношение зависимость B ® C, разбиваем r2 на отношения r3 (B, C) и r4 (A, B). Полученные отношения находятся в НФБК.

 

 

Использование аксиомы псевдотранзитивности



 

Имеем F-зависимости: Преподаватель ® Курс; Время, Курс ® Аудитория; Преподаватель, Время ® Аудитория. Зависимость Преподаватель, Время ® Аудитория - избыточная псевдотранзитивная зависимость, ее можно удалить.

 

Использование нескольких аксиом

Исходный набор F-зависимостей:



 

Имеем: B ® D; B, C ® D. По аксиоме пополнения можно удалить B,C ® D. Получаем:



 

Зависимость A ® B, C заменяем на A ® B и A ® C (аксиома проективности):

 



 

По аксиоме транзитивности удаляем A ® D и A ® C:



 

В полученном наборе F-зависимостей нет больше избыточных зависимостей – преобразование закончено.

Следует обратить внимание на такой момент: избыточные F-зависимости необходимо удалять по одной, каждый раз заново анализируя получаемый набор функциональных зависимостей.

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

· удалить A ® D (аксиома транзитивности);

· удалить B, C ® D (аксиома пополнения);

· заменить A ® B, C на A ® B и A ® C (аксиома проективности);

· удалить A ® C.

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

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

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

Минимальное покрытие не всегда является уникальным.

Обратимся к БД «Консультант».

Исходный набор F-зависимостей:



 

 

По аксиоме транзитивности можно удалить как избыточную зависимость:

а) № студента ® № телефона;

б) № студента ® № комнаты.

В результате будут получены два минимальных покрытия (первое – при выполнении пункта а); второе – при выполнении пункта б), использование которых приведет к построению тех же самых двух БД, проектирование которых уже обсуждалось нами.