- •Введение.
- •Информация и данные.
- •Выч. Система
- •Админ-р
- •Жизненный цикл БнД.
- •Классификация БнД.
- •Преимущества организации субд.
- •Недостатки организации бд.
- •Проектирование бд. (общий подход)
- •Независимость данных (2 уровня).
- •Концептуальное проектирование. Модели данных. Модель сущность-связь.
- •Инфологические мд.
- •Модель результ.
- •Объединение локальных моделей в глобальные.
- •Логическое проектирование.
- •Сетевая модель данных.
- •Правила построения сетевой модели.
- •Реляционная модель данных.
- •Плоский файл.
- •Хронологическая модель данных.
- •Операции над данными.
- •Операции реляционной алгебры.
- •Операторы обновления:
- •Реляционные сравнения:
- •Реляционное исчисление с переменными-кортежами.
- •Реляционное исчисление с переменными на доменах.
- •Реляционные ямд.
- •Язык запросов в sql.
- •Защита баз данных.
- •Функциональные зависимости.
- •Покрытие множества зависимостей.
- •Вычисление замыканий.
- •Декомпозиция схем отношений.
- •Нормализация отношений.
- •Алгоритм1: пополняющий декомпозицию схем отношений, которая обладает свойством соединения без потерь и приводит к отношениям находящимся в нфбк.
- •Алгоритм 2: приведения отношения к 3нф, использующей декомпозицию, сохраняющую функциональные зависимости.
- •Многозначные зависимости.
- •Правила вывода (аксиомы) для многозначных зависимостей.
- •Аксиомы, связывающие функциональные зависимости и многозначные зависимости.
- •Правила вывода:
- •Алгоритм вычисления базиса:
- •Секретность данных.
- •Физическая организация бд.
- •Методы доступа к данным.
- •Оптимизация запросов.
- •Общие стратегии оптимизации:
- •Законы оптимизации.
- •Алгоритм оптимизации выражений ра.
- •Точная оптимизация для подмножества реляционных запросов.
- •Минимизация конъюнктивных запросов.
- •Правила построения табло запросов:
- •Метод нахождения min-го запроса для простого тз.
- •Параллельные операции над бд.
- •Основные понятия.
- •Бесконечные ожидания и тупики.
- •Протоколы и расписание.
- •Простая модель транзакции.
- •Метод, позволяющий определить сериализуемость расписания.
- •Модель с блокировками для чтения и записи.
- •Параллельный доступ к иерархически структурированным элементам.
- •Алгоритм проверки сериализуемости расписания.
- •Защита от отказов.
- •Меры для восстановления бд.
- •Модификация запросов в распределенных бд.
- •Фрагменты отношений.
Алгоритм1: пополняющий декомпозицию схем отношений, которая обладает свойством соединения без потерь и приводит к отношениям находящимся в нфбк.
Входные данные: схема отношения и функциональные зависимости .
Выходные данные: декомпозиция , обладающая свойством соединения без потерь, такая, что каждая схема отношения в декомпозиции находится в НФБК относительно проекции на эту схему.
Метод: декомпозиция для конструируется итеративным методом
. Существует ключ . Если схема отношения из и не находится в НФБК, то пусть – зависимость, имеющая место в , где не содержит ключа , а .
Тогда в должен существовать некоторый атрибут, который не принадлежит и не принадлежит . В противном случае содержал бы ключ . Заменим на и , где состоит из и атрибутов , а – из всех атрибутов , за исключением . и . (это удаление транзитивной зависимости .
Декомпозиция на и обладает свойством соединения без потерь относительно множества функциональных зависимостей, спроецированных на . Если в и существуют транзитивные зависимости, то делаем декомпозиции и для . Т.к. в и меньше атрибутов, чем в , мы достигнем в конце концов некоторого момента, когда любая схема отношения в будет находиться в НФБК. При этом обладает свойством соединения без потерь, т.к. начальное состояние состоит только из , и все модификации сохраняли свойство соединения без потерь.
Алгоритм 2: приведения отношения к 3нф, использующей декомпозицию, сохраняющую функциональные зависимости.
Входные данные: схема отношения и множество функциональных зависимостей .
Выходные данные: сохраняющая зависимости декомпозиция схемы отношения такая, что каждая входящая в нее схема отношения находится в 3НФ относительно проекции на эту схему.
Метод: если существует некоторый атрибут в , участвующий в левой или правой части какой-либо зависимости из , то этот атрибут может сам по себе образовать некоторую схему отношения и его можно исключить из . Если в одной из зависимостей участвуют все атрибуты , то выходные данные образуют само . В противном случае декомпозиция, образующая выходные данные, состоит из схемы для каждой зависимости в . Если, однако, в имеются зависимости , то может быть использована схема вместо , и такая подстановка является предпочтительной.
Теорема: Пусть декомпозиция , образованная схемами отношений в 3НФ и построенная по алгоритму 2. Пусть ключ . Тогда декомпозиция такая, что все ее схемы отношений находятся в 3НФ. Эта декомпозиция сохраняет зависимости и обладает свойством соединения без потерь.
Пример:
В декомпозицию будут входить
Многозначные зависимости.
Кроме рассмотренных функциональных зависимостей существует другой вид зависимости – многозначная.
Пусть задана схема отношений , атрибуты . Существует (X мультиопределяет Y) – многозначная зависимость, если:
Из симметрии определения и следует, что в существует :
.
X Y Z
t 1
t 2
t 3