Функциональная зависимость атрибутов реляционных отношений. Нормализация отношений.

Функциональная зависимость (functional dependency) – это связь между атрибутами. Предположим, что мы знаем значение одного атрибута, то можем определить и значение другого атрибута. Например, нам известен Номер_счета_ Клиента в банке, то можно определить Состояние_Счета_Клиента. В таком случае можно сказать, что атрибут Состояние_Счета_Клиента функционально зависит от атрибута Номер_счета_Клиента.То есть, если в некотором отношении R имеются два атрибута X и Y (R(X,Y)), то говорят атрибут У функционально зависит от атрибута Х, если значение Х определяет значение У. Другими словами, если нам известно значение Х, мы можем определить значение У. Функциональные зависимости обозначаются следующим образом: Серийный_Номер_Компьютера > Объем_Памяти;

Номер_Счета_Клиента > Состояние_Счета_Клиента.

Первое выражение читается так: атрибут «Серийный_Номер_Компьютера» функционально определяет атрибут «Объем_Памяти» или атрибут «Объем_Памяти» функционально зависит от атрибута «Серийный_Номер_Компьютера». Атрибуты по правую сторону от стрелки называются детерминантами(determinants). Для установления функциональной зависимости атрибутов может быть использована и графическая интерпретация.

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

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

В функциональные зависимости могут быть вовлечены группы атрибутов. Рассмотрим отношение Оценки:

Оценки (Номер_студента, Дисциплина, Оценка).

Комбинация атрибутов Номера_студента и Дисциплина определяет атрибут Оценка. Такая функциональная зависимость записывается следующим образом:

(Номер_студента, Дисциплина) >Оценка.

Отметим, что для определения оценки требуется как номер студента, так и дисциплина. Имеет место следующее утверждение, если X > (Y,Z), то X>Y и X>Z. Например, если Номер_студента > (Имя_студента, Специальность), то Номер_студента > Имя_студента и

Номер_студента > Специальность. Но если (X,Y)>Z,то в общем случае неверно, что X>Z или Y>Z. Следовательно, если (Номер_студента, Дисциплина) > Оценка, то ни номер студента, ни дисциплина в отдельности оценку не определяют. В этом случае говорят о полной функциональной зависимости.

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

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

Инвертированный файл.

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

Широко распространены на практике методы многоаспекторного поиска по инвертированным файлам. Пусть имеется основной файл F, упорядоченный либо не упорядоченный по значениям вторичного ключа Ki. Построим дополнительный файл Fdiпо правилу:1)записи файла FDi имеют формат Fdi(Ki,P), где Ki-поле, принимающее значение вторичного ключа Ki записиосновного файла; P- указатели на записи основного файла f, имеющие данное значение вторичного ключа Ki; 2)записи файла Fdi упорядочены по полю Ki.

Построенный дополнительный файл Fdi называется инвертированным. В этом случае об основном файле F говорят, что он инвертирован по полю Ki. Количество записей в инвертированном файле FDi определяется количеством значений вторичного ключа Ki в записях основного файла F. Пример инвертированного файла по полю K2 для основного файла F.

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

Поскольку записи инвертированного файла упорядочены, но значению ключа, то для поиска записей можно использовать любой из рассмотренных выше методов поиска в упорядоченном файле (например, бинарный поиск или В -дерево). Чтобы выпол­нить многоаспектный поиск по n ключам, необходимо построить n инвертированных файлов.