Разработка модели оценки знаний

Алгоритм нормализации (т.е. алгоритм приведения отношений к 3НФ) описывается следующим образом.

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

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

Исходное отношение:.

Ключ: - сложный.

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

- зависимость всех атрибутов от ключа отношения.

- зависимость некоторых атрибутов от части сложного ключа.

Декомпозированные отношения:

- остаток от исходного отношения. Ключ .

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

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

Исходное отношение: .

Ключ: K.

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

- зависимость всех атрибутов от ключа отношения.

- зависимость некоторых неключевых атрибутов других неключевых атрибутов.

Декомпозированные отношения:

- остаток от исходного отношения. Ключ K.

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

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

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

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

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

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

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

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

Для ответов на эти вопросы нужно ответить на вопрос - что же представляет собой декомпозиция отношений с точки зрения операций реляционной алгебры? При декомпозиции мы из одного отношения получаем два или более отношений, каждое из которых содержит часть атрибутов исходного отношения. В полученных новых отношениях необходимо удалить дубликаты строк, если таковые возникли. Это в точности означает, что декомпозиция отношения есть не что иное, как взятие одной или нескольких проекций исходного отношения так, чтобы эти проекции в совокупности содержали (возможно, с повторениями) все атрибуты исходного отношения. Т.е., при декомпозиции не должны теряться атрибуты отношений. Но при декомпозиции также не должны потеряться и сами данные. Данные можно считать не потерянными в том случае, если возможна обратная операция - по декомпозированным отношениям можно восстановить исходное отношение в точности в прежнем виде. Операцией, обратной операции проекции, является операция соединения отношений. Имеется большое количество видов операции соединения. Т.к. при восстановлении исходного отношения путем соединения проекций не должны появиться новые атрибуты, то необходимо использовать естественное соединение.

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

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

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

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

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

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

Введем также понятие «внешний ключ»: атрибут отношения R1 является внешним ключом, если этот атрибут – не первичный ключ отношения R1, но его значения являются значениями первичного ключа некоторого отношения R2 (R1 и R2 не обязательно различны).

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

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

−        однозначную идентификацию записей таблицы; 

−        ускорение выполнений запросов к БД;

−        установка связи между отдельными таблицами БД;

−        использование ограничений ссылочной целостности;

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

Вместе с тем существуют и общие правила, состоящие в следующем:

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

−        ключ должен быть достаточным и не избыточным, т.е. не содержать поля, которое можно удалить без нарушения уникальности ключа;

−        в состав ключа не могут входить поля некоторых типов, например графическое поле, или поле комментария.

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

Первичным ключом в отношении «Stud» выбрано поле – FIO_stud. Во втором отношении «Gruppa» – Gruppa. В отношении «Prepod» – FIO_Prep. В отношении «Dolgnost» – Dolgnost. В отношении «Dostup» - Dostup. В отношении «Result» - ключ составной, он состоит из двух полей FIO_stud и test.

4.2 Потенциальные ключи

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

      уникальности: нет двух различных кортежей в R с одинаковым знанием К;

      не избыточности: ни какое из подмножеств К не обладает свойствами уникальности.

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

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

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

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

4.3 Ссылочная целостность

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

4.4 Первичные и внешние ключи

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

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

Внешние ключи:

      если сущность С связывает сущности А и В, то она должна включать внешние ключи, соответствующие первичным ключам сущностей А и В;

      если сущность В обозначает сущность А, то она должна включать внешний ключ, соответствующий первичному ключу сущности А.

Существуют три ограничения на внешний ключ:

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