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

С помощью операции

proj НОММУЗ (СОЧИНЕНИЯ)

можно получить перечень номеров, присвоенных всем композиторам, т. е. музыкантам, создавшим хотя бы по одному произведению. Но чтобы узнать имена всех композиторов, c полями НОММУЗ в записях файла СОЧИНЕНИЯ нужно связать соответcтвующие поля ИМЯМУЗ. Для этого достаточно произвести соединение файлов СОЧИНЕНИЯ и МУЗЫКАНТЫ, в результате которого произойдет слияние каждой записи файла СОЧИНЕНИЯ с записью файла МУЗЫКАНТЫ, содержащей имя автора.

Таким образом, список имен композиторов сформирует пара операций

proj ИМЯМУЗ (СОЧИНЕНИЯ join МУЗЫКАНТЫ).

Рассмотрим еще один пример.

Запрос: указать имя и дату рождения каждого композитора, написавшего вещь под названием <Кейсонг>.

Ответ дает следующая последовательность операций:

proj ИМЯМУЗ, ДАТАРОЖ (sel НАЗВАНИЕ='КЕЙСОНГ' (СОЧИНЕНИЯ) join МУЗЫКАНТЫ).

С помощью операции выбора из файла СОЧИНЕНИЯ выделяются записи всех сочинений, названных <Кейсонг>. Эти записи соединяются затем с теми записями файла МУЗЫКАНТЫ, у которых совпадают значения поля НОММУЗ. Это означает, что

каждая отобранная запись файла СОЧИНЕНИЯ дополняется информацией об авторе данного произведения. Окончательным итогом описанной последовательности операций реляционной алгебры являются следующие данные:

СИДИЙСКИЙ

ЭЙЭФСКИЙ

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

Запрос: перечислить все инструменты, на которых играют в ансамбле <Эйз> из Зедландии.

Вот выражение реляционной алгебры, которое позволит получить ответ на этот запрос:

proj ИНСТРУМЕНТ

(proj НОМАНС

(sel (НАЗВАНИЕ='ЭЙЗ') and (СТРАНАНС='ЗЕДЛАНДИЯ') (АНСАМБЛИ))

join УЧАСТНИКИ_АНСАМБЛЕЙ join ИСПОЛНИТЕЛИ).

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

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

Запрос: указать, когда в Эксландии исполнялось произведение под названием <Эмтьюн>.

Ответ на запрос получим с помощью такого выражения:

proj ДАТАИСП

(sel СТРАНАИСП='ЭКСЛАНДИЯ' (ИСПОЛНЕНИЯ)

join proj НОМСОЧ (sel НАЗВАНИЕ='ЭМТЬЮН' (СОЧИНЕНИЯ))).

Еще один пример развивает предыдущий. В нем потребуется вторая операция соединения.

Запрос: указать автора любого произведения, названного Эмтьюн, которое хотя бы однажды исполнялось в Эксландии.

На запрос отвечает следующее выражение:

proj ИМЯМУЗ

(proj НОМСОЧ

(sel СТРАНА='ЭКСЛАНДИЯ' (ИСПОЛНЕНИЯ)) join

sel НАЗВАНИЕ='ЭМТЬЮН' (СОЧИНЕНИЯ) join МУЗЫКАНТЫ).

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

2.7.3. СОЕДИНЕНИЕ ПО НЕСКОЛЬКИМ

ПОЛЯМ

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

Предположим, например, что файл ИМЯФАЙЛА1 содержит три записи:

G1 d h У

F1 3 7 4

F2 H N H

а файл ИМЯФАЙЛА2 - пять:

F1 3 3 7 4 4

F2 H H N H H

G2 A B A C B

Операция соединения

ИМЯФАЙЛА1 join ИМЯФАЙЛА2

формирует следующий набор данных:

G1 d d h У Y

FI 3 3 7 4 4

F2 H H N H H

G2 A В A С В

Как и прежде, в полученных записях имеется лишь по одному общему полю.

Запрос: указать страну и название каждого ансамбля, руководитель которого выступает одновременно и как исполнитель.

Ответ дает последовательность операций

proj НАЗВАНС, СТРАНАНС

(АНСАМБЛИ join ИСПОЛНИТЕЛИ join УЧАСТНИКИ АНСАМБЛЕЙ).

Поясним написанное. В результате первого соединения номер исполнителя НОМИСП связывается с номером НОМАНС, если этот исполнитель руководит ансамблем. Таким образом, все руководители, не являющиеся исполнителями, после этого соединения удаляются из списка. Второе соединение осуществляется

