Using a theory of semantically significant mappings for designing the relational databases.pdf Статья построена на примерах, взятых из уважаемых ис-точников, с указанием предлагаемых теорией реляционногопроектирования решений и нерешенных проблем. Вслед заэтим следует рассмотрение этих же примеров с точки зре-ния предлагаемой автором теории семантически значимыхотображений (в дальнейшем - теории отображений) [1]. Входе анализа примеров выявляются ошибки и неточности,допущенные авторами цитируемых работ, что говорит отрудности восприятия классической методологии дажепрофессионалами.Первую серию примеров возьмем у отечественногоклассика баз данных Кузнецова [2].Будем считать вслед за Кузнецовым, что «проблемапроектирования реляционной базы данных состоит в обос-нованном принятии решений о том, из каких отношенийдолжна состоять БД и какие атрибуты должны быть у этихотношений».ПРИВЕДЕНИЕ ОТНОШЕНИЙ КО ВТОРОЙИ ТРЕТЬЕЙ НОРМАЛЬНЫМ ФОРМАМПример и решение, предлагаемое Кузнецовым [2]:«Рассмотрим следующий пример схемы отноше-нияСОТРУДНИКИ-ОТДЕЛЫ-ПРОЕКТЫ(СОТР_НОМЕР, СОТР_ЗАРП, ОТД_НОМЕР,ПРО_НОМЕР, СОТР_ЗАДАН).Первичный ключ:СОТР_НОМЕР, ПРО_НОМЕР.Функциональные зависимости:СОТР_НОМЕР -> СОТР_ЗАРПСОТР_НОМЕР -> ОТД_НОМЕРОТД_НОМЕР -> СОТР_ЗАРПСОТР_НОМЕР, ПРО_НОМЕР -> СОТР_ЗАДАНМожно произвести следующую декомпозицию от-ношения СОТРУДНИКИ-ОТДЕЛЫ-ПРОЕКТЫ в дваотношения:СОТРУДНИКИ-ОТДЕЛЫ (СОТР_НОМЕР,СОТР_ЗАРП, ОТД_НОМЕР)Первичный ключ: СОТР_НОМЕРФункциональные зависимости:СОТР_НОМЕР -> СОТР_ЗАРПСОТР_НОМЕР -> ОТД_НОМЕРОТД_НОМЕР -> СОТР_ЗАРПСОТРУДНИКИ-ПРОЕКТЫ (СОТР_НОМЕР,ПРО_НОМЕР, СОТР_ЗАДАН)Первичный ключ: СОТР_НОМЕР, ПРО_НОМЕРФункциональная зависимость:СОТР_НОМЕР, ПРО_НОМЕР -> СОТР_ЗАДАНКаждое из этих двух отношений находится в 2NF.Рассмотрим отношение СОТРУДНИКИ-ОТДЕЛЫ,находящееся в 2NF. Заметим, что функциональная за-висимость СОТР_НОМЕР -> СОТР_ЗАРП являетсятранзитивной; она является следствием (в смысле ма-тематической логики) функциональных зависимостейСОТР_НОМЕР -> ОТД_НОМЕР и ОТД_НОМЕР ->-> СОТР_ЗАРП.Можно произвести декомпозицию отношенияСОТРУДНИКИ-ОТДЕЛЫ в два отношения:СОТРУДНИКИ (СОТР_НОМЕР, ОТД_НОМЕР)Первичный ключ: СОТР_НОМЕРФункциональная зависимость:СОТР_НОМЕР -> ОТД_НОМЕРОТДЕЛЫ (ОТД_НОМЕР, СОТР_ЗАРП)Первичный ключ: ОТД_НОМЕРФункциональная зависимость:ОТД_НОМЕР -> СОТР_ЗАРПКаждое из этих двух отношений находится в3NF».Данному случаю в теории отображений соответст-вует граф классов и отображений, приведенный нарис. 1.СОТР_НОМЕР СОТР_ЗАРПM M 11 N 1 MСОТР_ЗАДАН ПРО_НОМЕР ОТД_НОМЕРРис. 1. Граф классов и отображений для первого примераКаждой связи соответствует одно отношение,функциональные отображения определяют первичныеключи отношений (они являются множествами про-образов этих отображений). Обратите внимание, чтофункциональная зависимость СОТР_НОМЕР ->СОТР_ЗАРП представлена функциональным отобра-жением, являющимся композицией функциональныхотображений СОТР_НОМЕР -> ОТД_НОМЕР иОТД_НОМЕР -> СОТР_ЗАРП.В данном случае мы не стали переименовыватьклассы объектов, хотя по-хорошему для более точно-го отражения семантики граф должен быть таким, ка-ким он показан на рис. 2.СОТРУДНИК З/П_СОТР_ОТДЕЛАM M 11 N 1 MЗАДАНИЕ ПРОЕКТ ОТДЕЛРис. 2. Граф классов и отображений для первого примерас правильно поименованными классамиПРИВЕДЕНИЕ ОТНОШЕНИЙ К НОРМАЛЬНОЙФОРМЕ БОЙСА - КОДДАНа эту тему Кузнецовым предлагается следующийпример и решение [2]:«Рассмотрим следующий пример схемы отноше-ния:СОТРУДНИКИ-ПРОЕКТЫ (СОТР_НОМЕР,СОТР_ИМЯ, ПРО_НОМЕР, СОТР_ЗАДАН)Возможные ключи:СОТР_НОМЕР, ПРО_НОМЕР иСОТР_ИМЯ, ПРО_НОМЕРФункциональные зависимости:СОТР_НОМЕР -> СОТР_ИМЯСОТР_НОМЕР -> ПРО_НОМЕРСОТР_ИМЯ -> СОТР_НОМЕРСОТР_ИМЯ -> ПРО_НОМЕРСОТР_НОМЕР, ПРО_НОМЕР -> СОТР_ЗАДАНСОТР_ИМЯ, ПРО_НОМЕР -> СОТР_ЗАДАНВ этом примере мы предполагаем, что личностьсотрудника полностью определяется как его номером,так и именем (это не очень жизненное предположе-ние, но достаточное для примера).Независимо от того, какой из возможных ключейвыбран в качестве первичного ключа, эта схема нахо-дится в 3NF. Однако тот факт, что имеются функцио-нальные зависимости атрибутов отношения от атри-бута, являющегося частью первичного ключа, приво-дит к аномалиям. Например, для того, чтобы изменитьимя сотрудника с данным номером согласованнымобразом, нам потребуется модифицировать все кор-тежи, включающие его номер.Очевидно, что требование нормальной формыБойса - Кодда не выполненоидентифицирующего некоторую сущность, и набораиз нуля или более взаимно независимых атрибутов,некоторым образом описывающих эту сущность».А теперь проанализируем предложенный Кузне-цовым пример.Первый случай (опускаем упомянутые функцио-нальные зависимости).СОТРУДНИКИ-ПРОЕКТЫ (СОТР_НОМЕР,СОТР_ИМЯ, ПРО_НОМЕР, СОТР_ЗАДАН)Возможные ключи:СОТР_НОМЕР, ПРО_НОМЕР иСОТР_ИМЯ, ПРО_НОМЕРФункциональные зависимости:СОТР_НОМЕР -> СОТР_ИМЯСОТР_ИМЯ -> СОТР_НОМЕРСОТР_НОМЕР, ПРО_НОМЕР -> СОТР_ЗАДАНСОТР_ИМЯ, ПРО_НОМЕР -> СОТР_ЗАДАНПроверяем 3NF:- определение 3NF-1 неприменимо, поскольку унас два возможных ключа (кстати, если бы не былооговорки, то ответ был бы отрицательным, посколькуотношение не удовлетворяет условию 2NF);- по определению 3NF-2 отношение не находится в3NF, поскольку не выполнено второе условие (еслипервичный ключ - СОТР_НОМЕР, ПРО_НОМЕР, тонеключевой атрибут СОТР_ИМЯ зависит от частипервичного ключа СОТР_НОМЕР, аналогично и длядругого первичного ключа);- по определению 3NF-3 отношение находится в3NF, поскольку:- для ФЗ СОТР_НОМЕР -> СОТР_ИМЯ выполне-но третье условие;- для ФЗ СОТР_ИМЯ -> СОТР_НОМЕР выполне-но третье условие;- для ФЗ СОТР_НОМЕР, ПРО_НОМЕР ->-> СОТР_ЗАДАН выполнено второе условие;- для ФЗ СОТР_ИМЯ, ПРО_НОМЕР ->-> СОТР_ЗАДАН выполнено второе условие;- по определению 3NF-4 отношение не находится в3NF, поскольку кортеж отношения описывает сразудве сущности: участие сотрудника в проекте и самогосотрудника, характеристикой первой являетсяСОТР_ЗАДАН, а характеристикой второй -СОТР_ИМЯ.Оставим эту загадку на совести теоретиков клас-сического подхода. Посмотрим, к каким результатамприведет теория отображений.Данному случаю соответствует граф классов иотображений, показанный на рис. 3.СОТРУДНИК ИМЯ1 1M1 NЗАДАНИЕ ПРОЕКТРис. 3. Граф классов и отображений для второго примера(первый случай)Каждой связи соответствует одно отношение,функциональные отображения определяют возмож-ные ключи отношений. Атрибут СОТР_НОМЕР вы-бран в качестве первичного ключа отношения СО-ТРУДНИК, и именно он представляет во втором от-ношении объекты этого класса. Функциональная за-висимость СОТР_ИМЯ, ПРО_НОМЕР ->-> СОТР_ЗАДАН представлена функциональнымотображением, являющимся композицией функцио-нальных отображений ИМЯ -> СОТРУДНИК и СО-ТРУДНИК, ПРОЕКТ -> ЗАДАНИЕ.СОТРУДНИК (СОТР_НОМЕР, СОТР_ИМЯ)Возможные ключи:СОТР_НОМЕР и СОТР_ИМЯФункциональные зависимости:СОТР_НОМЕР -> СОТР_ИМЯСОТР_ИМЯ -> СОТР_НОМЕРСОТРУДНИКИ-ПРОЕКТЫ (СОТР_НОМЕР,ПРО_НОМЕР, СОТР_ЗАДАН)Возможный ключ:СОТР_НОМЕР, ПРО_НОМЕРФункциональная зависимость:СОТР_НОМЕР, ПРО_НОМЕР -> СОТР_ЗАДАНВторой случай (с учетом упомянутых функцио-нальных зависимостей).СОТРУДНИКИ-ПРОЕКТЫ (СОТР_НОМЕР,СОТР_ИМЯ, ПРО_НОМЕР, СОТР_ЗАДАН)Возможные ключи:СОТР_НОМЕР, ПРО_НОМЕР иСОТР_ИМЯ, ПРО_НОМЕРФункциональные зависимости:СОТР_НОМЕР -> СОТР_ИМЯСОТР_НОМЕР -> ПРО_НОМЕРСОТР_ИМЯ -> СОТР_НОМЕРСОТР_ИМЯ -> ПРО_НОМЕРСОТР_НОМЕР, ПРО_НОМЕР -> СОТР_ЗАДАНСОТР_ИМЯ, ПРО_НОМЕР -> СОТР_ЗАДАНДля начала построим минимальное покрытиефункциональных зависимостей - эквивалентный ис-ходному набор ФЗ, в котором представлены тольконеизбыточные ФЗ. Именно такие ФЗ позволяют выде-лить детерминанты отношения.Проанализируем функциональные зависимости:- СОТР_НОМЕР, ПРО_НОМЕР -> СОТР_ЗАДАНзаменяем на СОТР_НОМЕР -> СОТР_ЗАДАН.Покажем, что набор ФЗ СОТР_НОМЕР ->-> ПРО_НОМЕР и СОТР_НОМЕР, ПРО_НОМЕР ->-> СОТР_ЗАДАН эквивалентен набору функциональ-ных зависимостей СОТР_НОМЕР -> ПРО_НОМЕР иСОТР_НОМЕР -> СОТР_ЗАДАН, что даст нам правона такую замену. Правила вывода возьмем в [3].Второй набор является следствием первого:По правилу дополнения (если A -> B, то AC -> BC)из первой ФЗ имеем СОТР_НОМЕР, СОТР_НОМЕР ->-> ПРО_НОМЕР, СОТР_НОМЕР.По правилу транзитивности (если A -> B и B -> C,то A -> C) из только что полученного и второй ФЗимеем СОТР_НОМЕР, СОТР_НОМЕР -> СОТР_ ЗА-ДАН или СОТР_НОМЕР -> СОТР_ЗАДАН.Первый набор является следствием второго:По правилу дополнения (если A -> B, то AC -> BC)из второй ФЗ имеем СОТР_НОМЕР, ПРО_НОМЕР ->ПРО_НОМЕР, СОТР_ЗАДАН.По правилу рефлексивности (если множество ат-рибутов B является подмножеством множества атри-бутов A, то A -> B) имеем ПРО_НОМЕР,СОТР_ЗАДАН -> СОТР_ЗАДАН.По правилу транзитивности (если A -> B и B -> C,то A -> C) из только что полученных ФЗ имеемСОТР_НОМЕР, ПРО_НОМЕР -> СОТР_ЗАДАН.- СОТР_ИМЯ, ПРО_НОМЕР -> СОТР_ЗАДАНаналогично заменяем на СОТР_ИМЯ ->-> СОТР_ЗАДАН.- СОТР_ИМЯ -> ПРО_НОМЕР удаляем (избыточ-на, поскольку является следствием СОТР_ИМЯ ->-> СОТР_НОМЕР и СОТР_НОМЕР -> ПРО_НОМЕР).- СОТР_ИМЯ -> СОТР_ЗАДАН удаляем (избы-точна, поскольку является следствием СОТР_ИМЯ ->-> СОТР_НОМЕР и СОТР_НОМЕР -> СОТР_ЗАДАН).Таким образом, имеем следующее минимальноепокрытие функциональных зависимостей:СОТР_НОМЕР -> СОТР_ИМЯСОТР_ИМЯ -> СОТР_НОМЕРСОТР_НОМЕР -> ПРО_НОМЕРСОТР_НОМЕР -> СОТР_ЗАДАНВозможные ключи:СОТР_НОМЕР и СОТР_ИМЯПроверяем 3NF:- определение 3NF-1 неприменимо, поскольку унас два возможных ключа;- по определению 3NF-2 отношение находится в3NF;- по определению 3NF-3 отношение находится в3NF, поскольку для всех ФЗ выполнено второе усло-вие;- по определению 3NF-4 отношение находится в3NF, поскольку кортеж отношения описывает сущ-ность сотрудника со всеми ее характеристиками -именем, номером проекта, в котором он участвует, изаданием, которое он при этом выполняет.Более того, отношение СОТРУДНИКИ-ПРОЕКТЫ(СОТР_НОМЕР, СОТР_ИМЯ, ПРО_НОМЕР,СОТР_ЗАДАН) находится в нормальной форме Бой-са - Кодда (каждый детерминант является возможнымключом) и декомпозиции не подлежит.Данному случаю соответствует граф классов иотображений, показанный на рис. 4.СОТРУДНИК ИМЯ1 1M M1 1ЗАДАНИЕ ПРОЕКТРис. 4. Граф классов и отображений для второго примера(второй случай)Здесь достаточно одного отношения СОТРУД-НИКИ-ПРОЕКТЫ (СОТР_НОМЕР, СОТР_ИМЯ,ПРО_НОМЕР, СОТР_ЗАДАН) с возможными ключа-ми СОТР_НОМЕР и СОТР_ИМЯ и первичным клю-чом СОТР_НОМЕР.ПРИВЕДЕНИЕ ОТНОШЕНИЙ К ЧЕТВЕРТОЙНОРМАЛЬНОЙ ФОРМЕДля этого этапа нормализации Кузнецов предлага-ет следующий пример [2]:«Рассмотрим пример следующей схемы отноше-ния ПРОЕКТЫ (ПРО_НОМЕР, ПРО_СОТР,ПРО_ЗАДАН).Отношение ПРОЕКТЫ содержит номера проектов,для каждого проекта - список сотрудников, которыемогут выполнять проект, и список заданий, преду-сматриваемых проектом. Сотрудники могут участво-вать в нескольких проектах, и разные проекты могутвключать одинаковые задания.Каждый кортеж отношения связывает некоторыйпроект с сотрудником, участвующим в этом проекте,и заданием, который сотрудник выполняет в рамкахданного проекта (мы предполагаем, что любой со-трудник, участвующий в проекте, выполняет все за-дания, предусмотренные этим проектом). По причинесформулированных выше условий единственнымвозможным ключом отношения является составнойатрибут ПРО_НОМЕР, ПРО_СОТР, ПРО_ЗАДАН, инет никаких других детерминантов. Следовательно,отношение ПРОЕКТЫ находится в BCNF. Но приэтом оно обладает недостатками: если, например, не-который сотрудник присоединяется к данному проек-ту, необходимо вставить в отношение ПРОЕКТЫстолько кортежей, сколько заданий в нем предусмот-рено.В отношении ПРОЕКТЫ существуют следующиедве многозначные зависимости:ПРО_НОМЕР ->> ПРО_СОТРПРО_НОМЕР ->> ПРО_ЗАДАН.В нашем примере можно произвести декомпози-цию отношения ПРОЕКТЫ в два отношения:ПРОЕКТЫ-СОТРУДНИКИ (ПРО_НОМЕР, ПРО_СОТР)ПРОЕКТЫ-ЗАДАНИЯ (ПРО_НОМЕР, ПРО_ЗАДАН).Оба эти отношения находятся в 4NF и свободны ототмеченных аномалий».Данному случаю соответствует граф классов иотображений, показанный на рис. 5:СОТРУДНИКM M MN N L NЗАДАНИЕ ПРОЕКТM NРис. 5. Граф классов и отображений для третьего примераВ данном случае вообще ни к чему рассматриватьтернарную связь, поскольку по представленному опи-санию существенными являются две бинарные связии соответствующие отображения (на рисунке они по-казаны сплошными линиями). Связь между заданиямии сотрудниками происходит исключительно черезпроекты и представляет собой композицию этих би-нарных связей.Каждой бинарной связи соответствует одно отно-шение, отсутствие функциональных отображений го-ворит о том, что первичные ключи каждого отноше-ния представляют все атрибуты этого отношения.Как мы отметили, в таких случаях вообще не стоитопределять тернарную связь, но, тем не менее, такиеситуации возможны. Встает вопрос, как распознаватьтакие случаи и заменять тернарную связь парой би-нарных.Прежде всего, отметим, что подобный анализследует применять лишь в том случае, когда все оп-ределяющие роли отображения нефункциональны. Впротивном случае надо просто следовать этим ото-бражениям, как мы это делали в предыдущих приме-рах, и не искать многозначных зависимостей. К со-жалению, подобные ошибки допускают и уважаемыеавторы [4]:«Рассмотрим, например, отношение ЛИГА (КО-МАНДА, ТРЕНЕР, ИГРОК), где существует зависи-мость между командой и тренерами, которая, однако,не является функциональной, поскольку нельзя ска-зать, что команда однозначно определяет тренера. Тоже самое относится и к зависимости между командойи игроками. Зависимости подобного рода называютсямногозначными зависимостями (МЗ). Эти МЗ озна-чают, что игроки и тренеры находятся в зависимостиот команды, но не друг от друга».В этом случае граф классов и отображений выгля-дит, как показано на рис. 6.КОМАНДА1 1M MТРЕНЕР ИГРОКРис. 6. Граф классов и отображений для примерас командами, тренерами и игрокамиПричем функциональные бинарные отображениянастолько очевидны, что никому и не придет в головупопытка использования в данном случае тернарнойсвязи.Но вернемся к многозначной зависимости.Теорема 1. Пусть имеется три множества X, Y, Z.Если выполнены следующие условия:- проекция отображения X -> Y  Z на роль Y экви-валентна отображению X -> Y,- проекция отображения X -> Y  Z на роль Z экви-валентна отображению X -> Z,- композиция отображений Y -> X и X -> Z экви-валентна отображению Y -> Z или композиция ото-бражений Z -> X и X -> Y эквивалентна отображениюZ -> Y, то имеет место многозначная зависимостьX ->> Y | Z. Доказательство теоремы приведено вПриложении 1.Из текстового описания предметной области ясно,что кандидатом на связующее звено (множество X)является класс ПРОЕКТ. В таком случае необходимоубедиться в истинности следующих фактов:- проекция отображения ПРОЕКТ -> СОТРУД-НИК  ЗАДАНИЕ на роль СОТРУДНИК эквивалент-на отображению ПРОЕКТ -> СОТРУДНИК;- проекция отображения ПРОЕКТ -> СОТРУД-НИК  ЗАДАНИЕ на роль ЗАДАНИЕ эквивалентнаотображению ПРОЕКТ -> ЗАДАНИЕ;- композиция отображений СОТРУДНИК -> ПРО-ЕКТ и ПРОЕКТ -> ЗАДАНИЕ эквивалентна отобра-жению СОТРУДНИК -> ЗАДАНИЕ или композицияотображений ЗАДАНИЕ -> ПРОЕКТ и ПРОЕКТ ->-> СОТРУДНИК эквивалентна отображению ЗАДА-НИЕ -> СОТРУДНИК.Если все эти факты истинны, вы имеете много-значную зависимость ПРОЕКТ ->> ЗАДАНИЕ | СО-ТРУДНИК и в этом случае надо заменять тернарнуюсвязь парой бинарных.Для того, чтобы опровергнуть первый факт, надоутвердительно ответить на вопрос «Возможна лисвязь проекта с сотрудником вне выполнения зада-ния?» Для второго факта вопрос звучит так: «Воз-можно ли определение задания по проекту без егосвязи хотя бы с одним сотрудником?» Для третьегофакта - «Существует ли сотрудник, работающий попроекту, который выполняет не все задания этогопроекта?» или «Существует ли задание проекта, кото-рое выполняется не всеми сотрудниками этого проек-та?» Ответить на все эти вопросы, по-видимому, несоставит труда. Последние два факта и, соответствен-но, вопроса эквивалентны.ПРИВЕДЕНИЕ ОТНОШЕНИЙК ПЯТОЙ НОРМАЛЬНОЙ ФОРМЕВоспользуемся хрестоматийным примером из [3].«В качестве примера рассмотрим переменную-отношение ПОСТАВЩИК-ПРОЕКТ-ДЕТАЛЬ:SPJ(S#, P#, J#), где атрибуты представляют номер по-ставщика, номер проекта и номер детали соответст-венно. Эта переменная-отношение состоит только изключевых атрибутов, не содержит нетривиальныхфункциональных и многозначных зависимостей и по-тому находится в 4NF.Рассмотрим также три бинарные проекции SPJ:SP, PJ и JS. Утверждение «переменная-отношениеSPJ равна соединению трех своих проекций SP, PJ иJS» в точности эквивалентно следующему утвержде-нию: ЕСЛИ (s1, p1)  SP И (p1, j1)  PJ И (j1, s1)  JS,ТО (s1, p1, j1)  SPJ.Что означает зависимость соединения с практиче-ской точки зрения? Под таким ограничением понима-ется истинность следующего высказывания:Если верны утверждения «Смит поставляет гаеч-ные ключи», «Гаечные ключи используются в Ман-хэттенском проекте» и «Смит является поставщикомдля Манхэттенского проекта», то верно и утвержде-ние «Смит поставляет гаечные ключи для Манхэттен-ского проекта».В связи с наличием зависимости соединения пере-менная-отношение SPJ характеризуется многочис-ленными аномалиями обновления, которые можноустранить декомпозицией ее на SP, PJ и JS.Переменная-отношение R находится в пятой нор-мальной форме, которую иногда иначе называют про-екционно-соединительной, тогда и только тогда, ко-гда каждая нетривиальная (когда в рассматриваемомнаборе проекций нет проекции, совпадающей с R) за-висимость соединения в переменной-отношении Rподразумевается ее потенциальными ключами.Теперь следует объяснить, что означает понятие«зависимость соединения, подразумеваемая потенци-альными ключами». Для начала в качестве простогопримера рассмотрим переменную-отношение постав-щиков S (S#, SNAME, STATUS, CITY) с потенциаль-ными ключами S# и SNAME. Такая переменная-отношение удовлетворяет нескольким зависимостямсоединения, в частности:* {{S#, SNAME, STATUS}, {S#, CITY}} и* {{S#, SNAME}, {S#, STATUS}, {SNAME,CITY}}.Зависимость соединения *{A, B, …, Z} подразуме-вается потенциальными ключами тогда и только то-гда, когда каждое подмножество атрибутов A, B, …, Zфактически является суперключом для данной пере-менной-отношения.В данном случае во все подмножества атрибутовобеих зависимостей входят потенциальные ключи, азначит S находится в 5NF, и ее можно, но не следуетподвергать декомпозиции.В отличие от функциональных и многозначных за-висимостей (для которых обычно существует вполнеочевидное обоснование в реальном мире) обнаружитьвсе зависимости соединения совсем не просто. Суть втом, что смысловое значение зависимостей соедине-ния, которые не являются одновременно многознач-ными и функциональными, далеко не всегда очевид-но. Следовательно, процедура определения того, чтонекоторая переменная-отношение все еще находитсяв 4NF, а не в 5NF, и, таким образом, существует воз-можность ее дальнейшей декомпозиции, все еще ос-тается не вполне ясной».На такой минорной ноте апологет классическогоподхода к проектированию реляционных схем БД за-вершает обзор нормальных форм. Давайте теперь по-смотрим на зависимость соединения и 5NF с позицийтеории отображений.Первому примеру из [3] соответствует следующийграф классов и отображений (рис. 7).ПОСТАВЩИК (S)M M MN N L NДЕТАЛЬ (J) ПРОЕКТ (P)M NРис. 7. Граф классов и отображений для примерас поставщиками, деталями и проектамиТеорема 2. Пусть имеется три множества X, Y, Z.Если выполнены следующие условия:- проекция отображения X -> Y  Z на роль Y экви-валентна отображению X -> Y,- проекция отображения Y -> X  Z на роль Z экви-валентна отображению Y -> Z,- проекция отображения Z -> X  Y на роль X экви-валентна отображению Z -> X,то имеет место зависимость соединения * (XY, YZ,ZX). Доказательство теоремы приведено в Приложе-нии 2.Для того, чтобы убедиться в необходимости заме-ны тернарной связи тремя бинарными, необходимоопределить истинность следующих фактов:- проекция отображения ПРОЕКТ -> ПОСТАВ-ЩИК  ДЕТАЛЬ на роль ПОСТАВЩИК эквивалент-на отображению ПРОЕКТ -> ПОСТАВЩИК (или, чтоэквивалентно, - проекция отображения ПОСТАВ-ЩИК ->ДЕТАЛЬ  ПРОЕКТ на роль ПРОЕКТ экви-валентна отображению ПОСТАВЩИК -> ПРОЕКТ);- проекция отображения ПОСТАВЩИК -> ДЕ-ТАЛЬ  ПРОЕКТ на роль ДЕТАЛЬ эквивалентна ото-бражению ПОСТАВЩИК -> ДЕТАЛЬ (или, что экви-валентно, - проекция отображения ДЕТАЛЬ -> ПОС-ТАВЩИК  ПРОЕКТ на роль ПОСТАВЩИК эквива-лентна отображению ДЕТАЛЬ -> ПОСТАВЩИК);- проекция отображения ДЕТАЛЬ -> ПОСТАВ-ЩИК  ПРОЕКТ на роль ПРОЕКТ эквивалентна ото-бражению ДЕТАЛЬ -> ПРОЕКТ (или, что эквива-лентно, - проекция отображения ПРОЕКТ -> ПОС-ТАВЩИК  ДЕТАЛЬ на роль ДЕТАЛЬ эквивалентнаотображению ПРОЕКТ -> ДЕТАЛЬ);- композиция отображений ПОСТАВЩИК ->-> ПРОЕКТ и ПРОЕКТ -> ДЕТАЛЬ не эквивалентнаотображению ПОСТАВЩИК -> ДЕТАЛЬ (или, чтоэквивалентно, - композиция отображений ДЕТАЛЬ ->-> ПРОЕКТ и ПРОЕКТ -> ПОСТАВЩИК не эквива-лентна отображению ДЕТАЛЬ -> ПОСТАВЩИК);- композиция отображений ДЕТАЛЬ -> ПОСТАВ-ЩИК и ПОСТАВЩИК -> ПРОЕКТ не эквивалентнаотображению ДЕТАЛЬ -> ПРОЕКТ (или, что эквива-лентно, - композиция отображений ПРОЕКТ ->-> ПОСТАВЩИК и ПОСТАВЩИК -> ДЕТАЛЬ не эк-вивалентна отображению ПРОЕКТ -> ДЕТАЛЬ);- композиция отображений ПРОЕКТ -> ДЕТАЛЬ иДЕТАЛЬ -> ПОСТАВЩИК не эквивалентна отобра-жению ПРОЕКТ -> ПОСТАВЩИК (или, что эквива-лентно, - композиция отображений ПОСТАВЩИК ->-> ДЕТАЛЬ и ДЕТАЛЬ -> ПРОЕКТ не эквивалентнаотображению ПОСТАВЩИК -> ПРОЕКТ).Если все эти факты истинны, вы имеете зависи-мость соединения * (SP, PJ и JS) и в этом случае надозаменять тернарную связь тремя бинарными. Вообще,истинность первых трех фактов свидетельствует о на-личии либо просто зависимости соединения, либо ееболее строгого частного случая - многозначной зави-симости. Если какой-то из оставшихся фактов ложен,имеем соответствующую многозначную зависимость,если все они истинны - только зависимость соедине-ния.Для того, чтобы опровергнуть первый факт, надоутвердительно ответить на вопрос «Возможна лисвязь проекта с поставщиком без поставки им хотя быодной детали для этого проекта?» Для второго фактавопрос звучит так: «Возможна ли поставка детали по-ставщиком не по проекту?» Для третьего факта -«Возможно ли использование детали по проекту, еслиона не поставлялась никаким поставщиком?»Второму примеру из [3] (с отношением поставщи-ков S) соответствует граф классов и отображений, по-казанный на рис. 8.S# SNAME1 {SNAME} 1 {S#}1 {S#}{SNAME} 1 {S#}{SNAME}STATUS CITYРис. 8. Граф классов и отображенийдля примера с поставщикамиЗдесь наблюдается функциональность всех ото-бражений, определяющих роли, причем она связана сналичием двух возможных ключей S# и SNAME. Де-композиция не требуется.К сожалению, ограниченный объем статьи позво-лил рассмотреть лишь часть примеров использованиятеории семантически значимых отображений для про-ектирования реляционных баз данных. Но и этого, по-видимому, достаточно, чтобы сделать вывод о воз-можности ее использования для этих целей.ПРИЛОЖЕНИЕ 1.ДОКАЗАТЕЛЬСТВО ТЕОРЕМЫ 1Для доказательства воспользуемся рис. 9.X11ϕ− 11ƒ− ϕ3ƒ1ƒ2 ƒ3ϕ1 12 −ƒ 13ƒ− 13ϕ−Y Z12 −ϕ ϕ2Рис. 9. Граф классов и отображенийНа нем представлены три бинарных и одна тер-нарная связь, определяющие следующие отображе-ния:ϕ1 : X -> Y, 11ϕ− : Y -> X, ϕ2 : Y -> Z,12 −ϕ : Z -> Y, ϕ3 : Z -> X, 13ϕ− : X -> Z,ƒ1 : X -> Y  Z, 11ƒ− : Y  Z -> X,ƒ2 : Y -> X  Z, 12 −ƒ : X  Z -> Y,ƒ3 : Z -> X  Y, 13ƒ− : X  Y -> Z.Для формального представления МЗ воспользуем-ся более строгим ее определением, данным Мейе-ром [5]:«Пусть R - реляционная схема, X и Y - непересе-кающиеся подмножества R, и пусть Z = R - (XY). От-ношение r(R) удовлетворяет многозначной зависимо-сти (MV-зависимости) X ->> Y, если для любых двухкортежей t1 и t2 из r, для которых t1 (X) = t2 (X), в rсуществует кортеж t3 , для которого выполнены соот-ношения t3 (X) = t1 (X), t3 (Y) = t1 (Y) и t3 (Z) = t2 (Z).Из симметрии определения относительно t1 и t2 сле-дует, что в r существует также t4 , для которогоt4 (X) = t1 (X), t4 (Y) = t2 (Y) и t4 (Z) = t1 (Z)».В реляционном исчислении с переменными-кортежами условие, при котором наблюдается МЗX ->> Y, примет вид:t1t2(R(t1)R(t2)t1[X]=t2[X] t3(R(t3)t3[X]=t1[X]t3[Y]=t1[Y]t3[Z]=t2[Z])t4(R(t4)t4[X]=t1[X]t4[Y]=t2[Y]t4[Z]=t1[Z])) .После эквивалентного перевода этого выражения вреляционное исчисление с переменными на доменахполучим:x1y1z1x2y2z2(R(x1y1z1)R(x2y2z2)x1= x2  x3y3z3(R(x3y3z3)x3=x1y3=y1z3=z2) x4y4z4(R(x4y4z4)x4=x1y4=y2z4=z1)) .И, наконец, в исчислении, введенном в теорииотображений [1], это выражение примет следующийвид:( x1y1z1x2y2z2 =ƒ1(x1)=ƒ1(x2)x1=x2(  x3y3z3 = ƒ1(x3)x3=x1y3=y1z3=z2)( x4y4z4 =ƒ1(x4)x4=x1y4=y2z4=z1)) . (1)Теперь запишем формально приведенные нами фак-ты, достаточные, по нашему мнению, для наличия МЗ:1) проекция отображения ƒ1 : X -> Y  Z на роль Yэквивалентна отображению ϕ1 : X -> Y. По определе-нию проекции [1] имеем( ) xy y= ƒ1[Y](x)↔z< y,z>= ƒ1(x) . (2)По определению эквивалентности отображений [1]( ) xy y= ƒ1[Y](x)↔ y= ϕ1(x). (3)Делая в (2) эквивалентную замену, согласно (3),имеем( ) xy y= ϕ1(x)↔z< y,z>= ƒ1(x) . (4)2) проекция отображения ƒ1 : X -> Y  Z на роль Zэквивалентна отображению 13ϕ− : X -> Z. По определе-нию проекции имеем( ) xz z= ƒ1[Z](x)↔y< y,z>= ƒ1(x) . (5)По определению эквивалентности отображений( 1 )xz z= ƒ1[Z](x)↔ z= ϕ3− (x) . (6)Делая в (5) эквивалентную замену, согласно (6),имеем( 1 )xz z= ϕ3− (x)↔y< y,z>= ƒ1(x) . (7)3) композиция отображений 11ϕ− : Y -> X и 13ϕ− :X -> Z эквивалентна отображению ϕ2 : Y -> Z. По оп-ределению композиции [1]( 1( 1 )yz z= ϕ3− ϕ1− (y) ↔( 1 1 ))↔ xx= ϕ1− (y)z= ϕ3− (x) . (8)По определению эквивалентности отображений( 1( 1 ) )yz z= ϕ3− ϕ1− (y) ↔z= ϕ2(y) . (9)Делая в (8) эквивалентную замену в соответствиис (9), получаем( ( 1 1 ))yz z= ϕ2(y)↔ x x= ϕ1− (y)z= ϕ3− (x) . (10)4) композиция отображений ϕ3 : Z -> X и ϕ1 : X -> Yэквивалентна отображению 12 −ϕ : Z -> Y. По определе-нию композиции( ( ) yz y= ϕ1 ϕ3(z) ↔( )) ↔ xx= ϕ3(z)y= ϕ1(x) . (11)По определению эквивалентности отображений( ( ) 1 )yz y= ϕ1 ϕ3(z) ↔ y= ϕ−2 (z) . (12)Делая в (11) эквивалентную замену в соответствиис (12), получаем( 1 ( ))yz y= ϕ−2(z)↔ x x= ϕ3(z)y= ϕ1(x) . (13)Итак, если истинны приведенные факты, формулы(4), (7), (10) и (13) общезначимы.Пусть истинна посылка 1:( x1y1z1x2y2z2 =ƒ1(x1))  = ƒ1(x2)x1=x2 .В силу истинности ( ) x1y1z1 =ƒ1(x1)истинна и ( ) x1y1z1 =ƒ1(x1), а в соответст-вии с (4) - и ( ) x1y1 y1= ϕ1(x1) . По определению ин-версии [1] истинна также формула ( 1 )x1y1 x1= ϕ1− (y1) .В силу истинности ( ) x1y1z1 =ƒ1(x1)истинна и ( ) x1z1y1 =ƒ1(x1), а в соответст-вии с (7) - и ( 1 )x1z1 z1= ϕ3− (x1) .Рассуждая аналогично для второго конъюнкта по-сылки, как следствие имеем истинные формулы:( 1 )x2y2 x2=ϕ1− (y2) и ( 1 )x2z2 z2=ϕ3− (x2) .Таким образом, следствием посылки является сле-дующая формула:( 1 1x1y1z1x2y2z2 x1= ϕ1− (y1)z2= ϕ3− (x2)1 1 )x2=ϕ1− (y2)z1=ϕ3− (x1)x1=x2 ,а значит и( 1x1y1z1y2z2 x1= ϕ1− (y1)1 1 1 )z2=ϕ3− (x1)x1=ϕ1− (y2)z1=ϕ3− (x1) . (14)В силу истинности( 1 1 )x1y1z2 x1=ϕ1− (y1)z2=ϕ3− (x1)истинна и( 1 1 )y1z2x1 x1=ϕ1− (y1)z2=ϕ3− (x1) ,а в соответствии с (10) - и ( ) y1z2 z2=ϕ2(y1) .Рассуждая аналогично для второй пары конъюнк-тов, имеем истинную формулу: ( ) y2z1 z1=ϕ2(y2) .Таким образом, следствием посылки является сле-дующая формула:( x1y1z1y2z2 z2= ϕ2(y1)z1= ϕ2(y2)1 1x1= ϕ1− (y1)z2= ϕ3− (x1)1 1 )x1=ϕ1− (y2)z1=ϕ3− (x1) . (15)В соответствии с (10) ( ) y1z2 z2=ϕ2(y1) эквива-лентна ( ( 1 1 ))y1z2 x3 x3=ϕ1− (y1)z2=ϕ3− (x3) , а по-скольку те же самые выражения истинны и для x1 ,ничто не мешает тому, что x3= x1. Аналогично рас-суждаем для второго конъюнкта (15) и приходим кследующему следствию посылки:( 1 1x1y1z1y2z2x3x4 x3=ϕ1− (y1)z2=ϕ3− (x3)1 1 )x4=ϕ1− (y2)z1=ϕ3− (x4)x3=x1x4=x1 (16)Имея в виду эквивалентность предикатов для ин-версных отображений ϕ1 и 11ϕ− , используя (4) и (7),преобразуем (16) в:x1y1z1y2z2x3y3z3x4y4z4(==ƒ1(x3)=ƒ1(x3)=ƒ1(x4))  = ƒ1(x4)x3=x1x4=x1 . (17)Поскольку первые четыре конъюнкта должныбыть истинны для y1z1y2z2 , ничто не мешаетим быть истинными и для конкретных y3z3y4z4 , азначит следствием (17) является следующая формула:x1y1z1y2z2x3y3z3x4y4z4(==ƒ1(x3)y3=y1=ƒ1(x3)z3=z2)  = ƒ1(x4)z4 =z1x3 =x1x4 =x1 =ƒ1(x4)y4=y2=.Если в последней формуле исключить совпадаю-щие конъюнкты, то с точностью до перестановки ос-тавшихся конъюнктов она совпадает с заключением(1), что подтверждает, что из истинности ранее пред-ложенных фактов следует наличие многозначной за-висимости.Обратите внимание, что в доказательстве исполь-зовалась только формула (10), а эквивалентная ейформула (13) не пригодилась.ПРИЛОЖЕНИЕ 2.ДОКАЗАТЕЛЬСТВО ТЕОРЕМЫ 2Для формального представления зависимости со-единения воспользуемся приведенным определениемДейта. В реляционном исчислении с переменными-кортежами условие, при котором наблюдается зави-симость соединения * (XY, YZ, ZX), примет видt1t2t3(XY(t1)YZ(t2)ZX(t3)t1[Y]=t2[Y]t2[Z]=t3[Z]t3[X]=t1[X] t4(XYZ(t4)t4[X]=t1[X]t4[Y]=t2[Y]t4[Z]=t3[Z])) .После эквивалентного перевода выражения в ре-ляционное исчисление с переменными на доменахполучимx1y1z1x2y2z2x3y3z3(XY(x1y1)YZ(y2z2)ZX(z3x3) y1 = y2 z2=z3x3=x1 x4y4z4(XYZ(x4y4z4)x4=x1y4=y2z4=z3)) .И, наконец, в исчислении, введенном в теорииотображений [1], это выражение примет следующийвид:( x1y1z1x2y2z2x3y3z3 y1= ϕ1(x1)z2=ϕ2(y2)x3=ϕ3(z3)y1=y2z2=z3x3=x1(  x4y4z4 = ƒ1(x4) = ƒ2(y4) = ƒ3(z4)x4=x1y4=y2z4=z3)) . (18)Теперь запишем формально приведенные намифакты, достаточные, по нашему мнению, для наличиязависимости соединения (воспользуемся формулами(4), (7) предыдущего доказательства):1) проекция отображения ƒ1 : X -> Y  Z на роль Yэквивалентна отображению ϕ1 : X -> Y( ) xy y= ϕ1(x)↔z< y,z>= ƒ1(x) ; (19)2) проекция отображения ƒ2 : Y -> X  Z на роль Zэквивалентна отображению ϕ2 : Y -> Z( ) yz z= ϕ2(y)↔ x= ƒ2(y) ; (20)3) проекция отображения ƒ3 : Z -> X  Y на роль Xэквивалентна отображению ϕ3 : Z -> X( ) zx x= ϕ3(z)↔y= ƒ3(z) . (21)Итак, если истинны приведенные факты, формулы(19), (20) и (21) общезначимы.Пусть истинна посылка (18):( x1y1z1x2y2z2x3y3z3 y1= ϕ1(x1)z2= ϕ2(y2)x3= ϕ3(z3)y1=y2z2=z3x3=x1) .Делая в ней эквивалентные замены в соответствиис (19), (20) и (21), получаемx1y1z1x2y2z2x3y3z3x4y4z4(==ƒ1(x1)=ƒ2(y2)=ƒ3(z3)y1=y2z2=z3x3=x1) . (22)Поскольку первые три конъюнкта должны бытьистинны для x1y1z1x2y2z2x3y3z3, ничто немешает им быть истинными и для конкретныхx4y4z4 , а значит следствием (22) является следующаяформула:x1y1z1x2y2z2x3y3z3x4y4z4(==ƒ1(x4)=ƒ2(y4)=ƒ3(z4)y4=y1x4=x1z4=z2y4=y2x4=x3z4=z3y1=y2z2=z3x3=x1) . (23)Очевидно, что из (23) следует истинность заклю-чения (18), и это подтверждает, что из истинности ра-нее предложенных фактов следует наличие зависимо-сти соединения.

Скачать электронную версию публикации