    ЧАСТЬ III 

    Проектирование базы данных 

    О этой части речь пойдет о проектировании базы данных, точнее, о 
проектировании реляционной базы данных. В общем проблема формулируется 
следующим образом: как в некоторой базе данных для заданного набора данных 
выбрать подходящую логическую структуру? Иначе говоря, нужно решить вопрос, 
какие базовые отношения и с какими атрибутами следует задать. Большое 
практическое значение решения этой проблемы очевидно. 
    Приступая к подробному изложению этой темы, отметим следующие особенности. 
    •   Прежде всего следует заметить, что речь здесь пойдет о логическом, а 
не физическом макете. Это вовсе не значит, что физический макет не имеет 
большого значения, наоборот его значение очень велико. Однако, несмотря на 
это, нужно сделать следующие оговорки. 
    • Физический макет может рассматриваться как отдельная сопутствующая 
часть. Иначе говоря, для "правильного" составления макета базы данных следует 
прежде всего создать логический (т.е. реляционный) макет, а затем в виде 
отдельного шага отобразить этот логический макет на некоторые физические 
структуры, поддерживаемые СУБД. 
    • Физический макет по определению является специфическим для данной СУБД, 
однако его обсуждение выходит за рамки этой книги. Логический макет, наоборот, 
совершенно независим от СУБД, и для его реализации могут быть использованы 
некоторые строгие теоретические принципы. Именно эти принципы и будут описаны 
в данной книге. 
    К сожалению, на практике часто случается так, что реализация макета на 
физическом уровне может оказывать существенное обратное влияние на логический 
макет. Иначе говоря, в таком случае для достижения компромисса следует 
выполнить несколько циклов проектирования "логический макет — физический 
макет". Тем не менее, изложение материала в этой части ведется исходя из 
необходимости создания логического макета без учета особенностей физической 
организации, т.е. без учета требований к высокой производительности. Таким 
образом, основная цель этой части книги — "первоочередное создание логического макета". 

    9 Введение в системы баз данных 

    •   Хотя, как уже отмечалось ранее, речь в основном пойдет о реляционном 
макете, представленные здесь идеи также в равной степени относятся и к 
нереляционным базам данных. Иначе говоря, при создании макета данных в 
нереляционной системе следует прежде всего создать реляционный макет, а затем 
на отдельном следующем этапе отобразить этот реляционный макет на любые 
нереляционные структуры (например, иерархии), поддерживаемые в СУБД. 
    •   После всего сказанного следует подчеркнуть, что проектирование базы 
данных скорее искусство, чем просто наука. Конечно, существуют некоторые 
научные принципы составления таких макетов, и они будут изложены в следующих 
трех главах. Однако при проектировании базы данных возникает множество других 
проблем, которые не всегда можно охватить этими принципами. В результате 
теоретики и практики в области создания баз данных разработали большое число 
методологий проектирования. Среди них есть как достаточно точные и строгие, 
так и не очень, однако все они специализированные и предназначены для решения 
именно той проблемы, которая считалась неразрешимой к моменту создания данной 
конкретной методики. Иными словами, они были задуманы для поиска такого 
логического макета, который был бы, бесспорно, лучшим в данной ситуации. 
Поскольку все эти методологии являются в большей или меньшей степени 
специализированными, существует мало объективных критериев для предпочтения 
одной из них. Все же, несмо тря на это, в главе 12 будет описан один широко 
известный подход, менее специализированный, чем другие. 
    •  Следует также отметить некоторые допущения, используемые в дальнейшем изложении. 
    • Проектирование базы данных — это не единственное условие получения 
правильной организации структуры данных, помимо этого ключевым условием 
является также целостность данных. 
    • Далее в большинстве случаев макет рассматривается независимо от 
приложения. Иначе говоря, интерес представляют сами данные, а не то, как они 
используются. Независимость от приложения желательна потому, что обычно в 
момент проектирования базы данных не известны все возможные способы 
использования данных. Таким образом, необходимо, чтобы макет был стабильным, 
т.е. оставался работоспособным даже при возникновении в приложении новых (т.е. 
неизвестных на момент создания исходного макета) требований к данным. Следуя 
этим допущениям (и используя терминологию предыдущих глав), нужно создать 
концептуальную схему, т.е. абстрактный логический макет, не зависящий от 
аппаратного обеспечения, операционной системы, СУБД, языка программирования, 
пользователя и т.д. В частности, как уже указывалось ранее, не будет 
проявляться никакого интереса к поиску компромиссных решений для достижения 
повышенной производительности. 
    •   Как отмечалось выше, задача проектирования базы данных заключается в 
том, чтобы решить, какие базовые отношения и с какими атрибутами следует 
использовать. Фактически для этого также необходимо выяснить, какие домены 
следует использовать. К моменту создания книги этой теме было посвящено совсем 
немного публикаций, поэтому описание данного вопроса будет очень кратким. 
    В главе 9 описаны некоторые теоретические основы, а в главах 10, 11 — 