на основе двух общих полей, НОМИСП и НОМАНС. После него из результата предшествующего соединения исключаются записи, содержащие пары НОМИСП и НОМАНС, отсутствующие в записях файла УЧАСТНИКИ_АНСАМБЛЕЙ. Тем самым отсеиваются ансамбли, в которых не играют их руководители.

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

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

а) назвать города Эксландии, в которых давались концерты любых ансамблей;

б) указать дату создания каждого произведения под названием <Кейсонг>;

в) перечислить имена исполнителей, играющих на саксофоне;

г) перечислить названия сочинений, написанных Эйэфским;

д) указать даты исполнения произведений, созданных композиторами - уроженцами Зедландии;

е) перечислить руководителей всех ансамблей, в составе которых есть саксофонисты.

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

а) перечислить названия всех эксландских ансамблей, среди участников которых есть саксофонисты;

б) назвать все города Эксландии, в которых исполнялись любые вещи, созданные не ранее 1947 г.;

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

2.9. ОБЪЕДИНЕНИЕ

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

именами и типами полей. Иными словами, у файлов-операндов должны совпадать типы записей.

Результатом операции объединения

ИМЯФАЙЛА1 union ИМЯФАЙЛА2

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

F1 a b c

G1 4 5 6

а ИМЯФАЙЛА2

F1 d b e c

G1 2 5 4 6

В этом случае операция

ИМЯФАЙЛА1 union ИМЯФАЙЛА2

дает следующий набор записей:

F1 а b с d e

G1 4 5 6 2 4

При ответах на некоторые запросы вместо объединения предпочтительнее пользоваться выборов, включая в его условие операцию <ИЛИ>. Приведем пример подобной ситуации.

Запрос: назвать имена всех музыкантов, родившихся в Уайландии или Зедландии.

Ответ на этот запрос получим с помощью выражения:

proj ИМЯМУЗ

(sel (СТРАНАРОЖ = 'УАЙЛАНДИЯ') оr

(СТРАНАРОЖ = 'ЗЕДЛАНДИЯ') (МУЗЫКАНТЫ)).

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

Еще один пример.

Запрос: перечислить имена всех музыкантов, родившихся в Уайландии либо сочинивших вещь под названием <Кейсонг>.

Ответ на запрос даст следующая последовательность операций:

proj ИМЯМУЗ (sel СТРАНАРОЖ ='УАЙЛАНДИЯ' (МУЗЫКАНТЫ))

union

proj ИМЯМУЗ (МУЗЫКАНТЫ join sel НАЗВАНИЕ = 'КЕЙСОНГ' (СОЧИНЕНИЯ)).

Первым операндом в операции объединения служит набор имен музыкантов, родившихся в Уайландии, вторым - набор, объединяющий имена композиторов, которые написали произведения, названные <Кейсонг>.

2.10. ПЕРЕСЕЧЕНИЕ

В результате выполнения операции пересечения

ИМЯФАЙЛА1 intersection ИМЯФАЙЛА2

получается набор записей, входящих в состав обоих файлов. Если, например, в файле ИМЯФАЙЛА1 содержатся записи

F1 a b c

G1 4 5 6

а в ИМЯФАЙЛА2

F1 d b e c

G1 2 5 4 6

то их пересечением является следующая совокупность записей.

F1 b с

G1 5 6

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

Запрос: назвать имена всех композиторов, являющихся авторами по меньшей мере двух произведений - Кейсонг и Элпис.

Ответ можно получить с помощью такого выражения:

proj ИМЯМУЗ

(МУЗЫКАНТЫ join (proj НОММУЗ (sel НАЗВАНИЕ = 'КЕЙСОНГ' (СОЧИНЕНИЯ))

intersection

proj НОММУЗ (sel НАЗВАНИЕ = 'ЭЛПИС'(СОЧИНЕНИЯ)))).

А вот для ответа на следующий запрос операция пересечения не потребуется.

Запрос: перечислить всех композиторов, родившихся в Уайландии не позднее 1945 г.

Вместо пересечения здесь проще, воспользоваться логическим <И> в условии операции выбора (этого не удалось бы сделать в предыдущем случае).

proj ИМЯМУЗ

(sel (СТРАНАРОЖ='УАЙЛАНДИЯ') and (ДАТАРОЖ<) (МУЗЫКАНТЫ)).

