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

Помимо приведенного здесь списка литературы, следует также обратить внимание на ссылки к главе 10, особенно [10.4, 10.5] (т.е. ссылки на оригинальные статьи Кодда о 1НФ, 2НФиЗНФ).

11.1. Bernstein Р.А. Synthesizing Third Normal Form Relations from Functional Dependencies ACM TODS. - December, 1976. - 1, № 4.

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

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

А В (в R{A,B}) В С (в S{B,C}) А С (в Т{А,С})

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

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

11.2. Codd E.F. Recent Investigations into Relational Data Base Systems Proc. IFIP Congress. - Stockholm, Sweden, 1974.

Здесь приводится обзор других работ на данную тему, в частности дается улучшенное определение третьей нормальной формы , под которой фактически подразумевается нормальная форма Бойса-Кодда. Среди других тем можно найти обсуждение представлений и обновления представлений, подъязыков данных, обмена данными и исследований необходимости (по состоянию на 1974 год).

11.3. Date C.J. А Normalization Problem The Relational J. - 1992. - 4, № 2.

В этой статье рассматривается простая задача нормализации, которая используется для представления некоторых идей в области составления проекта базы данных и явного объявления ограничений целостности. Задача сформулирована на основе простой базы данных некоторой авиакомпании с перечисленными ниже ФЗ, где приняты следующие обозначения: FLIGHT - название авиарейса, DESTINATION - место назначения, HOUR - время отправления в часах, DAY - день недели, GATE - выход для посадки на самолет, PILOT - пилот.

{ FLIGHT } DESTINATION

{ FLIGHT } HOUR

{ DAY, FLIGHT } GATE

{ DAY, FLIGHT } PILOT

{ DAY, HOUR, GATE } DESTINATION

{ DAY, HOUR, GATE } FLIGHT

{ DAY, HOUR, GATE } PILOT

{ DAY, HOUR, PILOT } DESTINATION

{ DAY, HOUR, PILOT } FLIGHT

{ DAY, HOUR, PILOT } GATE

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

11.4. Heath I.J. Unacceptable File Operations in a Relational Database Proc. 1971 ACM SIGFIDET Workshop on Data Description, Access, and Control. - San Diego, Calif., November, 1971.

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

11.5. Kent W. А Simple Guide to Five Normal Forms in Relational Database Theory CACM. - February, 1983. - 26, № 2.

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

11.6. Rissanen J. Independent Components of Relations ACM TODS.- December, 1977. -2, №4.

11.7. Zaniolo C. A New Normal Form for the Design of Relational Database Schemata Ibid. - September, 1982. - 7, № 3.

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

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

11.1. Теорема Хита утверждает, что если переменная-отношение R{A, В, С} удовлетворяет функциональной зависимости А В (где А, В и С являются множествами атрибутов), то R равносильна соединению ее проекций R1 с атрибутами {А, В} и R2 с атрибутами {А, С}. Далее в этом доказательстве будет использован сокращенный неформальный вариант записи вида (а, Ь, с) для представления кортежа {А: а, Bsb, С:с}.

Сначала следует показать, что ни один кортеж переменной-отношения R не утрачивается при разбиении на проекции и обратном соединении этих проекций. Пусть (а, Ь, с) € R, тогда (а, Ь) 6 R1 и (а, с) 6 R2, а значит, (а, Ь, с) € R1 JOIN R2. I

Затем следует показать, что каждый кортеж этого соединения действительно является кортежем переменной-отношения R (т.е. при соединении не было получено никаких побочных и нежелательных кортежей). Пусть (а, Ь, с) е R1 JOIN R2. Тогда для генерации кортежа соединения должны выполняться зависимости (а, Ь) е R1 и (а, с) g R2. Следовательно, для генерации кортежа (а, с) е R2 для некоторого атрибута Ь* должен существовать кортеж (а, Ь*, с) е R. Тогда должен также существовать кортеж (а, Ь*) е R1. Теперь у нас есть (а, Ь) е R1 и (а, Ь*) е R1, а поскольку А В, значит, b=b*. Отсюда (а, Ь, с) g R. §

Теорема, обратная теореме Хита, утверждает, что если переменная-отношение R{A, В, С} равносильна соединению ее проекций R1 с атрибутами {А, В} и R2 с атрибутами {А, С}, то R удовлетворяет зависимости А -> В. Это утверждение неверно. В качестве примера переменной-отношения, которая равняется соединению двух ее проекций и вовсе не удовлетворяет никакой нетривиальной ФЗ, можно предложить переменную-отношение СТХ, которая показана на рис. 12.2.