рибутов названия курса (COURSE), а также атрибута-отношения с именами преподавателей (TEACHERS) и атрибута-отношения с названиями учебников (TEXTS) (на рис. 12.1 показаны два таких кортежа). Смысл каждого кортежа состоит в том, что соответствующий курс может преподаваться любым из указанных преподавателей с использованием всех указанных учебников. Предположим, что для заданного курса может быть определено произвольное количество соответствуюших преподавателей и учебников. Более того, допустим, хотя это и не совсем реалистичное допущение, что преподаватели и рекомендуемые учебники совершенно независимы друг от друга. Это значит, что независимо от того, кто преподает данный курс, всегда используется один и тот же набор учебников. Наконец, допустим, что определенный преподаватель или определенный учебник может быть связан с любым количеством курсов.

НСТХ

TEACHERS

Physics

Math

TEACHER

Prof. Green Prof. Brown

TEACHER

Prof. Green

TEXTS

TEXT

Basic Mechanics Principles of Optics

TEXT

Basic Mechanics Vector Analysis Trigonometry

Puc. 12.1. Пример значений данных в переменной-отношении НСТХ

Пусть необходимо (как в разделе 11.6 предыдущей главы) исключить атрибуты, принимающие в качестве значений отношения. Один из способов (но не тот, который описан в ответе к упр. 11.3; к нему мы вернемся в конце этого раздела) заключается в простой замене переменной-отношения НСТХ переменной-отношением СТХ с тремя скалярными атрибутами, COURSE, TEACHER и TEXT, как показано на рис. 12.2. Как видно из этого рисунка, каждый кортеж исходной переменной-отношения НСТХ порождает т *п кортежей в переменной-отношении СТХ, где W и W являются значениями кардинальности для отношений TEACHERS и TEXTS в данном кортеже переменной-отношения НСТХ. Обратите внимание, что все атрибуты результирующей переменной-отношения СТХ входят в состав ее ключа (в отличие от переменной-отношения НСТХ, потенциальный ключ которой {COURSE} состоял из единственного атрибута).

Puc. 12.2. Набор значений данных в переменной-отношении СТХ, эквивалентный приведенному выше примеру значений данных в переменной-отношении НСТХ

Данные, помещаемые в переменную-отнощение СТХ, имеют следующий смысл: кортеж {COURSE:с, TEACHER:t, ТЕХТ:х} появляется в переменной-отнощении СТХ тогда и только тогда, когда курс с читается преподавателем t с использованием учебника х. Тогда, принимая во внимание, что для каждого курса указаны все возможные комбинации имени преподавателей и названий учебников, можно утверждать, что для переменной-отнощения СТХ верно следующее ограничение.

ЕСЛИ кортежи (с, tl, х1) и (с, 12, х2) присутствуют одновременно,

ТО кортежи (c,tl,x2) и (c,t2,xl) также присутствуют одновременно.

(В данном случае для представления кортежей вновь использована сокращенная запись без указания имен атрибутов.)

Очевидно, что переменная-отнощение СТХ характеризуется значительной избыточностью, вследствие чего возникнут аномалии обновления. Например, для добавления информации о том, что курс физики может читаться новым преподавателем, необходимо создать два новых кортежа, по одному для каждого используемого учебника. Как можно избежать появления таких проблем? Здесь нетрудно заметить две следующие особенности.

1. Рассматриваемые проблемы возникают в результате того, что преподаватели и учебники совершенно не зависят друг от друга.

2. Ситуацию можно существенно улучшить, если выполнить декомпозицию переменной-отнощения СТХ на две проекции (например, с именами СТ и СХ) с атрибутами {COURSE, TEACHER} и {COURSE, TEXT} соответственно (рис. 12.3).

Puc. 12.3. Значения данных в проекциях СТ и СХ, которые соответствуют содержанию переменной-отношения СТХ, показанному на рис. 12.2

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

Замечание. Здесь читатель может возразить, что избыточность данных в переменной-отношении СТХ вовсе не была необходимой по определению, а потому соответствующие ей аномалии обновления также совершенно необязательно были неизбежны. Точнее говоря, можно предположить, что для описания некоторого курса в переменную-отно-

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

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

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

COURSE TEACHER

COURSE TEXT

Обратите внимание на двойную стрелку, которая в многозначной зависимости А -> В означает, что В многозначно зависит от А или А многозначно определяет В. Первая из

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

Исходя из изложенного, можно привести формальное определение многозначной зависимости.