2.11. ВЫЧИТАНИЕ

Результатом операции вычитания

ИМЯФАЙЛА1 difference ИМЯФАЙЛА2

является совокупность записей, имеющихся в ИМЯФАЙЛА1, но отсутствующих в ИМЯФАЙЛА2. Если, например, ИМЯФАЙЛА1 содержит записи

F1 a b c f

G1 4 5 6 5

а в ИМЯФАЙЛА2

F1 d b e c

G1 1 5 4 6

то операция

ИМЯФАЙЛА1 difference ИМЯФАЙЛА2

формирует набор записей

F1 a f

G1 4 5

Приведем пример запроса, для ответа на который приходится использовать вычитание.

Запрос: назвать имена всех музыкантов, не сочиняющих произведений.

Ответ даст последовательность операций

proj ИМЯМУЗ

(proj НОММУЗ (МУЗЫКАНТЫ)

difference

proj НОММУЗ (СОЧИНЕНИЯ) join МУЗЫКАНТЫ).

Интерес здесь представляет внутреннее выражение

proj НОММУЗ (МУЗЫКАНТЫ) difference proj НОММУЗ (СОЧИНЕНИЯ),

с помощью которого образуется совокупность НОММУЗ всех музыкантов, упомянутых в файле МУЗЫКАНТЫ, но не фигурирующих в файле СОЧИНЕНИЯ.

2.12. ДЕЛЕНИЕ

При выполнении операции деления

ИМЯФАЙЛА1 division ИМЯФАЙЛА2

требуется, чтобы каждое поле ИМЯФАЙЛА2 имело те же имя и тип, что и одно из полей ИМЯФАЙЛА1. В результате деления получается файл, поля которого содержатся в ИМЯФАЙЛА1, но отсутствуют в ИМЯФАЙЛА2. Запись включается в результат только при том условии, что в ИМЯФАЙЛА1 она сцеплена с каждой записью из ИМЯФАЙЛА2. Если, например, ИМЯФАЙЛА1 содержит записи

G2 A С В В А A В С

Gl d h h У У h d У

Fl 3 7 7 4 4 7 3 4

а ИМЯФАЙЛА2

Gl d h У

F1 3 7 4

то результат деления

ИМЯФАЙЛА1 division ИМЯФАЙЛА2

представляет собой файл

G2

А

В

В этом файле лишь одно поле - G2, которое входит в ИМЯФАЙЛА1 и не входит в ИМЯФАЙЛА2. Значение А поля G2 включено в результат деления по той причине, что в ИМЯФАЙЛА1 оно сцеплено с каждой записью ИМЯФАЙЛА2. Действительно,

в составе ИМЯФАЙЛА1 имеются все записи

G2 А А А

G1 d h У

F1 з 7 4

Значение С поля G2 не вошло в результат, поскольку в ИМЯФАЙЛА1 отсутствует запись

С d 3.

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

Запрос: перечислить номера ансамблей, в каждом из которых играют все исполнители, составляющие ансамбль Е6.

Ответ сформируем о помощью соотношения

УЧАСТНИКИ_АНСАМБЛЕЙ division

proj НОМИСП (sel НОМАНС = 'Е6' (УЧАСТНИКИ АНСАМБЛЕЙ)).

Второй операнд операции деления дает здесь список номеров всех исполнителей из ансамбля Е6.

2.13. УМНОЖЕНИЕ

Результатом операции умножения (В некоторых работах эту операцию называют декартовым произведением.- Прим. ред.)

ИМЯФАЙЛА1 product ИМЯФАЙЛА2

является совокупность записей, представляющих конкатенацию каждой записи ИМЯФАЙЛА1 с каждой записью ИМЯФАЙЛА2.

Пусть, например, даны файлы-операнды ИМЯФАЙЛА1

F1 b d

F2 4 7

и ИМЯФАЙЛА2

F3 A C

F4 4 R

В этом случае результат содержит записи

ИМЯФАЙЛА1.Fl b b d d

ИМЯФАЙЛА1.F2 4 4 7 7

ИМЯФАЙЛА2.F3 A C A C

ИМЯФАЙЛА2.F4 4 R 4 R

В образованном файле каждое поле сохраняет прежнее имя, но оно дополняется именем файла, из которого взято. Дополнительно имя предшествует имени поля и отделено от него точкой. Получающиеся при умножении составные имена, подобные ИМЯФАЙЛА1.F1, употребляются точно так же, как и простые.

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

