- •1. Концепция баз данных
- •1.1. Обоснование концепции баз данных. История вопроса
- •Количество абитуриентов по областям
- •1.2. Архитектура представления информации в концепции бд
- •Внешние представления
- •Файл 1
- •Общие сведения о студенте
- •Сведения об учебе
- •Сведения о неуспевающих студентах (количество)
- •1.3. Понятия схемы и подсхемы и их использование в субд
- •2. Информационная система сферы управления - основная область использования бд
- •3. Модели данных
- •3.1. Понятия модели и структуры данных
- •3.2. Линейная модель данных
- •3.3. Иерархическая структура (модель) данных
- •Студент
- •Семестр
- •3.4. Сетевая структура (модель) данных
- •Итоговая аттестация
- •Семестр
- •Студент
- •Студент1
- •Студент2
- •3.5. Реляционная модель данных
- •3.5.1. История применения реляционной модели данных
- •3.5.2. Основные понятия реляционной модели данных
- •3.5.3. Ключ отношения
- •3.5.4. Нормализация отношений
- •Студент
- •Студент
- •Студент
- •Общежите
- •3.5.5. Операции реляционной алгебры
- •Студент
- •Студенто
- •Нестудент
- •Встречи
- •Делитель
- •Студент
- •Студент
- •Студент
- •Семестр
- •3.5.6. Языки обработки реляционных бд
- •Студент
- •Аудитория
- •Делитель
- •Преподаватель
- •Студент
- •Студент
- •Итоговая аттестация
- •4. Процесс проектирования бд
- •4.1. Построение концептуальной информационной модели ПрО
- •4.1.1. Основные подходы для концептуального моделирования
- •4.1.1.1. Декомпозиционный подход
- •4.1.1.2. Интеграционный подход
- •1.1. Идентификация информационных потребностей пользователей предполагает:
- •1.2. Представление выявленных форм отображения информационных потребностей пользователей в виде исходных отношений предусматривает выполнение следующих действий:
- •1.2.1. Рекомендации по выявлению атрибутов
- •1.2.2. Определение вторичных атрибутов
- •2. Уточнение множества исходных отношений состоит из:
- •3. Связывание отношений и простых структур в кимпо
- •4.1.2. Модели, используемые в концептуальном проектировании
- •4.2. Выбор субд
- •4.3. Проектирование физической структуры бд
- •4.4. Case-средства, используемые при проектировании бд
- •4.5. Пример проектирования бд
Код
Ф.И.О.
Дата
Адрес
студента
студента
рождения
общежитияСтудент
Общежите
Ф.И.О. коменданта общежития
Рис. 3.25. Результат нормализации отношения рис. 3.24.
Нормальная форма Бойса-Кодда (НФБК)
Адрес
общежития
В результате нормализации по ЗНФ (нормальная форма) имеем следующее отношение Экзаменационная ведомость (рис. 3.26).
Номер
Номер
Дисциплина
Оцен
Преподаватель
зачетки
семестра
ка
8Г6101
1
Матанализ
5
Иванов
И.И.
8Г6102
1
Матанализ
4
Волков
В.В.
8Г6101
1
Программирование
5
Петров
П.П.
8Г6101
2
Матанализ
4
Иванов
И.И.
8Г6201
1
БД
иБЗ
5
Сидоров
О.П.
8Г6105
1
БД
иБЗ
5
Сидоров
О.П.
8Г6102
2
Программирование
4
Яковлев
Д.Ю.
Рис.
3.26. Отношение, удовлетворяющее ЗНФ и
не нормализованное по НФБК
В этом отношении однозначно можно сказать, какой преподаватель у какого студента принял экзамен по дисциплине в указанном семестре
и какую оценку при этом студент получил. Однако необходимо отметить, что:
Один преподаватель может принимать экзамен только по одной дисциплине;
По одной и той же дисциплине могут принимать экзамены различные преподаватели.
В результате можно заметить, что существует ФЗ Преподаватель-> Дисциплина. Если удалить какую-нибудь запись из представленного отношения, например последнюю (где студент с зач. книжкой № 8Г6102 во 2-ом семестре сдал экзамен по Программированию на 4 преподавателю Яковлеву Д.Ю.), то будет потеряна информация, что преподаватель Яковлев Д.Ю. принимает экзамен по дисциплине Программирование (это так называемая аномалия удаления). В этом случае есть еще один потенциальный ключ (Номер зачетки, Номер семестра, Преподаватель).
Таким образом, отношение, нормализованное по ЗНФ, может оказаться нежелательным в структуре БД, так как ЗНФ и как предшествующие НФ не учитывают того обстоятельства, что в отношении и может быть несколько потенциальных ключей, которые при этом могут иметь пересечения по составу атрибутов. Этот недостаток устранен в усиленной формулировке требования ЗНФ, данной Р. Бойсом (один из разработчиков SQL) и Э. Коддом (создатель РМД), соответствующая НФ отношения называется нормальной формой Бойса-Кодда (НФБК).
Определение НФБК: Отношение находится в НФБК, если каждый детерминант отношения является потенциальным ключом. Т.е. при нормализации по НФБК отсутствуют ФЗ атрибутов составного ключа от неключевых атрибутов.
В результате нормализации по НФБК исходное отношение декомпозируется на 2 отношения (теорема Хеза): в 1-ом отношении в состав ключа включается детерминант неучтенной выявленной ФЗ (в нашем случае Преподаватель), а зависимая часть этой ФЗ (в нашем случае Дисциплина) из ключа исходного отношения исключается и вместе с детерминантом составляет 2-ое отношение, в котором ключом и становится детерминант ФЗ. Представленное выше отношение в результате нормализации по НФБК декомпозируется на следующие отношения, представленные на рис. 3.27.
Номер |
Номер |
Преподаватель |
Оценка |
зачетки |
семестра |
|
|
8Г6101 |
1 |
Иванов И.И. |
5 |
8Г6102 |
1 |
Волков В.В. |
4 |
8Г6101 |
1 |
Петров П.П. |
5 |
8Г6101 |
2 |
Иванов И.И. |
4 |
8Г6201 |
1 |
Сидоров О.П. |
5 |
8Г6105 |
1 |
Сидоров О.П. |
5 |
8Г6102 |
2 |
Яковлев Д.Ю. |
4 |
Преподаватель
Дисциплина
Иванов
И.И.
Матанализ
Волков
В.В.
Матанализ
Петров
П.П.
Программирование
Сидоров
О.П.
БДиБЗ
Яковлев
Д.Ю.
Программирование
Рис.
3.27. Отношение, нормализованное по НФБК
НФБК является более сильным и независимым от ЗНФ, так как не требует удовлетворения нормализации по другим НФ (при этом должны быть выявлены все ФЗ отношения, детерминанты которых входят в состав ключа), а также не используется понятие транзитивной зависимости.
Четвертая нормальная форма (4НФ)
Предположим, необходимо хранить информацию о приемной компании вуза, а точнее, какой абитуриент на какой факультет подал заявление и какие предметы ему при этом необходимо сдавать (рис. 3.28).
При этом необходимо учитывать, что: —1 один абитуриент имеет право подавать заявление на несколько факультетов одновременно; —1 каждый факультет имеет свой список сдаваемых предметов. —1 один и тот же предмет может сдаваться на нескольких факультетах. —1 абитуриент обязан сдавать все предметы, указанные для факультета, на который он поступает, несмотря на то, что он, может быть, уже сдавал такие же предметы на другом факультете.
Код
абитуриента
Факультет
Предмет
1001
АВТФ
Математика
1001
АВТФ
Физика
1001
ИЭФ
Математика
1001
ИЭФ
Обществознание
1002
АВТФ
Математика
1002
АВТФ
Физика
1003
ИГНД
Математика
1003
ИГНД
Русский
язык
Рис.
3.28. Отношение, удовлетворяющее по НФБК
и не нормализованное по 4НФ
Все атрибуты этого отношения взаимно независимы и в совокупности составляют единственный первичный ключ. Отношение находится в НФБК.
Однако, при использовании такой структуры может возникнуть 2 нежелательные ситуации. Во-первых, при попытке добавить в это отношение новую запись, например (1004, ИЭФ, Математика), мы обязаны добавить также и записи (1004, ИЭФ, Обществознание), так как все абитуриенты ИЭФ обязаны иметь один и тот же список сдаваемых предметов. Во-вторых, при попытке удалить запись (1004, ИЭФ, Математика), мы обязаны удалить также и кортеж (1004, ИЭФ, Обществознание) по той же самой причине. Кроме того, если мы удалим кортеж (1003, ИГНД, Математика), а вместе с ним и кортеж (1003, ИГНД, Русский язык), то будет потеряна информация о предметах, которые должны сдаваться на ИГНД. Таким образом, вставка и удаление кортежей не может быть выполнена независимо от других кортежей отношения.
Декомпозиция этого отношения для устранения указанных ситуаций не может быть выполнена на основе ФЗ, так как это отношение не содержит никаких ФЗ. Это отношение является полностью ключевым, но можно понять, что какая-то взаимосвязь между атрибутами имеется. Эта взаимосвязь описывается понятием многозначной зависимости.
Для каждого факультета (для каждого значения из X) каждый поступающий на него абитуриент (значение из Y) сдает один и тот же список предметов (набор значений из Z), и для каждого факультета (для каждого значения из X) каждый сдаваемый на факультете экзамен (значение из Z) сдается одним и тем же списком абитуриентов (набор значений из Y). В отношении "Абитуриент-Факультет-Предмет" имеется многозначная зависимость Факультет->->Абитуриент|Предмет (Х—>—> Y\Z). Эта многозначная зависимость является нетривиальной, так как не существует ФЗ Х—> Y и X->Z. Именно наличие этой зависимости не позволяет независимо вставлять и удалять кортежи, кортежи обязаны вставляться и удаляться одновременно целыми наборами.
Для разрешения этой аномалии, избавления многозначной зависимости, исходное отношение необходимо декомпозировать следующим образом (теорема Фейджина): если имеется набор непересекающихся атрибутов (X,Y,Z) отношения R и существует многозначная зависимость X->->Y\Z, то декомпозиция отношения R выполняется на проекции R} =R[X, Y] и R2=R[X,ZJ.
Определение 4НФ: Отношение находится в 4НФ тогда и только тогда, когда отношение находится в НФБК и не содержит нетривиальных многозначных зависимостей.
Приведенное отношение "Абитуриент-Факультет-Предмет" находится в НФБК, но не в 4 НФ. Для того чтобы отношение было нормализовано по 4НФ, необходимо убрать из него многозначную зависимость, для чего декомпозируем исходное отношение на следующие отношения, представленные на рис. 3.29.
В полученных отношениях устранены аномалии вставки и удаления, характерные для отношения "Абитуриенты-Факультеты- Предметы". Заметим, что полученные отношения остались полностью ключевыми, и в них по-прежнему нет ФЗ.
Факультет
Код
абитуриента
АВТФ
1001
ИЭФ
1001
АВТФ
1002
ИГНД
1003
j
Факультет
Предмет
АВТФ
Математика
АВТФ
Физика
ИЭФ
Математика
ИЭФ
Обществознание
ИГНД
Математика
ИГНД
Русский
язык
Рис.
3.29. Отношение, нормализованное по 4НФ
Отношения с нетривиальными многозначными зависимостями возникают, как правило, в результате естественного соединения двух отношений по общему атрибуту. Фактически это приводит к попытке хранить в одном отношении информацию о двух независимых, разных сущностях. В качестве еще одного примера можно привести ситуацию, когда в одном отношении храниться информация о том, что студент изучает несколько дисциплин и посещает несколько спортивных секций, что приводит к возникновению нетривиальной многозначной зависимости Студент->->Дисциплина|СпортСекции.
Пятая нормальная форма (5НФ)
До сих пор предполагалось, что единственной необходимой или допустимой операцией в процессе нормализации является замена переменной отношения по правилам декомпозиции без потерь точно 2 ее проекциями. Однако существуют отношения, для которых нельзя выполнить декомпозицию без потерь на две проекции, но которые можно подвергнуть декомпозиции без потерь на три или большее количество проекций.
Рассмотрим следующий пример (рис. 3.30).
Преподаватель
Дисциплина
Группа
Иванов
И.И.
Программирование
8551
Петров
П.П.
Матанализ
8551
Петров
П.П.
Матанализ
8552
Сидоров
О.П.
ИС
8552
Сидоров
О.П.
БД
8МЯ61
Яковлев
Д.Ю.
Матанализ
8МЯ61
Рис.
3.30. Отношение, не нормализованное по
5НФ
В этом отношении один преподаватель может читать лекции по нескольким дисциплинам, при этом по каждой дисциплине он может читать лекции для разных групп. Одну дисциплину могут читать несколько преподавателей, но у одной группы по определенной дисциплине читает лекции только один преподаватель.
Представленное отношение находится в 4НФ. Однако при увольнении преподавателя необходимо удалить все записи, в которых указано, по каким дисциплинам и у каких групп он читал лекции.
Если отношение «Х-Y-Z» спроецировать на составные парные атрибуты {Х-Y}, {Y-Z}, {X-Z}, то соединение этих проекций дает исходное отношение. Это означает, что в рассматриваемом отношении существовала зависимость соединения. В результате отношение будет находиться в 5НФ.
Определение 5НФ: Отношения находится в 5НФ, которую иногда иначе называют проекционно-соединительной нормальной формой (ПСНФ), тогда и только тогда, когда каждая нетривиальная зависимость соединения в отношении определяется его потенциальным ключом.
Применим нормализацию по 5НФ для рассматриваемого примера. Разбиваем отношение «Преподаватель-Дисциплина-Группа» на 3 проекции {Преподаватель-Дисциплина} (ПД), {Дисциплина-Группа} (ДГ), {Преподаватель-Группа} (ПГ) (рис. 3.31):
ПД
Преподаватель |
Дисциплина |
Иванов И.И. |
Программирование |
Петров П.П. |
Матанализ |
Сидоров О.П. |
ИС |
Сидоров О.П. |
БД |
Яковлев Д.Ю. |
Матанализ |
ДГ
Дисциплина |
Группа |
Программирование |
8551 |
Матанализ |
8551 |
Матанализ |
8552 |
ИС |
8552 |
БД |
8МЯ61 |
Матанализ |
8МЯ61 |
ПГ
Преподаватель |
Группа |
Иванов И.И. |
8551 |
Петров П.П. |
8551 |
Петров П.П. |
8552 |
Сидоров О.П. |
8552 |
Сидоров О.П. |
8МЯ61 |
Яковлев Д.Ю. |
8МЯ61 |
Рис. 3.31. Проекции исходного отношения для нормализации по 5НФ
Получим попарные соединения полученных 3 приведенных выше проекций, которые будут иметь вид (рис. 3.32):
пд-пг |
||
Преподаватель |
Дисциплина |
Группа |
Иванов И.И. |
Программирование |
8551 |
Петров П.П. |
Матанализ |
8551 |
Петров П.П. |
Матанализ |
8552 |
Сидоров О.П. |
ИС |
8552 |
Сидоров О.П. |
ис |
8МЯ61 |
Сидоров О.П. |
БД |
8МЯ61 |
Сидоров О.П. |
БД |
8552 |
Яковлев Д.Ю. |
Матанализ |
8МЯ61 |
пд-дг |
||
Преподаватель |
Дисциплина |
Группа |
Иванов И.И. |
Программирование |
8551 |
Петров П.П. |
Матанализ |
8551 |
Петров П.П. |
Матанализ |
8552 |
Петров П.П. |
Матанализ |
8МЯ61 |
Сидоров О.П. |
ИС |
8552 |
Сидоров О.П. |
БД |
8МЯ61 |
Яковлев Д.Ю. |
Матанализ |
8551 |
Яковлев Д.Ю. |
Матанализ |
8552 |
Яковлев Д.Ю. |
Матанализ |
8МЯ61 |
ДГ-ПГ |
||
Преподаватель |
Дисциплина |
Группа |
Иванов И.И. |
Программирование |
8551 |
Петров П.П. |
Программирование |
8551 |
Иванов И.И. |
Матанализ |
8551 |
Петров П.П. |
Матанализ |
8551 |
Петров П.П. |
Матанализ |
8552 |
Сидоров О.П. |
Матанализ |
8552 |
Петров П.П. |
ИС |
8552 |
Сидоров О.П. |
ИС |
8552 |
Сидоров О.П. |
БД |
8МЯ61 |
Яковлев Д.Ю. |
БД |
8МЯ61 |
Сидоров О.П. |
Матанализ |
8МЯ61 |
Яковлев Д.Ю. |
Матанализ |
8МЯ61 |
Рис. 3.32. Отношения, полученные в результате соединения проекций исходного отношения
Далее в результате пересечения полученных проекций получаем исходное отношение, представленное на рис. 3.30.
5НФ является последней из известных НФ. Условия ее получения довольны нетривиальны и поэтому она почти не используется на практике. Кроме того, она имеет определенные недостатки: в полученных отношениях на основе проекций исходного отношения содержатся кортежи с ложной информацией (которой нет в исходном отношении), так как были эти отношения были получены в результате соединения проекций. Поэтому для правильной интерпретации необходимо рассматривать совместно все проекции основного отношения. На практике проектирования БД ограничиваются нормализацией по ЗНФ или НФБК.
