Базы данных. Вводный курс

Сергей Кузнецов

Назад Содержание Вперёд

9.3. Зависимости проекции/соединения и пятая нормальная форма

Приведение отношения к 4NF предполагает его декомпозицию без потерь на две проекции (как и в случае 2NF, 3NF и BCNF). Однако бывают (хотя и нечасто) случаи, когда декомпозиция без потерь на две проекции невозможна, но можно произвести декомпозицию без потерь на большее число проекций. Будем называть n-декомпозируемым отношением отношение, которое может быть декомпозировано без потерь на n проекций. До сих пор мы имели дело с 2-декомпозируемыми отношениями.

9.3.1. N-декомпозируемые отношения

Начнем с еще одного определения.

В переменной отношения R с атрибутами (возможно, составными) A и B MVD AB называется тривиальной, если либо AB, либо A UNION B совпадает с заголовком отношения R.

Тривиальная MVD всегда удовлетворяется. При AB она вырождается в тривиальную FD. В случае A UNION B = HR требования многозначной зависимости соблюдаются очевидным образом.

Для примера n-декомпозируемого отношения при n > 2 рассмотрим пятый вариант переменной отношения СЛУЖ_ПРО_ЗАДАН, в которой имеется единственно возможный ключ {СЛУ_НОМ, ПРО_НОМ, СЛУ_ЗАДАН} и отсутствуют нетривиальные MVD. Пример значения переменной отношения приведен на рис. 9.3.

Как показано на рис. 9.3, результат естественного соединения проекций СЛУЖ_ПРО_НОМ и ПРО_НОМ_ЗАДАН почти совпадает с телом исходного отношения СЛУЖ_ПРО_ЗАДАН, но в нем присутствует один лишний кортеж, который исчезнет после выполнения заключительного естественного соединения с проекцией СЛУЖ_ЗАДАНИЕ. Читателям предлагается убедиться, что исходное отношение будет восстановлено при любом порядке естественного соединения трех проекций.

9.3.2. Зависимость проекции/соединения

Утверждение о том, что значение отношения СЛУЖ_ПРО_ЗАДАН восстанавливается без потерь путем естественного соединения его проекций СЛУЖ_ПРО_НОМ, ПРО_НОМ_ЗАДАН и СЛУЖ_ЗАДАНИЕ эквивалентно следующему утверждению (BСПЗ, BСПН, BПНЗ и BСЗ обозначают тела значений переменных отношений СЛУЖ_ПРО_ЗАДАН, СЛУЖ_ПРО_НОМ, ПРО_НОМ_ЗАДАН и СЛУЖ_ЗАДАНИЕ соответственно):

IF ({сн, пн}  BСПН AND {пн, сз}  BСПЗ AND {сн, сз}  BСЗ)
THEN {сн, пн, сз}  BСПЗ
        

Чтобы возможность восстановления без потерь отношения СЛУЖ_ПРО_ЗАДАН путем естественного соединения его проекций СЛУЖ_ПРО_НОМ, ПРО_НОМ_ЗАДАН и СЛУЖ_ЗАДАНИЕ существовала при любом допустимом значении переменной отношения СЛУЖ_ПРО_ЗАДАН, должно поддерживаться следующее ограничение:

IF ({сн1, пн1, сз2}  BСПЗ AND {сн2, пн1, сз1}  BСПЗ
    AND {сн1, пн2, сз1}  BСПЗ)
THEN {сн1, пн1, сз1}  BСПЗ
        

Это обычное ограничение реального мира, которое для отношения СЛУЖ_ПРО_ЗАДАН может быть сформулировано на естественном языке следующим образом:

Если служащий с номером сн участвует в проекте пн, и в проекте пн выполняется задание сз, и служащий с номером сн выполняет задание сз, то служащий с номером сн выполняет задание сз в проекте пн.

В общем виде такое ограничение называется зависимостью проекции/соединения. Вот формальное определение.

Пусть задана переменная отношения R, и A, B, …, Z являются произвольными подмножествами заголовка R (составными, перекрывающимися атрибутами). В переменной отношения R удовлетворяется зависимость проекции/соединения (Project-Join Dependency – PJD) *( A, B, …, Z) тогда и только тогда, когда любое допустимое значение r переменной отношения R можно получить путем естественного соединения проекций этого значения на атрибуты A, B, …, Z.

Рис. 9.3.  Возможное значение переменной отношения СЛУЖ_ПРО_ЗАДАН (пятый вариант), результаты проекций и результат частичного естественного соединения

9.3.3. Аномалии, вызываемые наличием зависимости проекции/соединения

