Понятие функциональной зависимости в данных

Информация, данные, информационные системы

Лекция 5. Функциональные зависимости и реляционные базы данных

Оставим пока в стороне ответ на вопрос, почему проекты реляционных баз данных бывают плохими, т.е. зачем нужно проектировать реляционную базу данных. Попытаемся сначала ответить на вопросы "В чем заключается проектирование реляционных баз данных? и "Что лежит в основе процедур проектирования реляционных баз данных?"

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

На практике построение логической модели базы данных, независимо от используемой модели данных, выполняется с учетом двух основных требований: исключить избыточность и максимально повысить надежность данных. Эти требования вытекают из требования коллективного использования данных группой пользователей. Формальных средств описания данных, необходимых для проверки правильности заполнения конструкций моделей, явно недостаточно. Выбор сущностей, атрибутов и фиксация взаимосвязей между сущностями зависит от семантики предметной области и выполняется системным аналитиком субъективно в соответствии с его личным пониманием специфики прикладной задачи. Разные люди определяют и представляют данные по-разному.

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

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

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

Вспомним определение функции как соответствия множества аргументов определенным значениям из множества определения функции и способы задания функций: формула, график и перечисление (таблица). Нетрудно понять, что функциональную зависимость (ФЗ) можно определить на довольно широком классе объектов. Определение функции не накладывает никаких ограничений на множество аргументов и множество значений функции, кроме их существования и наличия соответствия между их элементами. Поскольку ФЗ можно задать таблично, а таблица есть форма представления отношения, то становится очевидной связь между ФЗ и отношением. Отношение может задавать ФЗ. Это утверждение является первой (1) конструктивной идеей, которая положена в основу теории проектирования реляционных баз данных.

Определение 1. Пусть r (A₁, A₂,..., A_n) - схема отношения R, a X и Y - подмножества r. Говорят, что Х функционально определяет Y, если каждому значению атрибутов кортежа отношения из Х соответствует не более одного значения атрибутов того же кортежа отношения из Y. Такая ФЗ обозначается как .

Как видно из определения, функциональная зависимость инвариантна к изменению состояний базы данных во времени.

Пример. Понятие функциональной зависимостиПродемонстрируем понятие функциональной зависимости на примере графика полетов аэропорта.ГРАФИК_ПОЛЕТОВ (Пилот, Рейс, Дата_вылета, Время_вылета)

Иванов		8.07	10:20
Иванов		9.07	13:30
Исаев		7.07	6:00
Исаев		11.07	10:20
Исаев		10.07	19:30
Петров		12.07	10:20
Петров		11.07	13:30
Фролов		8.07	6:00
Фролов		12.07	6:00
Фролов		14.07	13:30

Известно, что:

• каждому рейсу соответствует определенное время вылета;
• для каждого пилота, даты и времени вылета возможен только один рейс;
• на определенный день и рейс назначается определенный пилот.

Следовательно:

• "Время_вылета" функционально зависим от "Рейс": "Рейс" -> "Время_{} вылета";
• "Рейс" функционально зависим от {"Пилот", "Дата_вылета", "Время_вылета"}: {"Пилот", "Дата_вылета", "Время_вылета"} -> "Рейс";
• "Пилот" функционально зависим от {"Рейс", "Дата_вылета"}: {"Рейс", "Дата_вылета"} -> "Пилот".

Важной задачей при выявлении функциональных зависимостей на атрибутах отношения, которое по определению является множеством, является выяснение, какой из атрибутов выступает как аргумент, а какой - как значение ФЗ. Наиболее подходящими кандидатами в аргументы ФЗ являются возможные ключи, так как кортежи представляют экземпляры сущности, которые идентифицируются значениями атрибутов своего ключа. Нестрого говоря, функциональная зависимость имеет место на отношении, когда значения кортежа на одном множестве атрибутов однозначным образом определяют значения кортежа на другом множестве атрибутов. Это рабочее определение ФЗ не содержит в себе тех формальных элементов, которые позволяют ответить на вопрос "А как проверить наличие ФЗ между атрибутами отношения?" Необходимый для этого формализм дает нам использование реляционных операций. Для получения формального (строгого) определения наличия ФЗ в отношении обратимся к реляционным операциям.

Определение 2. Пусть имеется отношение R со схемой r, X и Y - два подмножества R. ФЗ имеет место на R, если множество имеет не более одного кортежа для каждого значения х. Такая ФЗ называется также F -зависимостью.

Как видно из определения, формальная проверка наличия ФЗ в отношении R состоит в выборе (селекции) отношения по значениям возможного ключа и установлении наличия однозначности между его значением и значениями других атрибутов.

Алгоритм, который проверяет, удовлетворяет ли отношение R ФЗ , состоит в сортировке отношения по значениям возможного ключа и установления факта однозначности между его значением и значениями других атрибутов. Этот алгоритм полезен, но он носит вспомогательный характер.

Ясно, что если семантика предметной области базы данных сложна, то проверить кортежи на принадлежность к ФЗ достаточно сложно. Сложно вообще установить наличие самой функциональной зависимости, отвечающей природе рассматриваемых данных. С помощью такого формального метода можно выявить ФЗ, которые не являются реальными и носят случайный характер. Проектировщику реляционных баз данных следует знать о таком методе проверки наличия ФЗ, но при проектировании новой базы данных его применение малоэффективно. Он может быть полезен при реинжиниринге существующей базы данных.

Функциональные зависимости фактически представляют собой утверждения обо всех отношениях предметной области. Эти отношения могут являться значениями схемы r и, в сущности, не могут быть получены формальными методами. Единственный способ установления функциональных зависимостей для схемы отношения r - это исследование семантики атрибутов сущностей предметной области. Являясь высказываниями о сущностях предметной области, они не могут быть доказаны. Это обстоятельство по существу порождает неединственность представления предметной области отношениями реляционной БД.

