    Глава 11 

    Нормальные формы более высокого порядка 

    11.1. Введение 

    В предыдущей главе были описаны основные идеи нормализации от первой 
нормальной формы до нормальной формы Бойса-Кодда (НФБК) включительно (т.е. до 
той формы, при описании которой может использоваться понятие функциональной 
зависимости). В этой главе обсуждение данного вопроса завершается описанием 
четвертой и пятой нормальных форм (4НФ и 5НФ). Как будет показано ниже, для 
определения 4НФ необходимо ввести понятие многозначной зависимости — МЗ, 
которое является обобщением понятия функциональной зависимости. Аналогично 
этому для определения понятия 5НФ потребуется ввести новый тип зависимости, 
которая называется зависимостью соединения — ЗС. Она является обобщением 
понятия многозначной зависимости точно так же, как многозначная зависимость 
является обобщением понятия функциональной зависимости. Сначала будут описаны 
понятия многозначной зависимости и 4НФ, а затем — понятия зависимости 
соединения и 5НФ с разъяснениями, почему 5НФ является в некотором смысле 
окончательной нормальной формо й. Сразу же следует отметить, что описание этих 
зависимостей будет менее формальным и полным, чем описание функциональных 
зависимостей, данное в главе 9. За более подробной информацией о них можно 
обратиться к работам, представленным в списке рекомендуемой литературы в конце главы. 
    После описания основных понятий дается обзор процедуры нормализации в 
целом с некоторыми дополнительными комментариями. Затем кратко обрисованы 
некоторые возможные направления будущих исследований в области нормализации, а 
в конце представлено резюме. 

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

    Пусть дано ненормализованное отношение UCTX (т.е. отношение, которое не 
находится в 1НФ), содержащее информацию о курсах обучения, преподавателях и 
учебниках (рис. 11.1). Каждый кортеж такого отношения состоит из названия 
курса (COURSE), a также групп имен преподавателей (TEACHERS) и названий 
учебников (TEXTS) (на рис. 11.1 показаны два таких кортежа). Под этим 
подразумевается, что каждый курс может преподаваться любым преподавателем 
соответствующей группы с использованием всех указанных учебников. Предположим, 
что для заданного курса может существовать любое количество соответствующих 
преподавателей и соответствующих учебников. Более того, допустим, хотя это и 
не совсем реалистичное допущение, что преподаватели и рекомендуемые учебники 
совершенно независимы друг от друга. Это значит, что независимо от того, кто 
преподает данный курс, всегда используется один и тот же набор учебников. 
Наконец, допустим, что определенный преподаватель или определенный учебник 
могут быть связаны с любым количеством курсов. 
    Теперь попробуем преобразовать это отношение в эквивалентное 
нормализованное отношение. Прежде всего, следует заметить, что для 
рассматриваемых данных функциональные зависимости не заданы (за исключением 
тривиальных зависимостей типа COURSE -> COURSE). Поэтому высказанные в 
предыдущей главе идеи не по

    Глава 11. Нормальные формы более высокого порядка	309 

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

    UCTX 
    COURSE	TEACHERS	TEXTS 

    Physics	Prof. Green	Basic Mechanics 
    Prof. Brown	Principles of Optics 
    Math	Prof . Green	Basic Mechanics 
    Vector Analysis 
    Trigonometry 
    
    Рис. 11.1. Таблица ненормализованного отношения UCTX 

    стх 

    COURSE	TEACHER	TEXT 
    Physics	Prof . Green	Basic Mechanics 
    Physics	Prof . Green	Principles of Optics 
    Physics	Prof. Brown	Basic Mechanics 
    Physics	Prof . Brown	Principles of Optics 
    Math	Prof. Green	Basic Mechanics 
    Math	Prof. Green	Vector Analysis 
    Math	Prof. Green	Trigonometry 
    
    
    Рис. 11.2. Таблица нормализованного эквивалентного отношения СТХ 

    В простейшей формулировке нормализованное отношение СТХ означает, что 
кортеж {COURSE:c, TEACHER:/, TEXT:*} появляется в данном отношении тогда и 
только тогда, когда курс с читается преподавателем t с использованием учебника 
х, Тогда, принимая во внимание допустимость существования для данного 
отношения всех возможных комбинаций преподавателей вместе с учебниками, можно 
утверждать, что для отношения СТХ верно следующее ограничение: 
    IF      присутствуют оба кортежа (c,tl,xl), (c,t2,x2) 
    THEN    присутствуют также оба кортежа (c,tl,x2), (c,t2,xl) 
    (В данном ограничении для представления кортежей использована сокращенная 
запись без указания имен атрибутов.) 
    Очевидно, что отношение СТХ характеризуется значительной избыточностью и 
приводит к возникновению аномалий обновления. Например, для добавления 
информации о том, что курс физики может читаться новым преподавателем, 
необходимо создать два новых кортежа, по одному для каждого учебника. Тем не 
менее, отношение СТХ находится в НФБК, поскольку является "полностью ключевым". 
    Замечание. Читатель может заметить, что для описания данного курса совсем 
не обязательно приводить все возможные комбинации преподаватель-учебник; 
например, достаточно было бы всего двух кортежей, чтобы показать, что для 
данного курса существуют два преподавателя и два учебника. Проблема 
заключается в том, какие два кортежа следует выбрать? Любой вариант выбора 
ведет к отношению с неочевидной интерпретацией и довольно странным характером 
обновления. Для того чтобы убедиться в этом, достаточно сделать 
соответствующий выбор кортежей и придать некоторый смысл отношению, 
получившемуся в результате такого выбора. Это значит, нужно задать критерии 
возможности того или иного обновления для данного отношения (подробнее это 
обсуждается в главе 4). 

    310 Часть III. Проектирование базы данных 

    Существование подобных "проблем" с отношениями в НФБК, такими как 
отношение СТХ, было замечено достаточно давно. Однако теперь, например для 
отношения СТХ, интуитивно ясно: эти трудности вызваны тем, что преподаватели и 
учебники совершенно независимы друг от друга. Кроме того, достаточно легко 
заметить, что ситуация может быть исправлена к лучшему, если заменить 
отношение СТХ его проекциями {COURSE, TEACHER} и {COURSE, TEXT}, показанными 
на рис. 11.3. Обе проекции являются "полностью ключевыми" и находятся в НФБК; 
более того, отношение СТХ может быть восстановлено с помощью обратного 
соединения проекций СТ и СХ и потому данная композиция выполняется без потерь. 
Однако только в 1971 году эти интуитивные идеи были сформулированы Фейгином 
(Fagin) в строгом теоретическом виде с помощью понятия многозначных зависимостей. 

    СТ			CX 

    COURSE	TEACHER		COURSE	TEXT 

    Physics Physics Math	Prof. Green Prof . Brown Prof. Green		Physics Physics 

Math Math Math	Basic Mechanics Principles of Optics Basic Mechanics Vector 

Analysis Trigonometry 
    
    
    
    
    Рис. 11.3. Таблицы проекций СТ и СХ 

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

    COURSE -» TEACHER COURSE -»• TEXT 

    Обратите внимание на двойную стрелку, которая в многозначной зависимости А 
—»• В означает, что "В многозначно зависит от А" или "А многозначно определяет В". 
    Первая из этих многозначных зависимостей означает, что хотя для каждого 
курса не существует одного соответствующего только этому курсу преподавателя, 
т.е. не выполняется функциональная зависимость COURSE -> TEACHER, тем не 
менее, каждый курс имеет вполне определенное множество соответствующих 
преподавателей (в общем случае их может быть несколько). Точнее, под понятием 
"вполне опреде

    Глава 11. Нормальные формы более высокого порядка 311 

    ленное множество в данном случае подразумевается, что для данного курса с 
и данного учебника х множество преподавателей I, соответствующее паре (с, х) 
отношения СТХ, зависит от значения с и совершенно не зависит от значения х. 
Вторая многозначная зависимость имеет аналогичную интерпретацию. 
    Исходя из изложенного, можно привести определение многозначной зависимости. 
    •  Пусть А, В и С являются произвольными подмножествами множества 
атрибутов отношения R. Тогда В многозначно зависит от А, что символически 
выражается записью 

    А -» В 

    (читается как "А многозначно определяет S" или "А двойная стрелка 5"), 
тогда и только тогда, когда множество значений В, соответствующее заданной 
паре (значение А, значение С) отношения R, зависит только от А, но не зависит 
от С. 
    (Так же, как и в случае с функциональными зависимостями, в данном случае 
интерес представляют не те многозначные зависимости, которые выполняются в 
некоторый момент времени, а те, которые выполняются всегда. Поэтому далее в 
данной главе из этих двух вариантов зависимостей будет рассматриваться 
последний вариант.) 
    Нетрудно показать (это обсуждается в работе Фейгина [11.8]), что для 
