Многозначная зависимость и четвертая нормальная форма

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

Мы не случайно представили эти атрибуты в виде иерархической структуры, так как именно она наиболее адекват­но отражает смысл связей между указанными атрибутами. У нас нет конкретной информации о связи преподавате­лей с учебниками, мы не знаем по какому учебнику тот или иной преподаватель излагает конкретную дисциплину. Тем не менее, при представлении этого отношения мы должны в каждом его кортеже указать значения всœех трех атрибутов (по крайней мере потому, что эти атрибуты составляют ключ, а значения ключевых атрибутов всœегда должны быть определœены). Единственным выходом из данной ситуации является следующий: если с предметом, к примеру БД, связаны преподаватели Иванов и Петров и учебники Основы БД, Введение в БД и Теория БД, то в отношении каждый из этих преподавателœей должен быть связан (ассоциирован) с каждым учебником, как это показано на примере ниже. Другого выхода нет.

ЛЕКЦИЯ	Предмет	Преподаватель	Учебник
	БД	Иванов	Основы БД
	БД	Иванов	Введение в БД
	БД	Иванов	Теория БД
	БД	Петров	Основы БД
	БД	Петров	Введение в БД
	БД	Петров	Теория БД

Другими словами, мы должны констатировать следующую семантику связи между преподавателями и учебника­ми: "Данный предмет преподают такие-то преподаватели и для чтения лекций по этому предмету всœе они исполь­зу­­ю­т ВСЕ указанные учебники".

Мы здесь приходим к следующему тезису:

Тезис: В случае если в предметной области отсутствует какая-либо непосредственная связь между атри­бу­та­ми А и В, а нам по тем или иным причинам крайне важно зафиксировать такую связь в отношении, то единственным коррект­ным решением является установление, что всœе значения атрибута А связаны со всœеми значениями атрибута В, и наоборот.

Отметим, что независимость преподавателœей от учебников и наоборот, а также трактовка такой независимости согласно приведенному выше тезису свидетельствует, что в нашем отношении Лекции атрибуты Преподаватель и Учебники обладают следующим важным свойством:

Множество учебников, которые связаны с конкретным предметом, совпадает со множеством учебников, которые связаны с парой значений <предмет, преподаватель> (с предметом "БД" связаны три учебника, эти же три учебника связаны с парами значений <"БД","Иванов"> и <"БД","Петров">). И наоборот, множество преподавате­лей, которые связаны с конкретным предметом, совпадает с множеством преподавателœей, которые связаны с парой значений <предмет, учебник>.

Данное свойство является принципиальным в понимании многозначной зависимости.

Очевидно, что такое отношение избыточно и приводит к трудностям в выполнении операций манипу­ли­ро­ва­ния. Лектор входит в атрибут Преподаватель столько раз, сколько имеется учебников и об этом следует помнить вся­кий раз, производя операции вставки удаления и замены преподавателœей. То же самое имеет место и для учебников.

В связи с этим было введено понятие многозначной зависимости.

Определœение . Пусть задано отношение R с атрибутами (или наборами атрибутов) А, В, С. Говорят, что существует многозначная зависимость (multivalued dependecy ) В от А (или А многозначно определяет В), и это обозначается как А ®® В, в случае если при заданных значениях атрибутов из А существует множество связанных значений атрибутов из В и это множество В-значений не зависит каким-либо образом от значений атрибутов из С.

К примеру, в отношении ЛЕКЦИЯ атрибут Преподаватель многозначно зависит от атрибута Предмет (Предмет ®® Преподаватель) и атрибут Учебник многозначно зависит от Предмет (Предмет ®® Учебник).

Дадим формальное определœение многозначной зависимости. Пусть отношение R определœено на множестве атрибутов M и А, В – подмножества М, причем А и В могут пересекаться. Определим через В R (а) множество проекций кортежей отношения R по атрибутам В, которые связаны с конкретным кортежем, спроецированным по атрибутам А, то есть:

В R (а) = {b | $r Î R, r[A] = a & r[B] = b}

Пусть С = М – (А В). Тогда будем говорить, что В R (а) в R имеет место многозначная зависимость А ®® В, если

