Ульман Дж. Базы данных на Паскале (стр. 3 )

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

В приведенном ниже примере ключом-кандидатом файла АДРЕСА_КЛИЕНТОВ служит поле НОМЕР_КЛИЕНТА.

НОМЕР_КЛИЕНТА 0391 0403 0569 0615

НАЗВАНИЕ уилкинсон сэмсон уилкинсон сэмсон

АДРЕС 19 КОБЛ-СТРИТ 31 ХАЙ-СТРИТ 31 ХАЙ-СТРИТ 19 КОБЛ-СТРИТ

Еще один ключ-кандидат образует пара полей НОМЕР_КЛИЕНТА и АДРЕС. Соединение проекций

proj НОМЕР_КЛИЕНТА, НАЗВАНИЕ (АДРЕСА_КЛИЕНТОВ) и

proj НОМЕР_КЛИЕНТА, АДРЕС (АДРЕСА_КЛИЕНТОВ) представляет собой

полную декомпозицию, однако она не позволяет избавиться от дублирования. Дело в том, что обе проекции содержат ключ-кандидат НОМЕР-КЛИЕНТА. Именно его присутствием и там и там объясняется нежелательный эффект. Заметим, что в обсуждавшемся выше примере полная декомпозиция файла ПОСТАВЩИКИ_ТОВАРОВ, с помощью которой устранялось дублирование данных, была сформирована как соединение двух проекций, общие поля которых не могли образовать ключ-кандидат.

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

Рассмотрим файл ИМЯФАЙЛА с полями FX, FY и FZ. Пусть выполняется равенство

ИМЯ ФАЙЛА = proj FX, FY (ИМЯФАЙЛА) join proj FY, FZ (ИМЯФАЙЛА),

причем FY, являясь ключом-кандидатом, входит в состав обеих проекций, образующих полную декомпозицию файла ИМЯФАЙЛА. В данном случае дублирование не исключено, поскольку файл ИМЯФАЙЛА может содержать такие записи, как

FX Х X'

FY Y Y

FZ Z Z

В этих записях пара значений Y и Z повторяется дважды. Налицо противоречие, поскольку предполагалось, что FY служит ключом-кандидатом, ввиду чего Y может встретиться максимум в одной записи. Этим и завершается доказательство. Оно практически не изменилось бы, если FX, FY и FZ обозначали не одиночные поля, а совокупность полей.

В общем случае у файла может быть несколько полных декомпозиций. Так, файл ПОСТАВЩИКИ_ТОВАРОВ имеет полную декомпозицию, составленную из проекций

proj ШИФР_ТОВАРА, НОМЕР_ТЕЛЕФОНА (ПОСТАВЩИКИ-ТОВАРОВ) и

proj ШИФР-ТОВАРА, НАЗВАНИЕ (ПОСТАВЩИКИ-ТОВАРОВ).

Обе они содержат ключ-кандидат файла ПОСТАВЩИКИ_ТОВАРОВ, ввиду чего замена его приведенной декомпозицией не гарантирует отсутствия дублирования. Однако ранее для этого файла была составлена другая декомпозиция, в которой не было

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

3.4. ПРИСОЕДИНЕННЫЕ ЗАПИСИ

Решая вопрос о том, что целесообразнее хранить - файл как таковой или его полную декомпозицию, следует принимать в расчет и проблему записей, получивших название <присоединенных>. Сначала рассмотрим пример подобной записи, а затем дадим точное определение.

Вновь вернемся к файлу ПОСТАВЩИКИ_ТОВАРОВ, который обсуждался в разд. 3.3.1. Предположим, что в этот файл понадобилось занести телефонный номер 6632 новой фирмы-поставщика, именуемой <Симсон>, от которой не поступало еще никаких товаров. Но поле ШИФР_ТОВАРА служит ключом, и его нельзя оставить пустым, иначе новую запись впоследствии невозможно будет идентифицировать. По этой причине номер телефона в файл ПОСТАВЩИКИ_ТОВАРОВ ввести не удастся. В то же время его можно записать в проекцию

proj НАЗВАНИЕ, НОМЕР_ТЕЛЕФОНА (ПОСТАВЩИКИ, ТОВАРОВ):