данного отношения R{A, 5, С} многозначная зависимость А —» В выполняется тогда 
и только тогда, когда также выполняется многозначная зависимость А —» С. Таким 
образом, многозначные зависимости всегда образуют связанные пары и потому их 
обычно представляют вместе в символическом виде: 

    А  -»    В  |   С. 

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

    COURSE   -»    TEACHER  |   TEXT 

    Ранее уже было сделано утверждение, что многозначные зависимости являются 
обобщениями функциональных зависимостей в том смысле, что всякая 
функциональная зависимость является многозначной. Точнее, функциональная 
зависимость — это многозначная зависимость, в которой множество зависимых 
значений, соответствующее заданному значению детерминанта, всегда является 
одноэлементным множеством. 
    Возвращаясь к исходной задаче с отношением СТХ, теперь можно отметить, что 
описанная ранее проблема с отношением типа СТХ возникает из-за того, что оно 
содержит многозначные зависимости, которые не являются функциональными. 
(Следует отметить совсем неочевидный факт, что именно наличие таких МЗ требует 
вставлять два кортежа, когда необходимо добавить данные еще об одном 
преподавателе физики.) Проекции СТ и СХ не содержат многозначных зависимостей, 
а потому они действительно представляют собой некоторое усовершенствование 
исходной структуры. Поэтому было бы желательно заменить отношение СТХ двумя 
этими проекциями. Это можно сделать, исходя из теоремы Фейгина [11.8], которая 
приведена ниже. 
    •  Теорема Фейгина. Пусть А, В и С являются множествами атрибутов 
отношения R{A, В, С}. Отношение R будет равно соединению его проекций {А, В} и 
{А, С} тогда и только тогда, когда для отношения R выполняется многозначная 
зависимость А -» В | С. 
    (Обратите внимание, что эта теорема является более строгой версией теоремы 
Хеза из главы 10.) Теперь согласно работе Фейгина [11.8] можно дать 
определение четвертой нормальной формы. (Эта нормальная форма получила такое 
название потому, что в момент ее появления НФБК все еще считалась третьей 
нормальной формой.) 
    •  Отношение R находится в четвертой нормальной форме (4НФ) тогда и только 
тогда, когда существуют такие подмножества А и В атрибутов отношения R, что 
выполняется (нетривиальная) многозначная зависимость А -»• В, Тогда все 
атрибуты отношения R также функционально зависят от атрибута А. 

    312	Часть III. Проектирование базы данных 

    Иначе говоря, в отношении R могут находиться только нетривиальные 
зависимости (функциональные или многозначные) вида К-+Х (т.е. некоторый 
атрибут X функционально зависит от потенциального ключа К). Это можно также 
сформулировать в следующей эквивалентной форме: отношение R находится в 4НФ, 
если оно находится в НФБК и все многозначные зависимости отношения R 
фактически являются функциональными зависимостями "от потенциальных ключей". 
Обратите внимание, что теперь наличие 4НФ предполагает наличие НФБК. 
    Отношение СТХ не находится в 4НФ, поскольку содержит многозначную 
зависимость, которая не является функциональной зависимостью, не говоря о том, 
что она должна быть функциональной зависимостью "от потенциального ключа". 
Однако обе проекции, СТ и СХ, находятся в 4НФ, которая по сравнению с НФБК 
позволяет создать улучшенную структуру и заменить ею прежнюю. Кроме того, 
Фейгин в [11.8] показал, что 4НФ всегда может быть получена, т.е. любое 
отношение может быть подвергнуто декомпозиции без потерь на эквивалентный 
набор отношений в 4НФ. Однако, как показано ниже в этой главе на примере 
отношения SJT, такая декомпозиция (или даже декомпозиция до НФБК) не всегда 
оказывается полезной и нужной. 
    В заключение следует отметить, что хотя идеи Риссанена, изложенные в 
посвященной независимым проекциям работе [10.6], основаны на функциональных 
зависимостях, их также можно сформулировать и на основе многозначных 
зависимостей. Необходимо напомнить, что отношение R{A, В, С}, удовлетворяющее 
функциональным зависимостям А —> В и В —> С, следует разбивать на проекции {А, 
В} и {В, С}, а не на проекции {А, В} и {А, С}. Это утверждение также верно, 
если вместо функциональных зависимостей использовать многозначные зависимости 
А —» В и В —» С. 

    11.3. Зависимости соединения и пятая нормальная форма 

    До сих пор в этой и на протяжении предыдущей главы предполагалось, что 
единственной необходимой или допустимой операцией в процессе декомпозиции 
является замена данного отношения (при декомпозиции без потерь) двумя его 
проекциями. Это допущение успешно выполнялось вплоть до определения 4НФ. 
Однако существуют отношения, для которых нельзя выполнить декомпозицию без 
потерь на две проекции, но которые можно подвергнуть декомпозиции без потерь 
на три или более проекции. Такое отношение называется не очень удачным, но 
достаточно удобным термином "«-декомпозируемое отношение" для некоторого п>2. 
Это значит, что для данного отношения возможна декомпозиция без потерь на п 
проекций, а на меньшее число проекций декомпозиция невозможна. Таким образом, 
отношение, для которого можно выполнить декомпозицию на две проекции, 
называется "2-декомпозируемым". 
    Замечание. Впервые возможность и-декомпозируемости была упомянута в работе 
Ахо (Aho), Беери (Beeri) и Ульмана (Ullman) [11.1], а частный случай для п=Ъ 
был также описан Николасом (Nicolas) [11.20]. 
    Рассмотрим в качестве примера отношение SPJ, показанное на рис. 11.4 (это 
упрощенный вариант отношения поставок из базы данных, содержащей информацию о 
поставщиках, товарах (деталях) и проектах). Это отношение является "полностью 
ключевым", не содержит нетривиальных функциональных и многозначных 
зависимостей и потому находится в 4НФ. На этом рисунке также показаны три 
бинарные проекции SP, PJ и JS отношения SPJ, результат соединения проекций SP 
и PJ по атрибуту Р#, а также этот результат, соединенный вместе с проекцией JS 
по комбинации атрибутов (J#, S#). Обратите внимание, что в результате первого 
соединения получено исходное отношение SPJ с еще одним дополнительным (и 
лишним) кортежем, а в результате второго соединения этот лишний кортеж исключается. 
    Замечание. Независимо от того, какая пара проекций будет выбрана для 
первого соединения, в итоге будет получен одинаковый результат, хотя 
промежуточные результаты будут разными в каждом случае (читателю предлагается 
проверить это утверждение). 

    Глава 11. Нормальные формы более высокого порядка	313 

    На рис. 11.4 предстанлен пример конкретного набора данных, соответствующих 
некоторому моменту времени. Однако, ест данное отношение удовлетворяет 
некоторому не зависящему от времени ограничению, то 3-декомпозируемость 
отношения SPJ может быть более фундаментальным и не зависящим от времени 
свойством, т.е. свойством, которое удовлетворяется для всех допустимых 
значений данного отношения. Для того чтобы понять, каким должно быть такое 
отношение, прежде всего отметим, что утверждение "отношение SPJ равно 
соединению трех проекций SP, PJ и JS" эквивалентно следующему утверждению: 

    IF	пара	(sl,pl)	находится в отношении SP 
    AND	пара	(pl,jl)	находится в отношении PJ 
    AND	пара	(jl,sl)	находится в отношении JS 
    THEN	тройка	(sl,pl,jl)	находится в отношении SPJ 
    
    
    SPJ		S#		Р#		J# 
    S1 S1 S2 S1		Р1 Р2 Р1 Р1		J2 Л Л Л 
    
    
    PJ .динение рибуту Р# I 
    SP I S#|  Р	#1				
I P#		J#			JS 1  J#l S#| 
    S1     Р S1     Р S2     Р	Г 2 1				Р1 Р2 Р1		J2 Л Л			
J2     S1 Л     S1 
Л     52 
    I __ SPJ Излишний кортеж	Со« *  по ат				——— » Соединение по комбинации •« 
—— атрибутов J#,S# I 
    S#	Р#	J# 
    S1 S1 S2 —— -    S2 S1	Р1 Р2 Р1 Р1 Р1	J2 Л Л J2 Л 
    original SPJ 
    
    
    Рис. 11.4. Отношение SPJ является соединением всех трех бинарных проекций, 
а не только двух 

    Это верно, поскольку очевидно, что тройка (sl,pljl) находится в соединении 
проекций SP, PJ и JS. (Обратное утверждение, т.е. если тройка (sl,pl,jl) 
присутствует в отношении SPJ, то, например, пара (si ,pl) присутствует в 
проекции SP, является истинным для любого отношения SPJ третьего порядка.) 
    Исходя из этих заключений можно сказать, что пара (si, pi) присутствует в 
отношении SP тогда и только тогда, когда тройка (sl,pl,j2) присутствует в 
отношении SPJ для некоторого значения/2; это аналогично для (pl,jl) и (/У, 
si). Тогда приведенное выше утверждение можно переписать в виде ограничения, 
накладываемого на отношение SPJ: 

    IF    (sl,pl,j2), (s2,pl,jl), (sl,p2,jl) находятся в отношении SPJ THEN   
(sl,pl,jl)        также находится в отношении SPJ 

    Если это утверждение выполняется всегда, т.е. для всех допустимых значений 
отношения SPJ, то тем самым будет получено независящее от времени (хотя и 
несколько странное) ограничение для данного отношения. Обратите внимание на 
циклическую структуру этого ограничения ("если значение si связано с р! нр! 
связано су'У, ау'У связано опять с si, то sl,pl iijl должны находиться в одном 
кортеже")! Отношение будет п-декомпозируемым для п>2 тогда и только тогда, 
когда оно удовлетворяет некоторому циклическому ограничению. 
    Далее 3-декомпозируемое ограничение для краткости будем называть ЗД-ограничением. 
    Однако, что означает циклическое ограничение с практической точки зрения? 
Для получения ответа на этот вопрос следует рассмотреть пример, в котором под 
этими ограничениями подразумевается, что если (например) в отношении SPJ 

    314 Часть III. Проектирование базы данных 

    а) Смит поставляет гаечные ключи, 
    б) гаечные ключи используются в Манхэттенском проекте, 
    в) Смит является поставщиком для Манхэттенского проекта, то 
    г) Смит поставляет гаечные ключи для Манхэттенского проекта. 
    Обратите внимание, что (как уже упоминалось в главе 1) из взятых вместе 
