- •Серия «Учебники и учебные пособия»
- •Э.П. Голенищев
- •И.В. Клименко
- •Рецензент
- •Предисловие
- •Введение
- •Глава 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. Краткий толковый словарь
- •Содержание
Любое априорное знание о различного рода ограничениях, накладываемых на совокупности данных, может принести большую пользу для достижения указанных целей.
Один из способов формализации этих знаний – установление зависимостей между элементами данных. Известно два основных типа таких зависимостей:
1)функциональные зависимости;
2)многозначные зависимости.
Функциональная зависимость является обобщением понятия ключа.
В табл. 2.7 представлено отношение График (ПИЛОТ, РЕЙС, ДАТА, ВРЕМЯ-ВЫЛЕТА). Это отношение показывает, какой пилот участвует в данном рейсе в данный день и каково время вылета самолета. Не любое сочетание значений атрибутов ПИЛОТ, РЕЙС, ДАТА и ВРЕМЯ-ВЫЛЕТА допустимо в таком расписании.
|
|
|
|
Таблица 2.7 |
|
|
|
|
|
График |
ПИЛОТ |
РЕЙС |
ДАТА |
ВРЕМЯ-ВЫЛЕТА |
|
Мовчан |
83 |
9 августа |
10:15 |
|
Мовчан |
116 |
10 августа |
13:25 |
|
Синицын |
281 |
8 августа |
05:50 |
|
Синицын |
301 |
12 августа |
18:35 |
|
Синицын |
83 |
11 августа |
10:15 |
|
Федотов |
83 |
13 августа |
10:15 |
|
Федотов |
116 |
12 августа |
13:25 |
|
Вишневский |
281 |
9 августа |
05:50 |
|
Вишневский |
281 |
13 августа |
05:50 |
|
Вишневский |
412 |
15 августа |
13:25 |
На табл. 2.7 накладываются следующие ограничения.
1.Для каждого рейса назначается только одно время вылета.
2.Для данного пилота, даты и времени вылета возможен только один рейс.
3.Для данного рейса и даты назначается только один пилот.
Эти ограничения являются примерами F-зависимостей (F-зависимость – функциональная зависимость между данными).
F-зависимость имеет место тогда, когда значения кортежа на одном множестве атрибутов единственным образом определяют эти значения на другом множестве атрибутов.
Указанные выше ограничения можно сформулировать следующим образом.
1.ВРЕМЯ функционально зависит от РЕЙСА.
2.РЕЙС функционально зависит от {ПИЛОТ, ДАТА, ВРЕМЯ}.
3.ПИЛОТ функционально зависит от {РЕЙС, ДАТА}.
Порядок в этих последовательностях могут менять и говорить, что РЕЙС, ДАТА функционально определяют ПИЛОТ, или символически:
Пусть r – отношение со схемой R, X и Y – подмножества R. Отношение r удовлетворяет функциональной зависимости X → Y, если
ВF-зависимости Х → Y подмножество X называется левой частью, а Y – правой частью.
2.4.3.2.Аксиомы вывода функциональных зависимостей
Для отношения r(R) в любой момент существует некоторое семейство F-зависимостей, которым это отношение удовлетворяет. Здесь может возникнуть та же проблема, что и с ключами: одно состояние отношения может удовлетворять F-зависимости, а другое – нет.
Требуется выявить семейство F-зависимостей F, которому удовлетворяют все допустимые состояния
56
r. Чтобы найти F, необходимы семантические знания об отношении r. Поэтому можно считать семейство F-зависимостей заданным в схеме отношения R, в этом случае любое отношение r(F) должно удовлетворять всем F-зависимостям из F. Не всегда ясно, что является первичным: множество допустимых состояний отношения, которое определяет F-зависимости, или F-зависимости накладывают ограничения на схему отношения [10].
Множество функциональных зависимостей, применимых к отношению r(R), конечно, так как существует только конечное число подмножеств множества R. Таким образом, всегда можно найти все F-зависимости, которым удовлетворяет r. Однако этот подход требует большого количества шагов и, соответственно, много времени.
Если известны некоторые F-зависимости из F, то часто можно вывести остальные.
Множество F-зависимостей F влечет за собой зависимость X → Y, если каждое отношение, удовлетворяющее всем зависимостям в F, удовлетворяет также зависимости X → Y.
Аксиома вывода - это правило, устанавливающее, что если отношение удовлетворяет определенным F-зависимостям, то оно должно удовлетворять и некоторым другим F-зависимостям.
Сформулировано шесть аксиом вывода F-зависимостей [10]. В этих формулировках используется обозначение r для отношения на R и W, X, Y и Z – для подмножеств R.
F1. Рефлексивность. Х → Х.
F2. Пополнение. Х → Y влечет за собой XZ → Y.
F3. Аддитивность. X → У и X → Z влечет за собой X → YZ.
F4. Проективность. X → YZ влечет за собой X → Y.
F5. Транзитивность. Х → Y и Y → Z влечет за собой X → Z.
F6. Псевдотранзитивность. X → Y и YZ → W влечет за собой XZ → W.
Некоторые аксиомы вывода могут быть получены из других. Например, транзитивность F5 является
частным случаем псевдотранзитивности F6 при Z = .
Приведенная система аксиом F1-F6 является полной. Это означает, что каждая F-зависимость, которая следует из множества F, может быть выведена путем одноили многократного применения к F этих аксиом.
Из аксиом F1, F2 и F6 можно вывести остальные, а значит, они образуют полное подмножество для F1-F6. Аксиомы F1, F2 и F6 являются также независимыми: ни одна из этих аксиом не может быть получена из двух других. Иногда эти три аксиомы называются аксиомами Армстронга.
Пусть F – множество F-зависимостей для отношения r(R). Замыкание F, обозначаемое F+, – это наименьшее содержащее F множество, такое, что при применении к нему аксиом Армстронга нельзя получить ни одной F-зависимости, не принадлежащей F. Так как F+ должно быть конечно, то можно вычислить его, начиная с F путем применения F1, F2 и F6 и добавления полученных F-зависимостей к F до тех пор, пока не перестанут получаться новые зависимости. Замыкание F зависит от схемы R.
Из множества F можно вывести F-зависимость X → Y, если X → Y принадлежит F+. Так как аксиомы вывода порождают только функциональные зависимости, то F влечет за собой X → Y, если X → Y выводится из F.
Пример 2.5. Пусть F = {AB → C, С → В} - множество F-зависимостей на r(АВС). Тогда:
В свете новых знаний об F-зависимостях, следует уточнить понятия ключа и суперключа.
Для данной схемы отношения R ключ - это подмножество К R, такое, что для любого допустимого отношения r(R) не существует двух различных кортежей t1 и t2 в r, таких, что r1К) = t2(К), и никакое
собственное подмножество K' K не обладает этим свойством.
Для некоторых допустимых отношений со схемой R подмножество К' может быть ключом, но
57
рассматриваются все допустимые отношения со схемой R. Суперключ – это любая совокупность атрибутов, содержащая ключ.
Нормализация - формальный метод анализа отношений на основе их первичного ключа (или потенциальных ключей) и существующих функциональных зависимостей [2, 7, 10].
Цель нормализации – получение такого проекта базы данных, в котором каждый факт хранится в одном месте, т.е. исключена избыточность информации. Это делается не столько с целью экономии памяти, сколько для исключения возможной противоречивости хранимых данных из-за их избыточности.
Нормальная форма представляет собой ограничение на схему базы данных (отношения), которое избавляет базу данных от некоторых нежелательных свойств.
Нормализация чаще всего выполняется в несколько последовательных этапов, результатом каждого из которых является некоторая нормальная форма с известными свойствами.
В теории реляционных баз данных разработано несколько нормальных форм (НФ), которые подчиняются правилу вложенности (рис. 2.25).
Рис. 2.25. Вложенность нормальных форм
Смысл вложенности нормальных форм в следующем: каждая нормальная форма является в некотором смысле более ограниченной, но и более желательной, чем предшествующая [17]. Это связано с тем, что (N + 1)-я нормальная форма не обладает некоторыми недостатками, свойственным N-й нормальной форме. Общий смысл дополнительного условия, налагаемого на (N + 1)-ю нормальную форму по отношению к N-й нормальной форме, состоит в исключении этих недостатков.
При реализации реляционной БД важно понимать, что только удовлетворение требований первой нормальной формы (1НФ) обязательно для создания отношений приемлемого качества. Все остальные формы могут использоваться по желанию проектировщика. Однако чтобы избежать аномалий обновления, описываемых ниже, нормализацию рекомендуется проводить как минимум до ЗНФ.
2.4.3.3. Первая нормальная форма
Схема отношения R находится в первой нормальной форме (1НФ), если значения в домене D(A) являются атомарными для каждого атрибута А в JR. Другими словами, значения в домене не являются ни списками, ни множествами простых или сложных значений [10].
Схема базы данных R находится в первой нормальной форме, если каждая схема отношения в R находится в 1НФ.
Определить понятие атомарности трудно: значение атомарное в одном приложении, может быть неатомарным в другом. Можно руководствоваться общим принципом, что значение неатомарно, если в приложении оно используется по частям.
Пример 2.6. Имеется отношение Сотрудники:
58
Сотрудники |
НОМЕР |
ФИО |
|
23 |
Вербов Александр Владимирович |
|
24 |
Фисенко Александр Сергеевич |
|
25 |
Фатхи Дмитрий Владимирович |
Если понадобится указать только фамилии сотрудников, то указанное отношение не находится в 1НФ, так как требуемые значения являются частью атрибута ФИО. Чтобы отношение в таких условиях находилось в 1НФ, атрибут ФИО должен быть разбит на части, как показано ниже.
Сотрудники |
НОМЕР |
ФАМИЛИЯ |
ИМЯ |
ОТЧЕСТВО |
|
23 |
Вербов |
Александр |
Владимирович |
|
24 |
Фисенко |
Александр |
Сергеевич |
|
25 |
Фатхи |
Дмитрий |
Владимирович |
Пример 2.7. Отношение Род, представленное ниже, не находится в первой нормальной форме потому, что оно включает величины, являющиеся совокупностью атомарных значений.
Род |
ИМЯ |
ПОЛ |
|
Иван, Александр, Сергей |
мужской |
|
Мария, Ирина |
женский |
Чтобы отношение Род находилось в 1НФ, оно должно быть представлено следующим образом.
Род |
ИМЯ |
ПОЛ |
|
Иван |
мужской |
|
Александр |
мужской |
|
Сергей |
мужской |
|
Мария |
женский |
|
Ирина |
женский |
В чем преимущество применения 1НФ? В том, что 1НФ позволяет выражать F-зависимости с той степенью детализации, с какой требует приложение, что невозможно без 1НФ.
Но и 1НФ обладает рядом существенных недостатков [2, 7, 10]. На первых этапах проектирования базы данных, после анализа предметной области и определения состава информации для хранения в БД обычно формируется так называемое универсальное отношение.
Универсальное отношение – одна таблица, находящаяся в 1НФ, в которой может храниться вся информация об интересующей предметной области. Другими словами схему этого отношения образует весь перечень интересующих атрибутов предметной области [5].
При использовании универсального отношения возникают следующие проблемы [5, 10].
1.Избыточность. Данные многих столбцов многократно повторяются. Повторяются и некоторые наборы данных.
2.Аномалии обновления:
а) аномалии добавления; б) аномалии изменения; в) аномалии удаления.
Аномалии обновления являются нежелательным побочным эффектом, обусловленным избыточностью хранимых данных при внесении изменений в отношение.
Рассмотрим отношение График.
График |
РЕЙС |
ДАТА |
ПИЛОТ |
ГАЛЕРЕЯ |
|
112 |
6 июня |
Иванов |
7 |
|
112 |
7 июня |
Петров |
7 |
|
203 |
9 июня |
Иванов |
12 |
Атрибуты РЕЙС ДАТА являются ключом отношения |
График, и это отношение должно также |
59