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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть R - ϶ᴛᴏ отношение. С одной стороны, оно имеет конкретное (постоянное) значение в данный момент времени. С другой стороны, это переменная, которая в каждый момент времени может принять неĸᴏᴛᴏᴩᴏᴇ новое значение.

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

Определœение функциональной зависимости. Пусть R – переменная отношения. X и Y – произвольные подмножества множества атрибутов R . Тогда Y функционально зависит от X , что в символическом виде записывается как X → Y (читается как ʼʼX функционально определяет Y ʼʼ) тогда и только тогда, когда для любого допустимого значения R каждое значение X связано точно с одним значением Y .

Здесь X называют детерминантом ФЗ, а Y – зависимой частью ФЗ.

Пример : Пусть R - ϶ᴛᴏ отношение Students . X – код студента͵ а Y – множество всœех атрибутов студента. Тогда X → Y , т.к. X представляет собой первичный ключ, который уникально идентифицирует запись в таблице Students .

Такое утверждение будет верно и для более общего случая: если X - ϶ᴛᴏ потенциальный ключ, то множество всœех атрибутов R всœегда функционально зависит от X .

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

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

Пример :

{StudentID , FirstName , LastName , MiddleName } → {BirthDate } – приводимая ФЗ.

{StudentID } → {BirthDate } – неприводимая ФЗ.

Множество функциональных зависимостей принято называть неприводимым тогда и только тогда, когда оно обладает всœеми тремя перечисленными ниже свойствами:

1. Зависимая часть каждой функциональной зависимости содержит только один атрибут.

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

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

Рассмотрение множества неприводимых ФЗ важно для нормализации отношений.

Выделяют два вида ФЗ:

1. Тривиальные ФЗ - ϶ᴛᴏ ФЗ, в которых правая часть (Y ) является подмножеством левой части (X ). С практической точки зрения они не представляют значительного интереса, однако с точки зрения формальной теории зависимостей крайне важно учитывать их наличие.

2. Нетривиальные ФЗ . Οʜᴎ действительно являются ограничениями целостности данных, в связи с этим в дальнейшем мы будем рассматривать именно нетривиальные ФЗ.

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

Пусть A , B , C - ϶ᴛᴏ подмножества множества атрибутов отношения R , AB – объединœение этих подмножеств.

1. Правило рефлексивности . В случае если множество B является подмножеством множества А , то А → В . (По сути, это определœение тривиальной зависимости.)

2. Правило дополнения . В случае если А → B , то АС → ВС .

3. Правило транзитивности . В случае если А → B и B→C , то А → С .

Каждое из этих правил должна быть доказано на базе определœения ФЗ.

При этом в целях упрощения получения всœех ФЗ можно вывести еще несколько дополнительных правил (пусть D - ϶ᴛᴏ еще одно произвольное подмножество множества атрибутов R ):

4. Правило самоопределœения . А → А .

5. Правило декомпозиции . В случае если А → ВС , то А → B и A → C .

6. Правило объединœения . В случае если А → В и А → С , то А → ВС .

7. Правило композиции . В случае если А → B и С → D , то АС → BD .

8. Теорема всœеобщего объединœения . В случае если А→ B и C → D , то А(С – В) → BD .

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

При этом следует иметь в виду, что эти правила не обеспечивают чёткого алгоритма получения всœех ФЗ. Более того, такого алгоритма не существует. Единственный путь - ϶ᴛᴏ перебор всœех вариантов.

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

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

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

Информация > формализация >> данные

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

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

Функциональная зависимость: «правильное решение = программа (программист)» и условие: «непрерывное соответствие задаче» действительны в большинстве случаев, но только совместно. Но это не та математическая основа, которая применяется при создании баз данных.

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

и базы данных

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

Основные варианты хранения, отличающиеся вариантами использования данных:

• файлы;
• базы данных.

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

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

Личный опыт и коллективный разум

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

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

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

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

• солидный Oracle;
• требовательный MS SQL Server;
• популярный MySQL.

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

Особенности программирования и данных

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

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

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

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

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

БД: простая зависимость в данных

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

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

Имя каждой колонки в каждой таблице должно быть уникальным в контексте задачи. Одно и то же данное не может быть в двух таблицах. Знать смысл понятий:

• «определить сущности»;
• «исключить избыточность»;
• «зафиксировать взаимосвязи»;
• «обеспечить достоверность».

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

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

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

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

Не обязательно, но вовсе не помешает представлять функциональную зависимость как:

F(x1, x2, …, xN) = (y1, y2, …, yN).

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

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

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

О старом добром Excel

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

