- •Предисловие
- •Основные функции систем управления базами данных (СУБД)
- •Основные понятия
- •Преимущества использования баз данных
- •Функции систем управления базами данных
- •Литература
- •Реляционная модель данных
- •Структуры данных. Фундаментальные свойства отношений
- •Целостность данных. Реляционные ключи
- •Манипулирование данными
- •Реляционная алгебра Кодда
- •Операции
- •Объединение
- •Пересечение
- •Разность
- •Декартово произведение
- •Сокращение (выборка, ограничение, селекция)
- •Проекция
- •Соединения
- •Деление
- •Приоритеты операций
- •Базис алгебры и ства операций
- •Базис
- •Свойства операций
- •Ограничения реляционной алгебры
- •Литература
- •Реляционное исчисление
- •Исчисление кортежей
- •Эквивалентность исчисления кортежей и реляционной алгебры
- •Исчисление доменов
- •Литература
- •Случаи неполной информации и ω-значения
- •Концепция трехзначной логики
- •Логические операторы
- •Кванторы
- •Арифметические операции и операции сравнения
- •ω-значения и домены
- •ω-значения и операторы реляционной алгебры
- •ω-значения и агрегирующие функции
- •Проблема интерпретации
- •ω-значения и ограничения целостности
- •Первичные ключи
- •Внешние ключи
- •Литература
- •Семантическое проектирование реляционных баз данных на основе ER-модели
- •Общий подход семантического моделирования
- •Основные понятия
- •Проектирование базы данных с помощью ER-модели
- •Литература
- •Проектирование реляционных баз данных при помощи нормализации
- •Жизненный цикл системы баз данных
- •Функциональные зависимости
- •Понятие функциональной зависимости
- •Тривиальные и нетривиальные зависимости
- •Замыкание множества зависимостей
- •Неприводимые множества зависимостей
- •Декомпозиция без потерь и функциональные зависимости
- •Диаграммы функциональных зависимостей
- •Сохранение независимости в смысле Риссанена
- •Многозначные зависимости
- •Нормализация
- •Понятие нормализации и её причины
- •Первая, вторая и третья нормальные формы
- •Нормальная форма Бойса–Кодда
- •Четвертая нормальная форма
- •Зависимости соединения и пятая нормальная форма
- •Литература
- •Основные принципы хранения данных во внешней памяти
- •Страничная организация хранения данных
- •Управление буферами внутренней памяти
- •Простая файловая организация страниц
- •Неупорядоченный файл
- •Упорядоченный файл
- •Индексирование
- •Индексно-прямой метод доступа
- •Индексно-последовательный метод доступа
- •Индекс на основе B+-деревья
- •Хэширование
- •Индексированные кластеры
- •Хэшированные кластеры
- •Литература
- •Управление транзакциями и синхронизация в реляционных СУБД
- •Понятие транзакции
- •Фундаментальные свойства транзакций
- •Изолированность транзакций
- •Синхронизационные блокировки
- •Простые блокировки
- •Гранулированные (намеренные) блокировки
- •Предикатные блокировки
- •Тупиковые ситуации
- •Метод временных меток
- •Механизм выделения версий данных
- •Литература
- •Журнализация и восстановление в реляционных СУБД
- •Журнализация и буферизация
- •Индивидуальный откат транзакции
- •Восстановление после мягкого сбоя
- •Восстановление после жесткого сбоя
- •Литература
- •Выполнение и оптимизация запросов в реляционных СУБД
- •Процесс оптимизации запроса
- •Преобразование запроса во внутреннюю форму
- •Преобразование запроса в каноническую форму
- •Выбор потенциальных низкоуровневых процедур
- •Генерация различных вариантов планов вычисления запроса и выбор плана с минимальными затратами
- •Низкоуровневая оптимизация операции выборки
- •Низкоуровневая оптимизация операции соединения
- •Литература
все зависимости отношения R, а именно: pA Ñ Bq ^ pB Ñ Cq ñ pA Ñ Cq по аксиоме транзитивности. При этом общий атрибут B является потенциальным ключом в R2, т. е. такая декомпозиция удовлетворяет теореме Риссанена, а значит, проекции независимы.
3.R1 A;CpRq с первичным ключом A и R2 B;CpRq с потенциальным ключом B. В этом случае общий атрибут C не является потенциальным ключом ни в одном отношении-проекции, а значит, проекции зависимы. К тому же из зависимостей A Ñ C (из R1) и B Ñ C (из R2) не вывести зависимость A Ñ B. При этом такая декомпозиция имеет потери — исходное отношение не восстановить.
7.3. Многозначные зависимости
Для определения четвертой нормальной формы необходимо ввести понятие многозначных зависимостей, являющихся обобщением функциональных зависимостей.
Пусть R — переменная отношения с заголовком HR, а A Ď HR; B Ď HR — некоторые подмножества её атрибутов.
Определение 11. Подмножество B многозначно зависит от (или мультиопределяет) A (обозна-
чается A B) тогда и только тогда, когда для каждого допустимого значения R при заданных значениях атрибутов B существует множество C, состоящее из нуля или более ассоциированных (связанных) значений атрибутов из B и это множество значений атрибутов B не связано каким-либо образом со значением атрибутов в HRzpA Y Bq.
Определение 11’. Подмножество B многозначно зависит от (или мультиопределяет) A тогда и только тогда, когда при каждом допустимом значении R существует C Ď HR такое, что множество значений атрибутов B, соответствующее заданной паре pA; Cq значений атрибутов A и C, зависит только от значений атрибутов A и не зависит от значений атрибутов C.
Определение 11”. Строгое определение1:
pA Bq ô @ r HR; Br P R p@t; s P BrqptrAs srBsq ñ
$
urAs vrAs trAs srAs;
&
ñDu; v P Br : urBs trBs ^ urHRzpA Y Bqs srHRzpA Y Bqs;
%vrBs srBs ^ vrHRzpA Y Bqs trHRzpA Y Bqs:
Замечание. Одновременное условий системы означает, что можно поменять местами B-значения в кортежах t и s для того, чтобы получить два новых кортежа, которые также должны принадлежать телу отношения r.
Лемма (Фейгин или Фейджин; Fagin). Для переменной отношения R с заголовком HR AYB YC многозначная зависимость A B выполняется тогда и только тогда, когда выполняется еще и многозначная зависимость A C.
Замечание. В силу этого утверждения многозначные зависимости образуют связанные пары, поэтому обычно их обозначают так: A B C.
Если в многозначной зависимости множество зависимых значений, соответствующее значению атрибутов детерминантов, всегда состоит ровно из одного элемента, то получим функциональную зависимость, т. е. если A Ñ B, то A B.
Для многозначных зависимостей тоже существует своя «аксиоматика», которая является расширением аксиом Армстронга.
1 Под обозначением T rAs будем подразумевать множество значений атрибутов A кортежа T , а под равенством таких множеств подразумевается равенство по значениям соответствующих атрибутов.
41