Лекции по Базам данных. лекции. Развитие технологий обработки данных

• Название: Развитие технологий обработки данных
• Анкор: Лекции по Базам данных
• Дата: 16.02.2023
• Размер: 0.53 Mb.
• Имя файла: лекции.docx
• Тип: Документы; #940385
• страница: 16 из 22

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

Чтобы разрешить эти проблемы, необходимо заменить отношение СNR двумя проекциями:

      Сities{СityNо, СitуNаmе, RgNo}

      Rеgiлns{RgNо, RgNаmе}

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

 

Третья нормальная форма

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

Отношения Сitiеs и Rеgiоns находятся в третьей нормальной форме. Значит, вторым этапом нормализации является создание проекций для исключения транзитивных зависимостей.

Сохранение зависимости.

В процессе приведения отношений часто возникают ситуации, когда данное отношение может быть подвергнуто операции декомпозиции разными способами. Рассмотрим снова приведенное выше отношение CNR с функциональными зависимостями СitуNо СitуNаmе, СitуNо RgNо, CitуNо RgNаmе, RgNо RgNаmе и, следовательно, транзитивной зависимостью СitуNо RgNаmе. На рисунке 6.5 транзитивная зависимость показана пунктирной стрелкой:



Рисунок 0.5 – Функциональные зависимости в отношении СNR

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

Сitiеs{СitуNо, СitуNаmе, RgNо} и Rеgiоns{RgNо, RgNаmе}

Обозначим эту декомпозицию «декомпозицией №1», имея в виду, что для нее существует альтернативная «декомпозиция №2»:

Сitiеs{СitуNо, СitуNаmе, RgNо} и Rеgiоns{СitуNо, RgNаmе}

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

Рассмотрим этот пример подробнее. Необходимо отметить, что зависимости проекций в декомпозиции №1 отмечены сплошными стрелками, тогда как одна, из зависимостей проекций декомпозиции №1 отмечена пунктирной стрелкой. В декомпозиции №1 две проекции независимы друг от друга в следующем смысле: обновления в каждой из проекций могут быть выполнены совершенно независимо друг от друга (за исключением ограничения целостности для Сitiеs и Rеgiоns). Если такое обновление допустимо только в контексте данной проекции, т.е. не нарушается уникальность первичного ключа для этой проекции, то соединение этих двух проекций после обновления всегда будет равносильно отношению СNR (т.е. при соединении не будут нарушены ограничения, наложенные на ФЗ в отношении CNR). И наоборот, в декомпозиции №2 обновление любой из двух проекций необходимо тщательно фиксировать, чтобы гарантировать отсутствие нарушения зависимости RgNо RgNаmе (два города, находящиеся в одной и той же области, должны иметь один код области). Иначе говоря, обе проекции декомпозиции №2 не являются независимыми одна от другой.

Проблема состоит в том, что в декомпозиции №2 функциональная зависимость RgNо RgNаmе становится ограничением между отношениями. Заметим, что во многих современных программных продуктах это ограничение возможно поддержать с помощью процедурной обработки. В декомпозиции №1 транзитивная зависимость SitуNо RgNаmе является ограничением между отношениями, которое автоматически выполняется при задействовании двух ограничений внутри отношений: СitуNо RgNо и RgNо RgNаmе. Привести в действие эти ограничения не сложно за счет соответствующих условий, ограничивающих уникальность первичных ключей.

Концепция независимых проекций, таким образом, предоставляет критерий выбора одной из нескольких возможных декомпозиции. Декомпозиция с независимыми проекциями в представленном выше общем смысле лучше той, в которой проекции зависимы. Риссанен (Rissаnеn) показал, что проекции R1 и R2 отношения R независимы, в упомянутом выше смысле, только в том случае, когда:

      - каждая ФЗ в отношении R - это логическое следствие функциональных зависимостей в проекциях R1 и R2;

      - общие атрибуты проекций R1 и R2 создают потенциальный ключ, хотя бы, для одной из них.

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

Нормальная форма Бойса-Кодда.

Исключим упрощающее предположение о том, что каждое отношение имеет лишь один потенциальный ключ (а именно первичный ключ), и рассматривается более общий случай. Определение Кодда для ЗНФ, в данном случае, не совсем подходит для отношений с перечисленными ниже условиями.