"ас Î R В R (аc) = В R (а)

Другими словами, совокупность значений атрибутов В, которая появляется в кортежах отношения R с хаданным значением а атрибутов А, появляется также с каждой комбинацией значений а и с Î С, ас Î R. Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, множество значений В для заданного а не зависит от значений С, появляющихся вместе с а.

По определœению А ®® Æ для любой совокупности атрибутов А из R. Более того всœеда имеет место А ®® В, в случае если R определœено только на множестве атрибутов А В. Эти два вида многозначных зависимостей называются тривиальными так как они присутствуют во любых отношениях.

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

Займемся многозначными зависимостями возникающими при приведении в 1НФ отношений с двумя и более многозначными атрибутами. К определению четвертой нормальной формы придем через обобщение понятия функции, заданной на отношении, до многозначной функциональной зависимости. Обобщение теоремы Хиса на такие зависимости называется теоремой Фейгина. Она определяет правило приведения к четвертой нормальной форме. Рассмотрим отношение, в котором курс может считать не один лектор, но для каждого лектора обязателен один и тот же набор учебников, обозначенных по фамилиям авторов (таблица 5.10). Имейте в виду, что такие авторы, как Чучкин, Пупкин, Малинин и Буренин когда-то существовали.

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

Таблица 5.11. Пример многозначной зависимости. 1НФ

ДИСЦИПЛИНА	ЛЕКТОР	УЧЕБНИК
Арифметика	Иванов	Чучкин & Пупкин
Арифметика	Иванов	Малинин & Буренин
Арифметика	Петров	Чучкин & Пупкин
Арифметика	Петров	Малинин & Буренин
Генетика	Карпов	Вайсман
Генетика	Карпов	Лысенко
РК

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

Образуется многозначная зависимость, в которой:

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

Определение . MV-зависимость называется тривиальной если, либо .

Рассмотрим еще одно отношение с многозначными зависимостями (рисунок 5.17). Обозначения: 3 - завод, Т - товар, М - магазин. Выполняется условие: каждый товар из группы товаров продается во все магазины из некоторой группы магазинов. При этом и в группе товаров и в группе магазинов может быть один экземпляр. Исходное отношение ЗТМ разлагается на отношения ЗТ и ЗМ. В отличие от первых четырех нормальных форм связи между созданными отношениями (ЗТ и ЗМ) отсутствуют.

Определение (MV-зависимость). Пусть - отношение, а - непересекающиеся множества его атрибутов. Атрибуты и многозначно зависят от (обозначение ) если из того, что в отношении содержатся кортежи и , следует, что в отношении содержится также кортеж .

По симметрии определения в содержится и кортеж. Атрибуты и как бы симметричны по отношению к .

При наличии MV-зависимости кортежи обязаны вставляться и удаляться одновременно целыми наборами.

Теорема Фейгина (R. Fagin) играет для многозначных зависимостей ту же роль, что теорема Хиса для функциональных зависимостей. Примем ее без доказательства.

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

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

Обучение

Рис. 4.5. К иллюстрации многозначных зависимостей

Для примера рассмотрим таблицу "Обучение" (рис. 4.5). В ней есть многозначная зависимость "Дисциплина-Преподаватель": дисциплина (в примере Информатика) может может читаться несколькими преподавателями (в примере Шипиловым и Голованевским). Есть и другая многозначная зависимость "Дисциплина-Учебник": при изучении Информатики используются учебники "Паскаль для всех" и "Язык Си". При этом Преподаватель и Учебник не связныфункциональной зависимостью, что приводит к появлению избыточности (для добавление еще одного учебника придется ввести в таблицу две новых строки). Дело улучшается при замене этой таблицы на две: (Дисциплина-Преподаватель и Дисциплина-Учебник).

[ Назад ] [ Содержание ] [ Вперед ]

Базы данных: О нормализации, функциональных и многозначных зависимостях
страницы в данном разделе
Базы данных: Данные и ЭВМ	Базы данных: Концепция баз данных
Базы данных: Архитектура СУБД	Базы данных: Модели данных
Базы данных: Основные понятия	Базы данных: Характеристика связей и язык моделирования

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