основные идеи дальнейшей нормализации, которые позволяют придать смысл 
неформальным утверждениям о преимуществах того или иного макета. Затем в главе 
12 приведены концепции модели объект/отношение и показано, как эти концепции 
можно использовать для построения макета "сверху вниз" (начиная с реальных 
объектов и заканчивая формальным макетом базы данных). 

    Глава 9 

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

    9.1. Введение 

    В этой главе представлена концепция функциональной зависимости (functional 
dependency — FD), которая если "не совсем фундаментальна, то очень близка к 
таковой". Эта концепция лежит в основе обсуждаемых в следующих главах тем, 
включая, в частности, теорию проектирования базы данных, описанную в главе 10. 
    По сути, функциональная зависимость (далее для ее обозначения часто будет 
использоваться аббревиатура ФЗ) является связью типа многие-к-одному между 
множествами атрибутов внутри данного отношения. Например, для отношения 
поставок SP существует функциональная зависимость между множеством атрибутов 
{S#, P#} и {QTY}, т.е. многим значениям пары атрибутов S#-P# соответствует 
одно значение атрибута QTY (для проверки этого утверждения можете обратиться к 
рис. 3.8). 
    В этой главе концепция функциональной зависимости определяется более 
точно, с разделением функциональных зависимостей на выполняемые в некоторых 
частных случаях и выполняемые всегда. Как уже говорилось выше, ФЗ обеспечивает 
основу для научного подхода к решению нескольких практических задач, поскольку 
обладает богатым набором интересных формальных свойств, позволяющих формально 
и строго решить многие проблемы. Ниже будут подробно описаны некоторые из этих 
формальных свойств и даны объяснения по поводу их практического применения. В 
конце главы представлено краткое резюме. 
    Замечание. При первом чтении этой главы многие разделы можно пропустить, 
поскольку большая часть материала, необходимого для понимания изложенного в 
следующих главах, содержится в первых нескольких разделах главы. Поэтому все 
остальные разделы можно лишь просмотреть, а затем вновь вернуться к ним, 
ознакомившись со всеми тремя главами этой части. 

    9.2. Основные определения 

    Для демонстрации основных идей данного раздела используется несколько 
измененная версия отношения поставок, которое в дополнение к обычным атрибутам 
S#, P# и QTY будет содержать также атрибут CITY, представляющий город 
соответствующего поставщика. Во избежание путаницы далее это измененное 
отношение будет называться SCP. Оно в виде таблицы представлено на рис. 9.1. 

    SCP 

    s#	CITY	P#	QTY 

    SI	London	PI	100 
    SI	London	P2	100 
    S2	Paris	PI	200 
    S2	Paris	P2	200 
    S3	Paris	P2	300 
    S4	London	P2	400 
    S4	London	P4	400 
    S4	London	P5	400 
    
    Рис. 9.1. Таблица отношения SCP 
    
    Глава 9. Функциональные зависимости 259 

    Следует четко различать: а) значение этого отношения (т.е. значение 
переменной отношения) в определенный момент времени; б) набор всех возможных 
значений, которые данное отношение (переменная) может принимать в различные 
моменты времени (подробнее это описано в главе 4). Сначала дадим определение 
концепции функциональной зависимости для пункта (а), а затем для пункта (б). 
    •  Пусть R — это отношение, а X и Y— произвольные подмножества множества 