НАЗВАНИЕ ДЖЕКСОН УИЛСОН РОБСОН СИМСОН

НОМЕР-ТЕЛЕФОНА 3692 5948 2514 6632

Записи, подобные последней, и называют присоединениями.

Сформулируем теперь общее определение присоединенной записи. Пусть R и S - наборы полей файла ИМЯФАЙЛА, и выполняется условие

ИМЯФАЙЛА = proj R (ИМЯФАЙЛА) join proj S (ИМЯФАЙЛА).

В качестве примера можно вновь взять файл ПОСТАВЩИКИ_ТОВАРОВ, отождествив с R пару полей (ШИФР_ТОВАРА, НАЗВАНИЕ), а с S -- пару полей (НАЗВАНИЕ, НОМЕР_ТЕЛЕФОНА). Запись является присоединенной, если она занесена в проекцию proj S (ИМЯФАЙЛА), но не входит в состав какой-либо записи

proj R (ИМЯФАЙЛА) join proj S (ИМЯФАЙЛА),

поскольку с ней невозможно образовать конкатенацию ни одной из записей проекции proj R (ИМЯФАЙЛА). В частности, proj ШИФР_ТОВАРА, НАЗВАНИЕ (ПОСТАВЩИКИ_ТОВАРОВ)

не содержит записей, где фигурировало бы название <Симсон>. По этой причине <Симсон> и номер телефона фирмы будут исключены из результата соединения

proj ШИФР ТОВАРА, НАЗВАНИЕ (ПОСТАВЩИКИ_ТОВАРОВ) join

proj НАЗВАНИЕ, НОМЕР_ТЕЛЕФОНА (ПОСТАВЩИКИ_ТОВАРОВ).

Если присоединенная запись занесена в proj S (ИМЯФАЙЛА),

последняя перестает быть точной проекцией ИМЯФАЙЛА. Тем не менее основное ее содержание не меняется, и поэтому будем обозначать ее по-прежнему proj S (ИМЯФАЙЛА).

Вернемся к проблеме запоминания телефона фирмы <Симсон>, которая еще не успела приступить к поставке товаров. В подобных обстоятельствах проблема решается с помощью присоединенных записей, которые можно хранить не в исходном файле, а в его полной декомпозиции. Возможны, однако, такие ситуации, когда использование полной декомпозиции для запоминания присоединенных записей лишено смысла.

Как и ранее, все решает наличие или отсутствие общего ключа-кандидата. Если в состав обеих проекций, образующих полную декомпозицию ИМЯФАЙЛА, входит ключ-кандидат, проблемы присоединенных записей практически не существует. Предположим, например, что в файл АДРЕСА_КЛИЕНТОВ (см. разд. 3.3.2) потребовалось поместить название новой фирмы - <Хобсон>, а также ее телефон - 0643, не указывая в то же время ее адреса. Эту информацию в виде записи

0643 ХОБСОН

можно занести в проекцию proj НОМЕР_КЛИЕНТА, НАЗВАНИЕ (АДРЕСА_КЛИЕНТОВ). Можно поступить и по-иному, поместив в файл АДРЕСА_КЛИЕНТОВ запись

0643 ХОБСОН пусто.

Словом <пусто> здесь обозначено поле, не содержащее никакого значения. Учитывая, что это поле не используется как ключ, в данном случае правила не нарушены. Таким образом, запись

0643 ХОБСОН

по существу не является присоединенной, поскольку ее можно поместить, объединив с пустым нолем, непосредственно в исходный файл.

Чтобы обосновать правильность последней операции, достаточно занести в проекцию proj НОМЕР_КЛИЕНТА, АДРЕС (АДРЕСА_КЛИЕНТОВ) вспомогательную запись

0643 пусто.

Ее конкатенация с записью

0643 ХОБСОН

из proj НОМЕР_КЛИЕНТА, НАЗВАНИЕ (АДРЕСА_КЛИЕНТОВ) дает запись

0643 ХОБСОН пусто

в файле АДРЕСА_КЛИЕНТОВ, который восстанавливается в результате соединения двух указанных проекций. Итак, можно считать, что в рассмотренном примере присоединенные записи отсутствуют.

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