Здесь уместно высказать гипотезу о том, почему бывают хорошие и плохие проекты баз данных. Во-первых, в силу субъективности подходов к анализу предметной области аналитики могут упустить важные ФЗ. Это может привести к тому, что, работая на множестве заведомо неэквивалентных схем, проектировщик создаст неудовлетворительный проект базы данных. Во-вторых, неединственность представления предметной области отношениями приводит к проблеме выбора из множества альтернатив. При этом схема базы данных, выбранная из набора эквивалентных схем, является правильной, но может организовывать данные для пользователя непривычным образом. В-третьих, можно определить ("накроить") схемы баз данных таким образом, что в результате операций с ФЗ будут потеряны и ФЗ, и сами данные.

Основные классы функциональных зависимостей

Анализ связей между сущностями в предметных областях позволяет выделить различные классы функциональных зависимостей.

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

Введем определение.

Определение 3. Говорят, что неключевой атрибут функционально полно зависит от составного ключа, если он функционально зависит от ключа, но не находится в функциональной зависимости ни от какой части составного ключа. Если неключевой атрибут зависит от части составного ключа, то говорят о частичной ФЗ.

Пример. Частичные и полные ФЗ

ПРЕПОДАВАТЕЛЬ_ПРЕДМЕТ (Личный номер, Предмет, Фамилия, Должность, Оклад, Часы)

1.	Иванов	доцент		Математика
2.	Исаев	доцент		Физика
3.	Фролов	профессор		Химия

Первичным ключом отношения ПРЕПОДАВАТЕЛЬ_ПРЕДМЕТ является пара атрибутов Личный_номер-Предмет. Значения атрибута Количество_часов зависят от значения атрибута Предмет, т.е. имеем частичную ФЗ Предмет -> Часы. Значения атрибута Фамилия зависят от значений атрибутов Личный_номер-Предмет, т.е. имеем полную функциональную зависимость {Личный_номер, Предмет} -> Фамилия.

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

Таким образом, выявление определенных функциональных зависимостей в отношениях базы данных позволяет преобразовать их с целью исключения избыточности и повышения надежности данных. Разбиение исходных отношений в соответствии с функциональными зависимостями - это вторая (2) конструктивная идея в теории проектирования реляционных баз данных. Формирование схем отношений путем разбиения исходных отношений по их атрибутам с учетом функциональных зависимостей является одним из способов создания хороших схем реляционных баз данных.

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

Анализ связей между сущностями в предметных областях позволяет определить, наряду с частичной и полной ФЗ, еще несколько классов ФЗ. Одним из таких классов является класс транзитивных ФЗ.

Определение 4. Пусть X, Y, Z - атрибуты отношения R. Если при этом имеются ФЗ и , но отсутствуют ФЗ и , то говорят, что Z транзитивно зависит от Х. Такие ФЗ называются транзитивными (Т-зависимостями).

Пример. Транзитивные ФЗ

Личный номер преподавателя определяет его должность, т.е. имеет место ФЗ Личный_номер -> Должность. С другой стороны, согласно тарификации каждой должности назначается определенный оклад, т.е. имеет место ФЗ Должность -> Оклад. Каждый преподаватель получает за работу соответствующий должности оклад, т.е. оклад преподавателя определяется через его должность.

Очевидно, что семантическая связь между атрибутами отношения может носить неоднозначный характер, это порождает существование класса многозначных зависимостей (MV-зависимостей). Например, один преподаватель может преподавать несколько предметов, а один предмет может преподаваться несколькими преподавателями. Многозначная зависимость может быть следующих типов: 1:N (один ко многим), M:1 (многие к одному) и M:N (многие ко многим).

Определение 5. Пусть r - некоторая схема отношения, X и Y - подмножества атрибутов r. Если при заданных значениях атрибутов из {X} существует некоторое множество, состоящее из нуля или более взаимосвязанных значений атрибутов из {Y}, никак не связанных со значениями других атрибутов этого отношения r - X - Y, то говорят о существовании многозначной зависимости между атрибутами X и Y: (класс MV-зависимостей).

Формально многозначная зависимость означает, что если в отношении имеются два кортежа t и s, такие, что их значения совпадают по атрибутам из Х, т.е. t[X] = s[X], то данное отношение содержит кортежи w и v, такие, что

1. w[X] = v[X] = t[X] = s[X],
2. w[Y] = t[Y], w[r - X - Y] = s[r - X - Y],
3. v[Y] = s[Y], v[r - X - Y] = t[r - X - Y].

Фактически многозначная зависимость означает, что значения атрибутов из Y в кортежах t и s можно поменять местами и получить два новых кортежа, также принадлежащих отношению R.

Разделение установленных функциональных зависимостей по различным отношениям может привести к нарушению принципа замкнутости реляционных операций, потере некоторых существующих кортежей или появлению мнимых кортежей. Это обстоятельство приводит к необходимости выделения еще одного класса функциональных зависимостей - класса зависимостей по соединению (J -зависимостей). Этот класс ФЗ требует от ФЗ наличия свойства восстанавливаемости по своим проекциям с помощью естественного соединения.

Пусть U - универсальное отношение, полученное объединением всех атрибутов сущностей предметной области в одно отношение.

Определение 6. Пусть r = {r_1, …, r_p} - множество схем на U. Отношение R \subset U удовлетворяет зависимости по соединению, если R разлагается без потерь на r как

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

Однако для практических целей проектирования реляционных баз данных достаточно знания рассмотренных классов ФЗ. Даже зависимость по соединению встречается очень редко.

Дата добавления: 2014-01-07