- •Введение.
- •Информация и данные.
- •Выч. Система
- •Админ-р
- •Жизненный цикл БнД.
- •Классификация БнД.
- •Преимущества организации субд.
- •Недостатки организации бд.
- •Проектирование бд. (общий подход)
- •Независимость данных (2 уровня).
- •Концептуальное проектирование. Модели данных. Модель сущность-связь.
- •Инфологические мд.
- •Модель результ.
- •Объединение локальных моделей в глобальные.
- •Логическое проектирование.
- •Сетевая модель данных.
- •Правила построения сетевой модели.
- •Реляционная модель данных.
- •Плоский файл.
- •Хронологическая модель данных.
- •Операции над данными.
- •Операции реляционной алгебры.
- •Операторы обновления:
- •Реляционные сравнения:
- •Реляционное исчисление с переменными-кортежами.
- •Реляционное исчисление с переменными на доменах.
- •Реляционные ямд.
- •Язык запросов в sql.
- •Защита баз данных.
- •Функциональные зависимости.
- •Покрытие множества зависимостей.
- •Вычисление замыканий.
- •Декомпозиция схем отношений.
- •Нормализация отношений.
- •Алгоритм1: пополняющий декомпозицию схем отношений, которая обладает свойством соединения без потерь и приводит к отношениям находящимся в нфбк.
- •Алгоритм 2: приведения отношения к 3нф, использующей декомпозицию, сохраняющую функциональные зависимости.
- •Многозначные зависимости.
- •Правила вывода (аксиомы) для многозначных зависимостей.
- •Аксиомы, связывающие функциональные зависимости и многозначные зависимости.
- •Правила вывода:
- •Алгоритм вычисления базиса:
- •Секретность данных.
- •Физическая организация бд.
- •Методы доступа к данным.
- •Оптимизация запросов.
- •Общие стратегии оптимизации:
- •Законы оптимизации.
- •Алгоритм оптимизации выражений ра.
- •Точная оптимизация для подмножества реляционных запросов.
- •Минимизация конъюнктивных запросов.
- •Правила построения табло запросов:
- •Метод нахождения min-го запроса для простого тз.
- •Параллельные операции над бд.
- •Основные понятия.
- •Бесконечные ожидания и тупики.
- •Протоколы и расписание.
- •Простая модель транзакции.
- •Метод, позволяющий определить сериализуемость расписания.
- •Модель с блокировками для чтения и записи.
- •Параллельный доступ к иерархически структурированным элементам.
- •Алгоритм проверки сериализуемости расписания.
- •Защита от отказов.
- •Меры для восстановления бд.
- •Модификация запросов в распределенных бд.
- •Фрагменты отношений.
Правила вывода (аксиомы) для многозначных зависимостей.
А1. (дополнение для многозначной зависимости)
Если , то
А2. (пополнение для мн.з.)
Если и , то
А3. (транзитивность для мн.з.)
Если и , то
Аксиомы, связывающие функциональные зависимости и многозначные зависимости.
А4. (копирования)
Если , то
А5. (объединения)
Если и , и для некоторого , то имеем
Пример: ?
R |
Рейс(X) |
День(Y) |
Тип(Z) |
t1 |
106 |
пн. |
Ту-154 |
t2 |
106 |
чт. |
Ту-154 |
t3 |
106 |
пн. |
Ил-86 |
t4 |
106 |
чт. |
Ил-86 |
t1t4 +
t1t3 –
Утверждение1: Если отношение со схемой удовлетворяет многозначной зависимости и , то удовлетворяет и .
Утверждение 2: Пусть – отношение со схемой , а подмножества такие, что . Отношение удовлетворяет многозначной зависимости т. и т.т., когда существует декомпозиция отношения , обладающая свойством соединения без потерь. .
Правила вывода:
(объединения)
Если и , то
(псевдотранзитивность)
Если , то
(декомпозиции)
Существует обобщение формы Бойса-Кодда для многозначных зависимостей, которая называется 4НФ:
Пусть – схема отношения и множество зависимостей. находится в 4НФ, если . содержит ключ отношения .
Теорема: Если отношение находится в 4НФ относительно множества , то оно находится и в НФБК относительно множества функциональных зависимостей , .
Из 2) и 3) следует:
Утверждение: Пусть – множество всех атрибутов. Тогда можно построить разбиение на множествах такое, что при имеем т. и т.т., когда
Множества называются базисом зависимостей для . Базисы используются для проверки: имеет ли место многозначная зависимость (проверяется, является ли объединением базисов)
Алгоритм вычисления базиса:
Входные данные: множество многозначных зависимостей , заданное на множестве атрибутов и множество .
Выходные данные: базис зависимостей относительно .
Пусть множество всех подмножеств множества такого, что имеем и есть либо , либо .
До тех пор, пока не превратится в совокупность не пересекающихся множеств, будем находить в нем очередную пару не пересекающихся множеств и , и заменять ее множествами , , , отбрасывая пустое множество в том случае, если одно из и содержится в другом.
Пусть в результате получаем совокупность .
До тех пор, пока возможны изменения в , будем находить зависимости , и некоторое множество в такое, что ; . Заменяем в на и .
Полученная совокупность есть базис зависимостей для .
Метод построения декомпозиции обладает свойством соединения без потерь.
Теорема: Пусть – схема отношения и – декомпозиция . Задано множество функциональных и многозначных зависимостей на : Тогда обладает свойством соединения без потерь т. и т.т., когда имеет место многозначная зависимость (или по пр. дополнения ).
Алгоритм построения декомпозиции отношения R, обладающего свойством соединения без потерь, может быть обобщен и на случай многозначной зависимости.
Приведение отношений к нормальной форме обеспечивает целостность данных.
Если отношение находится в 3НФ, то несколько несложных правил помогают сохранить семантическую целостность при операциях проектирования и соединения:
Проектирование корректно, если получающееся в результате отношение содержит тот же самый ключ, что и исходное отношение, или эквивалентный возможный ключ.
Отношение можно соединять с отношением , если:
а) ключ отношения является атрибутом отношения ;
б) ключ отношения однозначно определяется атрибутами отношения .
В общем случае секретность может быть нарушена при: сбое оборудования, ошибке оператора, программной ошибке в СУБД или операционной системе, или в прикладной программе.
Основная идея обеспечения ограничений целостности данных заключается в том, чтобы использовать ЯМД как средство выражения этих ограничений. Декларация ограничений целостности содержит 2 части. В первой из них должно быть выражено само ограничение, а во второй – описывается когда, при каких условиях должна выполняться сама проверка.
ЯМД реальных систем позволяет в той или иной мере поддерживать, если не все, то многие из рассмотренных ограничений целостности.