Пусть этими свойствами по отношению к файлу ИМЯФАЙЛА обладают две проекции, proj R (ИМЯФАЙЛА) и proj S (ИМЯФАЙЛА). Дополним proj S (ИМЯФАЙЛА) еще одной записью, которую обозначим s, и предположим, что ни одно из полей s,

входящих в ключ-кандидат, не является пустым.

Проекцию proj R (ИМЯФАЙЛА) также дополним специально сформированной записью r. Все поля этой вспомогательной записи, присутствующие одновременно в наборах R и S, по своему содержанию идентичны полям записи s, в то время как остальные пусты. Введение r в проекцию proj R (ИМЯФАЙЛА) не противоречит правилам, поскольку в силу своей структуры г включает ключ-кандидат, причем ни одно из его полей в этой записи не пусто. Очень важно также, что новая запись, не привнося никакой информации, помимо уже имеющейся в proj R (ИМЯФАЙЛА), фактически не меняет содержимого последней.

Завершим доказательство, осуществив соединение

proj R (ИМЯ ФАЙЛА) join proj S (ИМЯ ФАЙЛА).

Результат этой операции включает конкатенацию r и s. Следовательно, s нельзя считать присоединенной записью, поскольку, согласно определению, при соединении проекций такая запись не может войти в результирующий файл. Таким образом, показано, что присоединенные записи отсутствуют, если проекции,

порождающие полную декомпозицию, содержат общий ключ-кандидат исходного файла.

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

3.5. НОРМАЛИЗАЦИЯ

3.5.1. ПЯТАЯ НОРМАЛЬНАЯ ФОРМА

Говорят, что файл находится в пятой нормальной форме, если не существует ни одной его полной декомпозиции, в которую входили бы проекции, не имеющие общего ключа-кандидата. Можно сформулировать это условие и более строго: файл представлен в пятой нормальной форме тогда и только тогда, когда в каждой его полной декомпозиции все проекции содержат ключ-кандидат. Считается, что файл, не обладающий ни одной полной декомпозицией, также имеет пятую нормальную форму.

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

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

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

3.5.2. УПРАЖНЕНИЯ

В каждом из упражнений 1-6 совместно с исходным файлом дается одна или несколько его полных декомпозиций.

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

форме, следует доказать, что это действительно так. Можно считать, что, помимо представленных, других декомпозиций, способных заместить файл, не существует.

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

выпадающую из ненормализованного файла.

1. Представим себе подробный план парка, на котором отдельно указано каждое растущее дерево. Все деревья снабжены индивидуальными номерами. Исходный файл в этом упражнении именуется ДЕРЕВЬЯ. В нем хранятся краткие сведения относительно каждого дерева. Ниже приведены имена полей этого файла и четыре его записи.

НОМЕР_ДЕРЕВА 1 2 3 4

ПОРОДА БУК ПАДУБ БУК ЯСЕНЬ

ВЫСОТА 21 9 23 18

ВЕЧНОЗЕЛЕНОЕ НЕТ ДА НЕТ НЕТ

Первая полная декомпозиция

proj НОМЕР_ДЕРЕВА, ПОРОДА, ВЫСОТА (ДЕРЕВЬЯ),

proj НОМЕР_ДЕРЕВА, ВЕЧНОЗЕЛЕНОЕ (ДЕРЕВЬЯ).

Вторая полная декомпозиция

proj НОМЕР_ДЕРЕВА, ПОРОДА (ДЕРЕВЬЯ),

proj НОМЕР_ДЕРЕВА, ВЫСОТА (ДЕРЕВЬЯ),

proj НОМЕР_ДЕРЕВА, ВЕЧНОЗЕЛЕНОЕ (ДЕРЕВЬЯ).

Третья полная декомпозиция

proj НОМЕР_ДЕРЕВА, ПОРОДА, ВЫСОТА (ДЕРЕВЬЯ),

proj ПОРОДА, ВЕЧНОЗЕЛЕНОЕ (ДЕРЕВЬЯ).

2. Имя исходного файла - КОНФЕТЫ. Вот имена его полей

