6179

Модели данных: нормализация отношений

Реферат

Информатика, кибернетика и программирование

Модели данных: нормализация отношений. 1НФ. Нормализация отношений Центральная задача проектирования базы данных ЭИС - определение количества отношений и их атрибутного состава. Задача группировки атрибутов в отношения допускает множеств...

Русский

2012-12-30

80.5 KB

14 чел.

Модели данных: нормализация отношений. 1НФ.

  1.   Нормализация отношений

Центральная задача проектирования базы данных ЭИС - определение количества отношений и их атрибутного состава.

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

•  множество отношений должно обеспечивать минимальную избыточность представления информации,

• корректировка отношений не должна приводить к двусмысленности или потере информации,

•  перестройка набора отношений при добавлении в базу данных новых атрибутов должна быть минимальной.

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

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

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

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

Преобразование ненормализованного отношения в представление, соответствующее 1НФ - это операция нормализации.  Реляционная база данных в целом характеризуется 1НФ, если все ее отношения соответствуют 1НФ.

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

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

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

Иначе говорят, что В функционально зависит от А (обозначается В = f(A)). Отсутствие функциональной зависимости обозначается А—/  В.

 

Пример 1.

I1

ФИО

ГР

Иванов

Зуев

Смирнов

Яшина

 I960

1963

1960

1961

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

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

Одновременное соблюдение двух зависимостей вида А В и В А называется взаимно-однозначным соответствием и обозначается А В.

Пример 2.

I2

Магазин

Расч

ММЗ

Динамо АТЭ

704098 122096 440162

Можно допустить, что у каждого магазина единственный номер расчетного счета и утверждать, что каждый расчетный счет принадлежит единственному магазину. Это доказывает справедливость функциональных зависимостей Магазин Расч и Расч Магазин, т.е. Магазин Расч.

Примера 3.  

I3

ФИО

Дисциплина

Петров Федин Алешин Петров

Физика Химия Физика Химия

Отношение I3 описывает экзамены, сдаваемые студентами:  ФИО —/ Дисциплина и Дисциплина —/ ФИО, т.к.  каждый студент сдает экзамены по нескольким дисциплинам, и по каждой дисциплине экзамен сдается многими студентами. Т.е. отсутствуют функциональные зависимости.

Таким образом, для атрибутов А и В некоторого отношения возможны следующие ситуации:

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

• наличие А В (или В А), но не обе зависимости вместе,

• наличие взаимно-однозначного соответствия А В.

Понятие функциональной зависимости распространяется на ситуацию с тремя и более атрибутами в следующей форме. Группа атрибутов (для определенности А,В,С) функционально определяет атрибут D в отношении T(A,B,C,D,....), если каждому сочетанию значений <а,b,с> соответствует единственное значение d (а - значение A, b - значение В, с - значение С, d - значение D). Наличие такой функциональной зависимости будем обозначать А,В,С D.  

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

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

Для показателя со множеством атрибутов-признаков Р = {Р1, Р2, ... ,Рn} и атрибутом-основанием Q справедлива функциональная зависимость Р Q, но нельзя утверждать, что это единственная зависимость на указанных атрибутах.

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

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

Примера 4.  

I4

ZEN

RAM

AST

SPIM

BIG

1А

31

dwa

wii

73

ЗВ

21

bun

CUD

—*K

40

3D

30

mun

lam

58

40

31

sab

wii

40

Вероятным ключом отношения I4 является атрибут ZEN и пара атрибутов RAM, AST.

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

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

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

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

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

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

Набор атрибутов первичного ключа функционально определяет любой атрибут отношения. 

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

Пример 5.

I5

ФИО

Дисциплина

Дата

Преподаватель

Оценка

Петров Федин Алешин Петров

Физика Химия Физика Химия

10.02.11

10.02.11

14.02.11

14.02.11

Иванов

Смирнов

Иванов

Смирнов

4

5

5

5

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

ФИО, Дата Дисциплина,

ФИО, Дата Преподаватель,

ФИО, Дата Оценка.

Ясно, что

ФИО, Дата ФИО,

ФИО, Дата Дата

Следовательно, первичный ключ в отношении I5 составляют атрибуты ФИО, Дата и при поиске ключа не потребовались конкретные значения I5.

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

Теорема1

А, В А и А, В В.

Доказательство основано на том, что в строке <а,b> для атрибутов А и В значение а (как и значение b) присутствует один раз.

Теорема 2

А В и А С тогда и только тогда, когда А ВС.

Рассмотрим произвольное значение а атрибута А. Если АВ и АС, то imВ(а) и imC(a) содержат по одному элементу. Предположим, что зависимость А ВС неверна и im ВС(а) состоит из 2 или более элементов. Тогда либо im В(а), либо im С(а) должны содержать более одного элемента. Полученное противоречие доказывает зависимость А ВС.

Обратно, если А ВС, то  imВС(а)  содержит один элемент  вида <b,с> для любого а. Зафиксируем некоторое значение al. Значение b (как и значение с) встречается в сочетании с al только один раз, следовательно, справедливо А В и А С.

Теорема 3

Если АВ и ВС, то А С.

Предположим, что зависимость А С неверна и множество  imС(а)  содержит более одного элемента. Каждому значению а соответствует единственное значение b (в силу А В), поэтому  imC(b)  содержит более одного элемента. Получилось противоречие с условием В С, что и доказывает теорему.

Доказательства остальных теорем опираются на первые 3 теоремы.

Теорема 4

Если А  В, то АС В (С произвольно).

Доказательство :   АС А (теорема 1), А В (условие), следовательно, АС В по теореме 3.

Теорема 5

