Многозначная зависимость

Многозначная зависимость

Многозна́чная зави́симость (тж. МЗЗ) — обобщение понятия функциональной зависимости, широко использующееся в теории баз данных. В концепции нормальных форм вводится для формального определения четвертой нормальной формы

Содержание

Определения

Пусть существует некоторое отношение r со схемой R, а также два произвольных подмножества атрибутов A,B\subseteq R. Пусть C\overset{not}{\mathop{=}}\,R\backslash B.

В этом случае B многозначно зависит от A, тогда и только тогда, когда множество значений атрибута B, соответствующее заданной паре [a:A;c:C] отношения r, зависит от a и не зависит от c.

Символически выражается записью

A \twoheadrightarrow B.


Формально

\begin{align}
  & r\left( R \right),\ A,B\subseteq R,\ C=R\backslash B \\ 
 & \left( A\twoheadrightarrow B \right)\Leftrightarrow \forall {{t}_{1}},{{t}_{2}}\in r\ \exists {{t}_{3}},{{t}_{4}}\in r\ :\ \left\{ \begin{align}
  & {{t}_{1}}\left( A \right)={{t}_{2}}\left( A \right)={{t}_{3}}\left( A \right)={{t}_{4}}\left( A \right) \\ 
 & {{t}_{3}}\left( B \right)={{t}_{1}}\left( B \right) \\ 
 & {{t}_{3}}\left( C \right)={{t}_{2}}\left( C \right) \\ 
 & {{t}_{4}}\left( B \right)={{t}_{2}}\left( B \right) \\ 
 & {{t}_{4}}\left( C \right)={{t}_{1}}\left( C \right) \\ 
\end{align} \right. \\ 
\end{align}

Многозначная зависимость A\twoheadrightarrow B называется тривиальной, если выполняется хотя бы одно из условий:

  • Множество A является надмножеством B;
    B\subseteq A
  • Объединение A и B образует весь заголовок отношения.
    A\cup B=R

Пример

Предположим, у нас есть отношение, в которое входит список учебных дисциплин, рекомендованная литература и имена лекторов, читающих соответствующие курсы:

Учебные дисциплины
Дисциплина Книга Лектор
МатАн Кудрявцев Иванов А.
МатАн Фихтенгольц Петров Б.
МатАн Кудрявцев Петров Б.
МатАн Фихтенгольц Иванов А.
МатАн Кудрявцев Смирнов В.
МатАн Фихтенгольц Смирнов В.
ВМ Кудрявцев Иванов А.
ВМ Кудрявцев Петров Б.

Так как лекторы, читающие предмет, и книги, рекомендованные по предмету, друг от друга не зависят, то данное отношение содержит многозначную зависимость. Такое отношение обладает целым рядом аномалий. Одна из них состоит в том, что если мы хотим порекомендовать новую книгу по курсу МатАн, нам придется добавить столько новых записей, сколько лекторов ведут МатАн и наоборот.

Формально, здесь две МЗЗ: {Дисциплина} \twoheadrightarrow {Книга}|{Лектор}.

Во-первых, это избыточно. А во-вторых, для такого отношения необходимо разрабатывать дополнительный механизм контроля целостности. Оптимальным решением проблемы будет декомпозиция отношения на два с заголовками {Дисциплина, Книга} и {Дисциплина, Лектор}. Такая декомпозиция будет находиться в 4NF. Допустимость декомпозиции устанавливает теорема Феджина (см. далее).

Теоремы

Связные пары

Феджин показал, что многозначные зависимости образуют связные пары (в обозначениях определения):

\left( A\twoheadrightarrow B \right)\Leftrightarrow \left( A\twoheadrightarrow C \right).

Поэтому их часто представляют вместе в символической записи:

A\twoheadrightarrow B|C

Функциональные зависимости

Всякая функциональная зависимость является многозначной. Другими словами, функциональная зависимость — это многозначная зависимость, в которой множество зависимых значений, соответствующее заданному значению детерминанта, всегда имеет единичную мощность.

\left( A\to B \right)\Rightarrow \left( A\twoheadrightarrow B \right)

Правила вывода

В 1977 году Бэри, Феджин и Ховард установили, что правила вывода Армстронга можно обобщить и распространить, как на функциональные, так и на многозначные зависимости.

Пусть у нас есть отношение r\left( R \right) и множества атрибутов A,B,C,D\subseteq R. Для сокращения записи вместо X\cup Y будем писать просто XY.


Группа 1: базовые правила.

  • Дополнение
    \left( A\cup B\cup C=R \right)\wedge \left( B\cap C\subseteq A \right)\Rightarrow \left( \left( A\twoheadrightarrow B \right)\Leftrightarrow \left( A\twoheadrightarrow C \right) \right)
  • Транзитивность
    \left( A\twoheadrightarrow B \right)\wedge \left( B\twoheadrightarrow C \right)\Rightarrow \left( A\twoheadrightarrow C\backslash B \right)
  • Рефлексивность
    \left( B\subseteq A \right)\Rightarrow \left( A\twoheadrightarrow B \right)
  • Приращение
    \left( A\twoheadrightarrow B \right)\wedge \left( C\subseteq D \right)\Rightarrow \left( AD\twoheadrightarrow BC \right)


Группа 2: выводятся несколько дополнительных правил, упрощающих задачу вывода многозначных зависимостей.

  • Псевдотранзитивность
    \left( A\twoheadrightarrow B \right)\wedge \left( BC\twoheadrightarrow D \right)\Rightarrow \left( AC\twoheadrightarrow D\backslash BC \right)
  • Объединение
    \left( A\twoheadrightarrow B \right)\wedge \left( A\twoheadrightarrow C \right)\Rightarrow \left( A\twoheadrightarrow BC \right)
  • Декомпозиция
    \left( A\twoheadrightarrow BC \right)\Rightarrow \left( A\twoheadrightarrow B\cap C \right)\wedge \left( A\twoheadrightarrow B\backslash C \right)\wedge \left( A\twoheadrightarrow C\backslash B \right)


Группа 3: устанавливается связь между функциональными и многозначными зависимостями.

  • Репликация (копирование)
    \left( A\to B \right)\Rightarrow \left( A\twoheadrightarrow B \right)
  • Слияние
    \left( A\twoheadrightarrow B \right)\wedge \left( C\to D \right)\wedge \left( D\subseteq B \right)\wedge \left( B\cap C=\varnothing  \right)\Rightarrow \left( A\to D \right)


Группа 4: для функциональных зависимостей, выводятся из вышеприведенных правил.

  • \left( A\twoheadrightarrow B \right)\wedge \left( AB\to C \right)\Rightarrow \left( A\to C\backslash B \right)


Правила вывода Армстронга вместе с изложенными здесь правилами групп 1 и 3 образуют полный (используя их, можно вывести все остальные многозначные зависимости, подразумеваемые данным их множеством) и надежный («лишних» многозначных зависимостей вывести нельзя; выведенная многозначная зависимость справедлива везде, где справедливо то множество многозначных зависимостей, из которого она была выведена) набор правил вывода многозначных зависисмостей.

Применение

Декомпозиция отношений

Теорема Феджина

Пусть дано отношение r\left( A,B,C \right). Отношение r будет равно соединению его проекций r\left[ A,B \right] и r\left[ A,C \right] тогда и только тогда, когда для отношения r выполняется нетривиальная многозначная зависимость A\twoheadrightarrow B|C.

\left( r\left( A,B,C \right)=r\left[ A,B \right]\ \text{JOIN}\ r\left[ A,C \right] \right)\Leftrightarrow \left( A\twoheadrightarrow B|C \right)

Эта теорема является более строгой версией теоремы Хита.

См. также

Литература

  • К. Дж. Дейт Введение в системы баз данных = Introduction to Database Systems. — 8-е изд. — М.: «Вильямс», 2006. — С. 1328. — ISBN 0-321-19784-4

Wikimedia Foundation. 2010.

Смотреть что такое "Многозначная зависимость" в других словарях:

  • Функциональная зависимость (программирование) — Функциональная зависимость  концепция, лежащая в основе многих вопросов, связанных с реляционными базами данных, включая, в частности, их проектирование. Математически представляет бинарное отношение между множествами атрибутов данного… …   Википедия

  • Функциональная зависимость — Запрос «Отображение» перенаправляется сюда. Cм. также другие значения. В данной статье приведено общее определение математической функции. В средних школах и на нематематических специальностях высших учебных заведениях изучают более простое… …   Википедия

  • Нормализация баз данных — Нормальная форма требование, предъявляемое к отношениям в теории реляционных баз данных для устранения из базы избыточности, которая потенциально может привести к логически ошибочным результатам выборки или изменения данных. Содержание 1… …   Википедия

  • Четвёртая нормальная форма — (4NF)  одна из возможных нормальных форм отношения реляционной базы данных. Содержание 1 Определение 2 Пример 3 Примечания …   Википедия

  • Нормализация БД — Нормальная форма требование, предъявляемое к отношениям в теории реляционных баз данных для устранения из базы избыточности, которая потенциально может привести к логически ошибочным результатам выборки или изменения данных. Содержание 1… …   Википедия

  • Нормальные формы — Нормальная форма требование, предъявляемое к отношениям в теории реляционных баз данных для устранения из базы избыточности, которая потенциально может привести к логически ошибочным результатам выборки или изменения данных. Содержание 1… …   Википедия

  • Четвертая нормальная форма — Основная статья: Нормальная форма Четвёртая нормальная форма (4NF)  одна из возможных нормальных форм таблицы реляционной базы данных. Определение Таблица находится в 4NF, если она находится в BCNF и не содержит нетривиальных многозначных… …   Википедия

  • Пятая нормальная форма — Основная статья: Нормальная форма Пятая нормальная форма (5NF)  одна из возможных нормальных форм отношения реляционной базы данных. Содержание 1 Определение 1.1 Декомпозиция без потерь …   Википедия

  • МАТЕРИАЛИЗМ — (от лат. materialis вещественный) многозначная идея, которой чаще всего придается один или некоторые из следующих смыслов. 1. Утверждение относительно существования или реальности: только материя существует или является реальной; материя является …   Философская энциклопедия

  • Мерлин, Вольф Соломонович — В Википедии есть статьи о других людях с такой фамилией, см. Мерлин (значения). Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»