и часть помещенных в нем записей:

РЕЦЕПТ ИРИС ИРИС ИРИС ИРИС ТЯНУЧКА ТЯНУЧКА ТЯНУЧКА

ИНГРЕДИЕНТ САХАР МАСЛО МУКА ПАТОКА САХАР МАСЛО СГУЩЕННОЕ МОЛОКО

ГРАММЫ 450 225 5 20 450 225 400

КАЛОРИИ_НА_ГРАММ 3,7 7,8 3,5 3,2 3,7 7,8 4,5

Первая полная декомпозиция

proj РЕЦЕПТ, ИНГРЕДИЕНТ, ГРАММЫ (КОНФЕТЫ),

proj ИНГРЕДИЕНТ, КАЛОРИИ_НА_ГРАММ (КОНФЕТЫ).

Вторая полная декомпозиция

proj РЕЦЕПТ, ИНГРЕДИЕНТ, ГРАММЫ (КОНФЕТЫ),

proj РЕЦЕПТ, ИНГРЕДИЕНТ, КАЛОРИИ_НА_ ГРАММ (КОНФЕТЫ).

3. В исходном файле, названном ВИЗИТЫ (VISITS), фиксируются приезды людей в различные города и страны. Для простоты предполагается, что у всех визитеров разные фамилии и нет городов с одинаковыми названиями. Ниже указаны имена полей

файла и приведено несколько его записей.

ДАТА (DATE)

ФАМИ ЛИЯ (NAME) ДЖОНС СМИТ СМИТ СМИТ НАЙТ ЯНГ

ПРОФЕССИЯ (PROFESSION) БУХГАЛТЕР ПРОГРАММИСТ ПРОГРАММИСТ ПРОГРАММИСТ ИНЖЕНЕР ИНЖЕНЕР

ГОРОД (TOWN) ЭФТОН СИТОН ЭЙТОН ЭФТОН дитон СИТОН

СТРАНА (COUNTRY) УАЙЛАНДИЯ ЭКСЛАНДИЯ ЭКСЛАНДИЯ УАЙЛАНДИЯ ЭЕДЛАНДИЯ ЭКСЛАНДИЯ

Первая полная декомпозиция

proj ДАТА, ФАМИЛИЯ, ПРОФЕССИЯ, ГОРОД (ВИЗИТЫ),

proj ГОРОД, СТРАНА (ВИЗИТЫ).

Вторая полная декомпозиция

proj ДАТА, ФАМИЛИЯ, ГОРОД, СТРАНА (ВИЗИТЫ),

proj ФАМИЛИЯ, ПРОФЕССИЯ (ВИЗИТЫ).

Третья полная декомпозиция

proj ДАТА, ФАМИЛИЯ, ГОРОД (ВИЗИТЫ),

proj ГОРОД, СТРАНА (ВИЗИТЫ),

proj ФАМИЛИЯ, ПРОФЕССИЯ (ВИЗИТЫ).

4. Исходный файл, названный ПОЕЗДКИ, содержит записи о междугородных автобусных перевозках. Переезд из одного города в другой всегда совершается по неизменному маршруту, причем в день этим путем проезжает не более одного автобуса. В шестом поле файла отмечается продолжительность поездки.

Имена полей и образцы записей приведены ниже.

ОТКУДА УИНКЛБИ УИНКЛБИ КОКЛТОН

КУДА КОКЛТОН КОКЛТОН МАСЛГРОВ

ДАТА

ВОДИТЕЛЬ МАРШАЛЛ АРНОЛЬД МАРШАЛЛ

ВРЕМЯ 3.4 2.8 4.1

РАССТОЯНИЕ 62 62 62

Первая полная декомпозиция

proj ОТКУДА, КУДА, ДАТА, ВОДИТЕЛЬ, ВРЕМЯ (ПОЕЗДКИ),

proj ОТКУДА, КУДА, РАССТОЯНИЕ (ПОЕЗДКИ).

Вторая полная декомпозиция

proj ОТКУДА, КУДА, ДАТА, ВОДИТЕЛЬ (ПОЕЗДКИ),

proj ОТКУДА, КУДА, ДАТА, ВРЕМЯ (ПОЕЗДКИ),

