- •Предисловие
- •Основные функции систем управления базами данных (СУБД)
- •Основные понятия
- •Преимущества использования баз данных
- •Функции систем управления базами данных
- •Литература
- •Реляционная модель данных
- •Структуры данных. Фундаментальные свойства отношений
- •Целостность данных. Реляционные ключи
- •Манипулирование данными
- •Реляционная алгебра Кодда
- •Операции
- •Объединение
- •Пересечение
- •Разность
- •Декартово произведение
- •Сокращение (выборка, ограничение, селекция)
- •Проекция
- •Соединения
- •Деление
- •Приоритеты операций
- •Базис алгебры и ства операций
- •Базис
- •Свойства операций
- •Ограничения реляционной алгебры
- •Литература
- •Реляционное исчисление
- •Исчисление кортежей
- •Эквивалентность исчисления кортежей и реляционной алгебры
- •Исчисление доменов
- •Литература
- •Случаи неполной информации и ω-значения
- •Концепция трехзначной логики
- •Логические операторы
- •Кванторы
- •Арифметические операции и операции сравнения
- •ω-значения и домены
- •ω-значения и операторы реляционной алгебры
- •ω-значения и агрегирующие функции
- •Проблема интерпретации
- •ω-значения и ограничения целостности
- •Первичные ключи
- •Внешние ключи
- •Литература
- •Семантическое проектирование реляционных баз данных на основе ER-модели
- •Общий подход семантического моделирования
- •Основные понятия
- •Проектирование базы данных с помощью ER-модели
- •Литература
- •Проектирование реляционных баз данных при помощи нормализации
- •Жизненный цикл системы баз данных
- •Функциональные зависимости
- •Понятие функциональной зависимости
- •Тривиальные и нетривиальные зависимости
- •Замыкание множества зависимостей
- •Неприводимые множества зависимостей
- •Декомпозиция без потерь и функциональные зависимости
- •Диаграммы функциональных зависимостей
- •Сохранение независимости в смысле Риссанена
- •Многозначные зависимости
- •Нормализация
- •Понятие нормализации и её причины
- •Первая, вторая и третья нормальные формы
- •Нормальная форма Бойса–Кодда
- •Четвертая нормальная форма
- •Зависимости соединения и пятая нормальная форма
- •Литература
- •Основные принципы хранения данных во внешней памяти
- •Страничная организация хранения данных
- •Управление буферами внутренней памяти
- •Простая файловая организация страниц
- •Неупорядоченный файл
- •Упорядоченный файл
- •Индексирование
- •Индексно-прямой метод доступа
- •Индексно-последовательный метод доступа
- •Индекс на основе B+-деревья
- •Хэширование
- •Индексированные кластеры
- •Хэшированные кластеры
- •Литература
- •Управление транзакциями и синхронизация в реляционных СУБД
- •Понятие транзакции
- •Фундаментальные свойства транзакций
- •Изолированность транзакций
- •Синхронизационные блокировки
- •Простые блокировки
- •Гранулированные (намеренные) блокировки
- •Предикатные блокировки
- •Тупиковые ситуации
- •Метод временных меток
- •Механизм выделения версий данных
- •Литература
- •Журнализация и восстановление в реляционных СУБД
- •Журнализация и буферизация
- •Индивидуальный откат транзакции
- •Восстановление после мягкого сбоя
- •Восстановление после жесткого сбоя
- •Литература
- •Выполнение и оптимизация запросов в реляционных СУБД
- •Процесс оптимизации запроса
- •Преобразование запроса во внутреннюю форму
- •Преобразование запроса в каноническую форму
- •Выбор потенциальных низкоуровневых процедур
- •Генерация различных вариантов планов вычисления запроса и выбор плана с минимальными затратами
- •Низкоуровневая оптимизация операции выборки
- •Низкоуровневая оптимизация операции соединения
- •Литература
Литература
1.Date C. J., Darwen H. Foundation for Future Database Systems: The Third Manifesto. — 2nd ed. — Addison Wesley Professional, 2000. — 608 pp. — ISBN 9780201709285.
2.Дейт К. Дж. Типы данных. Отношения / пер. с англ. К. А. Птицына // Введение в системы баз данных (главы 6, 7). — 8-е изд. — М. : Издательский дом „Вильямс“, 2005.
3.Дейт К. Дж. Целостность данных / пер. с англ. К. А. Птицына // Введение в системы баз данных (глава 9). — 8-е изд. — М. : Издательский дом „Вильямс“, 2005.
4.Коннолли Т., Бегг К. Реляционная модель / пер. с англ. Р. Г. Имамутдинова, К. А. Птицына // Базы данных: проектирование, реализация и сопровождение (глава 3) / под ред. К. А. Птицына. — 3- е изд. — М. : Издательский дом „Вильямс“, 2003.
5.Кузнецов С. Д. Введение в реляционную модель данных // Базы данных. Вводный курс (лекция 3). — 2008. — URL: http://citforum.ru/database/advanced_intro/10.shtml.
6.Кузнецов С. Д. Реляционная алгебра A Дейта и Дарвена // Базы данных. Вводный курс (лекция 5). — 2008. — URL: http://citforum.ru/database/advanced_intro/15.shtml.
7.Кузнецов С. Д. Реляционная алгебра Кодда // Базы данных. Вводный курс (лекция 4). — 2008. — URL: http://citforum.ru/database/advanced_intro/13.shtml.
8.Тальхайм Б. Обзор семантических ограничений для моделей баз данных // Интеллектуальные системы. — 1998. — Т. 3, № 3–4. — С. 318—321. — URL: http://intsys.msu.ru/magazine/
archive/v3(3-4)/thalheim-307-351.pdf.
§3. Реляционная алгебра Кодда
Реляционная алгебра Кодда — это набор операций, принимающие и возвращающие отношения. Источником «оригинальной» (в смысле «истинной») алгебры принято считать работу Эдгара Кодда [1]. Предложенные им 8 операций можно разбить на две группы:
•Традиционные операции с множествами: объединение, пересечение, разность и декартово произведение.
•Специальные реляционные операции: сокращение (или выборка), проекция, соединение и деление.
Можно определить еще любое количество операций — лишь бы они принимали и давали в результате только отношения (например, левое и правое внешние соединения). Заметим, что все эти операцию никоим образом не изменяют отношения, а только выводят получающиеся временные отношения.
Реляционная алгебра обладает свойством замкнутости, т. к. все операции принимают на входе отношения и получают на выходе тоже отношения. Важным следствием этого является то, что можно использовать вложенные реляционные выражения, т. е. в тех местах реляционного выражения, где должно быть отношение (начиная с операндов операций), можно указывать любое реляционное выражение.
14