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

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

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

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

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

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

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

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

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

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

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

Пример. Понятие функциональной зависимости

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

на примере графика полетов аэропорта.

ГРАФИК_ПОЛЕТОВ (Пилот, Рейс, Дата_вылета, Время_вылета)

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

· каждому рейсу соответствует определенное время вылета;

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

· на определенный день и рейс назначается определенный пилот.

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

· "Время_вылета" функционально зависим от "Рейс": "Рейс" "Время_{} вылета";

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

· "Пилот" функционально зависим от {"Рейс", "Дата_вылета"}: {"Рейс", "Дата_вылета"} "Пилот".

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Определение 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 как

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

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

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

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

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

Такие рассуждения позволяют ввести следующие определения.

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

В примере выше мы видели, что если F содержит ФЗ из и , то зависимость логически следует из F.

Определение 8. Пусть F - множество ФЗ для схемы отношения r. Тогда замыканием F⁺ множества ФЗ F называется множество ФЗ, которое логически следует из F. F называется полным семейством ФЗ, если F⁺ = F.

Пример (без доказательства). Пусть . Тогда F⁺ состоит из всех зависимостей , таких, что выполняется одно из следующих условий:

· X содержит A, т.е. или ;

· X содержит B, но не A, и Y не содержит A, т.е. или B;

· есть или .

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

Определение 9. Пусть F - множество ФЗ для схемы отношения R(A₁, A₂, ..., A_n). Подмножество атрибутов X называется ключом отношения R, если ФЗ: принадлежит F⁺ и не для какого собственного подмножества ФЗ: не принадлежит F⁺.

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

Пример. Определение ключа отношения с помощью правил вывода

Используя три первых аксиомы вывода, покажем, что пара атрибутов {адрес, почтовый_индекс} из примера выше являются ключом отношения (город, адрес, почтовый_индекс), иначе имеет место ФЗ адрес, почтовый_индекс город, адрес, почтовый_индекс. Задана ФЗ: почтовый_индекс город. Используя аксиому пополнения, пополним эту ФЗ атрибутом адрес, получаем адрес, почтовый_индекс город, адрес. Задана ФЗ город, адрес почтовый_индекс. Используя аксиому пополнения, пополнив эту ФЗ атрибутами город, адрес, получим город, адрес город, адрес, почтовый_индекс. Тогда по аксиоме транзитивности получаем адрес, почтовый_индекс город, адрес, почтовый_индекс.

Можно доказать утверждение о том, что настоящие правила вывода позволяют по заданному множеству ФЗ F построить все зависимости, допускаемые на U. Таким образом, система правил вывода ФЗ 1-6 является надежной и полной.

Покажем, как можно доказать утверждение о полноте и надежности аксиом вывода. Аксиомы 1, 2 и 3 составляют независимое подмножество среди всех шести аксиом и называются аксиомами Армстронга. Из них можно вывести все остальные аксиомы. Поэтому надежность и полноту достаточно установить только для первых трех аксиом.

Надежность аксиом заключается в том, что если ФЗ выведена из F с помощью этих аксиом, то она справедлива на любом отношении, на котором справедливы ФЗ из F. Аксиома рефлексивности является надежной, так как нельзя иметь отношение R с двумя кортежами, которые совпадают по Х, но не совпадают по некоторому его подмножеству. Для доказательства аксиомы пополнения предположим, что имеется отношение R и справедлива ФЗ на R. Однако есть два кортежа t и s, которые совпадают по атрибутам XZ, но не совпадают по YZ. Поскольку они не могут совпадать по какому-либо атрибуту из Z, то они не должны совпадать по некоторому атрибуту из Y. Тогда они совпадают по X, но не совпадают по Y, что противоречит существованию ФЗ . Надежность аксиомы транзитивности уже была доказана в настоящем учебном элементе ранее.

Для доказательства полноты аксиом вывода введем понятие замыкания множества атрибутов X относительно множества ФЗ F.

Определение 10. Пусть F - множество ФЗ на множестве атрибутов U и . Тогда замыканием X⁺ множества ФЗ F называется множество атрибутов А, таких, что ФЗ может быть выведена из F по аксиомам 1-3.

Нетрудно показать, что ФЗ следует из аксиом 1-3 тогда и только тогда, когда . По определению замыкания для каждого атрибута из Y выводится ФЗ . По аксиоме объединения имеет место ФЗ . Обратно, если выполняется ФЗ , то по аксиоме декомпозиции имеет место ФЗ каждый атрибут из Y, и, следовательно, имеет место .