proj ОТКУДА, КУДА, РАССТОЯНИЕ (ПОЕЗДКИ).

5. Исходный файл ШАХМАТЫ содержит записи, в которых указаны дата встречи, фамилии участников и победитель, а также продолжительность игры. Два конкретных шахматиста могут сыграть не более одной партии в день. Имена полей и часть записей приведены ниже.

ДАТА	УЧАСТНИК_1	УЧАСТНИК 2	ПОБЕДИТЕЛЬ	ВРЕМЯ
	ГРАМБИГ	ПИВИЧ	ПИВИЧ	3,6
	ГРАМБИГ	СМИТ	СМИТ	2,5
	ГРАМБИГ	ПИВИЧ	ПИВИЧ	1,4
	СМИТ	ПИВИЧ	СМИТ	5,2

Полная декомпозиция

proj ДАТА, УЧАСТНИК_1, УЧАСТНИК_2, ПОБЕДИТЕЛЬ (ШАХМАТЫ),

proj ДАТА, УЧАСТНИК_1, УЧАСТНИК_2, ВРЕМЯ (ШАХМАТЫ).

В данном случае имеется всего одна полная декомпозиция, которую и предстоит проанализировать.

6. В исходном файле ИСКИ содержится подробная информация об исках, представленных страховым компаниям. Названия этих компаний не повторяются. По данному страховому полису может быть возбуждено несколько исков, но не более одного в день. Любой клиент может иметь несколько полисов. Ниже приведен

перечень полей файла ИСКИ.

ФИРМА

АДРЕС_ФИРМЫ

НОМЕР_ПОЛИСА

ДАТАСТРАХ

КЛАСС

СУММАСТРАХ

ДАТА_ИСКА

СУММА_ИСКА

НОМЕР_КЛИЕНТА

ИМЯ_КЛИЕНТА

АДРЕС_КЛИЕНТА

Первая полная декомпозиция

proj ФИРМА, АДРЕС_ФИРМЫ, HOMEР_ПОЛКСА. ДАТАСТРАХ,

НОМЕР_КЛИЕНТА, КЛАСС, СУММАСТРАХ (ИСКИ),

proj НОМЕР_ПОЛИСА, ИМЯ_КЛИЕНТА, АДРЕС_КЛИЕНТА, ДАТА.

ИСКА, СУММА_ИСКА (ИСКИ).

Вторая полная декомпозиция

proj ФИРМА, АДРЕС_ФИРМЫ (ИСКИ),

proj НОМЕР_КЛИЕНТА, ИМЯ_КЛИЕНТА. АДРЕС_КЛИЕНТА (ИСКИ),

proj НОМЕР_ПОЛИСА, ФИРМА, НОМЕР_КЛИЕНТАб ДАТАСТРАХ,

КЛАСС, СУММАСТРАХ (ИСКИ),

proj НОМЕР_ПОЛИСА, ДАТА_ИСКА, СУММА_ИСКА (ИСКИ).

3.6. ФУНКДИОНАЛЬНАЯ ЗАВИСИМОСТЬ

3.6.1. ОПРЕДЕЛЕНИЕ ФУНКЦИОНАЛЬНОЙ ЗАВИСИМОСТИ

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

подобную декомпозицию. Весьма полезно в связи с этим познакомиться с понятием функциональной зависимости.

Пусть Х и Y - наборы, каждый из которых объединяет одно или несколько полей файла ИМЯФАЙЛА. Y находится в функциональной зависимости от Х тогда и только тогда, когда с каждым данным значением Х связано не более одного значения Y. По отношению к ИМЯФАЙЛА функциональная зависимость Y от Х

создает ограничение, выражающееся в том, что любые две записи этого файла, содержащие одинаковые значения X, должны обязательно включать и совпадающие значения Y. Ограничение это действует не только на записи, уже имеющиеся в ИМЯФАЙЛА, ной на те, что потенциально могут попасть в него в будущем.