атрибутов отношения R. Тогда У функционально зависимо от X, что в 
символическом виде записывается как 
    X -> Y 
    (и читается либо как "^функционально определяет У", либо как "X стрелка 
У"), тогда и только тогда, когда каждое значение множества X отношения R 
связано в точности с одним значением множества Y отношения R. Иначе говоря, 
если два кортежа отношения R совпадают по значению X, они также совпадают и по 
значению Y. Например, таблица отношения SCP (см. рис. 9.1) удовлетворяет 
приведенной ниже функциональной зависимости, поскольку все кортежи отношения 
SCP с одинаковым значением атрибута S# имеют одинаковое значение атрибута CITY. 

    {   S#   }  ->  {  CITY } 

    На самом деле это отношение удовлетворяет нескольким функциональным зависимостям: 

    { s#, Р# } -> { OTY } { s#, Р# } -» { CITY } 
    {	S#, P# } -> {	CITY, QTY } 
    {	S#, P# } ~» {	S# } 
    {	S#, P# } -> {	Sf, P#, CITY, QTY } 
    {	S# } -> { QTY	} 
    {	CTY } -> { S#	} 

    (Упражнение. Проверьте правильность этого утверждения.) 
    Левая и правая стороны символической записи функциональной зависимости 
иногда называются детерминантом и зависимой частью соответственно. Как 
говорится в определении, детерминант и зависимая часть являются множествами 
атрибутов. Когда множество содержит только один атрибут, он называется 
одноэлементным множеством, скобки опускаются и символическая запись принимает вид 

    S# -> CITY 

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

    S# -» CITY 

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

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

    •   Пусть R является переменной отношения, аХи Y— произвольными 
подмножествами множества атрибутов отношения R. Тогда Y функционально зависимо 
от X, что в символическом виде записывается как 
    X ->  Y 
    (и читается либо как "X функционально определяет У", либо как "X стрелка 
У"), тогда и только тогда, когда для любого допустимого значения отношения R 
каждое значение X связано в точности с одним значением У. 
    Иначе говоря, для любого допустимого значения отношения R, когда бы два 
кортежа отношения R ни совпадали по значению X, они также совпадают и по 
значению У. Следовательно, далее термин "функциональная зависимость" будет 
использоваться в последнем безотносительном ко времени смысле (за исключением 
особо оговоренных случаев). 
    Ниже перечислено несколько безотносительных ко времени функциональных 
зависимостей для переменной отношения SCP: 

    {	S#, Р# } -» QTY 
    {	S#, Р# } -> CITY 
    {	S#, Р# } -> { CITY, QTY } {	S#, P# } -> S# 
    {	S#, P# } -> { S#, P#, CITY, QTY } 
    {	S# } -> CITY 

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

    S# -> QTY QTY -> S# 

    Иначе говоря, например, такое утверждение, как "число деталей для каждой 
поставки данного поставщика одинаково", истинно для значений таблицы на рис. 
9.1, но не верно для всех возможных допустимых значений отношения SCP. 
    Следует отметить, что если X является потенциальным ключом отношения R, 
например X является первичным ключом, то все атрибуты У отношения R должны 
быть обязательно функционально зависимы от X (это следует из определения 
потенциального ключа). В обычном отношении деталей Р, например, необходимо, 
чтобы выполнялась зависимость 

    Р# -> ( Р#, PNAME, COLOR, WEIGHT, CITY } 

    Фактически, если отношение R удовлетворяет функциональной зависимости А -» 
В и А не является потенциальным ключом, то R будет характеризоваться некоторой 
избыточностью. Например, в случае отношения SCP сведения о том, что каждый 
данный поставщик находится в данном городе, будут повторяться много раз (это 
хорошо видно на рис. 9.1). Более подробно этот вопрос обсуждается в главе 10. 
    Теперь, даже если ограничиться рассмотрением функциональных зависимостей, 
которые выполняются "всегда", множество функциональных зависимостей, 
выполняющихся для всех допустимых значений данного отношения может быть все 
еще очень большим, как показано на примере отношения SCP. (Упражнение. 
Попробуйте записать полное множество функциональных зависимостей для отношения 
SCP.) Большая часть оставшегося в этой главе материала посвящается методам 
сокращения этого обширного множества ФЗ до компактных размеров. 
    Почему эта цель столь важна? Одна из причин состоит в том, что, как уже 
отмечалось, функциональные зависимости являются ограничениями целостности, 
поэтому при каждом обновлении данных в СУБД все они должны быть проверены. 
Следовательно, для заданного множества функциональных зависимостей S 
желательно найти такое множество Т, которое (в идеальной ситуации) было бы 
гораздо меньшего раз

    Глава 9. Функциональные зависимости	261 

    мера, чем множество 5, причем каждая ФЗ множества S могла бы быть заменена 
функциональной зависимостью множества 7". Если бы такое множество Т было 
найдено, то в СУБД достаточно было бы использовать ФЗ из множества Т, а ФЗ из 
множества 5 подразумевались бы автоматически. Поэтому задача поиска 
подходящего множества Т представляет большой практический интерес. 

    9.3. Тривиальные и нетривиальные зависимости 

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

    {   S#,   Р#   }   -> S# 

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

    9.4. Замыкание множества зависимостей 

    Как уже упоминалось выше, некоторые ФЗ могут означать другие ФЗ. Например, 
приведенная ниже зависимость 

    {  S#,   Р#  }  ->  {  CITY,   CTY } 

    подразумевает следующие ФЗ: 

    {   S#,   Р#   }  -» CITY {   S#,   P#   }   -> QTY 

    В качестве более сложного примера можно привести отношение R с тремя 
атрибутами А, В и С, для которых выполняются функциональные зависимости А —> В 
и В —> С. В таком случае нетрудно заметить, что также выполняется зависимость 
А —> С, которая называется транзитивной функциональной зависимостью, т.е. С 
транзитивно через В зависит от А. 
    Множество всех ФЗ, которые задаются данным множеством функциональных 
зависимостей S, называется замыканием S и обозначается символом S'. Из 
сказанного выше становится ясно, что для выполнения сформулированной задачи 
следует найти способ вычисления S' на основе S. Первой попыткой решить эту 
проблему была статья Армстронга (Armstrong) [9.1], в которой представлен набор 
правил вывода функциональных зависимостей на основе заданных (эти правила 
также называются аксиомами Армстронга). Правила могут формулироваться разными 
способами, а самый простой из них приводится ниже. 
    •   Правила вывода Армстронга. Пусть в перечисленных ниже правилах А, В к 
С— произвольные подмножества множества атрибутов заданного отношения R, a 
символическая запись АВ означает объединение А и В. 
    1.	Рефлексивность: если В является подмножеством А, то А —> В. 
    2.	Дополнение: если А —> В, то АС —> ВС. 
    3.	Транзитивность: если А —> В и В —> С, тоЛ->С. 
    Каждое из этих правил может быть непосредственно доказано на основе 
определения функциональной зависимости (первое из них — это всего лишь определение 

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

    тривиальной зависимости). Более того, эти правила являются полными в том 
смысле, что для заданного множества функциональных зависимостей S минимальный 
набор ФЗ, которые подразумевают все зависимости S, может быть выведен из S на 
основе этих правил. Они также являются исчерпывающими, поскольку никакие 
дополнительные ФЗ не могут быть выведены (т.е. ФЗ, которые не подразумеваются 
зависимостями множества 5). Иначе говоря, эти правила могут быть использованы 
для получения замыкания S . 
    Из трех описанных выше правил для упрощения задачи практического 
вычисления замыкания S можно вывести несколько других правил. (Пусть D — это 
другое произвольное подмножество множества атрибутов R.) 
    4.	Самоопределение: А -> А. 
    5.	Декомпозиция: если А -» ВС, то А -» В и А -» С. 
    6.	Объединение: если А —> В иА -^ С, то А —> ВС. 
    1.	Композиция: если А —> В и С —» D, то АС —> BD. 
    Кроме того, Дарвен (Darwen) в своей работе [9.6] доказал следующее 
правило, которое назвал теоремой всеобщего объединения: 
    8.   Если А -> В и С -» D, то А и (С- В) —> BD (где символ "и" обозначает 
объединение множеств, а символ "-" — их разность). 
    Название "теорема всеобщего объединения" указывает на то, что некоторые 
перечисленные ранее правила могут быть выведены как частные случаи этой 
теоремы [9.6]. 
    Пример. Пусть дано некоторое отношение R с атрибутами А, В, С, D, E, F и 
следующими ФЗ: 

    А -> ВС 
    В -» Е CD -> EF 

    Обратите внимание, что способ записи несколько изменился (без ущерба для 
смысла): например, символы ВС означают множество, состоящее из атрибутов В и 
С, хотя ранее эти символы означали объединение В и С, где В и С были 
множествами атрибутов. 
    Замечание. Если необходимо, этому примеру можно придать более конкретный 
смысл, а именно: А — номер сотрудника, В — номер отдела, С— номер руководителя 
(начальника) данного сотрудника, D — номер проекта, возглавляемого данным 
руководителем (уникальный для каждого отдельно взятого руководителя), Е — 
название отдела, F—доля времени, уделяемая данным руководителем заданному проекту. 
    Теперь можно показать, что зависимость AD —» F выполняется для отношения R 
и таким образом принадлежит замыканию данного множества ФЗ. 

    1.	А -> ВС	( дано } 
    2.	А —» С	( из 1 согласно декомпозиции ) 
    3.	AD —> CD	( из 2 согласно дополнению ) 
    4.	CD -» EF	( дано ) 
    5.	AD —> EF	( из 3 и 4 согласно транзитивности ) 
    6.	AD -> F	( из 5 согласно декомпозиции ) 


    9.5. Замыкание множества атрибутов 

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

    Глава 9. Функциональные зависимости	263 

    подмножества, но не обязательно собственного подмножества, по крайней мере 
один потенциальный ключ. (Определение термина "суперключ", таким образом, 
может быть выведено из определения понятия "потенциальный ключ".) Таким 
образом, отсюда следует, что суперключи для данного отношения R — это такие 
подмножества К множества атрибутов отношения R, что функциональная зависимость 
к -> А истинна для каждого атрибута А отношения R. 
    Теперь предположим, что известны некоторые ФЗ, выполняющиеся для данного 
отношения, и требуется определить потенциальные ключи этого отношения. По 
определению потенциальными ключами называются неприводимые суперключи (т.е. 
суперключ содержит потенциальный ключ). Таким образом, выясняя, является ли 
данное множество атрибутов К суперключом, можно в значительной степени 
продвинуться к выяснению вопроса, является ли К потенциальным ключом. 
    Для этого нужно определить, будет ли набор атрибутов отношения R 
множеством всех атрибутов, функционально зависящих от К. Таким образом, для 
заданного множества зависимостей S, которые выполняются для отношения R, 
необходимо найти способ определения множества всех атрибутов отношения R, 
которые функционально зависимы от К, т.е. так называемое замыкание К множества 
К для S. Простой алгоритм вычисления этого замыкания показан на рис. 9.2. Ниже 
даны пояснения. Упражнение. Докажите, что этот алгоритм правильный. 

    CLOSURE [К, S] := К ; 
    do "forever" ; /* выполняется всегда */ 
    for each ED X -> Y in S   /* для каждой ФЗ X -> У в S */ do ; 
    if X is subset of CLOSURE[K, S]  /* если является подмножеством */ 
    then CLOSURE [К, S] := CLOSURE [К, S] UNION Y ; end ; 
    if CLOSURE[K, S] did not change on this iteration then leave loop ; /* 
если на этой итерации изменений не произошло, 
    вычисления завершаются */ end ; 

    Рис. 9.2. Вычисление замыкания (С множества К для S 

    Пример. Предположим, что дано отношение R с атрибутами А, В, С, D, Е и F и 
следующими ФЗ: 

    А -> ВС Е -» CF В -> Е 
    CD -> EF 

    Теперь вычислим замыкание {А, В}+ множества атрибутов {А, В} для данного 
множества ФЗ. 
    1.   Присвоим замыканию CLOSURE[A", 5] начальное значение — множество {А, В}. 
    2.  Теперь выполним внутренний цикл четыре раза, по одному разу для каждой 
ФЗ. На первой итерации (для зависимости А -» ВС) будет обнаружено, что левая 
часть действительно является подмножеством замыкания CLOSURE[A", S]; таким 
образом, к результату можно добавить атрибуты В и С. Замыкание CLOSURE[A", 5] 
теперь представляет собой множество {А, В, С}. 
    3.  На второй итерации (для зависимости ?-»CF) можно обнаружить, что левая 
часть не является подмножеством полученного до этого момента результата, 
который, таким образом, остается неизменным. 

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

    4.  На третьей итерации (для зависимости В —> Е) множество ? будет 
добавлено к замыканию CLOSURE[/v, S\, которое теперь будет иметь вид {А, В, С, Е}. 
    5.  На четвертой итерации (для зависимости CD —> EF) замыкание CLOSURE[/C, 
5] останется неизменным. 
    6.  Теперь внутренний цикл будет выполнен еще четыре раза. На первой 
итерации результат останется прежним, на второй он будет расширен до {А, В, С, 
Е, F}, а на третьей и четвертой — снова не изменится. 
    7.  Наконец, после еще одного четырехкратного прохождения цикла замыкание 
CLOSUREfA", S] остается неизменным и весь процесс в целом завершается с 
результатом {А, В, С, Е, F}+={A, В, С, Е, F}. Обратите внимание, что {А, В} не 
является суперключом (и, следовательно, потенциальным ключом). 
    Из сказанного выше можно сделать очень важное заключение: для заданного 
множества функциональных зависимостей S можно легко указать, будет ли заданная 
зависимость X -> Y следовать из S, поскольку это возможно тогда и только 
тогда, когда Y является подмножеством замыкания X* множества X для заданного 
множества 5. Иначе говоря, таким образом представлен простой способ 
определения, будет ли данная функциональная зависимостьX —> /включена в 
замыкание 5* множества S. 

    9.6. Неприводимое множество зависимостей 

    Пусть S1 и 52 являются двумя множествами ФЗ. Если любая ФЗ, которая 
является зависимостью множества S1, также является зависимостью множества 52, 
т.е. если 5/+ является подмножеством 52+, то 52 называется покрытием для 5/. 
(Некоторые авторы используют термин "покрытие" для обозначения эквивалентного 
множества.) Это значит, что если накладываемые в СУБД ограничения представлены 
зависимостями множества 52, то в этой СУБД также наложены ограничения на 
основе зависимостей множества 5/. 
    Далее, если 52 является покрытием для 5/, а 5/ — покрытием для 52, т.е. 
если S1+-S2+, то 57 и 52 эквивалентны. Ясно, что если 5/ и 52 эквивалентны и 
наложенные в СУБД ограничения представлены зависимостями множества 52, то эти 
ограничения также могут быть представлены зависимостями множества 5/, верно 
также и обратное утверждение. 
    Множество ФЗ называется неприводимым тогда и только тогда, когда 
выполняются перечисленные ниже свойства. 
    1. Правая часть (зависимая часть) каждой ФЗ множества 5 содержит только 
один атрибут (т.е. является одноэлементным множеством). 
    2.  Левая часть (детерминант) каждой ФЗ множества 5 является неприводимой, 
т.е. ни один атрибут не может быть опущен из детерминанта без изменения 
замыкания 5* (без конвертирования множества 5 в некоторое множество, не 
эквивалентное множеству 5). В таком случае ФЗ является неприводимой слева. 
    3.   Ни одна функциональная зависимость в 5 не может быть опущена из 5 без 
изменения замыкания 5* (т.е. без конвертирования множества 5 в некоторое 
множество, не эквивалентное множеству 5). 
    В качестве примера рассмотрим уже знакомое отношение деталей Р с 
перечисленными ФЗ: 

    Р# ->  PNAME Р# ->• COLOR Р# -> WEIGHT Р# -> CITY 

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

    Глава 9. Функциональные зависимости	265 

    1. Р# -» ( PNAME, COLOR ) :  Правая часть не является Р# —> 
WEIGHT	одноэлементным множеством Р# -> CITY 
    2. ( Р#, PNAME ) -> COLOR :  Эту зависимость можно 
    Р# -» PNAME	упростить устранением PNAME в левой Р# -» WEIGHT           
части без изменения замыкания Р# -> CITY 
    3. Р# -> Р#	:  Эту зависимость можно 
    Р# —> PNAME	упростить без изменения замыкания Р# -> COLOR Р# -> WEIGHT Р# 
-> CITY 

    Теперь можно сделать утверждение, что для каждого множества ФЗ существует, 
по крайней мере, одно эквивалентное множество, которое является неприводимым. 
Это достаточно легко продемонстрировать на следующем примере. Пусть дано 
исходное множество зависимостей S, тогда благодаря правилу декомпозиции можно 
без утраты общности предположить, что каждая ФЗ в множестве S имеет 
одноэлементную правую часть. Далее для каждой зависимости / этого множества S 
следует проверить каждый атрибут А в левой части/ Если множество S и множество 
зависимостей, полученное с помощью устранения атрибута А в левой части/ 
эквивалентны, то этот атрибут следует удалить. Затем для каждой оставшейся в 
множестве S зависимости/ если S и S -/эквивалентны, следует удалить/из 
множества S. Получившееся в результате таких действий множество S является 
неприводимым и эквивалентно исходному множеству S. 
    Пример. Пусть дано отношение R с атрибутами А, В, С, D и следующими ФЗ: 

    А -> ВС В ->  С Л -> В АВ ->  С АС ->  D 

    Теперь попробуем найти неприводимое множество ФЗ, эквивалентное данному множеству. 
    1. Прежде всего следует переписать ФЗ таким образом, чтобы каждая из них 
имела одноэлементную правую часть: 

    А -> в 
    А -> С В -» С Л -» В АВ -> С 
    АС -» D 

    Нетрудно заметить, что зависимость А —> В записана дважды, так что одну из 
них можно удалить. 

    2.  Затем атрибут С может быть опущен в левой части зависимости АС—> Д 
поскольку дана зависимость А —> С и с помощью дополнения можно получить А —> 
АС, а также поскольку дана зависимость АС —> D и с помощью транзитивности 
можно получить А —> D\ таким образом, атрибут С в левой части зависимости АС 
—> D является избыточным. 
    3.  Далее можно заметить, что зависимость АВ —> С может быть исключена, 
поскольку дана зависимость А -> С и с помощью дополнения можно получить АВ -> 
СВ, а с помощью декомпозиции —АВ —> С. 
    4.  Наконец, зависимость А -» С подразумевается зависимостями А -> В и В 
-> С, так что она также может быть устранена. В результате получится 
неприводимое множество зависимостей: 

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

    А -* В В -> С 
    Л -> D 
    Множество зависимостей /, которое неприводимо и эквивалентно некоторому 
другому множеству зависимостей S, называется неприводимым покрытием множества 
S. Таким образом, с тем же успехом в системе вместо исходного множества 
зависимостей S может быть использовано его неприводимое покрытие /. Однако 
следует отметить, что для заданного множества ФЗ не всегда существует 
уникальное неприводимое покрытие (это упоминается ниже в упражнениях). 

    9.7. Резюме 

    Функциональная зависимость — это отношение типа многие-к-одному между 
двумя множествами атрибутов определенного отношения. Для данного отношения R 
зависимость А —> В (где А и В являются подмножествами множества атрибутов 
отношения К) выполняется для отношения R тогда и только тогда, когда любые два 
кортежа отношения R с одинаковыми значениями А имеют одинаковые значения В. 
Наибольший интерес в данном случае представляют ФЗ, которые выполняются 
"всегда", т.е. для всех возможных значений данного отношения (при этом 
"отношение" в данном случае скорее значит "переменная отношения"). Каждое 
отношение обязательно удовлетворяет некоторой тривиальной функциональной 
зависимости; а функциональная зависимость тривиальна тогда и только тогда, 
когда правая часть (зависимая часть) является подмножеством левой части (детерминанта). 
    Некоторые ФЗ подразумевают другие зависимости. Для данного множества 
зависимостей S его замыканием 5"* называется множество всех ФЗ, 
подразумеваемых зависимостями множества S. Множество S обязательно является 
подмножеством собственного замыкания 5*. Правила Армстронга обеспечивают 
исчерпывающую и полную основу для вычисления 5* и S, хотя несколько 
дополнительных правил вывода (легко выводимых из правил Армстронга) позволяют 
упростить практические вычисления. 
    Для данного подмножества А множества атрибутов отношения R и множества 
зависимостей S, которые выполняются для отношения /?, замыканием А+ множества 
А для S называется такое множество всех атрибутов В отношения R, что 
зависимость А -> В является членом замыкания 5*". Если замыкание А+ состоит из 
всех атрибутов отношения R, то А является суперключом отношения R (а 
неприводимый суперключ является потенциальным ключом). В этой главе было дано 
описание простого алгоритма для получения замыкания А+ на основе А и S и, 
следовательно, для определения, является ли данная зависимость A"—» Y членом 
замыкания S (X—> Y является членом замыкания S тогда и только тогда, когда Y 
является подмножеством замыкания Jf). 
    Два множества зависимостей S1 и S2 эквивалентны тогда и только тогда, 
когда они являются покрытиями друг для друга, т.е. S1+-S2+. Каждое множество 
ФЗ эквивалентно по крайней мере одному неприводимому множеству. Множество 
функциональных зависимостей является неприводимым, если каждая ФЗ этого 
множества имеет одноэлементную правую часть, ни одна ФЗ множества не может 
быть устранена без изменения замыкания этого множества, ни один атрибут не 
может быть устранен из левой части любой ФЗ данного множества без изменения 
замыкания множества. 
    В заключение следует отметить, что многие высказанные выше соображения 
можно расширить для применения ограничений целостности вообще, а не только 
функциональных зависимостей. Например, верно, что: некоторые ограничения 
целостности являются тривиальными; некоторые ограничения целостности 
подразумевают другие; набор всех ограничений, подразумеваемых заданным 
множеством, может рассматриваться как замыкание этого множества; выяснение 
вопроса, будет ли некое ограничение находиться в некотором замыкании (т.е. 
будет ли заданное ограничение 

    Глава 9. Функциональные зависимости	267 

    подразумеваться некоторыми данными ограничениями), является очень 
интересной практической задачей; также интересной практической задачей 
является поиск неприводимого покрытия для некоторых данных ограничений. 
Благодаря наличию исчерпывающего и полного множества правил вывода 
функциональных зависимостей работа с ними более удобна, чем работа с 
ограничениями целостности вообще. В списках рекомендуемой литературы в конце 
этой и следующих глав даны ссылки на работы, описывающие несколько других 
типов ограничений (MVD, JD и IND), для которых существуют подобные наборы 
правил вывода. В данной книге, однако, другие типы ограничений не 
рассматриваются так подробно и полно, как функциональные зависимости. 

    Упражнения 

    9.1. Пусть R является отношением степени п. Каково максимальное количество 
функциональных зависимостей (как тривиальных, так и нетривиальных), которые 
выполняются для отношения R? 
    9.2. Как объяснить, что правила Армстронга являются исчерпывающими и полными? 
    9.3. Докажите правила рефлексивности, дополнения и транзитивности только 
на основе определения функциональной зависимости. 
    9.4. Докажите, что три предыдущих правила подразумевают правила 
самоопределения, декомпозиции, объединения и композиции. 
    9.5. Докажите "теорему всеобщего объединения", предложенную Дарвеном. 
Какие правила из перечисленных выше нужно использовать для этого? Какие 
правила можно вывести в виде особых случаев этой теоремы? 
    9.6. Дайте определение для: а) замыкания набора ФЗ; б) замыкания множества 
атрибутов для заданного множества ФЗ. 
    9.7. Перечислите множество всех ФЗ, которые всегда выполняются для 
отношения поставок SP. 
    9.8. Ниже приведено множество ФЗ для отношения R{A, В, С, D, E, F, G}: 
    А -> В ВС -> DE AEF -> G 
    Вычислите замыкание {А, С}+ для данного множества. Подразумевается ли 
зависимость ACF —> DG этим множеством? 
    9.9. Что означает понятие эквивалентности двух множеств функциональных 
зависимостей S1 и 52? 
    9.10. Что означает понятие неприводимости множества ФЗ? 
    9.11. Определите, эквивалентны ли два приведенных ниже множества ФЗ для 
отношения R{A,B, С, D, E}. 
    1.    А -> В	АВ -> С               D -> AC                 D -> Е 
    2.    А -> ВС	D -» АЕ 
    9.12. Найдите неприводимое покрытие приведенного ниже множества ФЗ для 
отношения R{A, В, С, D, E, F}. 
    АВ -> С С -» А ВС -> D ACD -> В BE -> С 

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

    СЕ -CF • D -. 
    » FA » BD EF 
    9.13. Для отношения TIMETABLE определены перечисленные ниже атрибуты. 
D	День недели (1-5) Р              Период времени в течение дня (1-8) С        
      Номер класса Т              Имя учителя L              Название урока 
    Кортеж {D:d, P:p, С:с, T:t, L:l] является элементом этого отношения тогда 
и только тогда, когда урок / проводится учителем t в классе с в момент времени 
{D:d,P:p}. Предположим, что длительность всех уроков равна одному периоду 
времени, кроме того, каждый урок имеет название, уникальное по отношению ко 
всем урокам этой недели. Какие ФЗ выполняются для этого отношения? Какие 
потенциальные ключи существуют для этого отношения? 
    9.14. Пусть задано отношение NADDR со следующими атрибутами: NAME 
(уникальное имя), STREET (улица), CITY (город), STATE (штат) и ZIP (индекс), 
где каждому индексу соответствует только один город и штат, а каждой улице, 
городу и штату соответствует только один индекс. Найдите неприводимое 
множество ФЗ для этого отношения. Какие потенциальные ключи существуют для 
этого отношения? 
    9.15. Пусть дано отношение R с атрибутами А, В, С, D, E, F, G, Н, /, J и 
приведенным ниже множеством ФЗ. 

    ABD -> Е 
    АВ -» G В -> F С -> J CJ-» I G -> Н 

    Является ли это множество неприводимым? Какие потенциальные ключи 
существуют для этого отношения? 

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

    9.1. Armstrong W. W. Dependency Structures of Data Base Relationships // 
Proc. IFIP Congress. — Stockholm, Sweden, 1974. 
    Впервые изложена формальная теория ФЗ (т.е. эта работа является 
первоисточником "аксиом Армстронга")- Также приведена точная характеристика 
потенциальных ключей. 
    9.2. Casanova M.A., Fagin R., Papadimitriou C.H. Inclusion Dependencies 
and Their Interaction with Functional Dependencies // Proc. 1st ACM 
SIGACT-SIGMOD Symposium on Principles of Database Systems. — Los Angeles, 
Calif, 1982. 
    Зависимости включения (inclusion dependencies — INDs) являются обобщением 
концепции ограничений целостности. Например, зависимость включения типа 
    SP.S# ——» S.S# 
    (символическая запись содержит несколько более длинную стрелку, 
подчеркивающую, что это зависимость другого типа) означает, что множество 
значений атрибута SP.S# должно быть подмножеством (не обязательно собст

    Глава 9. Функциональные зависимости 269 

    венным подмножеством) множества значений атрибута S.S#. Это, конечно, 
частный случай ограничения целостности, а в общем случае для зависимости 
включения не существует никаких ограничений на то, что левая часть является 
внешним ключом, а правая — потенциальным. Замечание. Зависимости включения 
имеют некоторое сходство с ФЗ, поскольку оба этих типа зависимостей 
представляют отношения многие-к-одному. 
    Предложено исчерпывающее и полное множество правил вывода для зависимостей 
включения, которые могут быть (в несколько нестрогой форме) представлены в 
следующем виде: 
    1.    А——>• А 
    2.    ЕСЛИ АВ——> CD, ТО А——> С И В——> D. 
    3.   Если л—>вив—> Q то А—>с 
    9.3. Casey R.G., Delobel С. Decomposition of a Data Base and the Theory of 
Boolean Switching Functions // IBM J. R&D. — 1973. — 17, № 5. 
    В работе показано, что для данного отношения множество ФЗ (которые в этой 
статье называются функциональными связями) может быть представлено как "булева 
переключательная функция". Кроме того, отмечено, что эта функция в некотором 
смысле уникальна, поскольку исходные ФЗ могут быть заданы многими совершенно 
различными (но эквивалентными) способами, каждый из которых в общем приводит к 
возникновению существенно разных булевых функций, но все такие функции могут 
быть сведены к той же канонической форме с помощью законов булевой алгебры. 
Показано, что проблема "декомпозиции" исходного отношения логически 
эквивалентна хорошо известной в булевой алгебре проблеме поиска "покрывающего 
множества из простых импликантов" для булевой функции, соответствующей этому 
отношению вместе с его ФЗ. Следовательно, исходная проблема может быть 
переформулирована в эквивалентную проблему в булевой алгебре, а для ее решения 
могут применяться хорошо известные методы. 
    Эта одна из первых работ, посвященных изучению применения теории 
зависимостей для широкого круга других дисциплин. Этому также посвящена 
публикация [9.8] и несколько работ, упомянутых в списках литературы в 
следующих главах. 
    9.4. Codd E.F. Further Normalization of the Data Base Relational Model // 
Data Base Systems, Courant Computer Science Symposia Series 6. — Englewood 
Cliffs, N.J.: Prentice-Hall, 1972. 
    Впервые представлена концепция функциональной зависимости. Понятие 
"дальнейшая нормализация" ("Further Normalization"), приведенное в заголовке, 
относится к некоторому типу специализированного макета базы данных, 
обсуждаемого в главе 10 (цель этой главы — продемонстрировать возможности 
использования идей ФЗ для решения проблем проектирования базы данных). 
Действительно, функциональные зависимости представляют собой одну из первых 
попыток разрешения этой проблемы. Однако идея ФЗ с тех пор доказала свою 
полезность и для более широкого практического применения. 
    9.5. Codd E.F. Normalized Data Base Structure: A Brief Tutorial // Proc. 
1971 ACM SIGFIDET Workshop on Data Description, Access, and Control. — San 
Diego, Calif, 1971. 
    Вводное изложение идей, представленных в [9.4]. 
    9.6. Darwen H. The Role of Functional Dependence in Query Decomposition // 
C.J. Date and H. Darwen. Relational Database Writings 1989-1991.— Reading, 
Mass.: Addison-Wesley, 1992. 

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

    Представлен набор правил наследования для функциональных зависимостей, с 
помощью которых может быть выведена выполнимость ФЗ для данного произвольного 
отношения на основе выполнимости этих зависимостей в отношении (или 
отношениях), из которого выведено данное отношение. Выведенное таким образом 
множество ФЗ может использоваться для определения потенциальных ключей для 
некоторого выведенного отношения. В результате можно получить правила 
наследования для потенциальных ключей, кратко упомянутые в главе 6 как 
"наиболее желательные". В статье показано, как эти правила наследования для ФЗ 
и потенциальных ключей могут использоваться для значительного повышения 
производительности СУБД, ее функциональности и удобства пользования. 
    9.7. Darwen H. Observations of a Relational Bigot // Presentation to BCS 
Special Interest Group on Format Aspects of Computing Science. — London, UK, 1990. 
    9.8. Fagin R. Functional Dependencies in a Relational Database and 
Propositional Logic // IBM J.R&D. — 1977. — 21, № 6. 
    Показано, что "аксиомы Армстронга" [9.1] строго эквивалентны системе 
импликационных утверждений в логике высказываний. Иначе говоря, задается 
отображение между ФЗ и утверждениями в логике высказываний, а затем показано, 
что данная зависимость / является последовательностью заданного множества 
зависимостей S тогда и только тогда, когда высказывание, соответствующее f, 
является логическим следствием множества высказываний, соответствующих 
множеству S. 
    9.9. Lucchesi C.L., Osborn S.L. Candidate Keys for Relations // J. Сотр. 
and Sys. Sciences.— 1978.— 17, №2. 
    Представлен алгоритм поиска всех потенциальных ключей, а также 
функциональных зависимостей, выполняющихся для этого отношения. 
    Ответы к некоторым упражнениям 
    9.1. Функциональная зависимость— это утверждение типа А —» В, где А и В 
являются подмножествами множества атрибутов отношения R. Поскольку множество 
из п элементов образует 2" возможных подмножеств, aAuB содержат 2" возможных 
значений каждое, следовательно, число возможных ФЗ равно 2"". 
    9.5. 1. А -> В	(дано) 
    2. С -> D	(дано) 
    3. А —> В г\ С	(зависимость соединения, 1) 
    4. С - В -> С - В	(самоопределение) 
    5. Ли ( С - В ) -> ( В п С ) и ( С - В ) (композиция, 3, 4) 
    6. А и ( С - В ) —> С	(упрощение, 5) 
    7. Д и ( С - В ) -> D	(транзитивность, 6, 2) 
    8. Ди ( С - В ) -» В и D	(композиция, 1, 7) 
    Доказательство завершено. 
    Использованные для доказательства правила указаны в комментариях. Среди 
них есть правила, которые являются особыми случаями теоремы Дарвена: 
объединение, транзитивность, композиция и дополнение. Таким же особым случаем 
теоремы Дарвена является следующее полезное правило: 
    • Если А ->• В и АВ -» С, тогда А -> С. 

    Глава 9. Функциональные зависимости	271 

    9.7. Ниже приведен полный набор ФЗ, т.е. замыкание, отношения SP. 

    { S#,	P#,	QTY	}	-> {	S#, P#, QTY } 
    { S#,	P#,	QTY	}	-> {	S#, P# } 
    { S#,	P#,	QTY	}	-» {	Р#, QTY } 
    { S#,	P#,	QTY	}	-> {	S#, QTY } 
    { S#,	P#,	QTY	}	-> {	S# } 
    { S#,	P#,	GTY	}	-> {	P# } 
    { S#,	P#,	QTY	}	-> {	QTY } 
    { S#,	P#,	QTY	}	-> {	} 
    { S#,	P# } ->	{ S#, PI, QTY } 
    { S#,	P# } ->	{ S#, PI } 
    { S#,	P# } ->	{ P#, QTY } 
    { S#,	P# } ->	{ S#, QTY } 
    { S#,	P# } ->•	{ S# } 
    { S#,	P# } ->	{ P# } 
    
    { S#,	P# } ->	{ QTY } 
    { S#,	P# } ->	{ } 
    {	P#,	QTY }	-> {	P#, QTY } 
    {	P#,	QTY }	-> {	P# } 
    {	P#,	QTY }	-> {	QTY } 
    {	P#,	QTY }	-* {	} 
    {	S#,	QTY	}	->	{	S#, QTY } 
    {	S#,	QTY	}	->	{	S# } 
    {	S#,	QTY	}	->	{	QTY } 
    {	S#,	QTY	}	->•	{	} 
    { S# } -» { S# } { S# } -» { } 
    { P# } -> { Ptt } { P# ) -> { } 
    {  QTY#  }  ->  {  QTY#   } {  QTY#  }  ->  {   } 
    {   }  ->  {   } 
    9.8. {A, C}+ = {А, В, С, D, ?}. На вторую часть вопроса следует дать 
утвердительный ответ. 
    9.11. Они эквивалентны. Расположим ФЗ из первого множества в отдельных строках: 
    1. А -» в 
    2. лв -» с 
    3. D -> АС 
    4. D -> ? 

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

    Тогда третья строка может быть заменена следующей строкой: 
    3.0-»АиО->С 
    Затем с помощью первой строки можно придать второй строке такой вид: 
    2. А -» С 
    Но поскольку теперь о -> л и А -» с; тогда по транзитивности это 
подразумевает о -> с; а в результате для третьей строки можно получить 
следующее выражение: 
    3. D ->• А 
    Таким образом, первое множество ФЗ эквивалентно следующему неприводимому множеству: 
    А ->	В 
    А -»	С 
    D ->•	А 
    D ->	Е 
    Приведенное ниже второе множество ФЗ, очевидно, эквивалентно данному 
неприводимому множеству: 
    А -» ВС D -> АЕ 
    Таким образом, два этих множества эквивалентны. 
    9.12. Прежде всего, следует переписать данное множество так, чтобы каждая 
ФЗ имела одноэлементную правую часть: 
    1. АВ -> С 
    2. С -> А 
    3. ВС -> D 
    4. ACD ->• В 
    5. В? -> С 
    6. С? -» А 
    7. СЕ -> F 
    8. CF -> В 
    9. CF -> D 
    10.D-». ? 1 1.D -> F 
    Тогда 
    • строка 2 подразумевает строку 6, поэтому строку 6 можно опустить; 
    • строка 8 подразумевает CF -> вс (по дополнению), которая вместе со 
строкой 3 подразумевает CF -> о (по транзитивности), так что строку 9 можно опустить; 
    • строка 8 подразумевает ACF -> АВ (по дополнению), а строка 11 
подразумевает ACD -» АСР(ПО дополнению), тогда ACD -» АВ(ПО транзитивности) и 
ACD -> в (согласно декомпозиции). Таким образом, строку 4 можно опустить. 
    На этом все операции вывода завершаются и множество становится неприводимым. 
    АВ -> С С -> А ВС -> D BE ->• С 

    Глава 9. Функциональные зависимости 273 

    СЕ -> F CF-> В D -> ? 
    D -> F 
    Вывод можно осуществить иначе: 
    • строка 2 подразумевает CD -> ACD (по композиции), которая со строкой 4 
подразумевает со -> в (по транзитивности), так что строку 4 можно заменить 
зависимостью со -> я, 
    • строка 2 подразумевает строку 6, так что строку 6 можно опустить (как и прежде); 
    • строки 2 и 9 подразумевают CF -> AD (по композиции), которая 
подразумевает CF -» дос (по дополнению), которая вместе со строкой 4 
подразумевает CF -> в (по транзитивности). Таким образом, строку 8 можно опустить. 
    На этом все операции вывода завершаются и множество становится неприводимым: 
    АВ -> С 
    С -> Л ВС -> D CD -» В 
    BE • 
    С 
    СЕ -> F CF -> D D -> ? D -> F 
    Обратите внимание, что тем самым получено два разных неприводимых покрытия 
для исходного множества ФЗ. 
    9.13. Потенциальными ключами являются L, DPC и DPT. 
    9.14. Используя сокращенную запись N, R, С, Т и Z для атрибутов NAME, 
STREET, CITY, STATE и ZIP соответственно, можно получить следующие зависимости: 
    N -> RCT        RCT -> Z        Z -> СГ 
    Очевидно, что эквивалентным неприводимым множеством является следующее: 
    N -> R        W-»C        W-»T        «СГ -» ?        Z-»C        Л^Г 
    Единственным потенциальным ключом является N. 
    9.15. На это упражнение ответ будет дан не полностью, хотя некоторые 
рассуждения здесь все же будут изложены. Во-первых, множество, очевидно, не 
является неприводимым, так как с -> j и cj-> i вместе подразумевают с-> I. 
Во-вторых, очевидным суперключом является множество {А, В, С, D, G, J} (т.е. 
множество всех атрибутов, упомянутых в левых частях данных ФЗ). Из этого 
множества можно исключить J, поскольку с -> J, а также можно исключить G, 
поскольку АВ -> G Так как ни один из атрибутов А, В, С, D не находится в 
правой части любой данной ФЗ, значит {А, В, С, D} является потенциальным ключом. 

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