Теперь, для того чтобы показать полноту аксиом 1-3, покажем, что если при заданном F ФЗ не может быть выведена из данных аксиом, то должно существовать такое отношение, в котором справедливы все ФЗ F, кроме ФЗ .

Рассмотрим отношение R с двумя кортежами:

Все зависимости из F справедливы на R. Следует показать, что не удовлетворяется на R. Допустим обратное. Из следует , иначе два кортежа, совпадая по Х, не совпадают по Y. Тогда ФЗ следует из аксиом 1-3, что приводит к противоречию. Таким образом, аксиомы 1-3 полны.

На основе аксиом вывода можно уточнить понятие замыкания множества ФЗ , как наименьшего множества, содержащего F, которое не может быть расширено за F с помощью аксиом 1, 2 и 3. Понятие замыкания является основным при доказательстве приведенного выше утверждения. Оно также важно при определении, имеет ли множество ФЗ F зависимость . Для этого достаточно проверить, принадлежит ли рассматриваемая зависимость множеству F⁺.

Вычисление замыкания конечного множества ФЗ является трудоемкой задачей, так как необходимо перебрать множество всех подмножеств, а таких множеств, как известно, 2ⁿ, где n - число элементов исходного множества. Однако вычислить замыкание X⁺ для данного множества атрибутов несложно. Алгоритм вычисления приведен ниже. Можно показать, что этот алгоритм корректно вычисляет замыкание X⁺.

Минимальные покрытия множеств функциональных зависимостей

Попытаемся теперь выяснить, какова роль F-зависимостей в реляционных базах данных. Как показали исследования, класс F-зависимостей оказывает существенное влияние на построение согласованных схем реляционных баз данных, определяет механизмы согласованности данных и целостности баз данных.

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

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

Определение 11. Два множества F-зависимостей F и G над схемой r отношения R эквивалентны, если их замыкания совпадают, т.е. F⁺ = G⁺.

Эквивалентность двух множеств ФЗ F и G устанавливается следующим образом: для каждой ФЗ из F проверяется ее принадлежность G⁺; для этого вычисляется Y⁺; затем проверяется вложение Z в Y⁺; если каждая зависимость F принадлежит G⁺, то каждая зависимость в F⁺ принадлежит G⁺; далее повторяем процедуру для G по отношению к F.

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

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

Определение 12. Множество F-зависимостей F неизбыточно, если у него нет собственного подмножества, эквивалентного ему самому.

Определение 13. Множество F-зависимостей F минимально, если оно содержит не больше F-зависимостей, чем любое эквивалентное ему множество.

Минимальное покрытие (МП) не может содержать избыточных зависимостей. Понятие МП F можно детализировать следующим образом:

· правая часть каждой ФЗ в F содержит один атрибут;

· ни для какой ФЗ из F множество не эквивалентно F;

· ни для какой ФЗ из F и собственного подмножества множества не эквивалентны.

Доказано, что для каждого множества ФЗ F существует эквивалентное ему минмальное покрытие. Для заданного F может существовать несколько минимальных покрытий. Ниже приведены общие алгоритмы проверки избыточности и построения минимальных покрытий.На практике часто требуется только знать, следует ли из D конкретная ФЗ или . Этого достаточно, чтобы исключить избыточные ФЗ. Для того чтобы определить, имеет ли место MV-зависимость , достаточно построить базис Х зависимостей и посмотреть, является ли Z - X объединением каких-либо его множеств. Для вычисления базиса зависимостей Х относительно D достаточно найти базис относительно множества МФЗ М, где М состоит из а) всех МФЗ из D и б) множества МФЗ для каждой ФЗ в D.

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

·  Аксиомы вывода ФЗ позволяют производить формальное (алгебраическое) манипулирование зависимостями разных классов: F- и MV-зависимостями. В рамках данных аксиом преобразования схем отношений реляционных баз данных будут эквивалентными.

·  Аксиомы вывода ФЗ позволяют оперировать отдельными атрибутами зависимостей, при этом сами ФЗ сохраняются: атрибуты из правой части ФЗ могут быть удалены; атрибуты из левой части ФЗ могут быть удалены, если удаляемый атрибут отсутствует в правой части; независимо от того, перекрываются ли множества атрибутов или нет, любые атрибуты из исходного множества можно одновременно подставлять в правую и левую части ФЗ. Несущественные зависимости могут быть удалены, а затем восстановлены.

·  Существует минимальный набор ФЗ, который позволяет восстановить исходный набор ФЗ. Это обстоятельство позволяет теоретически обосновать и практически проводить эквивалентные, сохраняющие семантический смысл данных, преобразования схем отношений реляционной базы данных.