В качестве примера возьмем файл АДРЕСА_КЛИЕНТОВ из разд. 3.3.2. Положив Х – НОМЕР_КЛИЕНТА, а Y - АДРЕС, сразу же можно убедиться, что Y функционально зависит от X. Действительно, АДРЕСА_КЛИЕНТОВ удовлетворяют данному выше определению уже потому, что ни в одной из записей значения НОМНР_КЛИЕНТА не повторяются.

Рассмотрим еще один, намеренно упрощенный, пример. Пусть файл содержит следующие четыре записи:

F1 A B C B

F2 h i j k

Очевидно, F2 не связано функциональной зависимостью с F1, поскольку значению B поля ЕЗ соответствуют два различных значения поля F2. В то же время нельзя утверждать, что F1 функционально зависит от F2, исходя лишь из имеющихся записей. Это допустимо только при том условии, что на файл дополнительно наложено ограничение, запрещающее, вводить в него такие новые записи, как, например,

F1 F2

C k

которая нарушает условие однозначного соответствия значений F2 значениям FL

Если Х состоит из нескольких полей, то говорят, что Y находится в полной функциональной зависимости от Х тогда и только тогда, когда:

а) Y функционально зависит от X.:

б) Y функционально не зависит от любого X', где X' – такое подмножество X, что по меньшей мере одно поле из Х не принадлежит X'.

Иными словами, утверждать, что Y связан G Х полной функциональной зависимостью, можно в том и только в том случае, если Y функционально зависит от Х и не зависит от любого его подмножества, не совпадающего с X.

Примером может служить файл ЗВЕРИ_В_НЕВОЛЕ из разд. 3.2. В нем поле ЗОНА_ОБИТАНИЯ функционально зависит от пары ЗООПАРК, ЖИВОТНОЕ. Действительно, любой паре значений, например,

9ЙТОН КЕНГУРУ

ЗЙТОН ВЕРБЛЮД

соответствует ровно по одному значению поля ЗОНА_ОБИТАНИЯ. Легко, однако, убедиться и в том, что ЗОНА_ОБИТАНИЯ функционально зависит также от поля ЖИВОТНОЕ. Совместно это означает, что ЗОНА_ОБИТАНИЯ не обладает полной функциональной зависимостью от пары ЗООПАРК, ЖИВОТНОЕ.

Завершим раздел еще одним простым примером. Предположим, что дан файл ЗАКАЗЫ со следующими полями:

НОМЕР_ЗАКАЗА ШИФР_ТОВАРА ОПИСАНИЕ КОЛИЧЕСТВО

{Шифр, присвоенный заказанному товару} {Описание товара} {Заказанное количество единиц товара}

Первичный ключ (и единственный ключ-кандидат) этого файла состоит из двух полей – НОМЕР_ЗАКАЗА и ШИФР_ТОВАРА.

В одиночку каждое из указанных полей не способно играть роль ключа-кандидата, поскольку файл может содержать по несколько записей с одинаковыми значениями НОМЕР_ЗАКАЗА и с одинаковыми значениями ШИФР_ТОВАРА. В то же время пара значений НОМЕР_ЗАКАЗА и ШИФР_ТОВАРА однозначно идентифицирует конкретную запись. Следовательно, этой паре соответствует единственное значение поля КОЛИЧЕСТВО, из чего можно заключить, что КОЛИЧЕСТВО связано полной функциональной зависимостью с полем НОМЕР_ЗАКАЗА и ШИФР_ТОВАРА. Действительно, условие б) выполняется: не исключено появление записей с повторяющимися значениями полей НОМЕР_ЗАКАЗА и ШИФР_ТОВАРА, вследствие чего поле КОЛИЧECTВO не зависит функционально ни от того, ни от другого в отдельности.

С другой стороны, поле ОПИСАНИЕ функционально зависит от поля ШИФР_ТОВАРА. Из этого следует, что ОПИСАНИЕ не находится в полной функциональной зависимости от ключа-кандидата НОМЕР_ЗАКАЗА, ШИФР_ТОВАРА.

3.6.2. ТЕОРЕМА ХИТА

Посвятим этот раздел доказательству теоремы Хита, устанавливающей связь между функциональной зависимостью и полной декомпозицией файла. Рассмотрим файл ИМЯФАИЛА, в котором выделим три набора полей: Н, J и К таких, что каждое