МУЗЫКАНТЫ product СОЧИНЕНИЯ.

Если бы не использовались дополнительные имена файлов, результат операции содержал бы два поля с одинаковым именем НОММУЗ.

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

Запрос: перечислить названия всех произведений, созданных после того, как родился Эйэфский.

Ответ получим с помощью выражения

proj СОЧИНЕНИЯ. НАЗВАНИЕ

(sel СОЧИНЕНИЯ. ДАТАСОЧ > МУЗЫКАНТЫ. ДАТАРОЖ

(СОЧИНЕНИЯ prodact sel ИМЯМУЗ = 'ЭЙЭФСКИЙ' (МУЗЫКАНТЫ))).

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

Запрос: назвать всевозможные пары имен музыкантов, родившихся в одной стране.

Если просто умножить файл МУЗЫКАНТЫ на самое себя, в результат войдут пары полей с одинаковыми составными именами. Это запрещено, поскольку имена полей файла должны быть уникальными. Разрешить проблему поможет введение альтернативного имени для файла МУЗЫКАНТЫ, которое принято называть псевдонимом или али асом. Чтобы задать это имя, перед последовательностью операций реляционной алгебры, формирующих ответ на запрос, необходимо поместить оператор aliases:

НОВЗЫКАНТЫ aliases МУЗЫКАНТЫ;

proj МУЗЫКАНТЫ. ИМЯМУЗ, НОВЗЫКАНТЫ. ИМЯМУЗ

(sel МУЗЫКАНТЫ. СТРАНАРОЖ = НОВЗЫКАНТЫ. СТРАНАРОЖ

(МУЗЫКАНТЫ product НОВЗЫКАНТЫ)).

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

НОВЗЫКАНТЫ aliases МУЗЫКАНТЫ;

proj МУЗЫКАНТЫ. ИМЯМУЗ, НОВЗЫКАНТЫ. ИМЯМУЗ

(sel (МУЗЫКАНТЫ. СТРАНАРОЖ = НОВЗЫКАНТЫ. СТРАНАРОЖ) and

(МУЗЫКАНТЫ. НОММУЗ < > НОВЗЫКАНТЫ. НОММУЗ)

(МУЗЫКАНТЫ product НОВЗЫКАНТЫ)).

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

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

относительно содержимого музыкальных файлов:

а) дать перечень номеров всех ансамблей, среди участников которых есть кларнетист или саксофонист (либо тот и другой);

б) дать перечень номеров всех ансамблей, среди участников которых есть и кларнетист, и саксофонист;

в) дать перечень номеров всех ансамблей, среди участников которых есть саксофонист, но пет кларнетистов;

г) перечислить имена всех музыкантов, не являющихся уроженцами Уайландии и родившихся не ранее 1946 г.;

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

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

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

з) назвать каждую страну, в которой исполнялись все сочинения Эйэфского;

и) назвать каждую страну, в которой не было исполнено ни одного сочинения Эйэфского;

к) перечислить названия ансамблей, дававших концерты во всех странах, в каждой из которых выступал любой из них;

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

2.15. ОПТИМИЗАЦИЯ ЗАПРОСОВ

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

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

(sel F = V (ИМЯФАЙЛА1)) join ИМЯФАЙЛА2,

записи из ИМЯФАЙЛА1 выбираются до того, как будет выполнена операция соединения. Выражение

sel F = V (ИМЯФАЙЛА1 join ИМЯФАЙЛА2)

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

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

ГЛАВА 3

ПРИНЦИПЫ НОРМАЛИЗАЦИИ

3.1. РАСПРЕДЕЛЕНИЕ ПОЛЕЙ ПО ФАЙЛАМ

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

3.2. ПОЛНАЯ ДЕКОМПОЗИЦИЯ

Начнем с простейшего примера. Рассмотрим зоологический файл, который назовем ЗВЕРИ_В_НЕВОЛЕ (ANIMALS). В нем три поля: ЗООПАРК, ЖИВОТНОЕ и ЗОНА_ОБИ-

ТАНИЯ. Предположим, что файл содержит ровно четыре записи:

ЗООПАРК эйтон эйтон БИТОН БИТОН

ЖИВОТНОЕ КЕНГУРУ ВЕРБЛЮД ЭМУ ВЕРБЛЮД

ЗОНА_ОБИТАНИЯ АВСТРАЛИЯ АРАВИЯ АВСТРАЛИЯ АРАВИЯ

