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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Введение

Диалектический подход к изучению природы и общества требует рассмотрения явлений в их взаимосвязи и непрестанном изменении. Понятия корреляции и регрессии появились в середине XIX в. благодаря работам английских статистиков Ф. Гальтона и К. Пирсона. Первый термин произошел от латинского «correlatio» – соотношение, взаимосвязь. Второй термин (от лат. «regressio» - движение назад) введен Ф. Гальтоном, который, изучая зависимость между ростом родителей и их детей, обнаружил явление «регрессии к среднему» – у детей, родившихся у очень высоких родителей, рост имел тенденцию быть ближе к средней величине.

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

Выше сказанным обусловлена актуальность выбора темы курсовой работы. Цель данной работы – исследовать функциональную зависимость между случайными величинами методами корреляционного и регрессионного анализов.

Глава 1 Корреляционный анализ

1.1 Функциональная, статистическая и корреляционная зависимости

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

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

В силу неоднозначности статистической зависимости между Y и Х для исследователя, в частности, представляет интерес усредненная по х схема зависимости, т.е. закономерность в изменении среднего значения - условного математического ожидания (Y) (математического ожидания случайной переменной Y, найденного при условии, что переменная Х приняла значение х) в зависимости от х.

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

Корреляционная зависимость может быть представлена в виде:

Предполагается, что φ(x)≠const и ψ(x)≠const, т.е. если при изменении х или у уcловные математические ожидания(Y) и не изменяются, то говорят, что корреляционная зависимость между переменными Х и У отсутствует. Сравнивая различные виды зависимости между Х иY, можно сказать, что с изменением значений переменной Х при функциональной зависимости однозначно изменяется определенное значение переменной у, при корреляционной – определенное среднее значение (условное математическое ожидание) Y, а при статистической- определенное (условное) распределение переменной Y (Рис.1.1)

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

Уравнения (1.1) и (1.2) называются модельными уравнениями регрессии (или просто уравнениями регрессии) соответственно Y по Х и Х по Y, функции ψ(x) и φ(у) – модельными функциями регрессии (или функциями регрессии), а их графики - модельными линиями регрессии (или линиями регрессии).

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

где – условная (групповая) средняя переменной Y при фиксированном значении переменной Х = х; ,…,- параметры кривой.

Аналогично определяется выборочная линия (кривая) регрессии Х по Y:

где – условная (групповая) средняя переменной Х при фиксированном значении переменной Y= у; -параметры кривой.

Уравнения (1.3), (1.4) называют также выборочными уравнениями регрессии соответственно Yпо Х и Х по Y.

При правильно определенных аппроксимирующих функциях) и с увеличением объема выборки (n) они будуг сходиться по вероятности соответственно к функциям регрессии ψ(x) и φ(у).

Статистические связи между переменными можно изучать методами корреляционного и регрессионного анализа. Основной задачей регрессионного анализа является установление формы и изучение зависимости между переменными. Основной задачей корреляционного анализа – выявление связи между случайными переменными и оценка ее тесноты.

1.2 Линейная парная регрессия

Данные о статистической зависимости удобно задавать в виде корреляционной таблицы.

Рассмотрим в качестве примера зависимость между суточной выработкой продукции Y (т) и величиной основных производственных фондов Х (млн руб.) для совокупности 50 однотипных предприятий (табл. 1).
(В таблице черези обозначены середины соответствующих интервалов, а через, и – соответственно их частоты.)

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

где - частоты пар () и; m – число интервалов по переменной Y.

Вычисленные групповые средние поместим в последнем столбце корреляционной таблицы и изобразим графически в виде ломаной, называемой эмпирической линией регрессии Y по X

Аналогично для каждого значения по формуле

вычислим групповые средние, где, l – число интервалов по переменной X.

По виду ломанной можно определить наличие линейной корреляционной зависимости Y по X между двумя рассматриваемыми переменными, которая выражается тем точнее чем больше объем выборки n:

Поэтому уравнение регрессии(1.3) будем искать в виде:

Отвлечемся на время от рассматриваемого примера и найдем формулы расчета неизвестных параметров уравнения линейной регрессии.

С этой целью применим метод наименьших квадратов, согласно которому неизвестные параметры и выбираются таким образом, чтобы сумма квадратов отклонений эмпирических групповых средних, вычисленных по формуле (1.5), от значений, найденных по уравнению регрессии (1.8), была минимальной:

На основании необходимого условия экстремума функции двух переменных S=S() приравниваем к нулю ее частные производные, т.е.

Откуда после преобразования получим систему нормальных уравнений для определения параметров линейной регрессии:

Учитывая (1.5) преобразуем выражение и с учетом (1.7), разделив обе части уравнений (1.10) на n, получим систему нормальных уравнений в виде:

где соответствующие средние определяются по формулам:

Подставляя значение из первого уравнения системы(1.11) в уравнение регрессии (1.8), получаем

Коэффициент b 1 в уравнении регрессии, называемый выборочным коэффициентом регрессии (или просто коэффициентом регрессии) Y по Х, будем обозначать символом. Теперь уравнение регрессии Y по Х запишется так:

Коэффициент регрессии Yпо Х показывает, на сколько единиц в среднем изменяется переменная Y при увеличении переменной Х на одну единицу.

Решая систему (1.11), найдем

где - выборочная дисперсия переменной X

µ - выборочный корреляционный момент:

Рассуждая аналогично и полагая уравнение регрессии (1.4) линейным, можно привести его к виду:

выборочный коэффициент регрессии (или просто коэффициент регрессии) Х по Y, показывающий, на сколько единиц в среднем изменяется переменная Х при увеличении переменной Y на одну единицу= – (–выборочная дисперсия переменной Y. зависимость . При этом все наблюдения располагаются... Линия тренда (рис. 2); 3) выбрать вид зависимости регрессии . Для нашего примера тип тренда...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рассмотрим для примера конкретную схему отношений и проанализируем её недостатки. Предположим, что данные о студентах, факультетах, специальностях, включены в таблицу со следующей схемой отношения: СТУДЕНТ (Код студента, Фамилия, Название факультета, Название специальности).

Эта схема отношений обусловливает следующие недостатки соответствующей базы данных :

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

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

Нормализация. Первая нормальная форма .

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

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

Рассмотрим следующий пример.

Таблица представляет сущность ЭКЗАМЕНАЦИОННАЯ ВЕДОМОСТЬ

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

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

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

Прежде чем перейти к построению второй нормальной формы , необходимо определить ряд формальных понятий.

8.2. Функциональные зависимости (зависимости между атрибутами отношения)

Пусть R(A 1 , A 2 , ..., A n) – схема отношения , а X и Y – подмножества {A 1 , A 2 , ..., A n } .

Функциональная зависимость на отношении R – это утверждение вида "Если два кортежа R совпадают по атрибутам множества (т.е. эти кортежи имеют в соответствующих друг другу компонентах одни и те же значения для каждого атрибута множества X ), то они должны совпадать и по атрибутам множества . Формально эта зависимость записывается выражением X -> Y , причем говорится, что X функционально определяет Y . Часто используется другое утверждение: X функционально определяет Y или Y функционально зависит от X (обозначается X -> Y ) тогда и только тогда, когда каждое значение множества X отношения R связано с одним значением множества Y отношения R . Иначе говоря, если два кортежа R совпадают по значению X , они совпадают и по значению Y .

Замечание. Вообще говоря, под термином " отношение " могут подразумеваться два понятия:

• отношение как переменная, которая может принимать разные значения (таблица, в строки и столбцы которой могут быть вписаны разные значения);
• отношение, как набор конкретных значений (таблица с заполненными элементами).

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

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

Пример функциональных зависимостей для отношения ЭКЗАМЕНАЦИОННАЯ ВЕДОМОСТЬ

Код студента -> Фамилия Код студента, Код экзамена -> Оценка

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