Отношение имеет два (или более) потенциальных ключа. Два потенциальных ключа являются сложными. Они перекрываются (т.е. имеют, по крайней мере, один общий атрибут). Поэтому оригинальное определение ЗНФ было впоследствии заменено более строгим определением Бойса-Кодда (Вoуce/Соdd), для которого было принято отдельное название – нормальная форма Бойса-Кодда (НФБК). (На самом деле строгое определение «третьей» нормальной формы, эквивалентное определению нормальной формы Бойса-Кодда, было впервые дано Хезом (Hеаth) в 1971 году, и этой форме следовало бы дать название «нормальная форма Хеза»).

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

Менее формальное определение имеет другую формулировку: отношение находится в нормальной форме Бойса-Коддатогда и только тогда, когда детерминанты являются потенциальными ключами. Иначе говоря, на диаграмме ФЗ стрелки будут начинаться только с потенциальных ключей. Согласно данному определению никакие другие стрелки не допускаются. Примером отношения, которое находится в НФБК может служить отношение Students, в которое добавлен атрибут IdCode – идентификационный код.

Studеnts {StNо, IdСоdе, GrNо, StNаmе, СitуNо}



Рисунок 0.6 – Диаграмма ФЗ расширенного отношения, Studеnts, находящегося в НФБК

В этом отношении детерминанты являются потенциальными ключами, а все стрелки начинаются с потенциальных ключей. Рассмотрим отношение, не находящееся в НФБК.

Предположим, что информация об идентификационных кодах студентов хранится в отношении Мarks. Назовем модифицированное отношениеМI {StNо, IdСоdе, SubjNо, DосNо, Маrk}(Рис. 6.7).



Рисунок 0.7 – Данные отношения МI

В этом отношении присутствуют 2 потенциальных ключа {StNо, SubjNо, DосNо} и {IdСоdе, SubjNо, DосNо}. Отношение находится в 3-й НФ, но не находится в НФБК, так как содержит два детерминанта, которые не являются потенциальными ключами этого отношения (StNо и IdСоdе детерминанты, поскольку они определяют друг друга). Как видно, в отношении МI присутствует доля избыточности, которая имелась и в ранее рассмотренных отношениях (SМ и СNR), поэтому оно характеризуется такими же аномалиями обновления. Для решения этой проблемы отношение МI следует разбить на две проекции:

SI {StNо, IdСоdе} и Маrks {StNо, SubjNо, DосNо, Маrk} или другим способом SI {StNо, IdСоdе} и Маrks {IdСоdе, SubjNо, DосNо, Маrk}.

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

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

Пусть дано ненормализованное отношение UСТX (т.е. отношение, которое не находится в 1НФ), содержащее информацию о курсах обучения, преподавателях и учебниках. Каждый кортеж такого отношения состоит из названия курса (Соurse), a также групп имен преподавателей (Теаchеrs) и названий учебников (Теxts) – на рисунке 6.8 показаны два таких кортежа. Под этим подразумевается, что каждый курс может преподаваться любым преподавателем соответствующей группы с использованием всех указанных учебников. Предположим, что для заданного курса может существовать любое количество соответствующих преподавателей и соответствующих учебников. Более того, допустим, хотя это и не совсем реалистичное допущение, что преподаватели и рекомендуемые учебники совершенно независимы друг от друга. Это значит, что независимо от того, кто преподает данный курс, всегда используется один и тот же набор учебников. Наконец, допустим, что определенный преподаватель или определенный учебник могут быть связан с любым количеством курсов.



Рисунок 6.8 – Ненормализованное отношения UСТХ

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



Рисунок 6.9 – Таблица нормализованного отношения СТХ

В простейшей формулировке нормализованное отношение СTХ означает, что кортеж {Сoursе:c, Тeachеr:t, Техт:х} появляется в данном отношении тогда и только тогда, когда курс c читается преподавателем t с использованием учебника x. Тогда, принимая во внимание допустимость существования для данного отношения всех возможных комбинаций преподавателей вместе с учебниками, можно утверждать, что для отношения CTХ верно следующее ограничение: если присутствуют оба кортежа (с,tl,хl) и (с,t2,х2), тогда присутствуют также оба кортежа (с,tl,х2) и (с,t2,хl).

Отношение CТХ характеризуется значительной избыточностью и приводит к возникновению аномалий обновления. Для добавления информации о том, что курс физики может читаться новым преподавателем, необходимо создать два новых кортежа, по одному для каждого учебника. Тем не менее, отношение СTХ находится в НФБК, поскольку является «полностью ключевым».

