- •Оглавление
- •1. Введение. Представление данных в памяти компьютера 3
- •2. Модели представления данных 43
- •3. Проектирование реляционных бд 83
- •4 Реляционная алгебра 114
- •5. Case – технологии 127
- •6. Организация доступа прикладной программы 178
- •1. Введение. Представление данных в памяти компьютера
- •1.1 Предмет дисциплины и ее задачи
- •1.2 Основные понятия
- •1.3 Файловые системы, как первый шаг к субд
- •1.4 Структурная схема субд и основные функции
- •1.5 Преимущества и недостатки субд по сравнению с файловыми системами
- •1.6 Организация внешней памяти реляционной субд
- •1.7 Типы и структуры данных
- •1.8 Типы и структуры данных, применяемые в реляционных бд
- •1.9 Типы и структуры данных, применяемые в объектно-реляционных бд
- •1.10 Понятие модели данных
- •2. Модели представления данных
- •2.1 Иерархическая модель данных
- •2.2 Сетевая модель данных
- •2.3 Реляционная модель данных
- •2.4 Свойства отношений. Отличие отношений от таблиц.
- •2.5 Понятие целостности данных
- •2.6 Ограничения реляционных баз данных
- •2.7 Суть постреляционного объектно-ориентированного подхода
- •2.8 Объектно-ориентированные субд и стандарт odmg
- •2.9 Объектно-реляционные субд
- •2.10 No sql бд и субд
- •1. NoSql базы в-основном оупенсорсные и созданы в 21 столетии.
- •6. Распределенные системы
- •3. Проектирование реляционных бд
- •3.1 Этапы разработки базы данных
- •3.2 Критерии оценки качества логической модели данных
- •3.3 Проектирование баз данных на основе нормализации отношений
- •3.4 Первая нормальная форма
- •3.5 Аномалии обновления
- •3.6 Функциональные зависимости
- •3.7 Вторая нормальная форма
- •3.8 Третья нормальная форма
- •3.9 Алгоритм нормализации (приведение к 3nf)
- •3.10 Oltp и olap-системы
- •3.11 Корректность процедуры нормализации. Теорема Хеза
- •3.12 Нормальная Форма Бойса-Кодда (nfbk)
- •3.13 Четвертая Нормальная Форма
- •3.14 Пятая Нормальная Форма
- •3.15 Продолжение алгоритма нормализации (приведение к 5 nf)
- •4 Реляционная алгебра
- •4.1 Операции над отношениями: общие сведения
- •4.2 Синтаксис операторов реляционной алгебры
- •4.3 Оптимизация алгоритмов реализации запросов
- •5. Case – технологии
- •5.1 Общие вопросы проектирования ис, понятие case-технологии
- •5.2 Жизненный цикл по ис
- •5.3 Модели жизненного цикла по
- •5.4 Методология rad
- •5.5 Структурный подход к проектированию ис
- •5.6 Методология функционального моделирования sadt (idef0)
- •5.7 Моделирование потоков данных (методология Гейна-Сарсона)
- •5.8 Методы построения диаграмм «сущность-связь» (erd)
- •5.9 Моделирование данных case-методом Баркера
- •5.10 Методология idef1
- •6. Организация доступа прикладной программы к серверу базы данных
- •6.1 Общие сведения
- •6.2 Использование специализированных библиотек и встраиваемого sql
- •6.4 Odbc – открытый интерфейс к бд на платформе ms Windows
- •6.5 Jdbc - интерфейс к базам данных на платформе Java
- •6.6 Прикладные интерфейсы ole db и ado
- •Литература
3.13 Четвертая Нормальная Форма
Понятие четвертой нормальной формы (4NF) рассмотрим на примере.
Пример 4. Пусть требуется учитывать данные об абитуриентах, поступающих в ВУЗ, и при анализе предметной области были выделены следующие требования:
каждый абитуриент имеет право сдавать экзамены на несколько факультетов одновременно;
каждый факультет имеет свой список сдаваемых предметов;
один и тот же предмет может сдаваться на нескольких факультетах;
абитуриент обязан сдавать все предметы, указанные для факультета, на который он поступает, несмотря на то, что он, может быть, уже сдавал такие же предметы на другом факультете.
Предположим, что нам требуется хранить данные о том, какие предметы должен сдавать каждый абитуриент. Попытаемся хранить данные в одном отношении АБИТУРИЕНТЫ-ФАКУЛЬТЕТЫ-ПРЕДМЕТЫ:
Таблица 23– Отношение АБИТУРИЕНТЫ-ФАКУЛЬТЕТЫ-ПРЕДМЕТЫ
Абитуриент |
Факультет |
Предмет |
Иванов |
Математический |
Математика |
Иванов |
Математический |
Информатика |
Иванов |
Физический |
Математика |
Иванов |
Физический |
Физика |
Петров |
Математический |
Математика |
Петров |
Математический |
Информатика |
В данный момент в отношении хранится информация о том, что абитуриент Иванов поступает на два факультета (математически и физический), а абитуриент Петров – только на математический. Кроме того, можно сделать вывод, что на математическом факультете нужно сдавать математику и информатику, а на физическом – математику и физику.
Кажется, что в отношении имеется аномалия обновления, связанная с тем, что дублируются фамилии абитуриентов, наименования факультетов и наименования предметов. Однако эта аномалия легко устраняется стандартным способом – вынесением всех наименований в отдельные отношения, оставляя в исходном отношении только соответствующие номера:
Таблица 24 – Новое отношение АБИТУРИЕНТЫ-ФАКУЛЬТЕТЫ-ПРЕДМЕТЫ
Номер абитуриента |
Номер факультета |
Номер предмета |
1 |
1 |
1 |
1 |
1 |
2 |
1 |
2 |
1 |
1 |
2 |
3 |
2 |
1 |
1 |
2 |
1 |
2 |
Таблица 25– Отношение АБИТУРИЕНТЫ
Номер абитуриента |
Абитуриент |
1 |
Иванов |
2 |
Петров |
Таблица 26 – Отношение ФАКУЛЬТЕТЫ
Номер Факультета |
Факультет |
1 |
Математический |
2 |
Физический |
Таблица 27– Отношение ПРЕДМЕТЫ
Номер Предмета |
Предмет |
1 |
Математика |
2 |
Информатика |
3 |
Физика |
Теперь каждое наименование встречается только в одном месте. И все-таки как в исходном, так и в модифицированном отношении имеются аномалии обновления, возникающие при попытке вставить или удалить кортежи.
Аномалия вставки. При попытке добавить в отношение АБИТУРИЕНТЫ-ФАКУЛЬТЕТЫ-ПРЕДМЕТЫ новый кортеж, например (Сидоров, Математический, Математика), мы обязаны добавить также и кортеж (Сидоров, Математический, Информатика), т.к. все абитуриенты математического факультета обязаны иметь один и тот же список сдаваемых предметов. Соответственно, при попытке вставить в модифицированное отношении кортеж (3, 1, 1), мы обязаны вставить в него также и кортеж (3, 1, 2).
Аномалия удаления. При попытке удалить кортеж (Иванов, Математический, Математика), мы обязаны удалить также и кортеж (Иванов, Математический, Информатика) по той же причине.
Таким образом, вставка и удаление кортежей не может быть выполнена независимо от других кортежей отношения.
Кроме того, если мы удалим кортеж (Иванов, Физический, Математика), а вместе с ним и кортеж (Иванов, Физический, Физика), то будет потеряна информация о предметах, которые должны сдаваться на физическом факультете.
Декомпозиция отношения АБИТУРИЕНТЫ-ФАКУЛЬТЕТЫ-ПРЕДМЕТЫ для устранения указанных аномалий не может быть выполнена на основе функциональных зависимостей, т.к. это отношение не содержит никаких функциональных зависимостей. Это отношение является полностью ключевым, т.е. ключом отношения является все множество атрибутов. Но ясно, что какая-то взаимосвязь между атрибутами имеется. Эта взаимосвязь описывается понятием многозначной зависимости.
Пусть − отношение, и − некоторые из его атрибутов (или непересекающиеся множества атрибутов).
Тогда атрибуты (множества атрибутов) и многозначно зависят от (обозначается ), тогда и только тогда, когда из того, что в отношении содержатся кортежи и следует, что в отношении содержится также и кортеж .
Меняя местами кортежи и в определении многозначной зависимости, получим, что в отношении должен содержаться также и кортеж . Таким образом, атрибуты и , многозначно зависящие от , ведут себя "симметрично" по отношению к атрибуту .
В отношении АБИТУРИЕНТЫ-ФАКУЛЬТЕТЫ-ПРЕДМЕТЫ имеется многозначная зависимость ФАКУЛЬТЕТ Абитуриент|Предмет.
Словами это можно выразить так – для каждого факультета (для каждого значения из ) каждый поступающий на него абитуриент (значение из ) сдает один и тот же список предметов (набор значений из ), и для каждого факультета (для каждого значения из ) каждый сдаваемый на факультете экзамен (значение из ) сдается одним и тем же списком абитуриентов (набор значений из ). Именно наличие этой зависимости не позволяет независимо вставлять и удалять кортежи. Кортежи обязаны вставляться и удаляться одновременно целыми наборами.
Если в отношении имеется не менее трех атрибутов и есть функциональная зависимость , то есть и многозначная зависимость .
Таким образом, понятие многозначной зависимости является обобщением понятия функциональной зависимости.
Многозначная зависимость называется нетривиальной многозначной зависимостью, если не существует функциональных зависимостей и .
В отношении АБИТУРИЕНТЫ-ФАКУЛЬТЕТЫ-ПРЕДМЕТЫ имеется именно нетривиальная многозначная зависимость Факультет Абитуриент|Предмет. В силу нетривиальности этой зависимости мы не можем воспользоваться теоремой Хеза для декомпозиции отношения.
Теорема Фейджина. Пусть − непересекающиеся множества атрибутов отношения . Декомпозиция отношения на проекции и будет декомпозицией без потерь тогда и только тогда, когда имеется многозначная зависимость .
Если зависимость является тривиальной, т.е. существует одна из функциональных зависимостей или , то получаем теорему Хеза.
Отношение находится в четвертой нормальной форме (4NF) тогда и только тогда, когда отношение находится в НФБК и не содержит нетривиальных многозначных зависимостей.
Отношение АБИТУРИЕНТЫ-ФАКУЛЬТЕТЫ-ПРЕДМЕТЫ находится в NFBK, но не в 4NF. Согласно теореме Фейджина, это отношение можно без потерь декомпозировать на отношения Факультеты-Абитуриенты и Факультеты-Предметы:
Таблица 28 – Отношение Факультеты-Абитуриенты
Факультет |
Абитуриент |
Математический |
Иванов |
Физический |
Иванов |
Математический |
Петров |
Таблица 29 – Отношение "Факультеты-Предметы"
Факультет |
Предмет |
Математический |
Математика |
Математический |
Информатика |
Физический |
Математика |
Физический |
Физика |
В полученных отношениях устранены аномалии вставки и удаления, характерные для отношения АБИТУРИЕНТЫ-ФАКУЛЬТЕТЫ-ПРЕДМЕТЫ.
Заметим, что полученные отношения остались полностью ключевыми, и в них по-прежнему нет функциональных зависимостей.
Отношения с нетривиальными многозначными зависимостями возникают, как правило, в результате естественного соединения двух отношений по общему полю, которое не является ключевым ни в одном из отношений. Фактически это приводит к попытке хранить в одном отношении информацию о двух независимых сущностях.
В качестве еще одного примера можно привести ситуацию, когда сотрудник может иметь много работ и много детей. Хранение информации о работах и детях в одном отношении приводит к возникновению нетривиальной многозначной зависимости Работник Работа|Дети.