ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.03.2021
Просмотров: 1583
Скачиваний: 23
141
СД
ДП
ПС
С
Д
Д
П
П
С
И
Ф
Ф
К
К
И
И
М
М
С
С
И
П
Ф
Ф
С
С
П
Рис
Декомпозиция
отношения
СТУД
_
ДИСЦ
_
ПРЕП
(
СДП
)
Возникает
вопрос
,
почему
необходима
декомпозиция
на
три
,
а
не
на
два
отношения
.
Можно
,
однако
,
увидеть
,
что
соединение
любых
двух
из
этих
отношений
не
обеспечивает
восстановления
исходного
отношения
.
Например
,
результатом
соединения
отношений
СД
и
ДП
по
атрибуту
Д
будет
отношение
СД
-
ДП
С
Д
П
И
Ф
К
И
Ф
С
И
М
С
П
Ф
К
←
лишний
кортеж
П
Ф
С
Рис
Соединение
отношений
СД
и
ДП
Видно
,
что
это
отношение
не
совпадает
с
исходным
отношением
СДП
(
рис
В
нем
имеется
лишний
кортеж
{
П
,
Ф
,
К
},
которого
не
было
в
отношении
СДП
.
Если
же
еще
выполнить
соединение
этого
отношения
СД
-
ДП
(
рис
с
третьим
отношением
ПС
(
рис
по
атрибутам
П
и
С
,
то
нетрудно
увидеть
,
что
лишний
кортеж
будет
исключен
и
исходное
отношение
СДП
будет
полностью
восстановлено
.
Поскольку
рассматриваемое
3
Д
-
ограничение
удовлетворяется
тогда
и
только
тогда
,
когда
отношение
равносильно
соединению
трех
его
проекций
,
такое
ограничение
еще
называют
зависимостью
соединения
(
или
зависимостью
проекции
-
соединения
).
Зависимость
соединения
(
join dependency
)
является
таким
же
семантическим
ограничением
данного
отношения
,
как
многозначная
и
функциональная
зависимости
.
Определение
зависимости
соединения
имеет
следующий
вид
.
Пусть
R
является
отношением
,
а
А
,
В
, …, Z –
произвольным
подмножеством
множества
атрибутов
отношения
R.
Отношение
R
удовлетворяет
зависимости
соединения
*
(
А
,
В
, …, Z
)
тогда
и
только
тогда
,
когда
оно
равносильно
соединению
своих
проекций
с
подмножествами
атрибутов
А
,
В
, …, Z.
142
Таким
образом
,
для
рассматриваемого
в
этом
разделе
отношения
СДП
(
рис
можно
записать
,
что
оно
удовлетворяет
зависимости
соединения
*(
СД
,
ДП
,
ПС
)
и
для
устранения
аномалий
операций
обновления
может
быть
представлено
своими
тремя
проекциями
{
С
,
Д
}, {
Д
,
П
}
и
{
П
,
С
}.
Сравним
приведенные
определения
зависимости
соединения
с
рассмотренной
выше
теоремой
Фейгина
.
Напомним
ее
:
Отношение
R
{
А
,
В
,
С
}
может
быть
декомпозировано
без
потерь
на
проекции
с
атрибутами
{
А
,
В
}
и
{
А
,
С
}
тогда
и
только
тогда
,
когда
для
отношения
R
выполняются
многозначные
зависимости
А
→
→
В
(
и
А
→
→
С
)
.
Можно
видеть
,
что
фактически
многозначная
зависимость
А
→
→
В
эквивалентна
(
является
частным
случаем
)
зависимости
соединения
*(
АВ
,
АС
).
Другими
словами
,
зависимость
соединения
является
обобщением
многозначной
зависимости
,
так
же
,
как
ранее
многозначная
зависимость
оказалась
обобщением
функциональной
зависимости
.
И
,
наоборот
,
многозначная
зависимость
является
частным
случаем
зависимости
соединения
,
а
функциональная
зависимость
–
частным
случаем
многозначной
зависимости
.
Таким
образом
,
мы
выяснили
,
что
отношение
может
находиться
в
четвертой
нормальной
форме
,
но
,
тем
не
менее
,
у
него
могут
быть
проблемы
операций
обновления
,
связанные
с
наличием
в
нем
зависимости
соединения
,
не
являющейся
многозначной
зависимостью
(
в
четвертой
нормальной
форме
многозначные
зависимости
отсутствуют
).
Эти
проблемы
могут
быть
решены
путем
декомпозиции
отношения
на
три
или
большее
число
его
проекций
.
Тем
самым
отношение
приводится
к
,
так
называемой
,
пятой
нормальной
форме
.
Дадим
ее
определение
.
Определение
пятой
нормальной
формы
.
Отношение
R
находится
в
пятой
нормальной
форме
(5
НФ
),
которая
также
называется
проекционно
-
соединительной
нормальной
формой
,
тогда
и
только
тогда
,
когда
каждая
зависимость
соединения
в
отношении
R
подразумевается
потенциальными
ключами
отношения
R.
Другими
словами
,
в
отношении
присутствуют
только
функциональные
зависимости
атрибутов
от
потенциальных
ключей
.
Пятая
нормальная
форма
является
окончательной
нормальной
формой
по
отношению
к
операциям
проекции
и
соединения
.
143
10.9.
Итоговая
схема
процедуры
нормализации
Рассмотренные
в
предыдущих
разделах
материалы
по
нормализации
отношений
путем
их
декомпозиции
без
потерь
,
с
целью
устранения
нежелательных
проблем
при
выполнении
операций
обновления
данных
можно
свести
к
последовательности
этапов
,
обеспечивающих
пошаговое
преобразование
отношений
в
последующие
нормальные
формы
вплоть
до
пятой
нормальной
формы
.
Эти
этапы
формулируются
следующим
образом
:
1.
Отношение
в
первой
нормальной
форме
разбивается
на
две
проекции
для
исключения
всех
функциональных
зависимостей
,
ключевых
атрибутов
от
первичного
ключа
,
которые
не
являются
неприводимыми
.
В
результате
получаются
отношения
во
второй
нормальной
форме
.
2.
Отношение
во
второй
нормальной
форме
разбивается
на
две
проекции
для
исключения
всех
транзитивных
функциональных
зависимостей
.
Этот
этап
приводит
к
отношениям
в
третьей
нормальной
форме
.
3.
Отношение
в
третьей
нормальной
форме
разбивается
на
две
проекции
для
исключения
детерминантов
,
не
являющихся
первичными
ключами
.
Получаем
отношения
в
нормальной
форме
Бойса
-
Кодда
.
4.
Отношение
в
нормальной
форме
Бойса
-
Кодда
разбивается
на
две
проекции
для
исключения
многозначных
зависимостей
для
приведения
в
четвертую
нормальную
форму
.
5.
Отношение
в
четвертой
нормальной
форме
разбивается
на
n
проекций
для
исключения
любых
зависимостей
проекции
-
соединения
,
которые
не
являются
функциональными
зависимостями
от
потенциальных
ключей
.
При
этом
важно
то
,
что
декомпозиция
отношений
на
проекции
должна
осуществляться
без
потерь
и
с
сохранением
зависимостей
.
Можно
обратить
внимание
на
предложенные
Фейгиным
интересные
альтернативные
определения
нормальной
формы
Бойса
-
Кодда
,
четвертой
нормальной
формы
и
пятой
нормальной
формы
.
Отношение
R
находится
в
нормальной
форме
Бойса
-
Кодда
тогда
и
только
тогда
,
когда
каждая
функциональная
зависимость
подразумевается
потенциальными
ключами
отношения
R
.
Отношение
R
находится
в
четвертой
нормальной
форме
тогда
и
только
тогда
,
когда
каждая
многозначная
зависимость
подразумевается
потенциальными
ключами
отношения
R
.
Отношение
R
находится
в
пятой
нормальной
форме
тогда
и
только
тогда
,
когда
каждая
зависимость
соединения
подразумевается
потенциальными
ключами
отношения
R
.
11.
Структуры
хранения
данных
и
методы
доступа
В
данном
разделе
рассматриваются
некоторые
вопросы
физического
хранения
данных
,
хранящимся
на
внешних
запоминающих
устройствах
прямого
доступа
,
то
есть
,
прежде
всего
,
дисковых
запоминающих
устройств
,
и
доступа
к
хранимым
данным
при
выполнении
информационных
запросов
пользователей
.
Ранее
,
в
разделе
была
рассмотрена
трехуровневая
архитектура
систем
с
базами
данных
.
Как
уже
говорилось
выше
,
одной
из
причин
введения
нескольких
уровней
представления
данных
является
обеспечение
независимости
прикладных
программных
систем
от
конкретных
структур
и
способов
организации
данных
при
их
хранении
на
физических
носителях
.
Такая
независимость
позволяет
при
разработке
прикладных
информационных
систем
использовать
более
высокоуровневые
и
абстрактные
формы
(
модели
)
представления
данных
максимально
приближенные
к
понятиям
моделируемой
предметной
области
.
Это
позволяет
существенно
облегчить
процесс
создания
сложных
информационных
систем
,
не
загружая
его
необходимостью
оперирования
деталями
,
связанными
с
представлением
данных
на
более
низких
,
в
том
числе
и
физическом
,
уровнях
.
Однако
,
на
практике
,
к
сожалению
,
обеспечить
полную
независимость
и
изолированность
различных
уровней
представления
данных
при
проектировании
прикладных
информационных
систем
не
удается
.
Одной
из
главных
причин
является
требование
обеспечения
эффективного
доступа
прикладной
системы
к
хранимым
данным
,
эффективного
с
точки
зрения
минимизации
времени
доступа
к
данным
.
Выбор
же
решений
наиболее
эффективных
с
точки
зрения
времени
выполнения
запросов
предполагает
знание
особенностей
выполнения
реализующих
их
процессов
,
происходящих
в
подсистемах
,
представляющих
более
низкие
уровни
архитектуры
информационной
системы
.
Например
,
при
использовании
для
работы
с
данными
языка
SQL,
один
и
тот
же
результат
может
быть
получен
с
помощью
различных
эквивалентных
форм
запросов
.
Реальное
же
время
выполнения
этих
запросов
может
оказаться
существенно
разным
,
особенно
при
большом
объеме
обрабатываемых
данных
.
В
связи
с
этим
,
для
выбора
наиболее
эффективного
варианта
грамотный
разработчик
уже
на
этапе
формирования
SQL-
запроса
должен
понимать
,
в
последовательность
каких
алгебраических
операций
будет
преобразован
конкретный
запрос
,
исполняющей
его
подсистемой
СУБД
,
и
,
более
того
,
какие
действия
могут
потребоваться
для
физического
доступа
к
запрашиваемым
145
данным
на
конкретном
носителе
от
дисковой
подсистемы
долговременного
хранения
данных
.
Необходимость
повышенного
внимания
к
структурам
хранимых
данных
и
методам
доступа
к
ним
обусловлено
тем
,
что
реальное
время
доступа
к
данным
в
системах
дисковой
памяти
существенно
больше
времени
доступа
к
данным
,
размещенным
в
оперативной
памяти
компьютера
.
11.1.
Хранение
отношений
и
доступ
к
хранимым
данным
Рассмотрим
основные
принципы
,
используемые
для
хранения
отношений
на
дисковых
запоминающих
устройствах
,
и
методы
организации
доступа
к
хранимым
данным
.
На
рис
приведена
схема
взаимодействия
СУБД
с
другими
подсистемами
,
участвующими
в
процессах
доступа
к
хранимым
данным
.
Рис
Схема
взаимодействия
СУБД
,
диспетчера
файлов
и
диспетчера
дисков
при
доступе
к
хранимым
данным
Схематично
,
с
точки
зрения
СУБД
,
отношения
базы
данных
выглядят
как
набор
записей
файлов
.
Обычно
записи
файлов
это
кортежи
отношения
.
Каждая
запись
обладает
уникальным
системным
идентификатором
(RowID),
который
Хранимая
база
данных
Система
управ
-
ления
дисками
Файловая
система
ОС
СУБД
Запрос
хранимой
записи
данных
Возвращение
хранимой
записи
Возвращение
хранимой
страницы
Чтение
данных
с
диска
Запрос
хранимой
страницы
Дисковая
операция
ввода
/
вывода