условий (а), (б) и (в) не следует (г). Действительно, точно такой же пример 
был рассмотрен в главе 1 в качестве "ловушки при соединении выражений". В 
данном частном случае, однако, следует сказать, что никакой ловушки нет, 
поскольку существует дополнительное ЗД-ограничение, взятое из реального мира, 
благодаря которому этот вывод является истинным. 
    Возвращаясь к главной теме данного обсуждения, следует отметить, что, 
поскольку ЗД-ограничение удовлетворяется тогда и только тогда, когда отношение 
равносильно соединению некоторых его проекций, такое ограничение называется 
зависимостью соединения. Зависимость соединения (ЗС) является таким же 
ограничением данного отношения, как многозначная и функциональная зависимости. 
Ниже дается определение этого понятия. 
    •   Пусть R является отношением, а А, В,..., Z— произвольными 
подмножествами множества атрибутов отношения R. Отношение R удовлетворяет 
зависимости соединения 

    *   (А,   В,   ...,   Z) 

    тогда и только тогда, когда оно равносильно соединению своих проекций с 
подмножествами атрибутов А, В,..., Z. 
    Например, если использовать сокращенную символьную запись SP для 
подмножества {S#, P#} множества атрибутов отношения SPJ и аналогично 
использовать сокращения PJ и JS, то отношение SPJ будет удовлетворять 
зависимости соединения *(SP, PJ, JS). 
    Отсюда ясно, что отношение SPJ с зависимостью соединения *(SP, PJ, JS) 
может быть 3-декомпозируемым. Однако следует ли выполнять такую декомпозицию? 
По всей видимости, да, так как отношение SPJ характеризуется многочисленными 
аномалиями обновления, которые можно устранить с помощью 3-декомпозиции. 
Некоторые примеры таких отношений приведены на рис. 11.5. Читателям 
предлагается в качестве упражнения попробовать выполнить для них операцию 3-декомпозиции. 

    SPJ					SPJ 
    S#	Р#	J#			S#	Р#	J# 
    S1	Р1	J2			S1	Р1	J2 
    S1	Р2	Л		•       Кортеж удален б побочны	S1 S2 S1	Р2 Р1 Р1	Л Л Л 

    •      Если вставляется кортеж (S2,P1,J1), то также должен быть вставлен 
кортеж (S1,P1,J1) 
    S2,P1,J1) может быть ез возникновения х эффектов 
    •      Однако обратное утверждение не является истинным					•      Если 
удаляется кортеж (S1,P1,J1), то также должен быть удален еще один кортеж (но какой?) 

    Рис. 11.5. Примеры задач с аномалиями обновления для отношения SPJ 

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

    Глава 11. Нормальные формы более высокого порядка 315 

    Также теорема Фейгина может быть сформулирована следующим образом: 
    •  Отношение R{A, В, С} удовлетворяет зависимости соединения *(АВ, АС) 
тогда и только тогда, когда оно удовлетворяет многозначной зависимости А —»• В 
\ С. 
    Поскольку эту теорему можно использовать в качестве определения 
многозначной зависимости, отсюда следует, что либо многозначная зависимость 
является частным случаем зависимости соединения, либо зависимость соединения 
является обобщением понятия многозначной зависимости (так же, как многозначная 
зависимость является обобщением понятия функциональной зависимости). Более 
того, из определения зависимости соединения следует, что из всех возможных 
форм это наиболее общая форма зависимости (при этом, конечно, имеется в виду, 
что термин "зависимость" употребляется в узкоспециализированном смысле). Это 
значит, что для отношений, которые подвергаются декомпозиции на проекции и 
обратной композиции с соединением проекций, не существует более высокой 
степени зависимости, по отношению к которой зависимость соединения является 
всего лишь частным случаем. (Однако если ввести другие операторы декомпозиции, 
то возможно появление других типов зависимости, которые будут кратко описаны 
ниже в этой главе.) 
    Возвращаясь к рассматриваемому примеру, можно обнаружить следующую 
проблему: отношение SPJ содержит зависимость соединения, которая не является 
ни многозначной, ни функциональной зависимостью. (Упражнение. Объясните, 
почему это проблематично?) Можно также заметить, что рекомендуется 
декомпозировать такое отношение на меньшие компоненты, а именно на проекции, 
заданные зависимостью соединения. Такой процесс декомпозиции может повторяться 
до тех пор, пока все результирующие отношения не будут находиться в пятой 
нормальной форме. 
    •  Отношение R находится в пятой нормальной форме (5НФ), которая также 
называется проекционно-соединительной нормальной формой, тогда и только тогда, 
когда каждая зависимость соединения в отношении R подразумевается 
потенциальными ключами отношения R. 
    (Понятие зависимости соединения, подразумеваемой потенциальными ключами 
отношения, разъясняется ниже.) 
    Отношение SPJ не находится в 5НФ. Оно удовлетворяет некоторой зависимости 