Нетрудно убедиться, что результат операций

(proj ЗООПАРК, ЖИВОТНОЕ (ЗВЕРИ_В_НЕВОЛЕ))

join

(proj ЖИВОТНОЕ, ЗОНА_ОБИТАНИЯ (ЗВЕРИ_В_НЕВОЛЕ))

полностью совпадает с исходным файлом ЗВЕРИ_В_НЕВОЛЕ. В общем случае полную декомпозицию файла определяют как совокупность произвольного числа его проекций, соединение которых идентично этому файлу. В частности, приведенный пример демонстрирует, как две проекции:

proj ЗООПАРК, ЖИВОТНОЕ (ЗВЕРИ_В_НЕВОЛЕ) и

proj ЖИВОТНОЕ, ЗОНА_ОБИТАНИЯ (ЗВЕРИ_В_НЕВОЛЕ), соединяясь, образуют полную

декомпозицию файла ЗВЕРИ_В_НЕВОЛЕ.

С другой стороны, соединение проекций

proj ЗООПАРК, ЗОНА_ОБИТАНИЯ (ЗВЕРИ_В_НЕВОЛЕ) и

proj ЖИВОТНОЕ, ЗОНА_ОБИТАНИЯ (ЗВЕРИ_В_НЕВОЛЕ)

дает следующий набор записей:

ЗООПАРК эйтон эйтон ЭЙТОН БИТОН БИТОН БИТОН

ЖИВОТНОЕ КЕНГУРУ ЭМУ ВЕРБЛЮД КЕНГУРУ ЭМУ ВЕРБЛЮД

ЗОНА_ОБИТАНИЯ АВСТРАЛИЯ АВСТРАЛИЯ АРАВИЯ АВСТРАЛИЯ АВСТРАЛИЯ АРАВИЯ

В нем есть две записи

ЭЙТОН БИТОН

ЭМУ КЕНГУРУ

АВСТРАЛИЯ АВСТРАЛИЯ

которые отсутствуют в самом файле ЗВЕРИ_В_НЕВОЛЕ. Таким образом, этот набор не идентичен исходному файлу и, следовательно, соединением проекций

proj ЗООПАРК, ЗОНА_ОБИТАНИЯ (ЗВЕРИ_В_НЕВОЛЕ) и

proj ЖИВОТНОЕ, ЗОНА_ОБИТАНИЯ (ЗВЕРИ_В_ НЕВОЛЕ) нельзя получить полную декомпозицию файла ЗВЕРИ_В_НЕВОЛЕ.

Материал последующих разделов в значительной мере посвящен проблемам реляционной теории нормализации. Уместно поэтому сформулировать здесь ее основные задачи.

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

2. Определение правил выбора одной из двух альтернативных

возможностей:

а) хранить файл в его непосредственном виде или

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

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

займемся чуть позже.

3.3. ДУБЛИРОВАНИЕ ИНФОРМАЦИИ

3.3.1. ПРИМЕРЫ ДУБЛИРОВАНИЯ

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

Проиллюстрируем это на примере файла ПОСТАВЩИКИ_ТОВАРОВ, включающего три поля:

ШИФР_ТОВАРА {Уникальный номер, идентифицирующий товар}

НАЗВАНИЕ {Название фирмы-поставщика}

НОМЕР_ТЕЛЕФОНА {Телефон фирмы-поставщика}

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

ШИФР_ТОВАРА АА39 АС22 АН84 АР83 AZ27 DD68 FS44 HS41 ММ72

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

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

Можно показать (это будет сделано несколько позднее), что две проекции: proj ШИФР_ТОВАРА, НАЗВАНИЕ (ПОСТАВЩИКИ-ТОВАРОВ) и

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

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

соединение этих проекций дает файл, идентичный исходному. Проекция

proj НАЗВАНИЕ, НОМЕР_ТЕЛЕФОНА (ПОСТАВЩИКИ_ТОВАРОВ) содержит следующий набор записей:

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

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

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

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

Устранить дублирование важно по двум причинам. Во-первых, можно добиться существенной экономии памяти. Во-вторых, если какой-то элемент дублируется N раз (например, телефон фирмы <Робсон> - трижды), то при корректировании данных

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

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

каждый номер упомянут лишь однократно, в силу чего несовпадение принципиально

невозможно.

3.3.2. КЛЮЧИ-КАНДИДАТЫ

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

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