- •Основы современных баз данных
- •1.1. Файловые системы
- •1.1.1. Структуры файлов
- •1.1.2. Именование файлов
- •1.1.3. Защита файлов
- •1.1.4. Режим многопользовательского доступа
- •1.2. Области применения файлов
- •1.3. Потребности информационных систем
- •2.1. Основные функции субд
- •2.1.1. Непосредственное управление данными во внешней памяти
- •2.1.2. Управление буферами оперативной памяти
- •2.1.3. Управление транзакциями
- •2.1.4. Журнализация
- •2.1.5. Поддержка языков бд
- •2.2. Типовая организация современной субд
- •2.3. Пример: System r
- •3.1. Основные особенности систем, основанных на инвертированных списках
- •3.1.1. Структуры данных
- •3.1.2. Манипулирование данными
- •3.1.3. Ограничения целостности
- •3.2. Иерархические системы
- •3.2.1. Иерархические структуры данных
- •3.2.2. Манипулирование данными
- •3.2.3. Ограничения целостности
- •3.3. Сетевые системы
- •3.3.1. Сетевые структуры данных
- •3.3.2. Манипулирование данными
- •3.3.3. Ограничения целостности
- •3.4. Достоинства и недостатки
- •4.1. Базовые понятия реляционных баз данных
- •4.1.1. Тип данных
- •4.1.2. Домен
- •4.1.3. Схема отношения, схема базы данных
- •4.1.4. Кортеж, отношение
- •4.2. Фундаментальные свойства отношений
- •4.2.1. Отсутствие кортежей-дубликатов
- •4.2.2. Отсутствие упорядоченности кортежей
- •4.2.3. Отсутствие упорядоченности атрибутов
- •4.2.4. Атомарность значений атрибутов
- •4.3. Реляционная модель данных
- •4.3.1. Общая характеристика
- •4.3.2. Целостность сущности и ссылок
- •5.1. Реляционная алгебра
- •5.1.1. Общая интерпретация реляционных операций
- •5.1.2. Замкнутость реляционной алгебры и операция переименования
- •5.1.3. Особенности теоретико-множественных операций реляционной алгебры
- •5.1.4. Специальные реляционные операции
- •5.2. Реляционное исчисление
- •5.2.1. Кортежные переменные и правильно построенные формулы
- •5.2.2. Целевые списки и выражения реляционного исчисления
- •5.2.3. Реляционное исчисление доменов
- •6.1. Проектирование реляционных баз данных с использованием нормализации
- •6.1.1. Вторая нормальная форма
- •6.1.2. Третья нормальная форма
- •6.1.3. Нормальная форма Бойса-Кодда
- •6.1.4. Четвертая нормальная форма
- •6.1.5. Пятая нормальная форма
- •6.2. Семантическое моделирование данных, er-диаграммы
- •6.2.1. Семантические модели данных
- •6.2.2. Основные понятия модели Entity-Relationship (Сущность-Связи)
- •6.2.3. Нормальные формы er-схем
- •6.2.4. Более сложные элементы er-модели
- •6.2.5. Получение реляционной схемы из er-схемы
- •7.1. Используемая терминология
- •7.2. Основные цели System r и их связь с архитектурой системы
- •7.3. Организация внешней памяти в базах данных System r
- •7.4. Интерфейс rss
- •7.5. Синхронизация в System r
- •7.6. Журнализация и восстановление в System r
- •8.1. История субд Ingres
- •8.2. Ingres как unix-ориентированная субд. Динамическая структура системы: набор процессов
- •8.3. Структуры данных, методы доступа, интерфейсы доступа к данным
- •8.4. Общая характеристика языка quel. Язык программирования equel
- •8.5. Общий подход к организации представлений, ограничениям целостности и контролю доступа
- •9.1. Хранение отношений
- •9.2. Индексы
- •9.2.1. B-деревья
- •9.2.2. Хэширование
- •9.3. Журнальная информация
- •9.4. Служебная информация
- •10.1. Транзакции и целостность баз данных
- •10.2. Изолированность пользователей
- •10.3. Сериализация транзакций
- •11.1. Синхронизационные захваты
- •11.1.1. Гранулированные синхронизационные захваты
- •11.1.2. Предикатные синхронизационные захваты
- •11.1.3. Тупики, распознавание и разрушение
- •11.2. Метод временных меток
- •12.1. Журнализация и буферизация
- •12.2. Индивидуальный откат транзакции
- •12.3. Восстановление после мягкого сбоя
- •12.4. Физическая согласованность базы данных
- •12.5. Восстановление после жесткого сбоя
- •13.1. Sequel/sql субд System r
- •13.1.1. Запросы и операторы манипулирования данными
- •13.1.2. Операторы определения и манипулирования схемой бд
- •13.1.3. Определения ограничений целостности и триггеров
- •13.1.4. Представления базы данных
- •13.1.5. Определение управляющих структур
- •13.1.6. Авторизация доступа к отношениям и их полям
- •13.1.7. Точки сохранения и откаты транзакции
- •13.1.8. Встроенный sql
- •13.1.9. Динамический sql
- •13.2. Язык sql в коммерческих реализациях
- •13.3. Стандартизация sql
- •14.1. Типы данных
- •14.2. Средства определения схемы
- •14.2.1. Оператор определения схемы
- •14.2.2. Определение таблицы
- •14.2.3. Определение столбца
- •14.2.4. Определение ограничений целостности таблицы
- •14.2.5. Определение представлений
- •14.2.6. Определение привилегий
- •15.1. Структура запросов
- •15.1.1. Спецификация курсора
- •15.1.2. Оператор выборки
- •15.1.3. Подзапрос
- •15.2. Табличное выражение
- •15.2.1. Раздел from
- •15.2.2. Раздел where
- •15.2.3. Раздел group by
- •15.2.4. Раздел having
- •15.3. Агрегатные функции и результаты запросов
- •15.3.1. Семантика агрегатных функций
- •15.3.2. Результаты запросов
- •16.1. Язык модулей или встроенный sql?
- •16.2. Язык модулей
- •16.2.1. Определение процедуры
- •16.3. Встроенный sql
- •16.4. Набор операторов манипулирования данными
- •16.4.1. Операторы, связанные с курсором
- •16.4.2. Одиночные операторы манипулирования данными
- •16.5. Динамический sql в Oracle V.6
- •16.5.1. Оператор подготовки
- •16.5.2. Оператор получения описания подготовленного оператора
- •16.5.3. Оператор выполнения подготовленного оператора
- •16.5.4. Работа с динамическими операторами sql через курсоры
- •17.1. Оператор выделения памяти под дескриптор
- •17.2. Оператор освобождения памяти из-под дескриптора
- •17.3. Оператор получения информации из области дескриптора sql
- •17.4. Оператор установки дескриптора
- •17.5. Оператор подготовки
- •17.6. Оператор отказа от подготовленного оператора
- •17.7. Оператор запроса описания подготовленного оператора
- •17.8. Оператор выполнения подготовленного оператора
- •17.9. Оператор подготовки с немедленным выполнением
- •17.10. Оператор объявления курсора над динамически подготовленным оператором выборки
- •17.11. Оператор определения курсора над динамически подготовленным оператором выборки
- •17.12. Оператор открытия курсора, связанного с динамически подготовленным оператором выборки
- •17.18. Подготавливаемый оператор позиционной модификации
- •17.19. Сводка новых возможностей sql-3
- •17.19.1. Типы данных
- •17.19.2. Некоторые другие свойства sql-3
- •18.1. Общая схема обработки запроса
- •18.2. Синтаксическая оптимизация запросов
- •18.2.1. Простые логические преобразования запросов
- •18.2.2 Преобразования запросов с изменением порядка реляционных операций
- •18.2.3 Приведение запросов со вложенными подзапросами к запросам с соединениями
- •18.3. Семантическая оптимизация запросов
- •18.3.1. Преобразования запросов на основе семантической информации
- •18.3.2. Использование семантической информации при оптимизации запросов
- •18.4. Выбор и оценка альтернативных планов выполнения запросов
- •18.4.1. Генерация планов
- •18.4.2. Оценка стоимости плана запроса
- •18.4.3. Более точные оценки
- •19.1. Открытые системы
- •19.2. Клиенты и серверы локальных сетей
- •19.3. Системная архитектура "клиент-сервер"
- •19.4. Серверы баз данных
- •19.4.1. Принципы взаимодействия между клиентскими и серверными частями
- •19.4.2. Преимущества протоколов удаленного вызова процедур
- •19.4.3. Типичное разделение функций между клиентами и серверами
- •19.4.4. Требования к аппаратным возможностям и базовому программному обеспечению клиентов и серверов
- •20.1. Разновидности распределенных систем
- •20.2. Распределенная система управления базами данных System r*
- •20.2.1. Именование объектов и организация распределенного каталога
- •20.2.2. Распределенная компиляция запросов
- •20.2.3. Управление транзакциями и синхронизация
- •20.3. Интегрированные или федеративные системы и мультибазы данных
- •21.1. Ориентация на расширенную реляционную модель
- •21.2. Абстрактные типы данных
- •21.3. Генерация систем баз данных, ориентированных на приложения
- •21.4. Оптимизация запросов, управляемая правилами
- •21.5. Поддержка исторической информации и темпоральных запросов
- •22.1. Связь объектно-ориентированных субд с общими понятиями объектно-ориентированного подхода
- •22.2. Объектно-ориентированные модели данных
- •22.3. Языки программирования объектно-ориентированных баз данных
- •22.3.1. Потеря соответствия между языками программирования и языками запросов в реляционных субд
- •22.3.2. Языки программирования ообд как объектно-ориентированные языки с поддержкой стабильных (persistent) объектов
- •22.3.3. Примеры языков программирования ообд
- •22.4. Языки запросов объектно-ориентированных баз данных
- •22.4.1. Явная навигация как следствие преодоления потери соответствия
- •22.4.2. Ненавигационные языки запросов
- •22.4.3. Проблемы оптимизации запросов
- •22.5. Примеры объектно-ориентированных субд
- •22.5.1. Проект orion
- •22.5.2. Проект o2
- •23.1. Экстенсиональная и интенсиональная части базы данных
- •23.2. Активные базы данных
- •23.3. Дедуктивные базы данных
6.1.1. Вторая нормальная форма
Рассмотрим следующий пример схемы отношения:
СОТРУДНИКИ-ОТДЕЛЫ-ПРОЕКТЫ
(СОТР_НОМЕР, СОТР_ЗАРП, ОТД_НОМЕР, ПРО_НОМЕР, СОТР_ЗАДАН)
Первичный ключ:
СОТР_НОМЕР, ПРО_НОМЕР
Функциональные зависимости:
СОТР_НОМЕР -СОТР_ЗАРП
СОТР_НОМЕР -ОТД_НОМЕР
ОТД_НОМЕР -СОТР_ЗАРП
СОТР_НОМЕР, ПРО_НОМЕР -СОТР_ЗАДАН
Как видно, хотя первичным ключом является составной атрибут СОТР_НОМЕР, ПРО_НОМЕР, атрибуты СОТР_ЗАРП и ОТД_НОМЕР функционально зависят от части первичного ключа, атрибута СОТР_НОМЕР. В результате мы не сможем вставить в отношение СОТРУДНИКИ-ОТДЕЛЫ-ПРОЕКТЫ кортеж, описывающий сотрудника, который еще не выполняет никакого проекта (первичный ключ не может содержать неопределенное значение). При удалении кортежа мы не только разрушаем связь данного сотрудника с данным проектом, но утрачиваем информацию о том, что он работает в некотором отделе. При переводе сотрудника в другой отдел мы будем вынуждены модифицировать все кортежи, описывающие этого сотрудника, или получим несогласованный результат. Такие неприятные явления называются аномалиями схемы отношения. Они устраняются путем нормализации.
Определение 6.Вторая нормальная форма (в этом определении предполагается, что единственным ключом отношения является первичный ключ)
Отношение R находится во второй нормальной форме (2NF) в том и только в том случае, когда находится в 1NF, и каждый неключевой атрибут полностью зависит от первичного ключа.
Можно произвести следующую декомпозицию отношения СОТРУДНИКИ-ОТДЕЛЫ-ПРОЕКТЫ в два отношения СОТРУДНИКИ-ОТДЕЛЫ и СОТРУДНИКИ-ПРОЕКТЫ:
СОТРУДНИКИ-ОТДЕЛЫ (СОТР_НОМЕР, СОТР_ЗАРП, ОТД_НОМЕР)
Первичный ключ:
СОТР_НОМЕР
Функциональные зависимости:
СОТР_НОМЕР -СОТР_ЗАРП
СОТР_НОМЕР -ОТД_НОМЕР
ОТД_НОМЕР -СОТР_ЗАРП
СОТРУДНИКИ-ПРОЕКТЫ (СОТР_НОМЕР, ПРО_НОМЕР, СОТР_ЗАДАН)
Первичный ключ:
СОТР_НОМЕР, ПРО_НОМЕР
Функциональные зависимости:
СОТР_НОМЕР, ПРО_НОМЕР -CОТР_ЗАДАН
Каждое из этих двух отношений находится в 2NF, и в них устранены отмеченные выше аномалии (легко проверить, что все указанные операции выполняются без проблем).
Если допустить наличие нескольких ключей, то определение 6 примет следующий вид:
Определение 6~
Отношение R находится во второй нормальной форме (2NF) в том и только в том случае, когда оно находится в 1NF, и каждый неключевой атрибут полностью зависит от каждого ключа R.
Здесь и далее мы не будем приводить примеры для отношений с несколькими ключами. Они слишком громоздки и относятся к ситуациям, редко встречающимся на практике.
6.1.2. Третья нормальная форма
Рассмотрим еще раз отношение СОТРУДНИКИ-ОТДЕЛЫ, находящееся в 2NF. Заметим, что функциональная зависимость СОТР_НОМЕР -СОТР_ЗАРП является транзитивной; она является следствием функциональных зависимостей СОТР_НОМЕР-ОТД_НОМЕР и ОТД_НОМЕР-СОТР_ЗАРП. Другими словами, заработная плата сотрудника на самом деле является характеристикой не сотрудника, а отдела, в котором он работает (это не очень естественное предположение, но достаточное для примера).
В результате мы не сможем занести в базу данных информацию, характеризующую заработную плату отдела, до тех пор, пока в этом отделе не появится хотя бы один сотрудник (первичный ключ не может содержать неопределенное значение). При удалении кортежа, описывающего последнего сотрудника данного отдела, мы лишимся информации о заработной плате отдела. Чтобы согласованным образом изменить заработную плату отдела, мы будем вынуждены предварительно найти все кортежи, описывающие сотрудников этого отдела. Т.е. в отношении СОТРУДИКИ-ОТДЕЛЫ по-прежнему существуют аномалии. Их можно устранить путем дальнейшей нормализации.
Определение 7.Третья нормальная форма. (Снова определение дается в предположении существования единственного ключа.)
Отношение R находится в третьей нормальной форме (3NF) в том и только в том случае, если находится в 2NF и каждый неключевой атрибут нетранзитивно зависит от первичного ключа.
Можно произвести декомпозицию отношения СОТРУДНИКИ-ОТДЕЛЫ в два отношения СОТРУДНИКИ и ОТДЕЛЫ:
СОТРУДНИКИ (СОТР_НОМЕР, ОТД_НОМЕР)
Первичный ключ:
СОТР_НОМЕР
Функциональные зависимости:
СОТР_НОМЕР -ОТД_НОМЕР
ОТДЕЛЫ (ОТД_НОМЕР, СОТР_ЗАРП)
Первичный ключ:
ОТД_НОМЕР
Функциональные зависимости:
ОТД_НОМЕР -СОТР_ЗАРП
Каждое из этих двух отношений находится в 3NF и свободно от отмеченных аномалий.
Если отказаться от того ограничения, что отношение обладает единственным ключом, то определение 3NF примет следующую форму:
Определение 7~
Отношение R находится в третьей нормальной форме (3NF) в том и только в том случае, если находится в 1NF, и каждый неключевой атрибут не является транзитивно зависимым от какого-либо ключа R.
На практике третья нормальная форма схем отношений достаточна в большинстве случаев, и приведением к третьей нормальной форме процесс проектирования реляционной базы данных обычно заканчивается. Однако иногда полезно продолжить процесс нормализации.