поле ИМЯ ФАЙЛА принадлежит лишь какому-то одному из этих трех наборов.

Теорема Хита. Если К функционально зависит от J, то справедливо тождество

ИМЯФАЙЛА = proj Н, J (ИМЯФАЙЛА) join proj J, К (ИМЯ ФАЙЛА).

Это означает, что при наличии функциональной зависимости К от J проекции proj Н, J (ИМЯФАЙЛА) и proj J, К, (ИМЯФАЙЛА) образуют полную декомпозицию исходного файла.

Доказательство теоремы. Возможные значения Н, J и К будем обозначать соответственно h и h’ j и j', k и k'. Каждая из указанных величин фактически может представлять собой совокупность значений нескольких полей.

Начнем доказательство с того, что введем вспомогательный файл ИМЯФАЙЛА1:

ИМЯ ФАЙЛА1 = proj Н, J (ИМЯФАЙЛА) join proJ J, К (ИМЯФАЙЛА).

Возьмем произвольную запись hjk, входящую в ИМЯФАЙЛА. Очевидно, hj принадлежит проекции proj Н, J (ИМЯФАЙЛА), a jk - проекции proj J. К (ИМЯФАЙЛА). Исходя из определения ИМЯФАЙЛА1 и свойств операции соединения, можно заключить, что запись hjk входит в файл ИМЯФАЙЛА1. Следовательно,

каждая запись ИМЯФАЙЛА является одновременно и записью ИМЯФАЙЛА1-

Далее рассмотрим произвольную запись h'j'k’ из файла ИМЯФАЙЛА1. Согласно определению файла ИМЯФАЙЛА1 выполняется равенство

proj Н, J (ИМЯФАЙЛА1) = proj Н, J (ИМЯФАЙЛА).

Отсюда можно сделать вывод, что в ИМЯФАЙЛА присутствует запись h’j’k’. Аналогичным образом равенство

proj J, К (ИМЯФАЙЛА1) = proj J, К (ИМЯФАЙЛА)

позволяет утверждать, что ИМЯФАЙЛА содержит запись hj’k'. Поскольку К функционально зависит от J, в записи h'j'k' и hj'k' входит одно и то же значение ]'. Следовательно, k = k' и h'j’k = h'j'k'. Последнее означает, что каждая запись ИМЯФАЙЛА1 присутствует в ИМЯФАЙЛА. Учитывая, что выполняется и

обратное, можно сделать вывод, что эти два файла тождественны, т. е. ИМЯФАЙЛА = ИМЯФАЙЛА1). Этим и завершается доказательство теоремы Хита.

3.7. НОРМАЛИЗАЦИЯ НА ОСНОВЕ ФУНКЦИОНАЛЬНОЙ ЗАВИСИМОСТИ

3.7.1. ПЕРВАЯ НОРМАЛЬНАЯ ФОРМА

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

Наиболее' общими свойствами среди нормальных форм обладает первая, с которой и начнем обсуждение. Файл находится в первой нормальной форме тогда и только тогда, когда ни одна из его записей не содержит в любом своем поле более одного значения и ни одно из ее ключевых полей не пусто. В качестве примера возьмем файл СОСТАВ_АНСАМБЛЯ

НОМАНС {Номер ансамбля}

УЧАСТНИКИ {Номера присвоенные музыкантам, играющим в ансамбле}

Предположим, что СОСТАВ_АНСАМБЛЯ включает следующие данные:

НОМАНС	УЧАСТНИКИ
Е1	Р1, Р8, Р9
Е2	РЗ, Р5
ЕЗ	Р9
Е4	P1, Р4, Р7
Е5	Р5, Р9
Е6	Р1, Р7
Е7	РЗ, Р5

Большинство записей файла содержат по несколько номеров в поле УЧАСТНИКИ - следовательно, это не первая нормальная форма. В то же время все музыкальные файлы из разд. 2.2 имеют первую нормальную форму, поскольку в каждом поле любой их записи помещается ровно по одному знaчению. Заметим, что строки символов, подобные записанным в поле АДРЕС файла АДРЕСА_КЛИЕНТОВ, рассматриваются как отдельные значения.