В переменной отношения СЛУЖ_ПРО_ЗАДАН выполняется PJD *({СЛУ_НОМ, ПРО_НОМ}, {ПРО_НОМ, СЛУ_ЗАДАН}, {СЛУ_НОМ, СЛУ_ЗАДАН}). Наличие такой PJD обеспечивает возможность декомпозиции отношения на три проекции, но возникает вопрос, зачем это нужно? Чем плохо исходное отношение СЛУЖ_ПРО_ЗАДАН? Ответ обычный: этому отношению свойственны аномалии обновления. Для примера предположим, что значением СЛУЖ_ПРО_ЗАДАН является отношение, показанное на рис. 9.4.

• Добавление кортежей. Если к ТСПЗ1 (рис. 9.4) добавляется кортеж <2941, 1, A>, то должен быть добавлен и кортеж <2934, 1, A>. Действительно, в теле отношения появятся кортежи <2934, 1, B>, <2941, 1, A> и <2934, 2, A>. Ограничение целостности требует включения и кортежа <2934, 1, A>. Интересно, что добавление кортежа <2934, 1, A> не нарушает ограничение целостности и, тем самым, не требует добавления кортежа <2941, 1, A>.

  
  Рис. 9.4.  Иллюстрации аномалий обновления в отношении СЛУЖ_ПРО_ЗАДАН при наличии зависимости соединения

• Удаление кортежа. Если из ТСПЗ2 удаляется кортеж <2934, 1, A>, то должен быть удален и кортеж <2941, 1, A>, поскольку в соответствии с ограничением целостности наличие второго кортежа означает наличие первого. Интересно, что удаление кортежа <2941, 1, A> не нарушает ограничения целостности и не требует дополнительных удалений.

9.3.4. Устранение аномалий обновления в 3-декомпозиции

После выполнения декомпозиции трудности с обновлением автоматически снимаются. Действительно, декомпозируем отношение СЛУЖ_ПРО_ЗАДАН на три отношения: СЛУЖ_ПРО_НОМ {СЛУ_НОМ, ПРО_НОМ}, СЛУЖ_ЗАДАНИЕ {СЛУ_НОМ, СЛУ_ЗАДАН} и ПРО_НОМ_ЗАДАН {ПРО_НОМ, СЛУ_ЗАДАН}. Результат декомпозиции значения переменной отношения СЛУЖ_ПРО_ЗАДАН с телом BСПЗ1 показан в верхней части рис. 9.5.

Теперь если мы хотим добавить данные о служащем с номером 2941, выполняющем задание A в проекте 1, то, естественно, вставим кортеж <2941, 1> в отношение СОТР-ПРО_НОМ, кортеж <2941, A> в отношение СОТР-ЗАДАНИЕ и кортеж <1, A> в отношение ПРО_НОМ-ЗАДАН. Результат этих операций показан в средней части рис. 9.5.

Но если выполнить естественное соединение декомпозированных отношений с телами, полученными после добавления данных о служащем с номером 2941, выполняющем задание A в проекте 1, то будет получено значение-отношение с заголовком отношения СЛУЖ_ПРО_ЗАДАН и телом BСПЗ2 (нижняя часть рис. 9.5). Тем самым, проведенная декомпозиция позволила избежать сложностей при выполнении добавления кортежей с получением корректных результатов.

Аналогично можно проиллюстрировать простоту и корректность операций удаления кортежей.

9.3.5. Пятая нормальная форма

Отношения СЛУЖ_ПРО_НОМ, СЛУЖ_ЗАДАНИЕ и ПРО_НОМ_ЗАДАН находятся в пятой нормальной форме, но, прежде чем привести ее определение, нам требуется ввести еще два важных понятия.

В переменной отношения R PJD *( A, B, …, Z) называется подразумеваемой возможными ключами в том и только в том случае, когда каждый составной атрибут A, B, …, Z является суперключом R, т. е. включает хотя бы один возможный ключ R.

В переменной отношения R зависимость проекции/соединения *(A, B, …, Z) называется тривиальной, если хотя бы один из составных атрибутов A, B, …, Z совпадает с заголовком R.

Рис. 9.5.  Иллюстрация декомпозиции отношения с зависимостью соединения

Легко убедиться, что нетривиальные PJD, подразумеваемые возможными ключами, существуют во всех отношениях с арностью, большей двух, первичный ключ которых не совпадает с заголовком отношения. Например, если в отношении СЛУЖ_ПРО_ЗАДАН атрибут СЛУ_НОМ является первичным ключом, то, очевидно, имеется PJD *({СЛУ_НОМ, ПРО_НОМ}, {СЛУ_НОМ, СЛУ_ЗАДАН}) (это следует из теоремы Хита). Но такие зависимости проекции/соединения неинтересны с точки зрения проектирования базы данных, поскольку не порождают аномалии обновления. Поэтому общепринятое определение пятой нормальной формы выглядит следующим образом.