1. Power On Self Test (POST) - запускается только один раз и сразу после включения питания. В этом тесте проверяется аппаратура на наличие грубых ошибок (функционирование аппаратуры вообще). Одним из видимых шагов на экране - тестирование памяти.
2. Инициализация - запускается каждый раз, когда машина перегружается (например, когда пользователь нажимает Ctrl-Alt-Del) - инициализирует все доступные устройства на плате и в слотах расширения (ISA, PCI, AGP).
3. Третья часть - это собственно BIOS (BASIC INPUT/OUTPUT SYSTEM) - базовая система ввода/вывода на низком уровне. Этими функциями пользуются некоторые операционные системы (DOS, Windows и др.) Обычно, весь BIOS располагается на отдельном чипе, который программируется на заводе, хотя в современных компьютерах может быть перепрограммирован прямо из системы. Т.е. сейчас используется Flash Memory.

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

Тест памяти - это наиболее видимая часть теста аппаратуры на этапе POST. Кстати, о видимости - видеоадаптер - тоже аппаратура, и его как раз необходимо инициализировать в первую очередь - чтобы пользователь мог видеть процесс тестирования и инициализации устройств. Так же, необходимо установить еще и режим (частоту обновления, разрешение) экрана. Ведь видеокарты могут быть сделаны разными фирмами, да еще и разные модели - кому как не БИОСу самой карточки знать досконально, как ее нужно инициализировать?
На каждой видеокарте есть свой BIOS, который опрашивается на его наличие при тестировании аппаратуры. Сначала системный БИОС ищет видео по стандартным адресам ISA VGA, - если там нет адаптера, то он ищется на PCI , потом на AGP (или сначала AGP, а потом PCI - это прописывается в установках BIOS SETUP). И если, видеобиос найден в одном из слотов, то управление передается на него.

И вообще, присутствие БИОСа на различных адаптерах заставляет системный БИОС отдавать им управление - в случае с видеоадаптером - это включение режима и т.д., в случае с сетевой картой - загрузка с сети (в случае с без дисковыми машинами - удаленная загрузка с сети) - при наличие BIOS на сетевой карте и наличие жесткого диска БИОС, например, может спросить - как будем грузиться - с сети или с имеющегося HDD? При наличии SCSI адаптера - он должен проинициализировать свои устройства (диски, CD-приводы, ленточные накопители и т.п.) и если таковые найдутся из числа дисков SCSI - необходимо будет поддержать int13 для того, чтобы система могла обращаться к ним, как к обычным жестким дискам. Хотя, инициализация SCSI устройств необязательна - например, при старте, ее можно отключать - если SCSI устройство не является загрузочным, это разумно.

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

Итак, коротко можно описать следующим образом: все, кроме SCSI, IDE, USB "оживает" сразу - из адаптеров исключение составляет видеоадаптер, который инициализируется даже до проверки памяти.

Далее - если в слотах ISA находятся другие устройства, имеющие свои ПЗУ (с BIOS) - они инициализируются на этапе проверки внешних устройств, потом проходит проверка и назначение PCI (проверка устройств Plug and Play). Кстати, PnP есть и на ISA адаптерах.
Только после этого начинается проверка наличия устройств на IDE шине.

Тут может возникнуть вопрос - а как быть, если на ISA нет видеоадаптера, а есть на PCI - но ведь он "оживает" сразу - не дожидаясь даже проверки всего PCI? Просто на PCI есть BIOS, отображаемый в обычное пространство памяти, и все VGA PCI имеют еще и стандартную VGA программную часть, находящуюся в тех же регистрах, как и в случае, если бы это был ISA адаптер. Системный BIOS проверяет, есть ли VGA на ISA шине - если да, то на PCI шину и "не лезет", если нет - то сканирует PCI.

Ну, и в конце концов, после инициализации - считывается первый сектор первой дорожки первой головки жесткого диска и управление передается загрузочному сектору, который уже управляет дальнейшими действиями (либо выдается сообщение типа "NO SYSTEM TO BOOT"). Или подобным же образом система грузится с дискеты.