Код студента -> Фамилия, Код студента -> Факультет

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

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

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

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

Если множество функциональных зависимостей совпадает с замыканием данного множества, то такое множество функциональных зависимостей называется полным .

Введенные понятия позволяют формально определить понятие ключа.

Пусть существует некоторая схема R с атрибутами A 1 A 2 ...A n , F – некоторое множество функциональных зависимостей и X – некоторое подмножество R . Тогда X называется ключом, если, во-первых, в F + существует зависимость X -> A 1 A 2 ...A n и, во-вторых, ни для какого подмножества Y , входящего в X , зависимость Y -> A 1 A 2 ...A n не принадлежит F + .

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

Частичной функциональной зависимостью будем называть зависимость неключевого атрибута от части составного ключа .

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

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

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

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

Сессия (№ зачетной книжки , Фамилия, Имя, Отчество, Предмет , Оценка);

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

Однако, помимо ограничения уникальности, связанной с этим ключом, на отношение непременно должно быть наложено то условие, что одна зачетная книжка выдается обязательно одному конкретному человеку и, следовательно, в этом отношении кортежи с одинаковым номером зачетной книжки должны содержать одинаковые значения атрибутов «Фамилия», «Имя» и «Отчество».

Если у нас имеется следующий фрагмент какой-то определенной базы данных студентов учебного заведения после какой-то сессии, то в кортежах с номером зачетной книжки 100, атрибуты «Фамилия», «Имя» и «Отчество» совпадают, а атрибуты «Предмет» и «Оценка» – не совпадают (что и понятно, ведь в них речь идет о разных предметах и успеваемости по ним). Это значит, что атрибуты «Фамилия», «Имя» и «Отчество» функционально зависят от атрибута «№ зачетной книжки», а атрибуты «Предмет» и «Оценка» функционально не зависят.

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

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

Определение : пусть X, Y – подсхемы схемы отношения S, определяющие над схемой S схему функциональной зависимости X > Y (читается «X стрелка Y»). Определим ограничения функциональной зависимости inv > Y> как утверждение о том, что в отношении со схемой S любые два кортежа, совпадающие в проекции на подсхему X, должны совпадать и в проекции на подсхему Y.

Запишем это же определение в формулярном виде:

Inv > Y> r (S ) = t 1 , t 2 ? r (t 1 [X ] = t 2 [X ] ? t 1 [Y ] = t 2 [Y ]), X , Y ? S;

Любопытно, что в этом определении использовано понятие унарной операции проекции, с которым мы сталкивались раньше. Действительно, как еще, если не использовать эту операцию, показать равенство друг другу двух столбцов таблицы-отношения, а не строк? Поэтому мы и записали в терминах этой операции, что совпадение кортежей в проекции на какой-то атрибут или несколько атрибутов (подсхему X) непременно влечет за собой совпадение этих же столбцов-кортежей и на подсхеме Y в том случае, если Y функционально зависит от X.

Интересно заметить, что в случае функциональной зависимости Y от X, говорят также, что X функционально определяет Y или что Y функционально зависит от X. В схеме функциональной зависимости X > Y подсхема X называется левой частью, а подсхема Y – правой частью.

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

Конец определения .

В частном случае, когда правая часть функциональной зависимости, т. е. подсхема Y, совпадает со всей схемой отношения, ограничение функциональной зависимости переходит в ограничение уникальности первичного или кандидатного ключа. Действительно:

Inv <K > S > r (S ) = ? t 1 , t 2 ? r (t 1 [K ] = t 2 [K ] > t 1 (S ) = t 2 (S )), K ? S ;

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

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

{№ зачетной книжки} > {Фамилия, Имя, Отчество};

{№ зачетной книжки, Предмет} > {Оценка};

2. Правила вывода Армстронга

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

Хорошим примером таких специальных правил являются правила вывода Армстронга.