• PHP, Perl, JavaScript, C++, Delphi.
• MySQL, Oracle, Visual FoxPro.

• Word.
• Excel.

Некоторые пользователи умудряют делать самостоятельно (без помощи программистов) в Word базы данных - реальный нонсенс.

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

Табличная идея, определила понятие функциональной зависимости наглядно и доступно, но нюансы есть у каждой базы данных. У каждой свое «лицо», но все от Excel до Oracle манипулируют простыми квадратами, то есть таблицами.

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

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

О том, куда реляционные отношения идут

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

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

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

Вариантов отношений можно придумать великое множество. Это математика с логикой, и она строгая! Информация - это своя математика, особенная. В ней о формальности можно говорить только с очень большим минусом.

Можно формализовать работу отдела кадров, написать АСУ для добычи нефти или производства молока, хлеба, сделать выборку в огромной базе гугла, яндекса или рамблера, но результат будет всегда статичен и каждый момент времени одинаков!

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

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

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

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

Если сменить тон и прислушаться к пульсу динамики, то все можно расписать на объекты. В первом приближении имя колонки в таблице - это объект, список имен - тоже объект, короче таблица - это объект шапки и в нем имена колонок в шапке. И шапки может вовсе не быть...

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

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

Лекции № 8-9.

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

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

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

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

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

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

Вначале вспомним некоторые понятия:

Простой атрибут - это атрибут, значения которого неделимы. Иными словами, в таблице нет полей типа ФИО или Адрес - они разложены на поля Фамилия, Имя, Отчество в первом случае и на поля Индекс, Город и т. д. во втором.

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

Определение функциональной зависимости: Пусть X и Y атрибуты некоторого отношения. Если в любой момент времени произвольному значению X соответствует единственное значение Y, то Y функционально зависит от X (X →Y)

Если ключ является составным, то любой атрибут должен зависеть от ключа в целом, но не может находиться в функциональной зависимости от какой-либо части составного ключа, т.е. функциональная зависимость имеет вид (X 1 , X 2 , ..., X) →Y.

Функциональная зависимость может быть полной или неполной.

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

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

Определение транзитивной функциональной зависимости: Пусть X, Y, Z - три атрибута некоторого отношения. При эtom X →Y и Y →Z, но обратное соответствие отсутствует, то есть Y не зависит от Z, а Х не зависит от Y. Тогда говорят, что Z транзитивно зависит от Х.

Определение многозначной зависимости: Пусть Х и Y атрибуты некоторого отношения. Атрибут Y многозначно зависит от атрибута X, если. каждому значению X соответствует множество значений Y, не связанных с другими атрибутами из отношения. Многозначные зависимости могут носить характер «один ко многим» (1:М), «многие к одному» (М:1) или «многие ко многим» (М:М), обозначаемые соответственно: X=>Y, Y<=X и X<=>Y. Например, преподаватель ведет несколько предметов, а каждый предмет может вестись несколькими преподавателями, тогда имеет место зависимость ФИО <=> Предмет.

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

ФИО - фамилия и инициалы преподавателя (совпадения фамилий и инициалов исключаются).

Должность - должность, занимаемая преподавателем.

Оклад- оклад преподавателя.

Стаж - преподавательский стаж. Д_Стаж - надбавка за стаж.

Кафедра - номер кафедры, на которой числится преподаватель.

Предмет - название предмета (дисциплины), читаемого преподавателем.

Группа - номер группы, в которой преподаватель проводит занятия.

Вид занятия - вид занятий, проводимых преподавателем в учебной группе.

Исходное отношение ПРЕПОДАВАТЕЛЬ

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

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

· каждый поставщик поставляет товар по определенной цене,

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

· каждый склад имеет свой объем.

Эти ограничения являются зависимостями, которые можно сформулировать следующим образом:

· адрес функционально зависит от поставщика,

· цена функционально зависит от товара и поставщика,

· номер склада функционально зависит от товара и поставщика,

· объем функционально зависит от номера склада.

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

Пусть отношение r имеет схему R , X и Y – подмножества R . Отношение r удовлетворяет функциональной зависимости X→Y , если π Y (σ X=x (r)) имеет не более чем один кортеж для каждого значения xÎX , т. е. значения атрибутов X однозначно определяют значения атрибутов Y.

Функциональную зависимость будем обозначать следующим образом:

· Поставщик → Адрес,

· {Товар, Поставщик}→ Цена,

· {Товар, Поставщик}→ Склад,

· Склад → Объем.

А читаются они так:

· Поставщик определяет Адрес,

· Товар и Поставщик определяют Цену,

· Товар и Поставщик определяют Склад,