Загрузка операционной системы является сложным процессом и состоит из нескольких этапов.


Немногие пользователи ПК знают, что происходит после нажати кнопки Power с их компьютером. Итак, поехали!

1. После включения питания ПК начинается процесс его автоматического тестирования, тот, что выполняется под управлением программы BIOS. Если на этом этапе будет найдено неисправное оборудование, то загрузка компьютера остановится с выводом на экран соответствующего сообщения либо звуковых сигналов.
2.После завершения автоматического тестирования BIOS ищет загрузочный сектор на дискете, HDD, компакт-диске либо ином носителе, поддерживаемом системной платой. Порядок поиска загрузочного сектора задается с поддержкой , описание которых можно обнаружить в инструкции к
3. После определения загрузочного диска с него загружается содержимое первого сектора диска, в котором находится основная загрузочная запись (Master Boot Record, MBR). В MBR также содержится таблица разделов диска, один из которых должен быть помечен как активный.

4. MBR находит активный раздел и передает управление загрузочной записи, которая должна находиться в первом секторе активного раздела. С подмогой загрузочной записи запускается менеджер загрузки Windows 7 (файл bootmgr, тот, что находится в корневой папке активного раздела).
5.Менеджер загрузки считывает данные конфигурации системы ПК, которые хранятся в файле BCD (Boot Configuration Data). При наличии нескольких записей в файле BCD будет отображено меню выбора операционной системы. Файл BCD находится в папке Boot активного раздела.
6. После выбора системы запускаются модуль загрузки операционной системы Winload. exe, компоненты ядра Ntoskrnl. exe и Hal. dll, системные службы и другие компоненты - данный этап сопровождается итогом анимированного экрана с логотипом Windows.
7. Загружается процесс winlogon. exe, тот, что управляет входом пользователей в систему. Если на компьютере имеется одна учетная запись, не защищенная паролем, вход будет исполнен автоматически. В другом случае система будет ждать выбора имени пользователя и ввода пароля.
8. В процессе входа в систему запускаются элементы автозагрузки, которые прописаны в реестре Windows 7 и папке Автозагрузка.
Исходя из изреченного выше, дозволено сделать итог, что для удачной загрузки Windows 7 нужны следующие данные.
Нынешние настройки BIOS обязаны обеспечивать загрузку с HDD, на котором установлена Windows 7. Если в BIOS установлена первоочередная загрузка со сменных носителей, следует также извлечь диски из приводов.

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

На активном разделе должна быть загрузочная запись Windows 7, а в его корневой папке должен находиться файл bootmgr.
В папке Boot активный раздела должен присутствовать файл BCD, содержащий верные записи об установленных операционных системах.

Примечание
в качестве 2-й операционной системы активный традиционно является раздел, на котором установлена предыдущая версия Windows. Именно там находятся файл bootmgr и папка Boot. Если же вы исполняли разбивку жесткого диска на разделы средствами Windows 7, то активным будет назначен спрятанный раздел размером около 100 Мбайт.
Если компьютер не загружается, попытайтесь узнать, на каком именно этапе происходит остановка. Сообщение, которое выводится при прекращении загрузки системы, обычно разрешает достаточно верно определить возникшую загвоздку.
Не поленитесь при необходимости перевести его с английского языка. Если вам не удалось обнаружить место ошибки по сообщениям либо загрузка останавливается без их возникновения, испробуйте воспользоваться следующими советами.
Посмотрите, отображается ли на экране меню выбора операционной системы либо меню дополнительных вариантов загрузки. Если нет, испробуйте в процессе загрузки несколько раз нажать клавишу F8. Если меню выбора вариантов загрузки не удалось вывести на экран, причинами могут быть ошибки оборудования, неправильные параметры BIOS, поврежденные загрузочные секторы либо файлы (см. этапы 1-5 описанной выше последовательности ).
Если меню загрузки отображается, но сразу после выбора операционной системы запуск останавливается, допустимо, в файле BCD содержатся ложные записи.
Если запуск останавливается позже итога анимированного экрана с логотипом Windows, возможно, поводом сбоя является драйвер устройства либо системная служба.