Но прежде чем приступать к анализу самих правил вывода Армстронга, введем в рассмотрение новый металингвистический символ «+», который называется символом метаутверждения о выводимости . Этот символ при формулировании правил записывается между двумя синтаксическими выражениями и свидетельствует о том, что из формулы, стоящей слева от него, выводится формула, стоящая справа от него.

Сформулируем теперь сами правила вывода Армстронга в виде следующей теоремы.

Теорема. Справедливы следующие правила, называемые правилами вывода Армстронга.

Правило вывода 1. + X > X;

Правило вывода 2. X > Y+ X ? Z > Y;

Правило вывода 3. X > Y, Y ? W > Z + X ? W > Z;

Здесь X, Y, Z, W – произвольные подсхемы схемы отношения S. Символ метаутверждения о выводимости разделяет списки посылок и списки утверждений (заключений).

1. Первое правило вывода называется «рефлексивность » и читается следующим образом: «выводится правило: “X функционально влечет за собой X”». Это самое простое из правил вывода Армстронга. Оно выводится буквально из воздуха.

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

2. Второе правило вывода называется «пополнение » и читается таким образом: «если X функционально определяет Y, то выводится правило: “объединение подсхем X и Z функционально влечет за собой Y”». Правило пополнения позволяет расширять левую часть ограничения функциональных зависимостей.

3. Третье правило вывода называется «псевдотранзитивность » и читается следующим образом: “если подсхема X функционально влечет за собой подсхему Y и объединение подсхем Y и W функционально влекут за собой Z, то выводится правило: «объединение подсхем X и W функционально определяют подсхему Z»”.

Правило псевдотранзитивности обобщает правило транзитивности, соответствующее частному случаю W: = 0. Приведем формулярную запись этого правила:

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

Правило вывода 1. inv X> r(S);

Правило вывода 2. inv Y> r(S) ? inv Y> r(S);

Правило вывода 3. inv Y> r(S) & inv Z> r(S) ? inv Z> r(S);

Проведем доказательства этих правил вывода.

1. Доказательство правила рефлексивности следует непосредственно из определения ограничения функциональной зависимости при подстановке вместо подсхемы Y – подсхемы X.

Действительно, возьмем ограничение функциональной зависимости:

Inv Y> r(S) и подставим в него X вместо Y, получим:

Inv X> r(S), а это и есть правило рефлексивности.

Правило рефлексивности доказано.

2. Доказательство правила пополнения проиллюстрируем на диаграммах функциональной зависимости.

Первая диаграмма – это диаграмма посылки:

посылка: X > Y

Вторая диаграмма:

заключение: X ? Z > Y

Пусть кортежи равны на X ? Z. Тогда они равны на X. Согласно посылке они будут равны и на Y.

Правило пополнения доказано.

3. Доказательство правила псевдотранзитивности также проиллюстрируем на диаграммах, которых в этом конкретном случае будет три.

Первая диаграмма – первая посылка:

посылка 1: X > Y

посылка 2: Y ? W > Z

И, наконец, третья диаграмма – диаграмма заключения:

заключение: X ? W > Z

Пусть кортежи равны на X ? W. Тогда они равны и на X, и на W. Согласно Посылке 1, они будут равны и на Y. Отсюда, согласно Посылке 2, они будут равны и на Z.

Правило псевдотранзитивности доказано.

Все правила доказаны.

3. Производные правила вывода

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

Что это за правила, как они получаются?

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

Необходимо специально отметить, что эти самые произвольные правила являются «производными» именно от пройденных нами ранее правил вывода Армстронга.

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

Теорема.

Следующие правила являются производными от правил вывода Армстронга.

Правило вывода 1. + X ? Z > X;

Правило вывода 2. X > Y, X > Z + X ? Y > Z;

Правило вывода 3. X > Y ? Z + X > Y, X > Z;

Здесь X, Y, Z, W, так же как и в предыдущем случае, – произвольные подсхемы схемы отношения S.

1. Первое производное правило называется правилом тривиальности и читается следующим образом:

«Выводится правило: “объединение подсхем X и Z функционально влечет за собой X”».

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

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

