- •Введение
- •1. Концепция информационных систем
- •1.1. Информация и данные предметных областей
- •1.2. Структура банка данных
- •1.2.1. База данных
- •1.2.2. Система управления базами данных
- •1.2.3. Словарь данных
- •1.2.4. Администратор базы данных и его функции
- •1.3. Контрольные вопросы
- •2. Инфомационное моделирование предметных областей для баз данных
- •2.1. Отображение явлений реального мира данными
- •2.2. Инфологическое моделирование по
- •2.3. Трехуровневое представление информационных объектов
- •2.4. Структурные элементы для моделирования данных
- •2.5. Ключи бд
- •2.6. Интеграция полей бд в отношения
- •2.7. Требования интеграции полей в отношения
- •2.8. Обобщенная структура модели данных в бнд
- •2.9. Er-модель бд
- •2.10. Формирование связей сущностей
- •Способ 1. Определение связи сущностей введением дополнительной сущности
- •Способ 2. Определение связей сущностей добавлением в тип сущности общих атрибутов
- •2.11. Бинарные отношения сущностей
- •2.12. Формы представления структур данных
- •2.13. Организация систем бд
- •2.14. Средства поддержки бд
- •2.15. Виды моделей данных для бд
- •Иерархическая модель данных
- •Сетевая модель данных
- •Реляционная модель данных
- •Контрольные вопросы
- •3. Системы управления базами данных
- •3.1. Функции и состав универсальной субд
- •3.2. Лингвистическое обеспечение субд
- •3.3. Независимость прикладных программ от данных
- •3.4. Операции над данными
- •Селекция данных
- •Обработка данных
- •Запросы к бд
- •3.5. Схема реализации запроса в БнД
- •Распределенная обработка данных
- •Комбинированная обработка данных
- •3.7. Целостность и ограничения целостности данных
- •3.8. Защита данных в бд
- •Контрольные вопросы
- •4.2.2. Вторичный ключ
- •4.3. Функциональные и многозначные зависимости
- •4.3.1. Функциональные зависимости
- •X y (X влечет y).
- •4.3.2. Аксиомы функциональных зависимостей
- •Контрольные вопросы
- •5. Реляционная алгебра
- •5.1. Операции над отношениями
- •5.2. Оператор "объединение" (union)
- •5.3. Оператор "вычитание" (difference)
- •5.4. Оператор "пересечение" (intersection)
- •5.5. Оператор "проектирование" (proj)
- •5.6. Оператор "выбор" (sel)
- •Комбинированный запрос с операторами proj и sel
- •5.7 Оператор "соединение" (join)
- •Запрос с соединением по одному полю
- •Алгоритм реализации
- •Запрос с соединением по нескольким полям
- •Алгоритм реализации
- •Оператор "соединение по условию"
- •5.8. Оператор "умножение" (product)
- •Запрос с оператором умножения
- •Алгоритм реализации
- •5.9. Оператор "деление" (division)
- •5.10. Оптимизация алгоритмов реализации запросов
- •Контрольные вопросы
- •6. Нормализация реляционных бд
- •6.1. Задачи нормализации Бд
- •6.2. Первая нормальная форма
- •6.3. Декомпозиция реляционных таблиц
- •Проблема дублирования, операторы реляционной алгебры для декомпозиции и объединения таблиц
- •Присоединенные записи
- •Теорема Хита
- •Критерий полной декомпозиции с исключением дублирования
- •6.4. Вторая нормальная форма
- •6.5. Третья нормальная форма
- •6.6. Экстранормализационные формы
- •Нормальная форма Бокса-Кодда
- •Четвертая нормальная форма
- •Пятая нормальная форма
- •6.7. Методические аспекты реализации нормализации
- •Контрольные вопросы
Контрольные вопросы
Что понимается под реляционной алгеброй, ее операторами и операндами?
Приведите характеристику оператора UNION и пример.
Приведите характеристику оператора DIFFERENCE и пример его применения.
Приведите характеристику оператора INTERSECTION и пример его применения.
Приведите характеристику оператора PROJ и пример.
Приведите характеристику оператора SEL и пример.
Приведите характеристику оператора JOIN и пример его применения.
Приведите характеристику оператора PRODUCT и пример его применения.
Приведите характеристику оператора DIVISION и пример.
Каковы цели и критерии оптимизации реализаций алгоритмов запросов?
6. Нормализация реляционных бд
6.1. Задачи нормализации Бд
Нормализацией БД называется процедура декомпозиции или композиции исходных схем отношений проекта БД, назначение ключей для каждого отношения с целью исключения возможных аномалий при манипулировании данными. Правила нормализации разработаны Коддом в 1972 году.
В результате нормализации обеспечивается:
регулярность описаний данных;
возможность присоединения новых полей, записей, связей без изменения существующих подсхем (или внешних моделей) и, соответственно, ПП. Это обычно требует больших дополнительных затрат по сопровождению;
максимальная гибкость при обработке произвольных запросов с рабочих мест пользователей.
Нормализация базируется на представлении данных двухмерными таблицами, составляющими основу реляционных моделей данных. Важно отметить, что любая иерархическая или сетевая модель данных может быть с некоторой избыточностью разложена в совокупность двухмерных таблиц.
Процесс нормализации реализуется поэтапно путем формирования последовательности так называемых нормальных форм (НФ).
6.2. Первая нормальная форма
Первым этапом нормализации является группировка атрибутов, заключающаяся в свертывании данных в двухмерные таблицы (или файлы), и выделении ключевых полей. В результате формируется первая нормальная форма.
Схема отношения R находится в первой нормальной форме (1НФ), когда все входящие в неё атрибуты являются атомарными, т.е. в любом поле содержится только одно значение, и любое ключевое поле не пусто.
Представление БД в 1НФ достаточно для применения языков манипулирования данными (реляционной алгебры, исчисления доменов или кортежей и др.). Однако при этом не исключаются аномалии, возникающие при манипулировании данными. Для их исключения необходима последующая нормализация отношений. Основной операцией для последующей нормализации отношений является их декомпозиция.
6.3. Декомпозиция реляционных таблиц
Проблема дублирования, операторы реляционной алгебры для декомпозиции и объединения таблиц
В БД возможно дублирование информации, т.е. многократноt повторение значений полей. Это нецелесообразно, так как:
перерасходуются ресурсы ЭВМ (память, время обработки);
корректировка данных требует одновременного изменения всех копий.
Одновременное изменение всех копий увеличивает вероятность нарушения целостности данных и кроме того, требует дополнительных временных затрат.
Исключение дублирования возможно проведением полной декомпозиции реляционных таблиц (РТ).
Полной декомпозицией реляционной таблицы R называется ее адекватное представление совокупностью некоторого числа проекций Ri (i = 1,2,...,n), получаемых в результате последовательного применения операции "Проектирование" реляционной алгебры. При полной декомпозиции в результате применения операции "Объединение" должна вновь образоваться исходная реляционная таблица R.
Операция декомпозиции реализуется оператором рroj, выполняющим следующую функцию:
из исходной РТ R оператор рroj выбирает заданные домены и размещает их в новой таблице R1 в задаваемом оператором порядке.
Синтаксис:
R1 = proj a1,...,ar(R),
где r <= n.
Пример.
Из РТ "Разработчики" (см. Рис. 0 .25) выбрать домены ГодРождения, ФИО.
R1 = proj ГодРождения, ФИО(Разработчики)
Результирующая таблица R1 приведена на Рис. 0 .26.
-
№Разработчика
ФИО
Год Рождения
Стаж
R1
Белов А.
1940
21
R2
КрыловГ
1962
17
R3
Фатов Р.
1964
11
R4
Белов А.
1953
21
R5
КрыловГ
1964
10
Рис. 0.25
ГодРождения |
ФИО |
1940 |
Белов А. |
1962 |
Крылов Г. |
1964 |
Фатов Р. |
1953 |
Белов А. |
1964 |
Крылов Г. |
Рис. 0.26
При необходимости получения исходной реляционной таблицы выполняется обратная операция - "Соединение". Это операция реляционной алгебры, которая производит соединение полученных в результате полной декомпозиции проекций (или композицию этих проекций) в первоначальную реляционную тиблицу.
Операция "Соединение" реализуется оператором join, выполняющим следующую функцию:
на основе двух реляционных таблиц R1 и R2, имеющих одно или несколько полей идентичных типов, формируется реляционная таблица R, состоящая из записей, каждая из которых является конкатенацией, т.е. соединением в одну тех записей таблиц R1 и R2, у которых совпадают значения полей всех идентичных типов.
Следовательно, соединение может быть реализовано двумя способами:
по одному полю;
по нескольким полям.
Синтаксис:
R = R1 join R2.
Пример 1.
Соединить таблицы R1 и R2 с одним общим полем.
R1: |
A |
B |
R2: |
B |
С |
Ответ: R: |
A |
B |
C | |
|
d |
3 |
|
3 |
a |
|
d |
3 |
a | |
|
h |
7 |
|
3 |
b |
|
d |
3 |
b | |
|
y |
4 |
|
7 |
a |
|
h |
7 |
a | |
|
|
|
|
9 |
c |
|
Пример 2.
Соединить таблицы R1 и R2 с двумя общими полями
-
R1:
A
B
C
R2:
B
C
D
Ответ: R:
A
B
C
D
d
3
a
3
a
c
d
3
a
c
h
7
b
3
a
d
d
3
a
d
y
4
a
4
a
e
y
4
a
e
g
2
c
Пример 3.
Рассмотрим БД
Поставщики (№КИ, Фирма, Телефон),
приведенную на рис.6.3, при следующих условиях:
любое КИ поставляется не более, чем одной фирмой;
все фирмы разноименны.
-
№КИ
Фирма
Телефон
A4
СИМ
1516512
B17
СИМ
1516512
C1
ВК
2611380
D14
ВК
2611380
D16
ВК
2611380
Рис. 0.27
Из Рис. 0 .27 видно, что в таблице рассматриваемой БД номера телефонов многократно повторяются, т.е. имеется дублирование информации.
Проведем декомпозицию исходной таблицы на две проекции:
R11 = proj №КИ, Фирма (Поставщики)
и
R12 = proj Фирма, Телефон (Поставщики).
Первую проекцию составляют домены №КИ и Фирма исходного файла (Рис. 0 .28,а), а вторую - домены Фирма и Телефон (Рис. 0 .28,б). Поскольку выполнение операции join над этими двумя проекциями восстанавливает исходную таблицу "Поставщики", изображенную на Рис. 0 .27, то декомпозиция является полной.
№КИ |
Фирма |
|
Фирма |
Телефон | |
A4 |
СИМ |
|
СИМ |
1516512 | |
B17 |
СИМ |
|
ВК |
2611380 | |
C1 |
ВК |
|
|
| |
D14 |
ВК |
|
б) | ||
D16 |
ВК |
|
|
-
а)
Рис. 0.28
Анализ полученных таблиц показывает, что в результате декомпозиции удалось полностью исключить дублирование номеров телефонов фирм. Это приводит к тому, что в случае смены, например, номера телефона фирмы ВК достаточно его однократной коррекции в таблице на Рис. 0 .25,б. В исходной же таблице на Рис. 0 .27 требовалась бы коррекция в четырех кортежах. Конечно, рассмотрен иллюстративный пример, и естественно, что в больших БД эффект декомпозиции выражается гораздо существеннее.