- •Предисловие
- •Основные функции систем управления базами данных (СУБД)
- •Основные понятия
- •Преимущества использования баз данных
- •Функции систем управления базами данных
- •Литература
- •Реляционная модель данных
- •Структуры данных. Фундаментальные свойства отношений
- •Целостность данных. Реляционные ключи
- •Манипулирование данными
- •Реляционная алгебра Кодда
- •Операции
- •Объединение
- •Пересечение
- •Разность
- •Декартово произведение
- •Сокращение (выборка, ограничение, селекция)
- •Проекция
- •Соединения
- •Деление
- •Приоритеты операций
- •Базис алгебры и ства операций
- •Базис
- •Свойства операций
- •Ограничения реляционной алгебры
- •Литература
- •Реляционное исчисление
- •Исчисление кортежей
- •Эквивалентность исчисления кортежей и реляционной алгебры
- •Исчисление доменов
- •Литература
- •Случаи неполной информации и ω-значения
- •Концепция трехзначной логики
- •Логические операторы
- •Кванторы
- •Арифметические операции и операции сравнения
- •ω-значения и домены
- •ω-значения и операторы реляционной алгебры
- •ω-значения и агрегирующие функции
- •Проблема интерпретации
- •ω-значения и ограничения целостности
- •Первичные ключи
- •Внешние ключи
- •Литература
- •Семантическое проектирование реляционных баз данных на основе ER-модели
- •Общий подход семантического моделирования
- •Основные понятия
- •Проектирование базы данных с помощью ER-модели
- •Литература
- •Проектирование реляционных баз данных при помощи нормализации
- •Жизненный цикл системы баз данных
- •Функциональные зависимости
- •Понятие функциональной зависимости
- •Тривиальные и нетривиальные зависимости
- •Замыкание множества зависимостей
- •Неприводимые множества зависимостей
- •Декомпозиция без потерь и функциональные зависимости
- •Диаграммы функциональных зависимостей
- •Сохранение независимости в смысле Риссанена
- •Многозначные зависимости
- •Нормализация
- •Понятие нормализации и её причины
- •Первая, вторая и третья нормальные формы
- •Нормальная форма Бойса–Кодда
- •Четвертая нормальная форма
- •Зависимости соединения и пятая нормальная форма
- •Литература
- •Основные принципы хранения данных во внешней памяти
- •Страничная организация хранения данных
- •Управление буферами внутренней памяти
- •Простая файловая организация страниц
- •Неупорядоченный файл
- •Упорядоченный файл
- •Индексирование
- •Индексно-прямой метод доступа
- •Индексно-последовательный метод доступа
- •Индекс на основе B+-деревья
- •Хэширование
- •Индексированные кластеры
- •Хэшированные кластеры
- •Литература
- •Управление транзакциями и синхронизация в реляционных СУБД
- •Понятие транзакции
- •Фундаментальные свойства транзакций
- •Изолированность транзакций
- •Синхронизационные блокировки
- •Простые блокировки
- •Гранулированные (намеренные) блокировки
- •Предикатные блокировки
- •Тупиковые ситуации
- •Метод временных меток
- •Механизм выделения версий данных
- •Литература
- •Журнализация и восстановление в реляционных СУБД
- •Журнализация и буферизация
- •Индивидуальный откат транзакции
- •Восстановление после мягкого сбоя
- •Восстановление после жесткого сбоя
- •Литература
- •Выполнение и оптимизация запросов в реляционных СУБД
- •Процесс оптимизации запроса
- •Преобразование запроса во внутреннюю форму
- •Преобразование запроса в каноническую форму
- •Выбор потенциальных низкоуровневых процедур
- •Генерация различных вариантов планов вычисления запроса и выбор плана с минимальными затратами
- •Низкоуровневая оптимизация операции выборки
- •Низкоуровневая оптимизация операции соединения
- •Литература
2.Connolly T. M., Begg C. E. Relational Calculus // Database systems: a practical approach to design, implementation, and management. — 4th ed. — San Jose, California : Addison-Wesley, 2005. — Pp. 103–111. — (International computer science series). — ISBN 9780321210258.
3.Lacroix M., Pirotte A. Domain-oriented relational languages // Proceedings of the third international conference on Very large data bases. Vol. 3. — Tokyo, Japan : IEEE Computer Society, Oct. 1977. — Pp. 370–378.
4.Majumdar A. K., Bhattacharyya P. Database management systems. — McGraw-Hill Education (India)
Pvt Limited, 2001. — ISBN 9780074622391. — URL: http://books.google.ru/books?id=fT6-
ziSWBcYC.
5.Ramakrishnan R., Gehrke J. Relational Calculus // Database management systems. — 3rd ed. — New York : McGraw-Hill Companies, Incorporated, 2003. — Pp. 103–111. — (McGraw-Hill international editions: Computer science series). — ISBN 9780072465631.
§5. Случаи неполной информации и ω-значения
Вповседневной жизни часто приходится сталкиваться с проблемой отсутствия некоторой информации. Поэтому в системах баз данных должен существовать механизм обработки подобных ситуаций. На практике наиболее типичный подход к решению этой проблемы основан на применении неопределенных значений (!-значений, NULL-значений) и трёхзначной логики.
5.1.Концепция трехзначной логики
Втрехзначной логике кроме значений «истина» (T) и «ложь» (F) есть еще значение «неизвест-
но» (U1).
Логические операторы
Таблица истинности для стандартных операций конъюнкции, дизъюнкции и отрицания имеют вид:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x ^ y |
T |
U |
F |
|
x _ y |
T |
U |
F |
|
|
x |
x |
x |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
T |
T |
U |
F |
|
T |
T T T |
|
|
T |
F |
F |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
U |
U U |
F |
|
U |
T |
U |
U |
|
U |
U |
T |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
F |
F F F |
|
F |
T |
U |
F |
|
|
F |
T |
F |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Эти таблицы построены с точки зрения «человеческой» логики, математически они могут быть построены на основе операторов min (для конъюнкции), max (для дизъюнкции) и отрицания Лукашевича s x 1 x, если интерпретировать T как 1, U как 1{2 и F как 0.
В последней таблице представлен дополнительный оператор — модальность «возможно» (maybe). Он приведен лишь в качестве примера одного из дополнительных операторов трехзначной логики, используемых для упрощения условий запросов.
Продемонстрируем применение оператора на примере запроса: «получить информацию о сотрудниках, которые могут быть (но это точно неизвестно) программистами и работают в Лондоне». Предположим, что все интересующие данные находятся в одном отношении R в атрибутах job (работа) и city (город). Тогда на языке исчисления кортежей (вернее, его небольшой модификации в связи с введением третьего значения истинности) запрос примет вид:
! )
T |pT P Rq ^ pT :city ’Лондон’q ^ pT :job ’Программист’q
1 U от англ. „unknown“ — «неизвестный». При этом стоит заметить, что выражения X U и X ! разные: первое означает, что значение переменной X известно и равно U, а второе — что значение переменной X неизвестно.
26