2. Второе производное правило называется правилом аддитивности и читается следующим образом: «Если подсхема X функционально определяет подсхему Y, и X одновременно функционально определяет Z, то из этих правил выводится следующее правило: “X функционально определяет объединение подсхем Y и Z”».

3. Третье производное правило называется правилом проективности или правилом «обращение аддитивности ». Оно читается следующим образом: «Если подсхема X функционально определяет объединение подсхем Y и Z, то из этого правила выводится правило: “X функционально определяет подсхему Y и одновременно X функционально определяет подсхему Z”», т. е., действительно, это производное правило является обращенным правилом аддитивности.

Любопытно, что правила аддитивности и проективности применительно к функциональным зависимостям с одинаковыми левыми частями позволяют объединять или, наоборот, расщеплять правые части зависимости.

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

Проведем доказательства перечисленных произвольных правил вывода.

1. Доказательство правила тривиальности .

Проведем его, как и все последующие доказательства, по шагам:

1) имеем: X > X (из правила рефлексивности вывода Армстронга);

Правило тривиальности доказано.

2. Проведем пошаговое доказательство правила аддитивности :

1) имеем: X > Y (это посылка 1);

2) имеем: X > Z (это посылка 2);

3) имеем: Y ? Z > Y ? Z (из правила рефлексивности вывода Армстронга);

4) имеем: X ? Z > Y ? Z (получаем при помощи применения правила псевдотранзитивности вывода Армстронга, а потом как следствие первого и третьего шагов доказательства);

5) имеем: X ? X > Y ? Z (получаем, применяя правило псевдотранзитивности вывода Армстронга, а после следует из второго и четвертого шагов);

6) имеем X > Y ? Z (следует из пятого шага).

Правило аддитивности доказано.

3. И, наконец, проведем построение доказательства правила проективности :

1) имеем: X > Y ? Z, X > Y ? Z (это посылка);

2) имеем: Y > Y, Z > Z (выводится при помощи правила рефлексивности вывода Армстронга);

3) имеем: Y ? z > y, Y ? z > Z (получается из правила пополнения вывода Армстронга и следствием из второго шага доказательства);

4) имеем: X > Y, X > Z (получается, применением правила псевдотранзитивности вывода Армстронга, а затем как следствие из первого и третьего шагов доказательства).

Правило проективности доказано.

Все производные правила вывода доказаны.

4. Полнота системы правил Армстронга

Пусть F (S ) - заданное множество функциональных зависимостей, заданных над схемой отношения S.

Обозначим через inv <F (S )> ограничение, накладываемое этим множеством функциональных зависимостей. Распишем его:

Inv <F (S )> r (S ) = ?X > Y ?F (S ) [inv Y> r (S )].

Итак, это множество ограничений, накладываемое функциональными зависимостями, расшифровывается следующим образом: для любого правила из системы функциональных зависимостей X > Y, принадлежащего множеству функциональных зависимостей F (S ), действует ограничение функциональных зависимостей inv Y> r (S ), определенных над множеством отношения r (S ).

Пусть какое-то отношение r (S ) удовлетворяет этому ограничению.

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

Правило вывода 1. inv < X > X > r (S );

Правило вывода 2. inv Y> r (S ) ? inv ? Z > Y> r (S );

Правило вывода 3. inv Y> r (S ) & inv ? W > Z> r (S ) ? inv ? W > Z>;

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

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

Необходимо заметить, что этот процесс построения замыкания конечен, ведь конечна сама схема отношения, на которой и проводятся все эти построения.

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

Если записать только что сказанное в формулярном виде, то получим:

F (S ) ? F + (S ), [F + (S )] + = F + (S );

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

X > Y ? F + (S ) ? ?r (S ) [inv <F (S )> r (S ) ? inv Y> r (S )];

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

(Доказательство этой теоремы мы рассматривать не будем, так как сам процесс доказательства не столь важен в нашем конкретном курсе лекций.)