- •Серия «Учебники и учебные пособия»
- •Э.П. Голенищев
- •И.В. Клименко
- •Рецензент
- •Предисловие
- •Введение
- •Глава 1. ИФОРМАЦИОННЫЕ СИСТЕМЫ НА БАЗАХ ДАННЫХ
- •1.1. Понятие информационной системы, информационное обеспечение
- •1.2. Понятие базы данных
- •1.3. Понятие системы управления базами данных
- •1.3.1. Обобщенная архитектура СУБД
- •1.3.2. Достоинства и недостатки СУБД
- •1.3.3. Архитектура многопользовательских СУБД
- •Технология «клиент/сервер»
- •Таблица 1.1
- •1.4. Понятие независимости данных
- •1.5. Категории пользователей базой данных
- •1.5.1. Общая классификация пользователей БД
- •1.5.2. Администратор базы данных
- •1.5.3. Разделение функций администрирования
- •Таблица 1.2
- •1.6. Средства администрирования баз данных
- •Таблица 1.3
- •Глава 2. ПРОЕКТИРОВАНИЕ БАЗ ДАННЫХ
- •2.1. Жизненный цикл информационной системы
- •2.1. Подходы и этапы проектирования баз данных
- •2.2.1. Цели и подходы к проектированию баз данных
- •2.2.2. Этапы проектирования баз данных
- •2.3. Инфологическое проектирование базы данных
- •Таблица 2.1
- •Пояснение
- •2.3.1. Модель «сущность-связь»
- •2.3.2. Классификация сущностей, расширение ER-модели
- •Рис. 2.15. Пример ловушки разрыва
- •2.4. Логическое проектирование
- •2.4.1. Выбор СУБД
- •2.4.1.1. Метод ранжировки
- •Таблица 2.2
- •Таблица 2.3
- •2.4.1.2. Метод непосредственных оценок
- •2.4.1.3. Метод последовательных предпочтений
- •Таблица 2.4
- •Таблица 2.5
- •2.4.1.4. Оценка результатов экспертного анализа
- •Таблица 2.6
- •Наименование параметра
- •2.4.2. Даталогические модели данных
- •2.4.2.1. Иерархическая модель
- •2.4.2.2. Сетевая модель
- •2.4.2.3. Реляционная модель
- •2.4.2.4. Достоинства и недостатки даталогических моделей
- •2.4.3. Нормализация
- •2.4.3.1. Понятие функциональной зависимости
- •Таблица 2.7
- •2.4.3.2. Аксиомы вывода функциональных зависимостей
- •2.4.3.3. Первая нормальная форма
- •НОМЕР
- •2.4.3.4. Вторая нормальная форма
- •2.4.3.5. Третья нормальная форма
- •2.4.3.6. Нормализация через декомпозицию
- •2.4.3.7. Недостатки нормализации посредством декомпозиции
- •2.4.3.8. Нормальная форма Бойса–Кодда (НФБК)
- •2.4.3.9. Многозначные зависимости
- •Таблица 2.8
- •Таблица 2.9
- •Таблица 2.10
- •2.4.3.10. Аксиомы вывода многозначных зависимостей
- •2.4.3.11. Четвертая нормальная форма
- •2.4.3.12. Зависимости соединения
- •2.4.3.13. Пятая нормальная форма
- •2.4.3.14. Обобщение этапов нормализации
- •Глава 3. ФИЗИЧЕСКАЯ ОРГАНИЗАЦИЯ ДАННЫХ В СУБД
- •3.1. Списковые структуры
- •3.1.1. Последовательное распределение памяти
- •3.1.2. Связанное распределение памяти
- •Рис. 3.4. Пример двунаправленного линейного списка
- •3.2. Модель внешней памяти
- •3.3. Методы поиска и индексирования данных
- •3.3.1. Последовательный поиск
- •Рис. 3.7. Пример организации файла при начальной загрузке
- •3.3.2. Бинарный поиск
- •3.3.3. Индекс - «бинарное дерево»
- •3.3.4. Неплотный индекс
- •3.3.5. Плотный индекс
- •3.3.6. Инвертированный файл
- •Глава 4. МАТЕМАТИЧЕСКИЕ ОСНОВЫ МАНИПУЛИРОВАНИЯ РЕЛЯЦИОННЫМИ ДАННЫМИ
- •4.1. Теоретические языки запросов
- •4.1.1. Реляционная алгебра
- •4.1.2. Реляционное исчисление кортежей
- •4.1.3. Реляционное исчисление доменов
- •4.1.4. Сравнение теоретических языков
- •4.2. Определение реляционной полноты
- •Глава 5. РАСПРЕДЕЛЕННЫЕ БАЗЫ ДАННЫХ И СУБД
- •5.1. Основные определения, классификация распределенных систем
- •5.2. Преимущества и недостатки распределенных СУБД
- •Таблица 5.1
- •5.3. Функции распределенных СУБД
- •5.4. Архитектура распределенных СУБД
- •5.5. Разработка распределенных реляционных баз данных
- •5.5.1. Распределение данных
- •Таблица 5.2
- •5.5.2. Фрагментация
- •5.5.3. Репликация
- •5.5.3.1. Виды репликации
- •5.5.3.2. Функции службы репликации
- •5.5.3.3. Схемы владения данными
- •5.5.3.4. Сохранение целостности транзакций
- •5.5.3.5. Моментальные снимки таблиц
- •5.5.3.6. Триггеры базы данных
- •5.5.3.7. Выявление и разрешение конфликтов
- •5.6. Обеспечение прозрачности
- •5.6.1. Прозрачность распределенности
- •5.6.2. Прозрачность транзакций
- •5.6.3. Прозрачность выполнения
- •5.6.4. Прозрачность использования
- •ЗАКЛЮЧЕНИЕ
- •ПРИЛОЖЕНИЯ
- •Приложение 1. Недостатки файловых систем
- •Приложение 2. Краткая история развития субд
- •Приложение 3. Сравнительная характеристика даталогических моделей
- •Сводная характеристика систем баз данных
- •Приложение 4. Пример мифологического проекта базы данных
- •Приложение 5. Обобщенная методика проектирования реляционных баз данных
- •Приложение 6. Принципы организации компьютерных сетей
- •Отличие ЛВС от систем на основе мини-ЭВМ
- •Таблица П.6.1
- •Приложение 7. Правила распределенных СУБД
- •Независимость от операционной системы
- •Приложение 8. Краткий толковый словарь
- •Содержание
удовлетворять F-зависимости РЕЙС→ГАЛЕРЕЯ. Пусть требуется обновить отношение, указав значение ключа и задавая значения всем остальным атрибутам. Однако если выполнить операцию
ИЗМЕНИТЬ (График; 112, 6 июня, ПИЛОТ=Иванов, ГАЛЕРЕЯ=8),
то отношение перестанет удовлетворять F-зависимости РЕЙС→ГАЛЕРЕЯ. Чтобы избежать нарушения F-зависимости, необходимо после каждого выполнения операции обновления просмотреть полученное отношение и везде (во всех кортежах), где появляется указанный в операторе номер рейса, изменить номер галереи на указанный в операторе. А требовалось всего лишь изменить один кортеж. Кроме того, информация о связи между номером рейса и номером галереи дублируется с рассмотренном отношении, что ведет к избыточности информации.
С точки зрения как обновления, так и устранения избыточности лучше представить ту же информацию в виде базы данных из двух отношений Пилот-График и Галерея-График.
Пилот-График |
РЕЙС |
ДАТА |
ПИЛОТ |
|
112 |
6 июня |
Иванов |
|
112 |
7 июня |
Петров |
|
203 |
9 июня |
Иванов |
Галерея-График |
РЕЙС |
ГАЛЕРЕЯ |
|
112 |
7 |
|
203 |
12 |
При этом сохраняется возможность восстановить первоначальное отношение График из двух новых отношений (см. гл.4). Указанной аномалии обновления больше не существует, так как нужно изменить только один кортеж, чтобы поменять назначение галереи. При этом устраняется и некоторая избыточность данных, так как каждая пара (номер рейса, номер галереи) записывается только однажды.
2.4.3.4. Вторая нормальная форма
Для данной схемы отношения R, атрибута А в Л и множества функциональных зависимостей F на R атрибут А называется первичным в R относительно F, если А содержится в каком-нибудь ключе схемы
R.В противном случае А называется непервичным в R.
Ключи в этом определении не следует путать с выделенными ключами для R, так как последние
могут быть на самом деле суперключами. Кроме того, могут существовать ключи для R, не являющиеся выделенными.
Пример 2.8. Пусть Д(РЕЙС, ДАТА, ПИЛОТ, ГАЛЕРЕЯ) и множество F={РЕЙС ДАТА → ПИЛОТ ГАЛЕРЕЯ, РЕЙС → ГАЛЕРЕЯ}.
Атрибуты РЕЙС и ДАТА являются первичными, ПИЛОТ и ГАЛЕРЕЯ - непервичными. (Допустимо, чтобы один пилот имел два рейса в день, так что ПИЛОТ ДАТА ключом не является.)
Схема отношения R находится во второй нормальной форме (2НФ) относительно множества функциональных зависимостей F, если она находится в первой нормальной форме (1НФ) и каждый непервичный атрибут полностью зависит от каждого ключа для R [10].
Схема базы данных R имеет вторую нормальную форму относительно F, если каждая схема отношения R из R находится в 2НФ относительно F.
Пример 2.9. Пусть R(РЕЙС, ДАТА, ПИЛОТ, ГАЛЕРЕЯ) и множество F={РЕЙС ДАТА → ПИЛОТ ГАЛЕРЕЯ, РЕЙС → ГАЛЕРЕЯ}, R={R}.
Схема не находится в 2НФ, так как ГАЛЕРЕЯ частично зависит от РЕЙС ДАТА. Если положить R={(PEHC, ДАТА, ПИЛОТ); (РЕЙС, ГАЛЕРЕЯ)}, тогда схема будет находиться во второй нормальной форме. РЕЙС теперь является ключом для схемы отношения (РЕЙС, ГАЛЕРЕЯ).
60
2.4.3.5. Третья нормальная форма
Рассмотрим другое отношение График, представленное ниже. Предположим, что это отношение имеет ключ РЕЙС ДЕНЬ и к тому же удовлетворяет функциональным зависимостям КОД-ПИЛОТА → ИМЯ и ИМЯ → КОД-ПИЛОТА.
Если выполнить операцию обновления
ИЗМЕНИТЬ (График; 112, б июня, КОД-ПИЛОТА=31039, ИМЯ=Иванов),
то изменяется функциональная зависимость ИМЯ → КОД-ПИЛОТА. Кроме того, имеется избыточная информация в виде пар КОД-ПИЛОТА, ИМЯ.
Проблема здесь не из-за частичной зависимости непервичного атрибута, хотя решение получается то же самое.
Это отношение можно представить в виде базы данных следующим образом.
Пилот-График |
РЕЙС |
ДАТА |
КОД-ПИЛОТА |
|
112 |
6 июня |
31174 |
|
112 |
7 июня |
30046 |
|
203 |
9 июня |
31174 |
Код |
КОД-ПИЛОТА |
ИМЯ |
|
31174 |
Иванов |
|
30046 |
Петров |
Возможность восстановления первоначального отношения сохраняется.
Перед определением третьей нормальной формы характеризуется транзитивная зависимость атрибутов.
Для данной схемы отношения R, подмножества X множества R, атрибута А в R и множества функциональных зависимостей F атрибут А называется транзитивно зависимым от X в R, если
существует подмножество Y R, такое, что X → Y, Y не определяет функционально X, Y → А относительно F и А ХY [10].
Пример 2.10. Пусть R(РЕЙС, ДАТА, КОД-ПИЛОТА, ИМЯ) и множество F={PEHC ДАТА → КОД-ПИЛОТА ИМЯ, КОД-ПИЛОТА → ИМЯ, ИМЯ → КОД-ПИЛОТА}.
Атрибут ИМЯ является транзитивно зависимым от РЕЙС ДАТА, так как РЕЙС ДАТА® КОДПИЛОТА, КОД-ПИЛОТА не определяет функционально РЕЙС ДАТА и КОД-ПИЛОТА®ИМЯ.
Схема отношения R находится в третьей нормальной форме (ЗНФ) относительно множества функциональных зависимостей F, если она находится в 1НФ и ни один из непервичных атрибутов в R не является транзитивно зависимым от ключа для R [10].
Схема базы данных R находится в третьей нормальной форме относительно F, если каждая схема отношения R в R находится в ЗНФ относительно F.
Пример 2.11. Пусть R и множество F те же, что и в примере 2.10, R=(R).
Схема базы данных R не находится в ЗНФ относительно F, потому что ИМЯ является транзитивно зависимым от РЕЙС ДАТА.
Если R={(PEHC, ДАТА, КОД-ПИЛОТА); (КОД-ПИЛОТА, ИМЯ)}, то R находится в ЗНФ относительно F.
Следует заметить, что любая схема отношения, находящаяся в ЗНФ относительно F, находится в 2НФ относительно F [10].
2.4.3.6. Нормализация через декомпозицию
Всегда можно начать с того, что, взяв некоторую схему отношения R, не находящуюся в ЗНФ
61
относительно множества F-зависимостей F, разложить ее в схему базы данных, имеющую ЗНФ относительно F.
Разложение схемы отношений означает разбиение схемы отношения на пару схем отношений R1 и R2 (возможно, пересекающихся) так, чтобы любое отношение r(R), удовлетворяющее F, разлагалось без потерь на R1 и R2. Возможно, нужно будет повторить процесс декомпозиции отношений R1 и R2, если какое-нибудь из них не окажется в ЗНФ. Декомпозиция продолжается до тех пор, пока все полученные отношения не окажутся в третьей нормальной форме относительно F.
На самом деле процесс декомпозиции схемы не бесконечен. Каждый раз, когда разлагается схема отношения, обе получившиеся в результате схемы становятся меньше, а в схеме отношения, содержащей только два атрибута, не может быть никакой транзитивной зависимости [10].
Пример 2.12. Пусть
R (РЕЙС, ПУНКТ-ОТПРАВЛЕНИЯ, ПУНКТ-НАЗНАЧЕНИЯ, ВРЕМЯ-ВЫЛЕТА, ВРЕМЯПРИБЫТИЯ, ДЛИТЕЛЬНОСТЬ-ПОЛЕТА, ТИП-САМОЛЕТА, I-КЛАСС, II-КЛАСС, КОЛИЧЕСТВО-ПОСАДОЧНЫХ-МЕСТ, ПИТАНИЕ)
где I-КЛАСС и II-КЛАСС – количество посадочных мест в каждом салоне. Пусть множество выделенных ключей
К={РЕЙС, ПУНКТ-ОТПРАВЛЕНИЯ ПУНКТ-НАЗНАЧЕНИЯ ВРЕМЯ-ВЫЛЕТА, ПУНКТОТПРАВЛЕНИЯ ПУНКТ-НАЗНАЧЕНИЯ ВРЕМЯ-ПРИБЫТИЯ}.
Предполагается, что в одно и то же время не может быть двух рейсов с одинаковыми пунктами отправления и назначения. Пусть все выделенные ключи действительно являются ключами, и пусть имеются также следующие F-зависимости в множестве F:
ТИП-САМОЛЕТА→I-КЛАСС II-КЛАСС КОЛИЧЕСТВО-ПОСАДОЧНЫХ-МЕСТ, ВРЕМЯ-ВЫЛЕТА ДЛИТЕЛЬНОСТЬ-ПОЛЕТА→ПИТАНИЕ, ВРЕМЯ-ПРИБЫТИЯ ДЛИТЕЛЬНОСТЬ-ПОЛЕТА→ПИТАНИЕ,
I-КЛАСС II-КЛАСС→КОЛИЧЕСТВО-ПОСАДОЧНЫХ-МЕСТ, I-КЛАСС КОЛИЧЕСТВО-ПОСАДОЧНЫХ-МЕСТ→II-КЛАСС, II-КЛАСС КОЛИЧЕСТВО-ПОСАДОЧНЫХ-МЕСТ→I-КЛАСС.
Казалось бы, ВРЕМЯ-ВЫЛЕТА ВРЕМЯ-ПРИБЫТИЯ→ДЛИТЕЛЬНОСТЬ-ПОЛЕТА также должна быть F-зависимостью, но, из-за того что время прибытия и время отправления указывается местное, ДЛИТЕЛЬНОСТЬ-ПОЛЕТА зависит от часовых поясов, к которым принадлежат соответствующие аэропорты.
Сначала удалим транзитивную зависимость атрибута ПИТАНИЕ от РЕЙСА через ВРЕМЯВЫЛЕТА ДЛИТЕЛЬНОСТЬ-ПОЛЕТА. Получим схему отношения
R1(РЕЙС, ПУНКТ-ОТПРАВЛЕНИЯ, ПУНКТ-НАЗНАЧЕНИЯ, ВРЕМЯ-ПРИБЫТИЯ, ДЛИТЕЛЬНОСТЬ-ПОЛЕТА, ТИП-САМОЛЕТА, I-КЛАСС, II-КЛАСС, КОЛИЧЕСТВО- ПОСАДОЧНЫХ-МЕСТ)
с выделенными ключами
K1={PEHC, ПУНКТ-ОТПРАВЛЕНИЯ ПУНКТ-НАЗНАЧЕНИЯ ВРЕМЯ-ВЫЛЕТА, ПУНКТОТПРАВЛЕНИЯ ПУНКТ-НАЗНАЧЕНИЯ ВРЕМЯ-ПРИБЫТИЯ}
и схему отношения
R2(ВРЕМЯ-ОТПРАВЛЕНИЯ, ДЛИТЕЛЬНОСТЬ-ПОЛЕТА, ПИТАНИЕ)
с выделенным ключом
62
К2={ВРЕМЯ-ОТПРАВЛЕНИЯ ДЛИТЕЛЬНОСТЬ-ПОЛЕТА}.
Схема R2 находится в ЗНФ, а схема R1 – нет, так как I-КЛАСС, II-КЛАСС и КОЛИЧЕСТВО- ПОСАДОЧНЫХ-МЕСТ транзитивно зависят от РЕЙСА через ТИП-САМОЛЕТА. Схема R1 разлагается на схему
R11(РЕЙС, ПУНКТ-ОТПРАВЛЕНИЯ, ПУНКТ-НАЗНАЧЕНИЯ, ВРЕМЯ-ВЫЛЕТА, ВРЕМЯПРИБЫТИЯ, ДЛИТЕЛЬНОСТЬ-ПОЛЕТА, ТИП-САМОЛЕТА)
с выделенными ключами
К11={РЕЙС, ПУНКТ-ОТПРАВЛЕНИЯ ПУНКТ-НАЗНАЧЕНИЯ ВРЕМЯ-ВЫЛЕТА, ПУНКТОТПРАВЛЕНИЯ ПУНКТ-НАЗНАЧЕНИЯ ВРЕМЯ-ПРИБЫТИЯ}
и схему
R12(ТИП-САМОЛЕТА, I-КЛАСС, II-КЛАСС, КОЛИЧЕ-СТВО-ПОСАДОЧНЫХ-МЕСТ)
с выделенным ключом
К12={ТИП-САМОЛЕТА}.
Схема отношения R11 находится теперь в ЗНФ относительно F, a R12 – нет, поскольку КОЛИЧЕСТВО-ПОСАДОЧНЫХ-МЕСТ транзитивно зависит от ТИПА-САМОЛЕТА через I- КЛАСС II-КЛАСС. Схема R12 разлагается на
R121(ТИПА-САМОЛЕТА, I-КЛАСС, II-КЛАСС)
с выделенным ключом
К121={ТИП-САМОЛЕТА}.
и схему отношения
R122(I-КЛАСС, II-КЛАСС, КОЛИЧЕСТВО-ПОСАДОЧНЫХ-МЕСТ)
с выделенным ключом
К122={I-КЛАСС II-КЛАСС}.
Декомпозиция R реализована до такой стадии, когда каждая схема отношения находится в ЗНФ относительно F. Следовательно, схема базы данных
находится в ЗНФ.
Схема базы данных R не однозначна. Есть точки, в которых можно выбирать пути декомпозиции определенного отношения с целью удаления транзитивно зависимого атрибута. Так, на первом шаге можно было выбрать
R2(ВРЕМЯ-ПРИБЫТИЯ, ДЛИТЕЛЬНОСТЬ-ПОЛЕТА, ПИТАНИЕ),
так как ПИТАНИЕ также транзитивно зависит от РЕЙСА через ВРЕМЯ-ПРИБЫТИЯ ДЛИТЕЛЬНОСТЬ-ПОЛЕТА. На третьем шаге существует три варианта декомпозиции R12 (Какие? ) Некоторые ключи для схем отношений не указаны как выделенные, например I-КЛАСС
63