- •Предисловие
- •Основные функции систем управления базами данных (СУБД)
- •Основные понятия
- •Преимущества использования баз данных
- •Функции систем управления базами данных
- •Литература
- •Реляционная модель данных
- •Структуры данных. Фундаментальные свойства отношений
- •Целостность данных. Реляционные ключи
- •Манипулирование данными
- •Реляционная алгебра Кодда
- •Операции
- •Объединение
- •Пересечение
- •Разность
- •Декартово произведение
- •Сокращение (выборка, ограничение, селекция)
- •Проекция
- •Соединения
- •Деление
- •Приоритеты операций
- •Базис алгебры и ства операций
- •Базис
- •Свойства операций
- •Ограничения реляционной алгебры
- •Литература
- •Реляционное исчисление
- •Исчисление кортежей
- •Эквивалентность исчисления кортежей и реляционной алгебры
- •Исчисление доменов
- •Литература
- •Случаи неполной информации и ω-значения
- •Концепция трехзначной логики
- •Логические операторы
- •Кванторы
- •Арифметические операции и операции сравнения
- •ω-значения и домены
- •ω-значения и операторы реляционной алгебры
- •ω-значения и агрегирующие функции
- •Проблема интерпретации
- •ω-значения и ограничения целостности
- •Первичные ключи
- •Внешние ключи
- •Литература
- •Семантическое проектирование реляционных баз данных на основе ER-модели
- •Общий подход семантического моделирования
- •Основные понятия
- •Проектирование базы данных с помощью ER-модели
- •Литература
- •Проектирование реляционных баз данных при помощи нормализации
- •Жизненный цикл системы баз данных
- •Функциональные зависимости
- •Понятие функциональной зависимости
- •Тривиальные и нетривиальные зависимости
- •Замыкание множества зависимостей
- •Неприводимые множества зависимостей
- •Декомпозиция без потерь и функциональные зависимости
- •Диаграммы функциональных зависимостей
- •Сохранение независимости в смысле Риссанена
- •Многозначные зависимости
- •Нормализация
- •Понятие нормализации и её причины
- •Первая, вторая и третья нормальные формы
- •Нормальная форма Бойса–Кодда
- •Четвертая нормальная форма
- •Зависимости соединения и пятая нормальная форма
- •Литература
- •Основные принципы хранения данных во внешней памяти
- •Страничная организация хранения данных
- •Управление буферами внутренней памяти
- •Простая файловая организация страниц
- •Неупорядоченный файл
- •Упорядоченный файл
- •Индексирование
- •Индексно-прямой метод доступа
- •Индексно-последовательный метод доступа
- •Индекс на основе B+-деревья
- •Хэширование
- •Индексированные кластеры
- •Хэшированные кластеры
- •Литература
- •Управление транзакциями и синхронизация в реляционных СУБД
- •Понятие транзакции
- •Фундаментальные свойства транзакций
- •Изолированность транзакций
- •Синхронизационные блокировки
- •Простые блокировки
- •Гранулированные (намеренные) блокировки
- •Предикатные блокировки
- •Тупиковые ситуации
- •Метод временных меток
- •Механизм выделения версий данных
- •Литература
- •Журнализация и восстановление в реляционных СУБД
- •Журнализация и буферизация
- •Индивидуальный откат транзакции
- •Восстановление после мягкого сбоя
- •Восстановление после жесткого сбоя
- •Литература
- •Выполнение и оптимизация запросов в реляционных СУБД
- •Процесс оптимизации запроса
- •Преобразование запроса во внутреннюю форму
- •Преобразование запроса в каноническую форму
- •Выбор потенциальных низкоуровневых процедур
- •Генерация различных вариантов планов вычисления запроса и выбор плана с минимальными затратами
- •Низкоуровневая оптимизация операции выборки
- •Низкоуровневая оптимизация операции соединения
- •Литература
Правое внешнее -соединение отличается лишь тем, что отношения меняются местами в определении:
Определение 12. Правым внешним -соединением отношений R1 и R2 по условию F называется
def
отношение R R1 'F R2 HR; BR , где
HR HR1'F R2 ;
!
BR BR1'F R2 Y pAR11 ; DR11 ; !q Y : : : Y pARn1 ; DRn1 ; !q Y T2
T2 P BR2 ^ @T1 P BR2 qF pT1:AR1 ; T2:AR2 qy FALSE( :
Замечание. Правое внешнее -соединение отношений R1 и R2 отличается от -соединения лишь тем, что дополнительно добавляются кортежи, образованные кортежами отношения R2, части которых не входят в обычное -соединение, к которым добавляются атрибуты отношения R1 с неопределенными значениями !.
А полное внешнее -соединение является объединением левого и правого внешних -соединений. Определение 13. Полным внешним -соединением отношений R1 и R2 по условию F называется
def
отношение R R1 'F R2 HR; BR , где
HR HR1'F R2 ;
!
BR BR1'F R2 Y T1 Y pAR12 ; DR12 ; !q Y : : : Y pARp2 ; DRp2 ; !q
T1 P BR1 ^ @T2 P BR2 qF pT1:AR1 ; T2:AR2 qy FALSE( Y
!
Y pAR11 ; DR11 ; !q Y : : : Y pARn1 ; DRn1 ; !q Y T2
T2 P BR2 ^ @T1 P BR2 qF pT1:AR1 ; T2:AR2 qy FALSE( :
Замечание. Полное внешнее -соединение можно переписать в виде:
R1 'F R2 R1 'F R2 Y R1 'F R2:
Аналогично внутреннему (обычному) -соединению можно определить левое, правое, полное внешние эквисоединения, просто заменив символ операции на знак равенства « ».
Деление
Предположим, что HR2 Ď HR1 , т. е. в отношении R2 все атрибуты совпадают по имени и домену с некоторыми атрибутами отношения R1. Обозначим остальные атрибуты отношения R1
def
как A HR1 zHR2 .
Определение 14. Результатом деления отношения R1 на отношение R2 называется отношение
def |
|
def |
HR; BR , где |
|
|
R R1 |
R2 |
|
def |
|
|
|
|
|
def |
HR A HR1 zHR2 |
; |
|
|
|
P BR1 ^ p@T2 P BR2 ApT1q Y T2 P BR1 qu ; |
||
|
|
|
BR t ApT1q |T1 |
при этом отношение R1 называется делителем, отношение R2 — делимым.
Замечание. Если все атрибуты отношения R1 трактовать как два составных tA; Bu, а атрибуты отношения R2 трактовать как один составной атрибут B, то результатом деления R1 R2 является отношение R с одним составным атрибутом A, тело которого состоит из кортежей T1 таких, что в теле отношения R1 содержатся кортежи T1 Y T2 для любого кортежа T2 отношения R2.
Замечание. Операцию деления можно записать через проекцию, декартово произведение и разность:
R1 R2 ApR1q A ApR1q R2 R1 :
19