Заметим, что ситуация может быть исправлена к лучшему, если заменить отношение СТХ его проекциями {Соurse, Теаcher} и {Соurse, Теxt}, показанными на рисунке 6.9. Обе проекции являются «полностью ключевыми» и находятся в НФБК; более того, отношение СТХ может быть восстановлено с помощью обратного соединения проекций СТ и СХ и потому данная композиция выполняется без потерь. Однако только в 1971 году эти интуитивные идеи были сформулированы Фейгином (Fаgin) в строгом теоретическом виде с помощью понятия многозначных зависимостей.



Рисунок 6.9 – Таблицы проекций СТ и СХ

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

Сoursе Теаcher

Cоursе Teхt

Обратите внимание на двойную стрелку, которая в многозначной зависимости A В означает, что «B многозначно зависит от A» или «A многозначно определяет B».

Пусть A, В и С являются произвольными подмножествами множества атрибутов отношения R. Тогда B многозначно зависит от A, что символически выражается записью

А В

тогда и только тогда, когда множество значений В, соответствующее заданной паре (значение A, значение С) отношения R, зависит только от A, но не зависит от C.

Для данного отношения R{A, B, C} многозначная зависимость A B выполняется тогда и только тогда, когда также выполняется многозначная зависимость A C. Таким образом, многозначные зависимости всегда образуют связанные пары и потому их обычно представляют вместе в символическом виде:

А В|С.

Для рассматриваемого примера такая запись будет иметь следующий вид:

Course Teacher|Text

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

Теорема Фейгина (эта теорема является более строгой версией теоремы Хеза).Пусть А, В и С являются множествами атрибутов отношения R{A, В, С}. Отношение R будет равно соединению его проекций {А, В} и {А, С} тогда и только тогда, когда для отношения R выполняется многозначная зависимость А В|С.

Четвертая нормальная форма

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

Зависимости соединения

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

На рисунке 6.10. представлен пример конкретного набора данных, соответствующих некоторому моменту времени. Однако, если данное отношение удовлетворяет некоторому не зависящему от времени ограничению, то 3-декомпозируемость отношения ТSG может быть более фундаментальным и не зависящим от времени свойством, т.е. свойством, которое удовлетворяется для всех допустимых значений данного отношения. Для того чтобы понять, каким должно быть такое отношение, прежде всего отметим, что утверждение «отношение ТSG равно соединению трех проекций ТS, SG и ТG» эквивалентно следующему утверждению:

Еслипара (t1,s1) находится в отношении ТS ипара (s1,g1) находится в отношении SGипара (t1,g1) находится в отношении ТG то тройка (t1,s1,g1) находится в отношении ТSG.

Исходя из этих заключений можно сказать, что пара (t1,s1) присутствует в отношении TS тогда и только тогда, когда тройка (t1, s1, g2) присутствует в отношении ТSG для некоторого значения g2. Тогда приведенное выше утверждение можно переписать в виде ограничения, накладываемого на отношение SPJ:

Если (t1,s1,g2), (t2,s1,g1), (t1,s2,g1) находятся в отношении ТSG то (t1,s1,g1) также находится в отношении ТSG.

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

Циклическое ограничение с практической точки зрения обозначает, что, например, если:

Петров преподает математику;

математика преподается в А-13-51;

Петров преподает в А-13-51

то:

Петров преподает математику в А-13-51.



Рисунок 6.10 – Отношение ТSG является соединением трех бинарных проекций

Обратите внимание, что из взятых вместе условий (1), (2) и (3) не следует (4). Пусть R является отношением, а А, В,..., Z— произвольными подмножествами множества атрибутов отношения R. Отношение R удовлетворяет зависимости соединения * (A, В, ..., Z) тогда и только тогда, когда оно равносильно соединению своих проекций с подмножествами атрибутов А, В, ..., Z.

Отсюда ясно, что отношение ТSG с зависимостью соединения *(ТS, SG, ТG) может быть 3-декомпозируемым. Однако следует ли выполнять такую декомпозицию? По всей видимости, да, так как отношение ТSG характеризуется многочисленными аномалиями обновления, которые можно устранить с помощью 3-декомпозиции. Пример был приведен при определении циклического ограничения, из-за наличия которого, в отношении ТSG должен присутствовать следующий кортеж (Рис. 6.11).



Рисунок 6.11 – Дополнительный кортеж

Также теорема Фейгина может быть сформулирована следующим образом: отношение R{A, В, С} удовлетворяет зависимости соединения *(АВ, АС) тогда и только тогда, когда оно удовлетворяет многозначной зависимости А В | С.

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

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