соединения, а именно ЗД-ограничению, которое, конечно, не подразумевается его 
единственным потенциальным ключом (этот ключ является комбинацией всех его 
атрибутов). Иначе говоря, отношение SPJ не находится в 5НФ, поскольку оно 
может быть 3-декомпозировано и возможность такой декомпозиции не 
подразумевается тем, что комбинация {S#, P#, J#} является потенциальным 
ключом. Наоборот, после 3-декомпозиции проекции SP, PJ и JS находятся в 5НФ, 
поскольку для них вовсе нет зависимостей соединения. 
    Так как еще не дано объяснение выражения "зависимость соединения, 
подразумеваемая потенциальными ключами", то не совсем очевиден факт, что любое 
отношение в 5НФ автоматически находится в 4НФ, поскольку многозначная 
зависимость является частным случаем зависимости соединения. Действительно, 
Фейгин в [11.9] показал, что любая многозначная зависимость, подразумеваемая 
потенциальным ключом, на самом деле должна быть функциональной зависимостью, в 
которой потенциальный ключ является детерминантом. В той же работе Фейгин 
показал, что данное отношение может быть подвергнуто декомпозиции без потерь 
на эквивалентный набор отношений в 5НФ, т.е. 5НФ всегда достижима. 
    Теперь следует объяснить, что означает понятие "зависимости соединения, 
подразумеваемой потенциальными ключами". Для начала рассмотрим простой пример, 
в котором (как и в главе 10) дано отношение поставщиков S с двумя 
потенциальными ключами S# и SNAME. Такое отношение удовлетворяет нескольким 
зависимостям соединения, например зависимости 

    *   (   {  S#,   SNAME,   STATUS  },   {  S#,   CITY }   }. 

    316	Часть IN. Проектирование базы данных 

    Это значит, что отношение S равносильно соединению его проекций с 
атрибутами {S#, SNAME, STATUS} и {S#, CITY}, а потому может быть подвергнуто 
декомпозиции без потерь на указанные проекции. (Заметьте, что его не следует, 
а можно подвергнуть декомпозиции.) Существование этой зависимости соединения 
следует (или подразумевается) из того, что S# является потенциальным ключом (в 
действительности это следует из теоремы Хеза [10.4]). Аналогично, отношение S 
также удовлетворяет приведенной ниже зависимости соединения: 

    * ( { S#, SNAME }, { S#, STATUS }, { SNAME, CITY } ). 

    Эта зависимость соединения следует из того, что оба атрибута, S# и SNAME, 
являются потенциальными ключами. 
    В общем случае Фейгин в [11.9] предлагает алгоритм, с помощью которого для 
заданной зависимости соединения и множества потенциальных ключей можно 
проверить, будет ли данная зависимость подразумеваться этими потенциальными 
ключами (хотя это не всегда сразу же становится очевидным, вспомните пример, 
приведенный выше). Таким образом, для заданного отношения R можно утверждать: 
R находится в 5НФ при условии, что известны все потенциальные ключи и все 
зависимости соединения для отношения R. Однако обнаружить все зависимости 
соединения совсем не просто. Многозначные и функциональные зависимости 
обнаружить довольно легко, поскольку они имеют достаточно понятную 
интерпретацию в терминах реального мира. В отличие от них, интуитивное 
значение зависимостей соединения, которые не являются многозначными и 
функциональными, не так очевидно. Следовательно, процесс определения, 
находится ли данное отношение в 4НФ или 5НФ и, таким образом, вероятно, может 
быть подвергнуто декомпозиции, все еще остается не очень ясным. Однако, как 
следует из опыта, такие отношения достаточно экзотичны и чрезвычайно редки на 
практике. 
    В заключение заметим, что, как следует из определения 5НФ, она является 
окончательной нормальной формой по отношению к проекции и соединению (что 
отражено в альтернативном названии этой формы — проекционно-соединительная 
нормальная форма). Таким образом, гарантируется, что отношение в пятой 
нормально форме не содержит аномалий, которые могут быть исключены разбиением 
на проекции. (Конечно, это не значит, что данное отношение свободно от всех 
возможных аномалий. Это всего лишь означает, что оно свободно от всех 
аномалий, которые могут быть исключены с помощью разбиения на проекции.) Если 
отношение находится в 5НФ, то единственными зависимостями соединения являются 
те, которые подразумеваются потенциальными ключами, и тогда единственными 
истинными будут декомпозиции, основанные на этих потенциальных ключах. (Каждая 
проекция в такой декомпозиции будет состоять из одного или нескольких 
потенциальных ключей, а также может включать несколько дополнительных 
атрибутов.) Например, отношение по ставщиков S находится в 5 НФ. Как уже 
упоминалось выше, это отношение может быть подвергнуто дальнейшей декомпозиции 
без потерь, но каждая проекция в таком случае все еще будет содержать один из 
исходных потенциальных ключей, и, следовательно, такая декомпозиция не 
принесет никаких дополнительных преимуществ. 

    11.4. Итоговая схема процедуры нормализации 

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

    Глава 11. Нормальные формы более высокого порядка	317 

    приведения состоит из разбиения на проекции отношений, полученных на 
предыдущем этапе. При этом заданные ограничения используются на каждом шаге 
процедуры нормализации для выбора проекций на следующем этапе. Ниже 
перечислены основные правила, которые используются в процедуре нормализации. 
    1.  Отношение в 1НФ следует разбить на проекции для исключения всех 
функциональных зависимостей, которые не являются неприводимыми. В результате 
этого будет получен набор отношений в 2НФ. 
    2.  Отношения в 2НФ следует разбить на проекции для исключения любых 
транзитивных функциональных зависимостей. На этом этапе будет получен набор 
отношений в ЗНФ. 
    3.  Отношения в ЗНФ следует разбить на проекции для исключения любых 
оставшихся функциональных зависимостей, в которых детерминанты не являются 
потенциальными ключами. В результате такого приведения будет получен набор 
отношений в НФБК. 
    Замечание. Правила 1-3 могут быть сконцентрированы в одном: "Исходное 
отношение следует разбить на проекции для исключения всех функциональных 
зависимостей, в которых детерминанты не являются потенциальными ключами ". 
    4.  Отношения в НФБК следует разбить на проекции для исключения любых 
многозначных зависимостей, которые не являются функциональными зависимостями. 
В результате будет получен набор отношений в 4НФ. 
    Замечание. На практике обычно такие многозначные зависимости исключаются 
перед выполнением этапов 1-3 (отделяя независимые повторяющиеся группы), как 
уже упоминалось при рассмотрении примера СТХ выше в этой главе. 
    5.  Отношения в 4НФ следует разбить на проекции для исключения любых 
зависимостей соединения, которые не подразумеваются потенциальными ключами, 
хотя в данном случае следует добавить фразу "если их можно выявить". Таким 
образом будет получен набор отношений в 5НФ. 
    Из приведенных выше правил можно выделить некоторые особенности. 
    1. Прежде всего, процесс разбиения на проекции на каждом этапе должен быть 
выполнен без потерь и с сохранением зависимости (там, где это возможно). 
    2.  Обратите внимание, что (как было впервые отмечено Фейгиным в [11.9]) 
существует довольно привлекательный набор альтернативных определений НФБК, 4НФ 
и ЗНФ. 
    • Отношение R находится в НФБК тогда и только тогда, когда каждая 
функциональная зависимость подразумевается потенциальными ключами отношения R. 
    • Отношение R находится в 4НФ тогда и только тогда, когда каждая 
многозначная зависимость подразумевается потенциальными ключами отношения R. 
    • Отношение R находится в ЗНФ тогда и только тогда, когда каждая 
зависимость соединения подразумевается потенциальными ключами отношения R. 
    Аномалии обновления, обсуждаемые в главе 10 и в предыдущих разделах данной 
главы, были вызваны как раз теми функциональными или многозначными 
зависимостями либо зависимостями соединения, которые не подразумевались 
потенциальными ключами. 
    3.  В общем, необходимо выделить следующие цели процесса нормализации: 
    • исключение некоторых типов избыточности; 
    • устранение некоторых аномалий обновления; 
    • проектирование макета базы данных, который являлся бы "хорошим" 
представлением реального мира, был интуитивно понятен и служил хорошей основой 
для дальнейшего развития; 
    • упрощение процесса наложения ограничений целостности. 
    Последний пункт данного списка следует рассмотреть отдельно. Общая идея 
(как уже обсуждалось раньше в этой книге) заключается в том, что некоторые 
ограничения под

    318	Часть III, Проектирование базы данных 

    разумевают другие ограничения. В качестве простейшего примера можно 
привести ограничение на зарплату, которая должна быть выше 100 долларов, а 
следовательно, выше нуля. Таким образом, если ограничение А подразумевает 
ограничение Б, то после приведения в действие ограничения А будет 
автоматически задействовано также ограничение Б (для этого даже не потребуется 
объявлять ограничение Б явным образом, за исключением случаев, когда это 
делается в виде комментария). Тогда приведение к 5НФ представляет собой 
простой путь наложения некоторых важных и распространенных ограничений. 
Главное — привести в действие условие уникальности потенциальных ключей, а 
затем все зависимости соединения (и все многозначные и функциональные 
зависимости) будут задействованы автоматически, поскольку все они 
подразумеваются потенциальными ключами. 
    4.   Необходимо вновь подчеркнуть тот факт, что данные рекомендации по 
поводу нормализации являются всего лишь рекомендациями и, вероятно, могут 
существовать соображения, по которым нормализацию не следует выполнять точно 
таким же образом "от начала и до конца". Классическим примером ситуации, когда 
полная нормализация не желательна, является отношение типа имя-адрес NADDR (из 
упражнений главы 10), хотя следует признать, что этот пример не совсем 
убедителен. Как правило, нормализацию обычно рекомендуется выполнять полностью. 
    5.  Следует также повторить идею, высказанную в главе 10, что понятия 
зависимости и дальнейшей нормализации семантические, т.е. связаны со смыслам 
данных. А реляционная алгебра и исчисление утверждений, а также построенные на 
их основе языки типа SQL, наоборот, связаны со значениями данных, а их 
интерпретация проводится на основе внешних факторов (например, пользователем). 
Таким образом, подобные формальные подходы и построенные на их основе языки не 
требуют и не могут требовать нормализации с уровнем выше первого. В этом 
случае рекомендации по процедуре нормализации могут прежде всего 
рассматриваться как некий порядок, согласно которому разработчик базы данных 
(и, следовательно, ее пользователь) может заключить некую часть, пусть даже 
очень малую, семантики реального мира в простую и понятную форму. 
    6.   Исходя из сказанного выше, необходимо отметить, что, хотя идеи 
нормализации чрезвычайно полезны для проектирования базы данных, они не 
являются универсальным средством по следующим причинам: 
    • Нормализация (как уже упоминалось выше) действительно может помочь 
привести в действие (и в очень простой форме) ограничения целостности, но, 
помимо зависимостей соединения, функциональных и многозначных зависимостей, 
существуют также другие типы ограничений, которые встречаются на практике. 
    • Декомпозиция может быть неуникальной (обычно, существует множество путей 
для приведения данного набора отношений к 5НФ), а для выбора предпочтительной 
декомпозиции среди нескольких альтернативных существует совсем немного критериев. 
    • Как уже упоминалось в главе 10 (пример с отношением SJT), преследование 
двух целей, т.е. приведение к НФБК и сохранение зависимости, может привести к 
конфликтной ситуации. 
    • Процедура нормализации позволяет избавиться от избыточности за счет 
разбиения на проекции, однако не всякую избыточность можно устранить таким образом. 
    Следует также отметить, что совершенные методики нисходящего 
проектирования тем или иным образом позволяют генерировать полностью 
нормализованный макет базы данных. 

    11.5. Другие нормальные формы 

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

    Глава 11. Нормальные формы более высокого порядка	319 

    просов — в настоящее время она обычно называется теорией зависимостей — 
развилась в значительную область знаний с несколькими различными (хотя и не 
пересекающимися) направлениями и обширной литературой. Исследования в этой 
области продолжаются и довольно успешно, хотя более глубокий обзор этих 
исследований выходит за рамки данной главы. Хороший обзор результатов, 
полученных в этой области по состоянию на середину 80-х годов можно найти в 
[10.12]. Ниже в качестве примера приведено описание двух других нормальных форм, 
    1. Доменно-ключевая нормальная форма — ДКНФ. Она была предложена Фейгиным 
в [11.10] и, в отличие от рассмотренных выше нормальных форм, не определяется 
на основе функциональных, многозначных зависимостей или зависимостей 
соединения. Вместо этого утверждается, что отношение R находится в ДКНФ тогда 
и только тогда, когда каждое ограничение, наложенное на отношение R, является 
логическим следствием ограничений доменов и ограничений ключей, наложенных на 
отношение R. 
    • Ограничение домена — это ограничение на использование значений для 
данного атрибута только из некоторого предписанного домена. (В последующих 
главах это ограничение будет также упоминаться как ограничение атрибута, а не 
как ограничение домена.) 
    • Ограничение ключа— это ограничение на то, что некоторый атрибут или 
некоторая комбинация атрибутов представляют собой потенциальный ключ. 
    Наложение ограничений на отношение, находящееся в ДКНФ, является 
концептуально очень простым, поскольку для этого достаточно задать ограничения 
домена и ключа, а все остальные ограничения будут приведены в действие 
автоматически. Обратите внимание, что под выражением "все остальные 
ограничения" подразумевается нечто большее, чем просто функциональные и 
многозначные зависимости или зависимости соединения. Фактически это обозначает 
предикат данного отношения, который определен в главе 4 (также описан далее в 
этой книге). 
    Фейгин в [11.10] показал, что любое отношение, находящееся в ДКНФ, 
находится в 5НФ (а значит, и в 4НФ), а также в форме типа (3,3)НФ (подробнее 
об этом рассказывается ниже). Однако не всегда можно добиться приведения к 
ДКНФ или получить ответ на вопрос, когда такое приведение может быть выполнено. 
    2.   Нормальная форма типа "выборка—объединение". Снова рассмотрим 
отношение поставщиков S. Согласно описанной выше теории нормализации, это 
отношение находится в 5НФ и, следовательно, не характеризуется аномалиями и не 
нуждается в дальнейшем разбиении на проекции для устранения аномалий. Но зачем 
хранить сведения обо всех поставщиках в одном отношении? Может было бы лучше 
разместить данные о поставщиках из Лондона в одном отношении (например, 
отношении LS), из Парижа— в другом (например, PS) и т.д.? Иначе говоря, может 
быть стоило бы рассмотреть возможность декомпозиции на основе выборки (имеется 
в виду выборка по строкам), а не на основе проекции? Лучше или хуже будет 
структура, полученная в результате такой декомпозиции? (Фактически она всегда 
получается хуже, однако классическая теория нормализации не может дать ответа 
на поставленные выше вопросы.) 
    Другим направлением в исследованиях нормализации является применение 
декомпозиции на основе других операций, отличных от проекции. В 
рассматриваемом выше примере, как уже упоминалось, оператором декомпозиции 
является непересекающаяся выборка, а соответствующий оператор композиции 
является непересекающимся объединением. Таким образом, всегда можно создать 
"выбирающе-объединительную" теорию нормализации, аналогичную, но независимую 
относительно обсуждаемой здесь проекционно-соединительной теории нормализации. 
(Действительно, Фейгин в [11.9] назвал 5НФ проекционно-соединительной 
нормальной формой, поскольку это была именно такая нор

    320	Часть III. Проектирование базы данных 

    мальная форма, которая была связана с операторами проекции и соединения.) 
Автору настоящей книги ничего не известно о дальнейшем развитии аналогичных 
теорий, однако некоторые исходные идеи можно найти в статье Смита [11.26], где 
определена нормальная форма под названием (3,3)НФ. Подразумевается, что 
отношение в (3,3)НФ уже находится в НФБК, однако не обязательно находится в 
4НФ, так же как отношение в 4НФ не обязательно находится в (3,3)НФ. Таким 
образом, как и предполагалось выше, приведение к форме типа (3,3)НФ является 
независимым по отношению к приведению к 4НФ (и 5НФ). Более подробно об этом 
можно прочесть в [ 11.9, 11.17]. 

    11.6. Резюме 

    Эта глава завершает обсуждение дальнейшей нормализации с описанием 
многозначных зависимостей, являющихся обобщением функциональных зависимостей, 
а также зависимостей соединения, являющихся обобщениями многозначных 
зависимостей. Ниже даны определения этих понятий с неформальной точки зрения. 
    •   Отношение R{A, В, С} удовлетворяет многозначной зависимости А -» В С 
тогда и только тогда, когда множество значений В, соответствующее заданной 
паре (А, С), зависит только от значения А, и аналогично множество значений 
атрибута С, соответствующее заданной паре (А, В), зависит также только от 
значения А. Такое отношение может быть подвергнуто декомпозиции без потерь на 
проекции {А, В} и {А, С}, а многозначные зависимости являются необходимым и 
достаточным условием истинности такой декомпозиции (теорема Фейгина). 
    •   Отношение R{A, В,..., Z} удовлетворяет зависимости соединения *(А, 
В,..., Z) тогда и только тогда, когда оно равно соединению его проекций по 
атрибутам А, В,..., Z. Такое отношение может быть (очевидно) разбито на 
проекции на основе декомпозиции без потерь. 
    Отношение находится в 4НФ, если единственными многозначными зависимостями, 
которым оно удовлетворяет, являются функциональные зависимости, 
подразумеваемые потенциальными ключами. Отношение находится в 5НФ (также 
называемой проекционно-соединительной нормальной формой) тогда и только тогда, 
когда единственными зависимостями соединения, которым оно удовлетворяет, 
являются функциональные зависимости, подразумеваемые потенциальными ключами. 
Пятая нормальная форма (которая всегда достижима) является окончательной 
нормальной формой по отношению к операциям проекции и соединения. 
    Также в этой главе кратко представлена схема процедуры нормализации в виде 
некоторой неформальной последовательности этапов с комментариями и кратким 
описанием некоторых дополнительных нормальных форм. 
    В заключение следует отметить, что дальнейшие исследования в этой области 
чрезвычайно перспективны. Дело в том, что теория дальнейшей нормализации, 
точнее, теория зависимостей действительно все еще остается одним из очень 
субъективных научных разделов проектирования баз данных, для которого 
необходимо создать более твердые принципы и методики. Поэтому любой успех в 
дальнейшем изучении этой теории представляет значительный интерес для исследователей. 

    Упражнения 

    11.1. Пусть С— это некоторое множество, а отношение R{A, В} таково, что 
кортеж (а, Ь) содержится в R тогда и только тогда, когда а и b принадлежат С. 
Каким функциональным и многозначным зависимостям, а также каким зависимостям 
соединения удовлетворяет R1 В какой нормальной форме находится это отношение? 
    11.2. Пусть некоторая база данных содержит информацию о распространителях 
продукции, регионах распространения и о самой продукции. Каждый распро

    Глава 11. Нормальные формы более высокого порядка	
    321 11 Введение в системы баз данных 


    странитель отвечает за продажи в одном или нескольких регионах, а каждый 
регион имеет одного или нескольких распространителей. Аналогично, каждый 
распространитель продает один или несколько видов продукции, а каждый вид 
продукции распространяется одним или несколькими распространителями. Каждый 
вид продукции продается в каждом регионе, однако два распространителя не могут 
продавать один и тот же продукт в одном и том же регионе. Все распространители 
продают одинаковый набор продукции в каждом регионе, за который они отвечают. 
Спроектируйте реляционную структуру, подходящую для таких условий и данных. 
    11.3. В ответе к упр. 10.3 в главе 10 был дан алгоритм декомпозиции без 
потерь для отношения R с разбиением его на множество отношений в НФБК. 
Измените этот алгоритм таким образом, чтобы совершить то же преобразование, но 
уже к 4НФ. 
    11.4. (Модифицированная версия упр. 11.2). Пусть некоторая база данных 
содержит информацию о распространителях продукции, регионах распространения и 
о самой продукции. Каждый распространитель отвечает за продажи в одном или 
нескольких регионах, а каждый регион имеет одного или нескольких 
распространителей. Аналогично, каждый распространитель продает один или 
несколько видов продукции, а каждый вид продукции распространяется одним или 
несколькими распространителями. Каждый вид продукции продается в одном или 
нескольких регионах, а в каждом регионе продается один или несколько видов 
продукции. Более того, если распространитель R отвечает за распространение в 
регионе А, продукт Р продается в регионе А, а распространитель R отвечает за 
продажу продукта Р, то R продает Р в А. Спроектируйте реляционную структуру, 
подходящую для таких условий и данных. 

    Список литературы 

    11.1. Aho A.V., Beeri С., Ullman J. D. The Theory of Joins in Relational 
Databases // ACM TODS.— 1979.— 4, № 3. (Впервые опубликована в Proc. 19th IEEE 
Symposium on Foundations of Computer Science. — 1977.) 
    Первая попытка рассмотреть отношения, которые равны соединению не двух, а 
трех или более проекций отношения. Основная цель статьи — представить алгоритм 
для определения, является ли данная зависимость соединения логическим 
следствием данного набора функциональных зависимостей (пример его воплощения 
приведен в [11.2]). Эта проблема эквивалентна определению, будет ли данная 
декомпозиция выполняться без потерь для заданного набора функциональных 
зависимостей. В статье также обсуждается вопрос расширения алгоритма для 
случая, когда заданные зависимости являются не функциональными, а многозначными. 
    11.2. Beeri С., Fagin R., Howard J.H. A Complete Axiomatization for 
Functional and Multivalued Dependencies // Proc. 1977 ACM SIGMOD Intern. Conf. 
on Management of Data. — Toronto, Canada, 1977. 
    Представляет собой обобщение результатов работы Армстронга (Armstrong) 
[9.1], распространяемое на многозначные зависимости так же, как и на 
функциональные. В частности, в работе дается строгий и полный набор правил 
вывода для многозначных зависимостей. 
    1.   Образование дополнения. Если множества атрибутов А, В, С содержат все 
атрибуты отношения и А является супермножеством В о С, то А —» В тогда и 
только тогда, когда А -» С. 
    2.   Рефлексивность. Если В является подмножеством А, то А -» В. 

    322	Часть III, Проектирование базы данных 

    3.  Дополнение. Если А —» В и С является подмножеством D, то AD —» ВС. 
    4.   Транзитивность. Если А -»?и/?-»С,тоЛ -» С-В . 
    Далее следуют дополнительные полезные правила, которые выводятся из 
приведенных выше правил. 
    5.	Псевдотранзитивность. Если А —» В и ВС —» D, то АС —» D-BC. 
    6.	Объединение. Если А -» ВиА -» С, то А -» ВС. 
    1.	Декомпозиция. Если А -» ВС, то А -» В п С, А -» В-С и А -» С-В. 
    Затем в статье представлены еще два правила, по которым можно вывести 
некоторые другие функциональные зависимости на основе определенных комбинаций 
функциональных и многозначных зависимостей. 
    8.   Репликация. Если А -> В, то А -» В. 
    9.   Слияние. Если А —» В, С —> D, D является подмножеством S, а 
пересечение В п С пусто, то А —» D. 
    Правила Армстронга (подробнее это обсуждалось в главе 9) вместе с 
правилами 1—4, 8 и 9 образуют строгий и полный набор правил для функциональных 
и многозначных зависимостей. 
    В статье также выведено еще одно полезное правило, связывающее 
функциональные и многозначные зависимости. 
    10. Если А -» Я и Лб -> С, то Л ->• С-В. 
    11.3. Brosda V., Vossen G. Update and Retrieval Through a Universal Schema 
Interface // ACM TODS. — 1988. — 13, № 4. 
    См. аннотацию к [11.14]. 
    11.4. Carlson C.R., Kaplan R.S. A Generalized Access Path Model and Its 
Application to a Relational Data Base System // Proc. 1976 ACM SIGMOD Intern. 
Conf. on Management of Data. — Washington, D.C., 1976. 
    См. аннотацию к [ 11.14]. 
    11.5. Date C.J. Will the Real Fourth Normal Form Please Stand Up? // C. J. 
Date and Hugh Darwen. Relational Database Writings 1989-1991.— Reading, Mass.: 
Addison-Wesley, 1992. 
    В работе отмечается, что существует несколько различных понятий в области 
проектирования баз данных, которые относятся к одному и тому же названию — 
четвертая нормальная форма (4НФ). Цель данной работы — прояснить смысл этого понятия. 
    11.6. Date C.J., Fagin R. Simple Conditions for Guaranteeing Higher Normal 
Forms in Relational Databases // Ibid. (Работа также опубликована в ACM TODS. 
— 1992. —17, №3.) 
    В работе показано, что если отношение R находится в ЗНФ и все 
потенциальные ключи отношения R простые (т.е. на основе одного атрибута), то R 
автоматически находится в ЗНФ. Иначе говоря, в таком случае не стоит 
беспокоиться о разных и относительно сложных вопросах, связанных с 
многозначными зависимостями, зависимостями соединения, 4НФ и ЗНФ, которые 
обсуждаются в данной главе. 
    Замечание. В статье также доказан другой результат, а именно: если 
отношение R находится в НФБК и хотя бы один из потенциальных ключей является 
простым, то отношение R автоматически находится в 4НФ, но не обязательно в ЗНФ. 
    11.7. Delobel С., Parker D.S. Functional and Multivalued Dependencies in a 
Relational Database and the Theory of Boolean Switching Functions. Tech. 
Report No. 142. — Dept. Maths. Appl. et Informatique, Univ. de Grenoble, 
France, 1978. 

    Глава 11. Нормальные формы более высокого порядка	323 

    Эта работа расширяет тему, затронутую в [9.3], от функциональных 
зависимостей до многозначных. 
    11.8, Fagin R. Multivalued Dependencies and a New Normal Form for 
Relational Databases // ACM TODS. — 1977. — 2, № 3. 
    Под упомянутой в заголовке этой статьи новой нормальной формой 
подразумевается 4НФ. 
    Здесь следует добавить замечание о внедренных многозначных зависимостях. 
Допустим, что отношение СТХ, рассмотренное в этой главе, расширено 
дополнительным атрибутом DAYS, представляющим число дней, затраченных на 
преподавание содержания учебника TEXT некоторым преподавателем TEACHER, 
который ведет некоторый курс обучения COURSE. Такое расширенное отношение 
обозначим CTXD и рассмотрим приведенный ниже образец данных этого отношения. 

    CTXD 
    COURSE	TEACHER	TEXT	DAYS 
    Physics	Prof. Green	Basic Mechanics	5 
    Physics	Prof . Green	Principles of Optics	5 
    Physics	Prof. Brown	Basic Mechanics	6 
    Physics	Prof. Brown	Principles of Optics	4 
    Math	Prof . Green	Basic Mechanics	3 
    Math	Prof. Green	Vector Analysis	3 
    Math	Prof . Green	Trigonometry	4 

    Первичным ключом в данном случае является комбинация {COURSE, TEACHER, 
TEXT} со следующей функциональной зависимостью: 

    { COURSE, TEACHER, TEXT } -» DAYS. 

    Можно заметить, что данное отношение находится в 4НФ, поскольку не 
содержит никаких многозначных зависимостей, которые также не являются 
функциональными зависимостями (если вспомнить определения 4НФ и МЗ). Однако 
оно не содержит двух внедренных многозначных зависимостей (атрибута TEACHER от 
атрибута COURSE и атрибута TEXT от атрибута COURSE). Внедренная зависимость В 
от А выполняется для отношения R, если в некоторой проекции отношения R 
выполняется "обычная" многозначная зависимость А —> В. Обычная многозначная 
зависимость является специальным случаем внедренной многозначной зависимости, 
но не все внедренные многозначные зависимости являются обычными многозначными зависимостями. 
    Как иллюстрирует данный пример, внедренные многозначные зависимости также 
предполагают избыточность, как и обычные МЗ, однако такая избыточность не 
может быть исключена с помощью разбиения на проекции. Представленное выше 
отношение нельзя подвергнуть декомпозиции без потерь (оно фактически находится 
не только в 4НФ, но и в 5НФ), поскольку атрибут DAYS зависит от всех трех 
атрибутов — COURSE, TEACHER и TEXT, а потому не может находиться в отношении 
без какого-либо из них. Вместо этого две внедренных многозначных зависимости 
следует рассматривать как дополнительные явно заданные ограничения данного 
отношения (подробнее это описано в последующих главах книги). 
    11.9. Fagin R. Normal Forms and Relational Database Operators // Proc. 
1979 ACM S1GMOD Intern. Conf. on Management of Data. — Boston, Mass., 1979. 
    В статье представлена концепция проекционно-соединительной нормальной 
формы (или 5НФ). Эта концепция также может рассматриваться как определение 
того, что можно назвать "классической" теорией нормализации, т.е. теорией 
декомпозиции без потерь, основанной на проекции как операторе 

    324 Часть III. Проектирование базы данных 

    декомпозиции и на естественном соединении как соответствующем операторе композиции. 
    11.10. Fagin R. A Normal Form for Relational Databases That Is Based on 
Domains and Keys // ACM TODS. — 1981. — 6, № 3. 
    11.11. Fagin R. Acyclic Database Schemes (of Various Degrees): A Painless 
Introduction // IBM Research Report RJ3800.— 1983. (Переиздано: Ргос. СААР83 
8th Colloquium on Trees in Algebra and Programming: Springer-Verlag Lecture 
Notes in Computer Science No. 159 (eds. G. Ausiello and M. Protasi).— New 
York, N.Y.: Springer-Verlag, 1983.) 
    Выше в этой главе было показано, как некоторое тройное отношение SPJ, 
которое удовлетворяет некоторому циклическому ограничению, может быть 
подвергнуто декомпозиции без потерь с образованием трех бинарных отношений. 
Полученная в результате структура базы данных (в этой работе она называется 
схемой) является циклической, поскольку каждое из трех отношений имеет 
атрибут, общий с каждым из остальных двух отношений. Многие реальные 
структуры, наоборот, являются ациклическими. Ациклические структуры обладают 
большим количеством формальных свойств, которые вообще-то не приняты в области 
баз данных. В этой статье Фейгин представляет и разъясняет некоторые из таких свойств. 
    11.12. Fagin R., Vardi M.Y. The Theory of Data Dependencies— A Survey// 
IBM Research Report RJ4321.— 1984. (Переиздано: Mathematics of Information 
Processing // Proc. Symposia in Applied Mathematics 34, American Mathematical 
Society, 1986.) 
    В работе излагается краткая история теории зависимостей по состоянию на 
середину 80-х годов (следует обратить внимание, что слово "зависимость" в 
данном случае не относится только к функциональным зависимостям). В частности, 
в статье подытожены основные достижения в трех отдельных областях этой теории 
с перечнями рекомендуемой литературы по каждой из тем. Эти три темы включают 
проблему импликации, универсальную реляционную модель и ациклические схемы. 
Проблема импликации заключается в выяснении для заданного набора зависимостей 
D и некоторой отдельной зависимости d, будет ли d логическим следствием D 
(подробнее это обсуждается в разделе 9.7). Универсальная реляционная модель и 
ациклические схемы кратко обсуждаются в комментариях к [11.14] и [11.11] соответственно. 
    11.13. Fagin R., Mendelzon А.О., Ullman J.D. A Simplified Universal 
Relation Assumption and Its Properties // ACM TODS. — 1982. — 7, № 3. 
    Здесь содержится предположение о том , что "реальный мир" всегда может 
быть представлен с помощью универсального отношения [11.14], которое 
удовлетворяет точно одной зависимости соединения вместе с некоторым множеством 
функциональных зависимостей, а также обсуждаются следствия такого предположения. 
    11.14. Kent W. Consequences of Assuming a Universal Relation//Ibid. — 
1981. — 6, №4. 
    Здесь несколькими различными способами представлена концепция 
универсального отношения. В первом способе предполагается согласно порядку 
нормализации, описанному в последних главах, возможность задания исходного 
универсального отношения, которое включает все атрибуты рассматриваемой базы 
данных, а затем показано, как такое отношение может быть последовательно 
заменено меньшими проекциями вплоть до достижения некоторой "приемлемой" 
структуры. Но является ли исходное предположение реальным или справедливым? В 
работе утверждается, что это не так и с практической, и с теоретической точек 
зрения. В ответ на данную статью появилась публикация [11.27], а в ответ на 
нее — [11.15]. 

    Глава 11. Нормальные формы более высокого порядка	325 

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

    RETRIEVE STATUS WHERE COLOR = 'Red' 

    В этой связи идея имеет две более или менее различающиеся интерпретации. 
    1. Одна возможность заключается в том, что система должна каким-то образом 
самостоятельно определить, какому логическому пути нужно следовать для 
выполнения запроса (в частности, какие соединения ей необходимо создавать). 
Таков подход, предлагаемый в [11.4] (эта статья, по всей видимости, является 
первой статьей, посвященной возможности создания универсального интерфейса 
пользователя, хотя термин "универсальное отношение" и не упоминается в ней). 
Этот подход в значительной степени зависит от соответствующего наименования 
атрибутов. Таким образом, например, для двух атрибутов номера поставщика (в 
отношениях S и SP) должны быть заданы одинаковые имена; и наоборот, для 
атрибутов города поставщика и товара поставщика (в отношениях S и Р 
соответственно) не должны быть заданы одинаковые имена. Если какое-либо из 
этих правил будет нарушено, то некоторые запросы могут быть выполнены не 
совсем корректно. 
    2.   В другой, менее амбициозной, интерпретации следует рассматривать все 
запросы в терминах предопределенного набора соединений — в действительности 
предопределенного представления, состоящего из соединения всех отношений в 
рассматриваемой базе данных. 
    Поскольку нет сомнений в том, что любой из представленных здесь подходов 
позволяет значительно упростить выражение для вычисления многих практических 
запросов (действительно, такой подход может поддерживаться любым естественным 
интерпретируемым языком программирования), ясно, что система должна 
поддерживать способность явного указания (логического) пути доступа. Для того 
чтобы продемонстрировать это, рассмотрим следующий запрос: 

    RETRIEVE STATUS WHERE COLOR Ф 'Red' 

    Что означает этот запрос: "Получить статус всех поставщиков, которые 
поставляют не красные детали" или "Получить статус всех поставщиков, которые 
не поставляют красные детали"? Какое бы значение из двух не было выбрано, 
должна также существовать формулировка и для другого. Аналогично, в первом 
примере можно также использовать заданную формулировку для альтернативной 
интерпретации: "Получить статус для поставщиков, которые поставляют только 
красные детали". В качестве третьего примера можно привести запрос "Получить 
имена поставщиков, находящихся в одном и том же месте", для которого, 
очевидно, придется явным образом задать соединение (поскольку в этой задаче 
содержится соединение отношения S с самим собой). 
    11.15. Kent W. The Universal Relation Revisited //ACM TODS. — 1983. — 8, № 4. 
    11.16. Korth H.F. et al. System/U: A Database System Based on the 
Universal Relation Assumption // Ibid. — 1984. — 9, № 3. 
    Здесь приводится описание теории языка определения данных (data definition 
language — DDL), языка обработки данных и практического воплощения 
экспериментальной универсальной реляционной системы, созданной в Стэн-фордском университете. 

    326	Часть III. Проектирование базы данных 

    11.17. Maier D., Ullman J.D. Fragments of Relations // Proc. 1983 SIGMOD 
Intern. Conf. on Management of Data. — San Jose, Calif, 1983. 
    11.18. Maier D., Ullman J.D., Vardi M.Y. On the Foundations of the 
Universal Relation Model // ACM TODS.— 1984.— 9, №2. (Более ранняя версия этой 
статьи под заголовком "The Revenge of the JD" опубликована в Proc. 2nd ACM 
SIGFACT-SIGMOD Symposium on Principles of Database Systems. — Atlanta, Ga., 1983.) 
    11.19. Maier D., Ullman J.D. Maximal Objects and the Semantics of 
Universal Relation Databases//ACM TODS. — 1983. —8, № 1. 
    Максимальные объекты представляют собой подход для разрешения проблемы 
двузначности, которая возникает в универсальных реляционных системах с 
ациклической структурой (подробнее это описано в [11.11]). Максимальный объект 
соответствует предварительно объявленному подмножеству атрибутов 
универсального отношения, которое имеет ациклическую базовую структуру. Такие 
объекты используются для интерпретации запросов, которые в ином случае были бы двусмысленными. 
    11.20. Nicolas J.M. Mutual Dependencies and Some Results on Undecomposable 
Relations // Proc. 4th Intern. Conf. on Very Large Data Bases. — Berlin, FOR, 1978. 
    В работе вводится концепция "взаимной зависимости", которая в 
действительности представляет собой частный случай зависимости соединения, не 
являющейся многозначной или функциональной зависимостью, и включает точно три 
проекции (как в примере с зависимостью соединения, упомянутом выше в этой 
главе). Однако эта концепция не имеет ничего общего с понятием взаимной 
зависимости, описанным в главе 10. 
    11.21. Osborn S.L. Towards a Universal Relation Interface // Proc. 5th 
Intern. Conf. on Very Large Data Bases. — Rio de Janeiro, Brazil, 1979. 
    В статье предполагается, что если две или более последовательности 
соединений в универсальной реляционной системе генерируют потенциальный ответ 
на заданный запрос, то желательным откликом будет соединение всех таких 
потенциальных ответов. Приводятся алгоритмы для генерации всех таких 
последовательностей соединений. 
    11.22. Parker D.S., Delobel С. Algorithmic Applications for a New Result 
on Multivalued Dependencies // Ibid. 
    Здесь описано применение результатов работы [11.7] для решения различных 
проблем, например для тестирования операции декомпозиции без потерь. 
    11.23. Sagiv Y., Delobel С., Parker D.S., Fagin R. An Equivalence between 
Relational Database Dependencies and a Subclass of Propositional Logic // 
JACM. — 
    1981. —28, №3. 
    Это комбинация работ [9.8] и [11.24]. 
    11.24. Sagiv Y., Fagin R. An Equivalence between Relational Database 
Dependencies and a Subclass of Propositional Logic // IBM Research Report 
RJ2500. — 1979. 
    Здесь результаты работы [9.8], полученные для функциональных зависимостей, 
расширены для многозначных зависимостей. 
    11.25. Sciore E. A Complete Axiomatization of Full Join Dependencies // JACM.— 
    1982. —29, №2. 
    Здесь результаты работы [11.2], полученные для функциональных 
зависимостей, расширены для многозначных зависимостей. 
    11.26. Smith J.M. A Normal Form for Abstract Syntax // Proc. 4th Intern. 
Conf. on Very Large Data Bases. — Berlin, FOR, 1978. 

    Глава 11. Нормальные формы более высокого порядка	327 

    Здесь впервые представлено понятие нормальной формы типа (3,3)НФ. 
    11.27. Ullman J.D. On Kent's Consequences of Assuming a Universal Relation 
// ACM TODS.—1983.—8, №4. 
    11.28. Ullman J.D. The U.R.  Strikes Back // Proc.   1st ACM  
SIGFACT-SIGMOD Symposium on Principles of Database Systems. — Los Angeles, 
Calif, 1982. 

    Ответы к упражнениям 

    11.1. Прежде всего обратите внимание, что отношение R содержит все 
возможные значения А в паре со всеми возможными значениями В, более того, 
множество всех возможных значений А, например S, такое же, как и множество 
всех значений В. Таким образом, отношение R равносильно декартову произведению 
множества S на само это множество. Или в эквивалентной формулировке: отношение 
R равносильно декартову произведению проекции отношения R по А с проекцией 
отношения R по В. Таким образом, R удовлетворяет следующим многозначным 
зависимостям (которые не являются тривиальными, поскольку не удовлетворяют 
всем отношениям): 
    (   }    -»    Л   |   В. 
    Эквивалентно также утверждение, что отношение R удовлетворяет зависимости 
соединения *(А, В) (помните, что соединение без общих атрибутов деградирует и 
становится декартовым произведением). 
    Отсюда следует, что отношение R не находится в 4НФ, однако находится в 
НФБК (полностью ключевое), и оно не удовлетворяет никаким нетривиальным 
функциональным зависимостям. 
    Замечание. Отношение R также удовлетворяет двум многозначным зависимостям: 
    А   -»    В  |   {   } 
    В   -»    А  |   {   } 
    Однако эти многозначные зависимости являются тривиальными, поскольку 
удовлетворяют любым бинарным отношениям с атрибутами А ч В. 
    11.2. Сначала введем три отношения с первичными ключами имен 
распространителей, названий регионов и названий продукции соответственно: 

    REPS      ( REP#, ... ) 
    PRIMARY KEY ( REP# ) AREAS     ( AREA#, . . . ) 
    PRIMARY KEY ( AREA* ) PRODUCTS  ( PRODS, ... ) 
    PRIMARY KEY ( PROD* ) 

    Затем представим связь между распространителями и продажами с помощью 
следующего отношения: 

    RA ( REP#, AREA* ) 
    PRIMARY KEY ( REP#, AREA# ) 

    А связь между распространителями и продукцией — с помощью отношения 

    RP ( REP#, PROD* ) 
    PRIMARY KEY { REP#, PROD# ) 

    Оба отношения являются связями типа многие-ко-многим, 

    328	Часть III. Проектирование базы данных 

    Это упражнение иллюстрирует тот факт, что порядок нормализации адекватно 
представляет некоторые семантические аспекты данной проблемы (в основном 
зависимости, которые подразумеваются потенциальными ключами, где под 
зависимостями имеются в виду функциональные и многозначные зависимости, а 
также зависимости соединения). Но явное указание дополнительных зависимостей 
может также потребоваться по некоторым другим причинам, а отдельные 
особенности могут быть и вовсе не представлены на основе таких зависимостей. 
Это упражнение также демонстрирует, что не всегда желательно "полностью" 
нормализовать отношение (отношение APR находится в НФБК, но не в 4НФ). 
    11.3. Все вносимые изменения достаточно просты — стоит лишь заменить 
упоминания функциональных зависимостей и НФБК понятиями многозначной 
зависимости и 4НФ. Тогда алгоритм декомпозиции будет следующим: 0.  Зададим 
отношение R в качестве начального значения для декомпозиции D. 
    1.  Для каждого отношения Т (которое не находится в 4НФ) из D выполним 
действия, перечисленные в пунктах 2 и 3. 
    2.  Пусть зависимость X -» К является многозначной для отношения Т, 
которое не удовлетворяет требованиям 4НФ. 
    3.  Заменим отношение Т в D двумя его проекциями, а именно: одной по 
атрибутам X и Y, а другой — по всем атрибутам, за исключением У. 
    11.4. Это пример "циклического ограничения", которому соответствует 
приведенная ниже реляционная структура: 

    REPS	(  REP#,   ...   ) 
    PRIMARY KEY ( REP# ) 
    AREAS   ( AREA*, . . . ) 
    PRIMARY KEY ( AREA* ) 
    PRODUCTS; REP#, ... ) 
    PRIMARY KEY ( PROD# ) 
    RA     ( REP#, AREA* ) 
    PRIMARY KEY ( REP#, AREA# ) 
    RP     ( REP#, PROD# ) 
    PRIMARY KEY   (  REP#,   PRODtt   ) 
    AP        ( AREA*, PROD# ) 
    PRIMARY KEY ( AREAtt, PROD# ) 

    Также пользователю следует указать, что соединение отношений RA, RP и АР 
не содержит "ловушки соединения". 

    330 Часть III. Проектирование базы данных 