Если А В, то АС ВС ( С произвольно).

Доказательство:   АС В (теорема 4), АС С (теорема 1), следовательно, АС ВС по теореме 2.

Теорема 6 

Если А В и ВС  D, то AC  D.

Доказательство Из А В следует АС ВС (теорема 5).  ВС D (условие), поэтому АС D по теореме 3.

Количество теорем, которые можно доказать в таком стиле, можно расширить.

Для некоторого множества функциональных зависимостей F введем множество F~, называемое покрытием. Покрытие F~ содержит все функциональные зависимости, которые можно получить из множества F в результате применения теорем 1-6 (включая и содержимое F). Одно и то же покрытие F~ может быть получено из различных множеств функциональных зависимостей. Среди таких множеств выделим множество с минимальным числом зависимостей и назовем его минимальным покрытием (базисом) множества зависимостей F.

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

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

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

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


 

А также другие работы, которые могут Вас заинтересовать

44700. Особенности Экспорта 418.5 KB
  Экспорт Схемы в Графический Файл и Текстовый файл Профессиональный уровень Изготовителя Образца позволяет Вам экспортировать вашу диаграмму образца в следующие типы графических изображений: BMP JPEG TIFF RGB CMYK и 8 битов полутоновый GIF PCX WMF EMF и EPS 8 битов полутоновых растровых только. Информация вашей схемы может экспортироваться в Формат RTF RTF файл. Это откроет Мастер Экспорта схемы который будет вести Вас через процесс экспорта.
44701. Особенности Размещения Страницы 1.3 MB
  Эти возможности включают: Текстовое форматирование Форматирование параграфа Таблицы Разделы с выбираемыми номерами столбца и страницей устанавливают размеры форматируют Заголовки и Нижние колонтитулы Вставка объектов из других приложений Дополнительные специализированные возможности также обеспечены чтобы смешать особенности обработки текстов с возможностями дизайна РМ. Эти специализированные возможности включают: Таблицы мулине нитей содержание которых и форматирование могут быть...
44702. Графическая схема (Chart Graphic) 363 KB
  Таблица мулине нитей Этот раздел описывает как использовать таблицы мулине нитей в размещении. Вставка Таблицы Вышивального шелка ПотокаInserting Floss Thred Tble Чтобы вставлять Таблицу мулине направьте курсор в размещение где Вы хотите чтобы таблица была вставлена и затем выбирите Insert Edit Floss Tble в Меню разметки или нажать следующий значок инструментальной панели: . Удаление Таблицы мулине нитей Deleting Floss Thred Tble Чтобы удалять Таблицу мулине щелкните правой кнопкой мыши по таблице и затем выберите Delete...
44703. Диалоговое окно General Options 760 KB
  Следующие параметры настройки будут использоваться: Столбец: Центр Column: Center Данные: Право Dt: Right Выберите Sve чтобы использовать эти варианты как значение по умолчанию для новых таблиц. Настройки Customiztions Выберите включить ли черный контур outline вокруг образца цвета. Выберите Sve чтобы использовать эти варианты как значение по умолчанию для новых таблиц. Выберите Sve чтобы использовать эти варианты как значение по умолчанию для новых таблиц.
44704. Структурирование Документа 407.5 KB
  Если таблицы или разделы не используются то каждый элемент размещения будет направлен в страницу или страницы на отдельных строках используя единственный столбец. Для каждой страницы или группы страниц один или более Разделов могут быть созданы. Для каждого Раздела ориентация на бумаге размер страницы края страницы страница опций номерования и номер столбцов может быть выбрана.
44705. Особенности библиотеки (Library Features) 2.13 MB
  Создание Библиотеки Шрифта Creting Font Librry Особенность текста входящая в РМ использует сделанные образцы шрифта. Они специализированы в схемы библиотек куда каждый символ номер символ шрифта нарисованный в одной ячейке библиотеки. Название ячейки для каждой ячейки образца шрифта фактический символ шрифта который ячейка представляет. Рисуйте все символы числа символы для вашего шрифта.
44706. Панели инструментов Pattern Makera 853 KB
  Панель Min Главная 1 создать новый файл схемы 2 импорт графического файла в новый файл схемы 3 открыть файл схемы 4 сохранить текущий файл 5 печать 6 вырезать выделенный фрагмент в буфер обмена 7 копировать выделенный фрагмент в буфер обмена 8 вставить фрагмент из буфера обмена на текущую схему 9 отменить действие 10 вставить схему из галереи 11 вызвать справку Панель View Вид 1 отобразить схему в виде крестиков 2 отобразить схему в виде символов 3 отобразить схему в виде цветных квадратов 4 показать...
44707. Работа программы PM для вышивки крестом 2.61 MB
  Основные Особенности РМ позволяет Вам создавать схемы которые включают следующий стежок напечатает: Полный крест Полукрест Четверть Миниатюрный Назад Прямо бэкстич Специальный Французский Узел Цепочка ячеек До 240 цветов мулине вышивального шелка может использоваться при содействии дизайна. Эта особенность удобна когда Вы хотите использовать нарисованный эскиз как схему {руководство} для вашего дизайна. После создания дизайна РМ позволяет Вам создавать размещение страницы для...
44708. Преобразование сканированной Фотографии 3.65 MB
  Чтобы открыть Мастера Импортирования выберите Import Imge и затем Импортируйте В Новую схему из меню File или щелкните кнопкой панели Import Imge. Чтобы развернуть экран щелкните кнопкой Mximum которая расположена в верхнем правом угле главного окна Pttern Mker. Щелкните Browse чтобы выбрать файл. Щелкните Open после вашего выбора.