· Склад определяет Объем.

На языке функциональных зависимостей ключ для схемы R – это подмножество KÍR , такое, что K →R , и никакое собственное подмножество K¢ÍK этим свойством не обладает.

Нормальные формы

Сформулируем правила, по которым следует проводить де­компо­­зицию отношения. Этот процесс называется нормализацией, т. е. при­­ведением отношения к нормальной форме.

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

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

Например, атрибут ФИО является составным, состоит из трех данных: фамилии, имени и отчества.

Чтобы привести схему в 1НФ, нужно все составные атрибуты заменить простыми.

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

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

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

Например, в отношении Поставка первичными атрибутами являются Товар и Поставщик . Атрибут Цена функционально полно зависит от ключа, а атрибут Адрес зависит от части ключа, т. е. только от атрибута Поставщик , это неполная функциональная зависимость. Значит, схема Поставки не находится во 2НФ.

Чтобы привести схему, находящуюся в 1НФ, ко 2НФ, нужно разбить ее на несколько схем:

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

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

В примере с отношением Поставки в результате приведения схемы ко 2НФ получатся два отношения:

Поставки_1 (Товар , Поставщик , Цена, Склад, Объем ),

Поставки_2 (Поставщик , Адрес ).

Однако информация об объеме склада продолжает дублироваться. Для устранения этого недостатка схемы существует третья нормальная форма.

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

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

Схема отношения Поставки_1 (Товар , Поставщик , Цена, Склад, Объем ) не находится в 3НФ, так как в ней присутствует транзитивная зависимость:

{Товар, Поставщик } → Склад , Склад → Объем .

Чтобы привести схему, находящуюся во 2НФ, в 3НФ, нужно:

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

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

В примере с отношением Поставки_1 в результате приведения схемы к 3НФ получатся два отношения:

Поставки_1_1 (Товар , Поставщик , Цена, Склад ),

Поставки_1_2 (Склад , Объем ).

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

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

В рассмотренном примере в результате декомпозиции вместо одного отношения Поставки мы получили три новых отношения:

Поставки_1_1 (Товар , Поставщик , Цена, Склад ),

Поставки_1_2 (Склад , Объем ),

Поставки_2 (Поставщик , Адрес ).

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

Как вы заметили, схема в 3НФ избавляет базу данных от дублирования информации и аномалий обновления, но не всегда.

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

· каждый студент, изучающий данный предмет, обучается только одним преподавателем,

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

Из этих ограничений вытекают следующие функциональные зависимости:

· {Студент, Предмет} → Преподаватель;

· Преподаватель → Предмет.

Из функциональных зависимостей вытекает, что ключом отношения Лекции будет набор атрибутов {Студент , Предмет }.

Отношение Лекции находится в 3НФ. Но оно страдает аномалиями обновления. Если требуется удалить информацию о том, что Петров изучает Физику, то утратится информация о том, что профессор Серов преподает Физику. В то же время информация о том, что профессор Белый ведет Алгебру, дублируется.

Эти трудности вызваны тем, что существует функциональная зависимость первичного атрибута от непервичного. Эта проблема решается в нормальной форме Бойса–Кодда.

Отношение находится в нормальной форме Бойса–Кодда (НФБК) , если оно находится в 3НФ и в нем отсутствуют зависимости первичных атрибутов от непервичных. Эквивалентное определение требует, чтобы все левые части функциональных зависимостей были потенциальными ключами.

Приведя отношение к НФБК, мы получим два отношения: Лекции_1 (Студент, Преподаватель ) и Лекции_2 (Преподаватель, Предмет ).

Многозначные зависимости

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

Многозначная зависимость обозначается двойной стрелкой: X→→Y .

Рассмотрим отношение Преподаватель (Номер , Имя_ребенка , Предмет , Должность ). Предметная область накладывает следующие ограничения:

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

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

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

· каждый предмет могут вести несколько преподавателей.

Тогда отношение Преподаватель имеет две многозначные зависимости и одну функциональную:

· Номер→→Имя_ребенка,

· Номер→→Предмет,

· Номер→Должность.

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

Для избавления от этих аномалий необходимо привести отношение к четвертой нормальной форме.

Отношение находится в четвертой нармальной форме (4НФ ), если оно находится в нормальной форме Бойса–Кодда и в нем отсутствуют многозначные зависимости, которые не являются функциональными.

После приведения отношения Преподаватель к 4НФ мы получим три отношения:

Преподаватель_1 (Номер , Должность ),

Преподаватель_2 (Номер , Имя_ребенка ),

Преподаватель_3 (Номер , Предмет ).

Свойства декомпозиции