Переменная отношения R находится в пятой нормальной форме, или в нормальной форме проекции/соединения (5NF, или PJ/NF – Project-Join Normal Form) в том и только в том случае, когда каждая нетривиальная PJD в R подразумевается возможными ключами R.

Таким образом, чтобы распознать, что данная переменная отношения R находится в 5NF, необходимо знать все возможные ключи R и все PJD этой переменной отношения. Обнаружение всех зависимостей соединения является нетривиальной задачей, и для ее решения нет общих методов. Поэтому на практике проектирование реляционных баз методом нормализации обычно завершается после достижения 4NF, и отношения, находящиеся в 4NF, как правило, находятся и в 5NF. Зачем же тогда была введена эта туманная и труднодостижимая пятая нормальная форма?

Ответ на этот естественный вопрос состоит в том, что 5NF является «окончательной» нормальной формой, которой можно достичь в процессе нормализации на основе проекций. «Окончательность» понимается в том смысле, что у отношения, находящегося в 5NF, отсутствуют аномалии обновлений, которые можно было бы устранить путем его декомпозиции. Другими словами, такие отношения далее нормализовать бессмысленно.

9.4. Заключение

Процесс проектирования реляционной базы на основе метода нормализации преследует две основных цели:

• избежать избыточности хранения данных;
• устранить аномалии обновления отношений.

Рассмотрим, насколько эти цели актуальны в современных условиях, когда объемы доступных носителей внешней памяти непрерывно возрастают, стоимость их падает, а современные серверы реляционных баз данных способны автоматически поддерживать целостность баз данных. Здесь следует отметить два важных обстоятельства.

Во-первых, теория реляционных баз данных и методы их проектирования активно развивались уже более 25 лет тому назад. Ситуация в области технологии аппаратуры и программного обеспечения тогда была совсем иной, чем сегодня, и хорошо нормализованные реляционные базы данных в значительной степени способствовали росту эффективности приложений.

Во-вторых, в то время реляционные базы преимущественно использовались в информационных системах оперативной обработки транзакций (On-Line Transaction Processing – OLTP). Характерные примеры таких систем мы отмечали в лекции 1 – банковские системы, системы резервирования билетов и мест в гостиницах. Системам категории OLTP свойственны частые обновления базы данных, поэтому аномалии обновлений, даже если их корректировка производится СУБД автоматически, могут заметно снижать эффективность приложения.

Сегодня на переднем крае приложений баз данных находятся системы категории оперативной аналитической обработки (On-Line Analytical Processing – OLAP). В подобных системах, в частности, системах поддержки принятия решений, базы данных в основном используются для выборки данных, поэтому аномалиями обновлений можно пренебречь, а объем этих баз настолько огромен, что можно пренебречь и избыточностью хранения.

Значит ли это, что подход к проектированию реляционных баз данных методом нормализации утратил свою роль? Нет!

Мир приложений баз данных в настоящее время огромен. Сегодня любое мало-мальски приличное предприятие использует хотя бы одно приложение баз данных – бухгалтерские, складские, кадровые системы. Это системы категории OLTP с частым обновлением данных и умеренными запросами к базе данных, не вызывающими соединений многих отношений. Для небольших компаний равно важны как эффективность информационных систем, так и стоимость используемых аппаратно-программных средств. Правильно спроектированные, хорошо нормализованные реляционные базы данных помогают решению корпоративных проблем.

Да, любое правильно развивающееся предприятие рано или поздно приходит к использованию систем категории OLAP, например, некоторой разновидности систем поддержки принятия решений (Decision Support System – DSS). В базах данных таких систем обновления очень редки, а запросы могут иметь произвольную сложность, включая соединения многих отношений. Но, во-первых, технологически правильно для системы OLAP поддерживать отдельную базу данных (обычно подобные базы данных называют хранилищами данных – DataWarehouse), а во-вторых, основными источниками данных для построения таких хранилищ данных являются базы данных систем OLTP. Так что актуальность правильно спроектированных баз данных OLTP-систем не уменьшается, а постоянно возрастает.

Следует ли из этого, что принципы нормализации непригодны для проектирования баз данных OLAP-приложений? И снова в ответ категорическое НЕТ! Возможно, окончательная схема такой базы данных должна быть денормализована из соображений повышения эффективности выполнения запросов. Но чтобы получить правильную денормализованную схему, нужно сначала понять, как выглядит нормализованная схема.

Основной вывод этой и предыдущей лекций можно сформулировать следующим образом. Пока мы остаемся в мире реляционных баз данных, для правильного проектирования базы данных необходимо понимать принципы нормализации, воспринимая их не как догму, а как руководство к действию. Кстати, это относится не только к «ручному» проектированию реляционных баз данных, но и к их проектированию с применением семантических моделей данных и CASE-средств, которые мы обсудим в следующих двух лекциях.

Назад Содержание Вперёд