- •Введение.
- •Информация и данные.
- •Выч. Система
- •Админ-р
- •Жизненный цикл БнД.
- •Классификация БнД.
- •Преимущества организации субд.
- •Недостатки организации бд.
- •Проектирование бд. (общий подход)
- •Независимость данных (2 уровня).
- •Концептуальное проектирование. Модели данных. Модель сущность-связь.
- •Инфологические мд.
- •Модель результ.
- •Объединение локальных моделей в глобальные.
- •Логическое проектирование.
- •Сетевая модель данных.
- •Правила построения сетевой модели.
- •Реляционная модель данных.
- •Плоский файл.
- •Хронологическая модель данных.
- •Операции над данными.
- •Операции реляционной алгебры.
- •Операторы обновления:
- •Реляционные сравнения:
- •Реляционное исчисление с переменными-кортежами.
- •Реляционное исчисление с переменными на доменах.
- •Реляционные ямд.
- •Язык запросов в sql.
- •Защита баз данных.
- •Функциональные зависимости.
- •Покрытие множества зависимостей.
- •Вычисление замыканий.
- •Декомпозиция схем отношений.
- •Нормализация отношений.
- •Алгоритм1: пополняющий декомпозицию схем отношений, которая обладает свойством соединения без потерь и приводит к отношениям находящимся в нфбк.
- •Алгоритм 2: приведения отношения к 3нф, использующей декомпозицию, сохраняющую функциональные зависимости.
- •Многозначные зависимости.
- •Правила вывода (аксиомы) для многозначных зависимостей.
- •Аксиомы, связывающие функциональные зависимости и многозначные зависимости.
- •Правила вывода:
- •Алгоритм вычисления базиса:
- •Секретность данных.
- •Физическая организация бд.
- •Методы доступа к данным.
- •Оптимизация запросов.
- •Общие стратегии оптимизации:
- •Законы оптимизации.
- •Алгоритм оптимизации выражений ра.
- •Точная оптимизация для подмножества реляционных запросов.
- •Минимизация конъюнктивных запросов.
- •Правила построения табло запросов:
- •Метод нахождения min-го запроса для простого тз.
- •Параллельные операции над бд.
- •Основные понятия.
- •Бесконечные ожидания и тупики.
- •Протоколы и расписание.
- •Простая модель транзакции.
- •Метод, позволяющий определить сериализуемость расписания.
- •Модель с блокировками для чтения и записи.
- •Параллельный доступ к иерархически структурированным элементам.
- •Алгоритм проверки сериализуемости расписания.
- •Защита от отказов.
- •Меры для восстановления бд.
- •Модификация запросов в распределенных бд.
- •Фрагменты отношений.
Операторы обновления:
РМ кроме РА может включать операции реляционного присвоения. Операция присвоения дает возможность «запоминать» значение некоторых алгебраических выражений в БД и т.о. изменять состояние БД, т.е. обновлять ее.
Присвоение – это грубая операция, потому что она позволяет только полностью заменить значение отношения.
, где – реляционные выражения, представляющие совместимые по типу отношения.
Операцию присвоения можно теоретически использовать для описания более точных операций: вставки и удаления:
, где – тоже отношение, состоящее из одного кортежа.
Но операции объединения и разности не позволяют должным образом обрабатывать ошибки. Так, при выполнении операции объединения не пресекается попытка вставки уже существующего кортежа, а при операции удаления – удаление несуществующего кортежа. Поэтому используются явные операции вставки, обновления и удаления:
Значение отношения вычисляется, и все кортежи результата вставляются в отношение .
в – может быть реляционным выражением.
– скалярное выражение.
(может быть выражение)
Все эти операции действуют на уровне множеств. Множество кортежей обновляется; вставляется; удаляется.
Реляционные сравнения:
РА в том виде, в котором она была изначально определена, не поддерживала прямого сравнения двух отношений. Например, является ли одно подмножеством другого.
– арифметический оператор сравнения
Для определения, является ли отношение пустым, используется функция, возвращающая логическое значение: истина, если отношение пусто, ложь – в противном случае.
Реляционное исчисление с переменными-кортежами.
Аналогично тому, как РА использует в качестве операндов отношения, РИ кортежей строит свои выражения из кортежей.
Выражение в РИ строятся из атомов. Атомы могут быть трех типов:
, где – имя отношения, а – переменная-кортеж. Этот атом означает, что есть кортеж отношения .
, где и – переменные-кортежи, – арифметический оператор сравнения; – номера столбцов кортежей и соответственно. Этот атом означает, что -й компонент находится в отношении с -й компонентой .
ti θС, Сθti , где и – то же, что в 2); С = . Этот атом означает, что -й компонент кортежа находится в отношении с константой С.
Переменная называется связанной, если этой переменной в формуле предшествует квантор или . В противном случае переменная называется свободной.
Выражение определяется рекурсивно следующим образом:
Каждый атом является выражением. Переменные в выражении являются свободными или связанными в зависимости от того, были ли они свободными или связанными в атоме.
Если φ1 и φ2 – выражения РИ, то φ1 φ2, φ1 φ2, ¬φi – также выражения РИ. В результирующем выражении переменные будут свободными или связанными так же, как они были свободными или связанными в выражениях φ1 и φ2.
Если φ – формула, то – формула, которая утверждает, что существуют значения , при подстановке которых вместо всех свободных вхождений переменной в формулу , эта формула становится истинной. Переменная становится связанной, остальные свободны или связанны в зависимости от того, свободны они или связанны в формуле .
Если φ – формула, то – формула. Эта формула утверждает, что какое бы значение подходящей арности мы не подставляли вместо свободных вхождений в , формула является истинной. Лает то же, что в 3).
Формулы могут заключаться в скобки. Если их нет, то приоритет операций:
Ничто другое не является формулой.
Таким образом, формула в РИ с переменными-кортежами есть выражение вида , где – единственная свободная переменная-кортеж. А само исчисление кортежей определяется так же, как РИ только с другим О.
Пример:
РИ с переменными-кортежами в том виде, в каком его определили, позволяет представить некоторые бесконечные отношения. Например, означает все возможные не принадлежащие кортежи. Для того чтобы этого избежать вводится понятие безопасных выражений, для которых каждый компонент любого кортежа , удовлетворяющий , должен быть элементом множества .
D(φ) - множество символов, которые явно появляются в выражении φ, либо являются компонентами какого-либо кортежа отношения , упомянутого в φ. Множество является функцией отношений, которые должны подставляться вместо переменных отношения в . Т.к. – все отношения предполагаются конечными, то и множество конечно.
Rj имеет nj компонент, – множество констант.
Выражение реляционного исчисления с переменными-кортежами называется безопасным, если выполняются условия:
Всякий раз, когда кортеж t удовлетворяет выражению φ, каждая компонента кортежа t принадлежит множеству D(φ).
Для любого подвыражения вида , входящего в выражение , каждый компонент , если t удовлетворяет .
Если для любого подвыражения вида , входящего в выражение , каждый компонент , то t будет удовлетворять выражению .
Условие 3 может показаться не интуитивным, но мы должны заметить, что формула эквивалентна . Последняя является безопасной, если для которого истинно и . Домены и одни и те же, следовательно, условие 3 устанавливает, что формула безопасна, когда безопасна формула .
Пример безопасного выражения:
Пусть – формула такая, что любая ее подформула вида и безопасна. Тогда безопасно каждое выражение вида
(*),
т.к. любое , удовлетворяющее (*), принадлежит , в силу чего каждый из его компонентов принадлежит . Например, такой вид имеет формула разности множеств: при .
Обобщения: безопасным является выражение:
должны быть символом, появляющемся в -ом компоненте кортежа из . Такой вид имеет проекция
.
На основании приведенных условий можно утверждать, что если – формула, в которой любая подформула вида или безопасна, то безопасно выражение вида (*), т.к. любой кортеж , удовлетворяющий этой формуле, принадлежит . Следовательно, любая компонента выражения (*).
Если φ состоит из подвыражений φ1 и φ2, связанных связками , и каждое φi может быть определено правилами 1-3, то безопасность выражения φ определяется безопасностью выражений φ1 и φ2.
Безопасные выражения РИ с переменными-кортежами эквивалентны РА.
Теорема: Если существует выражение РА, то существует эквивалентное ему безопасное выражение в РИ с переменными-кортежами.