close

Вход

Забыли?

вход по аккаунту

?

PresnyakovShakhomirov

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное учреждение
высшего профессионального образования
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ
Г. В. Преснякова, А. В. Шахомиров
ПРОЕКТИРОВАНИЕ
РЕЛЯЦИОННЫХ БАЗ ДАННЫХ
Учебное пособие
Санкт-Петербург
2015
УДК 004.65(075.8)
ББК 32.81я73
П73
Рецензенты:
кандидат технических наук Г. С. Евсеев;
доктор технических наук Е. Т. Мирончиков
Утверждено
редакционно-издательским советом университета
в качестве учебного пособия
Преснякова, Г. В.
П73
Проектирование реляционных баз данных: учеб. пособие/
Г. В. Преснякова, А. В. Шахомиров. – СПб.: ГУАП, 2015. – 125 с.
ISBN 978-5-8088-1006-8
Учебное пособие содержит подробную информацию о возможных
методах проектирования реляционных баз данных. Подробно изложен формальный метод синтеза, а также теоретический материал по
основам теории реляционных структур данных, необходимый для
понимания особенностей этого метода.
Рассматривается также широко используемый в средствах автоматизированного проектирования баз данных метод ER-диаграмм,
или метод «сущность-связь», для которого предложена простая процедура уменьшения количества результирующих таблиц, основанная на модификации одного из правил данного метода. Использование этой процедуры часто приводит к совпадению результатов проектирования с результатами, полученными методом синтеза.
Предложен комбинированный метод проектирования, существенно упрощающий поиск множества функциональных зависимостей атрибутов, которые используются как исходные данные для
выполнения алгоритма синтеза.
Материал учебного пособия проиллюстрирован большим количеством примеров.
Учебное пособие предназначено для выполнения лабораторных
и курсовых работ по дисциплинам «Базы данных», «Базы данных,
базы знаний», а также может быть использовано при выполнении
квалификационных бакалаврских работ и дипломных проектов
специалистов.
Подготовлено к публикации кафедрой аэрокосмических компьютерных технологий по рекомендации методической комиссии
института аэрокосмических приборов и систем.
УДК 004.65(075.8)
ББК 32.81я73
ISBN 978-5-8088-1006-8
© Преснякова Г. В., Шахомиров А. В., 2015
© Санкт-Петербургский государственный
университет аэрокосмического
приборостроения, 2015
ВВЕДЕНИЕ
В настоящее время возможно использование нескольких методов проектирования реляционных баз данных:
– декомпозиция;
– синтез;
– метод «сущность-связь» или метод ER-диаграмм (Entity –
сущность, Relationship – связь);
– комбинированный метод (синтез + метод «сущность-связь»).
Каждый из них имеет свою сферу применения. Так, метод декомпозиции целесообразно использовать для очень простых баз
данных с небольшим количеством атрибутов или тогда, когда требуется переход к четвертой нормальной форме и выше.
Кроме того, метод декомпозиции имеет ряд существенных недостатков, о которых будет сказано ниже.
Синтез целесообразно использовать тогда, когда легко может быть
получено множество функциональных зависимостей атрибутов. Однако во многих случаях процесс построения этого множества требует
от разработчика больших усилий, особенно для «больших» баз данных с большим количеством атрибутов. Если эта трудность преодолима, то метод синтеза является, по мнению авторов, одним из лучших методов проектирования. Это хорошо формализованный метод,
который, однако, требует, как и метод декомпозиции, знания некоторых основ реляционных структур данных, которым посвящены первые разделы данного учебного пособия. Преодолеть указанную выше
трудность поможет комбинированный метод проектирования.
Метод ER-диаграмм прост, в отличие от методов декомпозиции
и синтеза не требует никаких теоретических знаний, а выполняется на основе небольшого количества правил и здравого смысла. Однако он имеет существенные недостатки, некоторые из них можно
устранить. Как? Для этого также потребуются теоретические знания в области основ реляционных структур данных.
В некоторых частных случаях результаты проектирования по методу ER-диаграмм можно приблизить к результатам проектирования
по методу синтеза до полного или почти полного совпадения. Такие
частные случаи также рассмотрены в пособии.
Все перечисленные проблемы будут подробно освещены в данном учебном пособии. Материал учебного пособия иллюстрируется
большим количеством примеров.
В приложении жирным шрифтом отмечены основные термины
и определения, необходимые для понимания материала.
3
1. ОСНОВЫ ТЕОРИИ РЕЛЯЦИОННЫХ СТРУКТУР ДАННЫХ
1.1. Определение отношения
Отношение R можно определить как множество кортежей, каждый из которых представляет собой строку V = (v1, v2,...,vk). Элементы vi кортежа V выбираются из определенных доменов, vi Di [7].
Каждый домен Di представляет собой некоторое множество значений. Так, доменами могут быть множества целых или действительных чисел, цепочек символов заданной длины, множество значений {0,1} и пр.
Длина кортежа определяется количеством элементов в нем.
Все кортежи отношения R имеют одинаковую длину k, которая
называется арностью или степенью отношения.
Отношение можно представить в виде таблицы, где каждая строка есть кортеж, и каждый столбец соответствует одному компоненту – атрибуту, значение которого определяется из соответствующего домена. Таким образом, если столбцам таблицы присвоить
имена атрибутов, то порядок столбцов станет несущественным, и
кортежи можно будет рассматривать как отображения имен атрибутов в значения, принадлежащие соответствующим доменам.
Имя отношения и список имен его атрибутов называется схемой
отношения. Так, отношение по имени R с атрибутами A1, A2,..., Ak
будем записывать в виде схемы: R (A1, A2,..., Ak) или R = A1, A2,...,
Ak или R = A1... Ak.
Совокупность схем отношений, используемых для представления реляционной модели данных, называется схемой реляционной
базы данных, а текущие значения этих отношений (экземпляры
схем отношений) – реляционной базой данных.
Пример 1. Для предметной области ПОСТАВКА_ДЕТАЛЕЙ с сущностями ПОСТАВЩИКИ и ДЕТАЛИ можно определить отношение:
PPD (PN,
p1
p1
p2
p2
p3
PIM,
Иванов
Иванов
Петров
Петров
Кротов
ST,
80
80
40
40
100
GOR,
Москва
Москва
Самара
Самара
СПб
DN,
d1
d2
d1
d2
d2
Здесь PN – номер поставщика;
PIM – имя поставщика;
ST – статус поставщика;
4
DIM,
болт
гайка
болт
гайка
гайка
CENA,
80
100
80
100
100
KOL)
100
150
50
100
200
GOR – город, в котором находится поставщик;
DN – номер детали, поставляемой поставщиком;
DIM – имя поставляемой детали;
CENA – цена поставляемой детали;
KOL – количество поставляемых деталей.
Каждая строка отношения является кортежем. Каждый кортеж
состоит из восьми элементов, поэтому арность отношения kPPD = 8.
Значения первого элемента всех кортежей (столбец PN) принадлежат домену «цепочки символов» (p1, p2, p3), значения второго
элемента всех кортежей (столбец PIM) – также цепочки символов,
…, значения восьмого элемента всех кортежей (столбец KOL) принадлежат домену целых чисел. Таким образом, домены отношения
не обязательно должны быть различны.
Если называть отношение таблицей, то обычно используют другую терминологию, а именно строки таблицы называют записями, столбцы – полями, а арность определяется количеством полей
(столбцов).
1.2. Основы реляционной алгебры
Итак, основным понятием реляционной алгебры является понятие отношения R, которое определяется как множество кортежей
длины k для некоторого фиксированного k, называемого арностью
отношения. Иногда представляется удобным присвоить имена
компонентам кортежей (атрибутам), хотя в других случаях целесообразно считать компоненты неименованными и обращаться к ним
по номерам.
В реляционной алгебре определяются пять основных операций
над отношениями, с помощью которых можно описать процедуру
получения ответа на любой запрос. Результатом операции также
является отношение.
Запрос – это операция над отношениями, результатом которой
также является отношение.
Основные операции, таким образом, образуют функционально
полный набор операций. Кроме основных, можно определить еще
и дополнительные операции, которые не расширяют функциональных возможностей основных операций и потому не являются необходимыми, но обеспечивают краткость записи процедуры получения ответа на запрос. Каждая дополнительная операция может быть
выражена через основные операции реляционной алгебры [4], [7].
5
1.2.1. Основные операции реляционной алгебры
1. Объединение (UNION).
В результате выполнения операции объединения отношений R
и S получается результирующее отношение REZ, в которое включаются кортежи, принадлежащие R или S, или им обоим (аналог
теоретико-множественной операции ИЛИ). Повторяющиеся кортежи из результирующего отношения исключаются. Последнее справедливо для любой операции реляционной алгебры.
Математическая запись: REZ = R  S. Операция объединения
применяется только к отношениям одинаковой арности, причем
kREZ = kR = kS.
Отметим, что схемы отношений-операндов могут быть различными (различные имена атрибутов). Тогда операция объединения
отношений выполнима, если соответствующие значения компонент кортежей принадлежат одному домену.
Например, для отношений-операндов R и S, схемы которых различны, результирующее отношение REZ будет безымянным:
R =A
a
d
c
B
b
a
c
C
c
f
d
и
S=D E F
b g a
d a f
;
REZ = R ∪ S =
⏐ ⏐
a b c
d a f
c c d
b g a
Такое результирующее отношение получено при условии, что
значения атрибутов (A,D) выбраны из одного домена, например, D1,
а (B,E) – из домена D2 и (C,F) – из домена D3. Если принадлежность
значений атрибутов доменам была бы другой, например, такой: (A,
E) – домену D1, (B,D) – домену D2, (C,F) – домену D3, то, прежде чем
выполнять операцию объединения, нужно было бы переставить
столбцы D и E в отношении S или – столбцы A и B в отношении R.
Если же схема отношений-операндов одинакова, то в результате
получится отношение с такой же схемой.
Пример 2. Пусть отношение R – множество кортежей поставщиков, поставляющих деталь d1, а S – множество кортежей поставщиков из Москвы (из примера 1 в разделе 1.1):
R = PN, PIM,
ST, GOR ;
p1 Иванов 80 Москва
p2 Петров 40 Самара
6
S = PN, PIM,
ST, GOR
p1 Иванов 80 Москва
В этом примере схемы отношений одинаковые и REZ = R  S
есть множество кортежей поставщиков, которые находятся в Москве, или поставляют деталь d1, или и то и другое:
REZ = PN, PIM ,
ST , GOR
p1
Иванов 80
Москва
p2
Петров 40
Самара
Используя эту операцию, можно к отношению REZ добавить новый кортеж, например, для поставщика из Петербурга (p4, Морозов, 100, СПб):
REZ = REZ  (p4, Морозов, 100, СПб)
2. Вычитание (MINUS).
Математическая запись: REZ = R \ S. В результирующее отношение включаются кортежи из R, не принадлежащие S, и арности
отношений удовлетворяют условию: kREZ = kR = kS. Для схем отношений-операндов и результирующего отношения действуют те же
ограничения, что и в операции объединения. Например:
R= A
a
d
c
B
b
a
c
C
c
f
d
и
S= D E F
b g a
d a f
;
REZ = R\ S =
⏐ ⏐
a b c
c c d
Для условий примера 2 результирующее отношение REZ = R \ S
состоит из кортежей поставщиков, поставляющих деталь d1, но не
проживающих в Москве:
REZ = PN,
p2
PIM ,
Петров
ST , GOR
40
Самара
Операция вычитания используется для удаления ненужных
кортежей отношения.
3. Декартово произведение (TIMES).
Результирующее отношение REZ = RS состоит из кортежей,
первые kR компонент которых – кортежи из R, а последние kS компонент – кортежи из S и kREZ = kR + kS (производится операция
«склеивания» кортежей отношений-операндов). Арности отношений-операндов могут быть любыми.
7
Например:
R=A B C
a b c
b b a
и
S =D E
a b
b b
;
REZ = R S = A
a
a
b
b
B
b
b
b
b
C
c
c
a
a
D
a
b
a
b
E
b
b
b
b
Декартово произведение часто используется как промежуточная
операция для получения результатов других операций, таких как
 – соединения и естественного соединения, рассмотренных далее.
4. Проекция (PROJECT).
Дает возможность построить вертикальное подмножество отношения-операнда.
Математическая запись: REZ =  i1, i2 , ..., iM (R),
где iJ – атрибуты отношения-операнда R, заданные своими именами или номерами (целыми числами из диапазона [1, kR]). Как было
сказано выше, повторяющиеся кортежи из результирующего отношения исключаются. Арности отношений REZ и R связаны условием kREZ  kR. Арность операнда может быть любой. Например:
R=A
a
b
a
B
b
b
a
C
c
c
b
D
a
c
b
;
REZ =  BC ( R ) =  2, 3 ( R ) = B
b
a
Пример 3. Пусть R = PN,
p1
p2
p3
PIM ,
Иванов
Петров
Петров
ST ,
80
40
80
C
c
b
GOR
Москва
Самара
Москва
Ответ на запрос: «Найти все города, в которых размещены поставщики» может быть получен как результат выполнения операции проекции R на атрибут GOR. Результирующее отношение получим в виде столбца:
REZ =  GOR ( R ) = GOR
Москва
Самара
8
5. Селекция, или выбор (SELECT).
Дает возможность построить горизонтальное подмножество отношения. Отбор кортежей в результирующее отношение может
производится с использованием операций:
– математических, или арифметических (+ – / * и пр.);
– отношения (<, , = , ,,>);
– логических (NOT (), AND (), OR () и пр.).
Математическая запись операции селекции: REZ = B = b (R), что
означает селектирование (выбор) из отношения R тех кортежей,
для которых значение атрибута B равно b. Следующий пример иллюстрирует использование в селекции математических операций и
операций отношения:
R= A B C
5 8 4
3 2 1
;
REZ = σ A < (B − 1) (R) = A
5
B
8
C
4
Рассмотрим пример реальных данных.
Пример 4. Пусть R = PN,
p1
p2
p3
PIM,
Иванов
Петров
Кротов
ST,
80
40
80
GOR
Москва
Самара
Москва
Ответ на запрос «Найти все имена поставщиков из Москвы»
можно получить последовательным выполнением операций селекции и проекции:
REZ = GOR = Москва (R) и далее REZ = PIM(REZ)
или с использованием вложенных выражений:
REZ = PIM(GOR = Москва (R)).
1.2.2. Дополнительные операции реляционной алгебры
6. Пересечение (INTERSECTION).
Отношений R и S дает множество кортежей, которые принадлежат как R, так и S (аналог теоретико-множественной операции И).
Математическая запись: REZ = R  S и kREZ = kR = kS.
Операция пересечения отношений выполняется при тех же ограничениях, что и операция объединения. Например:
9
R = A B C и S =D
a b c
b
b c c
a
a a b
a
E F ; REZ = R  S =  
c c
b c c
a a
a a b
a b
Операция пересечения может быть выражена через основные
операции реляционной алгебры (операцию вычитания) следующим образом:
REZ = R  S = R \ (R \ S).
Это означает, что в результирующее отношение включаются
кортежи из R НЕ (не принадлежащие S), т. е. принадлежащие S.
7. Деление (DIVISION).
Математическая запись: REZ = R  S. Деление выполнимо, если
делитель S  , атрибуты делителя образуют некоторое подмножество атрибутов делимого R и kR>kS. Арности частного, делимого и
делителя связаны условием kREZ = kR – kS. Деление – одна из самых трудных для восприятия операций, поэтому рассмотрим ее
подробнее.
Пусть u1 и u2 – кортежи делителя S. Тогда, если в делимом R
найдутся кортежи t u1 и t u2, то t – кортеж частного REZ. Будем
называть t «осколком» кортежей из R.
Таким образом, частное REZ состоит из «осколков» t длины
kR – kS таких, что для всех кортежей u из S в данном R существует
кортеж tu  R. Другими словами, если для всех кортежей делителя существуют одинаковые «осколки» кортежей делимого, то эти
«осколки» должны присутствовать в частном.
Например:
R= A B C D
a b c d
a b e f
b c e f
e d c d
e d e f
a b d e
m n c d
 tu
REZ = RS = A B
a
b
e
d
 t
Повторяющиеся кортежи из результата
исключаются.
Для того же R и S1 = C D , REZ = R S1 =A B
c d
a b
е
d
m n
и S=C D
c d  u1
e f  u2
;
Как можно выразить операцию деления через основные операции реляционной алгебры, можно узнать из работы [7].
10
Используя операцию деления, можно существенно упростить
процедуру получения ответа на запрос. Проиллюстрируем этот
факт примером.
Пример 5. Пусть задано отношение R в виде:
R = PN DN KOL
p1 d1 100
p1 d2 150
p2 d1 50
p2 d2 100
p3 d2 200
Получить ответ на запрос: «Найти номера
поставщиков, поставляющих обе детали d1, d2
(PN? DN = d1 and DN = d2 ) можно, по крайней
мере, двумя способами.
А. С помощью операции деления, если определить делитель
в виде S = DN
d1
d2.
Тогда частное будет таким:
REZ =  PN, DN ( R)  S =PN , где  PN, DN ( R) = PN , DN
p1
p1 d1
p2
p1 d2
p2 d1
p2 d2
p3 d2.
Б. Без использования операции деления, что значительно сложнее:
REZ = PN(PN, DN(R)) \ PN((PN(PN, DN(R)) x S) \ PN, DN(R)).
8. -соединение отношений (JOIN).
Осуществляется с использованием операций отношения (<, =,
 >). Математическая запись:
REZ = R S, где L , M – атрибуты, задаваемые их именами или
L M
номерами, и L  R, M  S, а  – операция отношения.
Результирующее отношение REZ – это множество кортежей арности kREZ = kR+kS, в которых атрибуты L и M связаны операцией .
Например:
R =A B C
1
4
7
2 3
5 6
8 9
и S =D E
3 1
6 2
;
REZ = R S = A B C D E
B<D
1 2 3 3 1
1 2 3 6 2
4 5 6 6 2
11
Операцию -соединения легче выразить через основные операции реляционной алгебры, если использовать не имена, а номера
атрибутов:
REZ = R S =  M (k
MN
R + N)
(R S),
где M и N – номера атрибутов в пределах своих отношений R и S
соответственно, а kR – арность отношения R.
Если в качестве операции  используется равенство (equal), то
такое соединение называется эквисоединением.
Отношения-операнды могут иметь общие атрибуты, которые
всегда будут присутствовать в схеме результирующего отношения, даже если -операцией является равенство. Например (общие
атрибуты в отношениях-операндах выделены):
R=A
1
4
2
B
2
1
4
C и S =B D L
3
4 2 2
3
2 1 1
5
;
R  S = A R.B C S.B D
1
2 3 4 2
1
2 3 2 1
4
1 3 4 2
4
1 3 2 1
2
4 5 4 2
2
4 5 2 1
L
2
1
2
1
2
1
(+)
(+)
Выделенные в декартовом произведении кортежи войдут в результирующее отношение.
Таким образом:
REZ = R S = A R .B C
B=B
1
2 3
2
4 5
S.B D
2
1
4
2
L.
1
2
В этом примере принадлежность атрибута определенному отношению изображается с использованием префикса, в качестве которого выступает имя отношения, например, R.B и S.B.
9. Естественное соединение отношений (JOIN).
Математическая запись: REZ = R  S.
Операция выполняется как эквисоединение отношений по общим атрибутам. Атрибуты задаются только именами. Операция
выполняется за три шага.
Шаг 1. Вычисляем декартово произведение отношений-операндов RS. Например:
12
R = AB
a b
d b
b b
c a
C и
c
c
f
d
S =B C D ;
b c d
b c e
RS = A
a
a
d
d
b
b
c
c
R.B R.C S.B S.C
b
c
b
c
b
c
b
c
b
c
b
c
b
c
b
c
b
f
b
c
b
f
b
c
a
d
b
c
a
d
b
c
D
d (+)
e (+)
d (+)
e (+)
d
e
d
e
Шаг 2. Из декартова произведения отбираем кортежи, у которых
равны значения общих атрибутов. В примере: R.B = S.B и R.C = S.C.
Такие кортежи отмечены (+).
Шаг 3. Перенесем отмеченные кортежи в результирующее отношение REZ, исключая повторяющиеся кортежи и используя общие
атрибуты один раз. Тогда
REZ = R S = A B C D
BC
a
a
d
d
b
b
b
b
c
c
c
c
d
e
d
e
Перед выполнением операции естественного соединения обычно
осуществляется сортировка отношений-операндов по общим атрибутам.
Указанная выше последовательность шагов позволяет понять,
что операцию естественного соединения можно выразить через основные операции реляционной алгебры следующим образом:
REZ = R  S = L ,..., L , N ,..., N ((R. N = S. N ) ...  (R. N = S. N )
1
m 1
k
1
1
k
k
(RS)),
где L1,..., Lm, N1,..., Nk – атрибуты декартова произведения, из которых N1,..., Nk являются общими атрибутами для отношений R и S.
Пример 6. Пусть R = PN, PIM, ST,
p1 Иванов 80
p2 Петров 40
p3 Кротов 80
GOR и S = PN,
Москва
p1
Самара
p1
Москва
p2
p2
p3
DN, KOL
d1 100
d2 150
d1
50
d2 100
d2 200
Ответ на многотабличный запрос: «Найти номера поставщиков из
Москвы, поставляющих деталь d2 в количестве больше 100 штук»
13
(PN?  GOR = Москва and DN = d2 and KOL>100)
можно получить, используя операцию естественного соединения
отношений R и S по общему атрибуту PN. Выполнив последовательность из трех шагов, указанных выше, получим естественное
соединение в виде:
R S = PN,
PN
p1
p1
p2
p2
p3
PIM,
Иванов
Иванов
Петров
Петров
Кротов
ST,
80
80
40
40
80
GOR,
Москва
Москва
Самара
Самара
Москва
DN,
d1
d2
d1
d2
d2
KOL
100
150
50
100
200
Далее, выполняя сначала селекцию естественного соединения, а
затем проекцию, получим следующую процедуру получения ответа
на запрос:
REZ =  PN((GOR = Москва)
 (DN = d2)  (KOL > 100)
(R S) ) = PN
PN
p1
p3
1.2.3. Примеры запросов
Рассмотрим несколько примеров запросов реальных данных из
предметной области ПОСТАВКА_ДЕТАЛЕЙ, используя отношения, схемы которых таковы:
Post (PN, PIM, ST, GOR);
Det (DN, DIM, CENA);
PD (PN, DN, KOL).
Эти отношения связаны между собой по общим атрибутам (выделены), что дает возможность выполнять многотабличные запросы. Для каждого запроса укажем процедуру получения ответа на
запрос, используя операции реляционной алгебры.
Пример 7. Получить сведения о поставщиках, имеющих статус 100
(* ?  ST = 100).
Процедура получения ответа на такой запрос запишется в виде:
REZ = ST = 100 (Post).
Пример 8. Удалить из отношения Post все сведения о поставщике p1 можно так:
Post = Post \ {p1, *}.
14
Пример 9. Получить номера поставщиков, поставляющих деталь d2:
(PN ?  DN = d2).
Процедура получения ответа на такой запрос запишется в виде:
REZ = PN (DN = d2 (PD)).
Пример 10. Получить номера поставщиков, поставляющих детали по цене, меньшей 150 денежных единиц (PN ?  CENA<150):
REZ = PN( CENA < 150 (Det) PD).
DN
Пример 11. Получить имена и название города поставщиков, поставляющих гайки в количестве >100 (PIM, GOR ?  DIM = гайка
AND KOL>100):
REZ = PIM, GOR(( DIM = гайка (Det)  KOL > 100(PD)) Post).
DN
PN
Пример 12. Все поставщики переехали из Москвы в СанктПетербург. Выполнить соответствующую корректировку отношения Post (PN, PIM, GOR).
Создадим сначала вспомогательное отношение T1 = GOR.
СПб
Теперь укажем процедуру получения ответа на запрос:
1. В промежуточное отношение T2 отберем из Post кортежи для
поставщиков из Москвы: T2 = GOR = Москва (Post).
2. Выделим в отношение Т3 их номера и имена: Т3 = PN, PIM (T2).
3. Добавим к ним столбец с названием города – СПб, используя
операцию декартова произведения: T4 = T3T1. Теперь все поставщики из Москвы стали проживать в Санкт-Петербурге.
4. В промежуточное отношение T5 отберем из Post кортежи для
поставщиков не из Москвы: T5 = Post \ T2.
5. Объединим данные о поставщиках не из Москвы с данными
о поставщиках, переехавших в Санкт-Петербург: REZ = T5  T4.
Указанную процедуру можно записать одним оператором:
REZ = (Post \ GOR = Москва (Post)) 
(PN, PIM (GOR = Москва (Post))T1).
Поставив в соответствие каждой операции реляционной алгебры оператор языка запросов, можно сконструировать простой язык
15
запросов реляционной алгебры. Поскольку набор операций обладает функциональной полнотой, этим же свойством будет обладать и
сконструированный язык запросов. С его помощью можно написать процедуру получения ответа на любой сколь угодно сложный
запрос. Например, для рассматриваемого примера процедура получения ответа на запрос может быть записана как последовательность операторов:
1. SELECT Post WHERE GOR = Москва GIVING T2.
2. PROJECT T2 OVER PN, PIM GIVING T3.
3. T3 TIMES T1 GIVING T4.
4. Post MINUS T2 GIVING T5.
5. T5 UNION T4 GIVING REZ.
Используя идею вложенности операторов (подставляя вместо
Т2, Т3, Т4 и Т5 полученные для них выражения), перечисленную
выше цепочку операторов можно представить одним оператором
в виде:
(PostMINUS (SELECT Post WHERE GOR = Москва))
UNION
((PROJECT (SELECT Post WHERE GOR = Москва) OVER PN, PIM) TIMES T1)
GIVING REZ.
Язык запросов реляционной алгебры был исторически первым
языком запросов, который использовали ранние СУБД. Однако у
него есть один существенный недостаток, а именно процедурность.
Это означает, что нужно указывать последовательность выполнения операторов для получения ответа на запрос. Иногда более
простое выражение может потребовать большего времени для выполнения процедуры, чем более сложное выражение. Это привело к необходимости создания достаточно сложных оптимизаторов
запросов. В конце концов разработчики СУБД от языков запросов
реляционной алгебры отказались и начали использовать непроцедурные (или слабо процедурные) языки запросов, основанные на
реляционном исчислении. Таким языком запросов является SQL
(Structured Query Language) – структурированный язык запросов,
который в настоящее время широко используется почти во всех
реляционных СУБД и имеет несколько стандартов. На языке SQL
не надо указывать процедуру получения ответа на запрос, а нужно определить, что нужно делать, откуда брать данные, при каком
условии и что мы хотим получить в ответе. Так, например, запрос
на JET SQL (стандарт для СУБД Microsoft Access) будет сформулирован так:
16
Для примера 8:
DELETE *
FROM Post
WHERE PN = "p1";
Для примера 7:
SELECT Post.*
FROM Post
WHERE ST = 100;
Для примера 9:
SELECT PN
FROM PD
WHERE DN = "d2";
Для примера 11:
SELECT PIM, GOR
FROM Post, Det, PD
WHERE (DIM="гайка") AND (KOL > 100) AND
(Det.DN = PD.DN) AND (Post .PN = PD.PN);
Для примера 10:
SELECT DISTINCT PN
FROM Det, PD
WHERE (CENA<150) AND
(Det.DN = PD.DN);
Для примера 12:
UPDATE Post SET GOR = "СПб "
WHERE GOR = " Москва".
1.3. Функциональные зависимости атрибутов
1.3.1. Основные определения
Говорят, что атрибут X функционально определяет Y или Y
функционально зависит от X (записывается как X  Y), если в
любом экземпляре схемы R каждому значению атрибута X (левая
часть зависимости) в каждый момент времени соответствует точно
одно значение Y (правая часть зависимости).
Например, пусть R = XYZ и задан экземпляр схемы R в виде:
r(R) = X
a
m
a
Y
b
b
b
Z
c
b
d
Тогда, если во всех возможных экземплярах схемы R справедливы те же зависимости, что и в r(R), можно сделать вывод о существовании функциональной зависимости XY (так как для X = a всегда
Y = b) и отсутствии зависимости Y  Z (так как для Y = b Z принимает разные значения: c, b, d). Также отсутствует зависимость Y  X
(так как для Y = b X принимает разные значения: a и m). Отсутствие
зависимости будем обозначать так: X ↛ Y.
Аналогично можно определить понятие функциональной зависимости между наборами атрибутов X, Y отношения R = A1, A2,...,
Ak, когда X  {A1,...,Ak} и Y  {A1,...,Ak}.
Заметим, что из существования зависимости X  Y вовсе не следует существование зависимости Y  X. Этот факт легко просматривается в только что приведенном примере.
17
Левую часть зависимости называют детерминантом, а правую –
зависимой частью [5], [7].
Зависимости, в которых правая часть содержится в левой, будем называть тривиальными зависимостями, например, AB  A.
Впервые концепция функциональной зависимости была предложена Коддом [11].
Для наборов атрибутов расширяют понятие функциональной зависимости до понятия полной функциональной зависимости, о которой будет сказано в разделе 1.9.2.
Зная семантику данных предметной области ПОСТАВКА_ДЕТАЛЕЙ с сущностями ПОСТАВЩИКИ, ДЕТАЛИ на множестве
атрибутов U = {PN, PIM, ST, GOR, DN, DIM, CENA, KOL}, можно
определить следующее множество функциональных зависимостей
(набор атрибутов взят из примера 1):
F = {PN  PIM, PN  GOR, PN  ST, GOR  ST, DN  DIM,
DN  CENA, (PN,DN)  KOL}.
Множество F может содержать не все зависимости. Некоторые
зависимости могут быть получены путем логического вывода из
F-зависимостей. Например, если в F имеются зависимости PN  GOR
и GOR  ST (подчеркнуты), то зависимость PN  ST логически
следует из них транзитивно.
Можно утверждать, что если некоторый набор атрибутов X является первичным ключом схемы отношения R, то будет справедлива любая функциональная зависимость вида X  Y, где Y – любое множество атрибутов схемы R. Этот факт следует из определения функциональной зависимости атрибутов.
Итак, пусть F – некоторое множество функциональных зависимостей, справедливых для схемы отношения R на множестве атрибутов U, а X  Y – некоторая функциональная зависимость, такая,
что (X  Y)  F и X, Y  U. Говорят, что зависимость X  Y логически следует из F, если для каждого экземпляра отношения r(R),
удовлетворяющего всем зависимостям из F, также имеет место зависимость X  Y.
Важно уметь выводить зависимости из заданного множества
функциональных зависимостей. Такую возможность предоставляют аксиомы и правила вывода функциональных зависимостей
атрибутов.
18
1.3.2. Аксиомы и правила вывода
функциональных зависимостей
Итак, для вывода одних зависимостей из других используют аксиомы Армстронга и правила вывода функциональных зависимостей,
базирующиеся на этих аксиомах [1], [7]. Рассмотрим их подробнее.
Аксиома рефлексивности. Если Y  X  U, где U – множество
всех атрибутов, зависимость X  Y логически следует из F.
Например, пусть U = ABC и X = {A,B}, а Y = {A}. Тогда по аксиоме рефлексивности будет справедливой зависимость AB  A.
Видно, что эта аксиома дает только тривиальные зависимости,
в которых правая часть содержится в левой.
Аксиома пополнения. Если справедлива зависимость X  Y и
Z  U, то также будет справедливой и зависимость XZ  YZ, т. е.
левая и правая части зависимости могут быть пополнены одинаковым набором атрибутов (в данном случае Z).
Например, если для заданного множества атрибутов U = ABCD
справедлива зависимость A  B, то будут справедливы также и зависимости AC  BC, AD  BD, ACD  BCD, AA  BA и так далее.
Аксиома транзитивности. Если справедливы зависимости X  Y
и Y  Z, то также справедлива и зависимость X  Z.
Аксиома коммутативности. Из справедливости зависимости
XY Z следует справедливость зависимости YX  Z.
Аксиома-свертка. Зависимость XX  Y может быть заменена
зависимостью X  Y.
Перечисленные выше аксиомы являются непротиворечивыми,
надежными, т. е. приводят только к истинным заключениям, и
полными, т. е. с их помощью можно получить любое справедливое
следствие из исходного множества функциональных зависимостей
F. На основе этих аксиом строятся следующие правила вывода зависимостей.
Правило объединения. Пусть заданы U, F и X,Y,Z  U. Если
справедливы зависимости X  Y и X  Z, то также будет справедливой и зависимость X  YZ (объединение по правым частям).
Правило псевдотранзитивности. Если справедливы зависимости X  Y и WY  Z, то будет справедливой и зависимость XW  Z,
где X, Y, W  U.
Правило декомпозиции (разложения). Если справедлива зависимость X  Y и Z  Y, то будет также справедливой и зависимость
X  Z (декомпозиция правой части). Например, если для некоторого набора атрибутов U = ABCD справедлива зависимость A  BCD,
19
то будут справедливы и зависимости A  B, A  C, A  D, A  BC,
A  BD, A  CD.
Пример 13. Для приведенного ниже экземпляра отношения R
справедливо следующее множество функциональных зависимостей: F = {A  B, A  C}.
r(R) = A
a
m
a
e
m
z
B
b
b
b
f
b
b
C
c
k
c
k
k
k
D
d
b
s
l
d
l
Попробуем из полученного множества F
логически вывести зависимости
AB  B (), AC  B, AD  B, ABC  B(),
ABD  B(),ACD  B, ABCD  B(),
AB  C, . . .
Зависимости, отмеченные символом (), являются тривиальными и могут быть получены по аксиоме рефлексивности.
Зависимость AC  B выводится следующим образом. Из зависимости (A  B)  F по аксиоме пополнения следует зависимость
AC BC (левую и правую части зависимости A  B пополнили атрибутом С), из которой по правилу декомпозиции получаем зависимость AC  B. Аналогично можно вывести зависимости AD  B,
ACD  B и другие зависимости.
Если зависимость (A  B)  F и U = ABCDE..., то из нее выводимы все нетривиальные зависимости вида AC  B, ACD  B,
ACDE  B,..., т. е. левую часть любой зависимости из F можно пополнять любым количеством любых атрибутов из множества U.
Построение множества функциональных зависимостей F – один
из самых ответственных процессов, который выполняется проектировщиком базы данных на основе анализа семантики данных.
Этот процесс не поддается полной формализации, а потому является «слабым» звеном проектирования. С другой стороны, его результаты используются как исходные данные на последующих,
полностью формализованных этапах проектирования. Поэтому
построение F следует выполнять особенно тщательно, многократно
перепроверяя результат.
При построении множества F нужно стремиться к уменьшению
количества зависимостей в нем. Одна из причин этого состоит в том,
что функциональные зависимости являются ограничением целостности для отношений [6] базы данных. Это означает, что каждая
зависимость должна выполняться всегда при любых экземплярах
20
отношений, что накладывает определенные ограничения на все допустимые значения атрибутов, и при каждом обновлении данных
все зависимости должны быть проверены. Очевидным способом
сокращения размера множества F является исключение тривиальных зависимостей, т. е. таких зависимостей, которые не могут не
выполняться, например {PN, DN}  PN, а также зависимостей, выводимых из некоторого «базисного» набора зависимостей.
Заметим, что при построении множества функциональных зависимостей подчас и не нужно стремиться к нахождению только «базисных» зависимостей. Множество F может содержать и больше
зависимостей, поскольку существуют формальные процедуры для
уменьшения количества зависимостей в F путем удаления «лишних», т. е. зависимостей, выводимых из оставшихся. Некоторые из
таких процедур будут описаны в разделах 1.7 и 2.2.
В основе процедуры построения множества F лежит метод перебора атрибутов и их наборов. Однако использование аксиом и правил вывода функциональных зависимостей и некоторых вспомогательных приемов может несколько уменьшить перебор. Для того
чтобы дать рекомендации по уменьшению перебора атрибутов, необходимо изучить некоторые теоретические вопросы. Поэтому дадим эти рекомендации позднее, а сейчас рассмотрим простой пример построения множества F на основе полного перебора атрибутов
и их наборов на реальных данных.
Пример 14 [7]. Пусть схемой базы данных является график вылета самолетов из аэропорта, задаваемый в виде отношения со схемой
ГРАФИК (ПИЛОТ, РЕЙС, ДАТА_ВЫЛЕТА, ВРЕМЯ_ВЫЛЕТА).
Для предварительного анализа семантики атрибутов можно
указать экземпляр этого отношения, например:
r(ГРАФИК) = ПИЛОТ,
Иванов
Петров
Иванов
Петров
РЕЙС,
83
281
301
83
ДАТА,
10.08
10.08
10.08
11.08
ВРЕМЯ
10:15
15:30
18:10
10:15
Поскольку анализ семантики данных следует проводить на всех
возможных экземплярах отношения, то следует попытаться экстраполировать наши представления о семантике данных, полученных из одного экземпляра, на другие экземпляры схемы. Иногда
для этого полезно построить абстрактный экземпляр схемы, из которого была бы понятна семантика данных, например такой:
21
ПИЛОТ, РЕЙС, ДАТА, ВРЕМЯ
p1
r1
d1
v1
p1
r2
d1
v2
p1
r1
d2
v1
p1
r2
d2
v2
p2
r1
d3
v1
p2
r2
d3
v2
Первый кортеж абстpактного экземпляра пишем произвольно,
например p1, r1, d1, v1. Второй и далее – со смыслом, рассуждая
примерно следующим образом. Если возможен кортеж для того же
пилота, то во втором кортеже пишем также p1. Пилот p1 не может в
один день выполнить еще раз тот же рейс при условии, что каждый
рейс отправляется в любой день в одно и то же время. Поэтому во
втором кортеже пишем другой номер рейса, например r2. Пилот p1
может выполнить другой рейс в тот же день, поэтому пишем дату
также d1. Время этого рейса должно быть отличным от v1 при условии, что в одно и то же время может отправляться не более одного
рейса, поэтому напишем другое время отправления рейса, например v2. Продолжаем этот процесс дальше, пока не будет полностью
ясна семантика данных. Теперь будем строить множество F из полученного абстрактного экземпляра формально, используя определение функциональной зависимости атрибутов, которое было
дано в разделе 1.3.1. Будем строить только нетривиальные функциональные зависимости с одиночным атрибутом в правых частях,
поскольку этого легко добиться, используя правило декомпозиции
правых частей зависимостей. В левых частях зависимостей может
быть несколько атрибутов (один, два,..., n–1, где n – количество
атрибутов схемы базы данных). Общее количество различных левых частей – m, где
n–1
m =  C ni . Для рассматриваемого примера n = 4 и m = 14.
i=1
Шаг 1. Перечислим все возможные зависимости с одиночным
атрибутом в левой части:
ПИЛОТ→РЕЙС РЕЙС→ ПИЛОТ ДАТА → ПИЛОТ ВРЕМЯ→ПИЛОТ
ПИЛОТ→ДАТА РЕЙС → ДАТА
ДАТА→ РЕЙС
ВРЕМЯ → РЕЙС ⊕
ПИЛОТ→ВРЕМЯ РЕЙС → ВРЕМЯ ⊕ ДАТА → ВРЕМЯ ВРЕМЯ→ДАТА
Воспользовавшись определением функциональных зависимостей атрибутов, найдем зависимости, справедливые на абстракт22
ном экземпляре. Отметим их символом  и будем считать эти зависимости первым «базисным» набором, который должен быть включен в конструируемое множество F. Неотмеченные зависимости на
абстрактном экземпляре не выполняются.
Таким образом получен первый «базисный» набор из двух зависимостей:
{РЕЙС  ВРЕМЯ, ВРЕМЯ  РЕЙС}
Шаг 2. Перечислим все возможные зависимости с двумя атрибутами в левых частях:
ПИЛОТ, РЕЙС  ДАТА
ПИЛОТ, РЕЙС  ВРЕМЯ 
РЕЙС, ДАТА  ПИЛОТ 
РЕЙС, ДАТА  ВРЕМЯ 
ПИЛОТ, ДАТА  РЕЙС
ПИЛОТ, ДАТА  ВРЕМЯ
РЕЙС, ВРЕМЯ  ПИЛОТ
РЕЙС, ВРЕМЯ  ДАТА
ПИЛОТ, ВРЕМЯ  РЕЙС 
ПИЛОТ, ВРЕМЯ  ДАТА
ДАТА, ВРЕМЯ  ПИЛОТ 
ДАТА, ВРЕМЯ  РЕЙС 
Отмеченные зависимости выполняются на абстрактном экземпляре. Однако, зависимости, отмеченные символом , логически
выводимы из зависимостей, полученных на шаге 1, поэтому их
можно не включать в конструируемое множество F. Например, зависимость (ПИЛОТ, РЕЙС)  ВРЕМЯ выводится из зависимости
РЕЙС  ВРЕМЯ следующим образом:
– следуя аксиоме пополнения, пополним обе части зависимости
РЕЙС ВРЕМЯ атрибутом ПИЛОТ. Получим зависимость (ПИЛОТ, РЕЙС)  (ПИЛОТ, ВРЕМЯ);
– по правилу декомпозиции правой части эта зависимость может быть заменена двумя зависимостями: тривиальной зависимостью (ПИЛОТ, РЕЙС)  ПИЛОТ и зависимостью (ПИЛОТ, РЕЙС) 
 ВРЕМЯ.
Аналогично выводится из той же зависимости РЕЙС  ВРЕМЯ
и зависимость (РЕЙС, ДАТА)  ВРЕМЯ.
Зависимости (ПИЛОТ, ВРЕМЯ)  РЕЙС и (ДАТА, ВРЕМЯ) 
РЕЙС выводятся из зависимости ВРЕМЯ  РЕЙС также по аксиоме пополнения и правилу декомпозиции.
Зависимости, отмеченные символом , не выводятся из зависимостей, полученных на шаге 1, а потому они должны быть добавлены к первому «базисному» набору. В результате получим «базисный» набор уже из четырех зависимостей:
23
{РЕЙС  ВРЕМЯ, ВРЕМЯ  РЕЙС, (РЕЙС, ДАТА)  ПИЛОТ,
(ДАТА, ВРЕМЯ)  ПИЛОТ}
Шаг 3. Перечислим все возможные зависимости с тремя атрибутами в левых частях:
ПИЛОТ, РЕЙС, ДАТА  ВРЕМЯ 
ПИЛОТ, РЕЙС, ВРЕМЯ  ДАТА
ПИЛОТ, ДАТА, ВРЕМЯ  РЕЙС 
РЕЙС, ДАТА , ВРЕМЯ  ПИЛОТ 
Отмеченные зависимости выполняются на абстрактном экземпляре. Видно, что зависимость (ПИЛОТ, РЕЙС, ДАТА)  ВРЕМЯ
выводима из зависимости РЕЙС  ВРЕМЯ, зависимость (ПИЛОТ,
ДАТА ВРЕМЯ)  РЕЙС – из зависимости ВРЕМЯ  РЕЙС, а зависимость (РЕЙС, ДАТА, ВРЕМЯ)  ПИЛОТ – из зависимости
(ДАТА, ВРЕМЯ)  ПИЛОТ.
Итак, на шаге 3 не удается пополнить «базисный» набор зависимостей, а потому результирующее множество зависимостей можно
записать в виде:
F = {РЕЙС ВРЕМЯ, ВРЕМЯ  РЕЙС, (РЕЙС, ДАТА)  ПИЛОТ,
(ДАТА, ВРЕМЯ)  ПИЛОТ}
Еще раз проанализируем полученное множество зависимостей.
Оказывается, что зависимость (ДАТА, ВРЕМЯ)  ПИЛОТ также
выводима из остальных зависимостей множества F следующим образом.
Пополним зависимость ВРЕМЯ  РЕЙС атрибутом ДАТА. Получим зависимость (ДАТА, ВРЕМЯ)  (РЕЙС, ДАТА). Тогда зависимость (ДАТА, ВРЕМЯ)  ПИЛОТ транзитивно выводима из
зависимостей
(ДАТА, ВРЕМЯ)  (РЕЙС, ДАТА)
(РЕЙС, ДАТА)  ПИЛОТ
Только что полученная зависимость также просто выводится из
остальных зависимостей, как и предыдущие зависимости. Но так
бывает не всегда. Иногда не удается сразу найти простой вывод для
какой-нибудь зависимости. В этом случае хотелось бы не мучить
себя поиском процедуры вывода, а решить вопрос принципиально
о возможности вывода одной зависимости из других зависимостей.
Другими словами, полезно уметь устанавливать факт выводимости
одной зависимости из других. Если факт выводимости какой-либо зависимости будет установлен (теорема 1 из раздела 1.4), тогда
можно ее не выводить, а просто удалить, как «лишнюю», из множества F.
24
Итак, для рассматриваемого примера окончательно имеем:
F = {РЕЙС  ВРЕМЯ, ВРЕМЯ  РЕЙС, (РЕЙС, ДАТА)  ПИЛОТ}
Заметим, что при построении множества функциональных зависимостей подчас и не нужно стремиться к нахождению только «базисных» зависимостей. Множество F может содержать и больше
зависимостей, поскольку существуют формальные процедуры для
уменьшения количества зависимостей в F путем удаления «лишних», т. е. выводимых из оставшихся, зависимостей. Некоторые из
таких процедур будут описаны ниже.
В только что рассмотренном примере для построения множества
F используется полный перебор возможных вариантов. Однако перебора можно избежать, если использовать комбинированный метод
проектирования, который подробно будет рассмотрен в разделе 2.5.
Для выявления «лишних» зависимостей потребуется научиться
вычислять замыкание атрибутов.
1.4. Замыкания
В теории реляционных структур данных рассматривают два
вида замыкания:
– замыкание множества функциональных зависимостей F на заданном множестве атрибутов U (обозначается F+);
– замыкание набора атрибутов X  U относительно множества
функциональных зависимостей F (обозначается X+).
Замыканием F+ множества функциональных зависимостей F на
множестве атрибутов U называется множество всех зависимостей
вида X  Y, каждая из которых или принадлежит F, или логически следует из F, включая и тривиальные зависимости.
Если F = F+, то множество F называют полным.
Вычисление замыкания F+ для известного множества функциональных зависимостей F является, как правило, трудоемкой задачей, так как множество F+ может содержать большое количество
зависимостей, даже если их немного в самом множестве F. Поэтому обычно задача построения замыкания F+ и не ставится. Однако
часто необходимо решать задачу принадлежности некоторой зависимости замыканию F+. Как следует из определения, некоторая
зависимость принадлежит замыканию F+, если она принадлежит
множеству F или выводится из него, т. е. опять нам нужно уметь
устанавливать факт выводимости одной зависимости из других.
25
Для решения этой задачи нужно использовать понятие замыкания
атрибутов.
Пусть F – множество функциональных зависимостей, определенное на множестве атрибутов U и X  U.
Замыканием X+ набора атрибутов X относительно F называется множество таких атрибутов Aj из U, зависимости которых от X
(X  Aj) логически следуют из F.
Замыкание множества атрибутов X+ обладает важным свойством [7], которое позволяет сразу определить, следует ли зависимость X  Y из множества F, т. е. установить факт выводимости
одной зависимости из других. Это свойство может быть сформулировано в виде следующей теоремы.
Теорема 1. Функциональная зависимость X  Y логически следует из F, если и только если правая часть зависимости Y содержится в замыкании атрибутов левой части зависимости, т. е. Y  X+.
Таким образом, чтобы установить факт выводимости заданной
зависимости из остальных зависимостей, надо уметь вычислять замыкание атрибутов.
Известен итерационный алгоритм вычисления замыкания атрибутов [7], который здесь приводить не будем, а рассмотрим решение
поставленной задачи на простом примере. Это решение очевидным
образом вытекает из итерационного алгоритма.
Пример 15. Пусть U = ABCDEHG и F = {A  D, AB  DE, CE  G,
E  H}.
Вычислим AB+. Замыкание набора атрибутов AB должно включать само AB и все зависимые от AB атрибуты. Таким образом,
AB+ = AB...
Чтобы добавить зависимые от AB атрибуты, надо найти в F такие
зависимости, в левых частях которых содержатся подмножества набора AB (это A, B и AB). Такими зависимостями являются A  D и
AB  DE. Тогда атрибут D зависит от A, а DE зависит от AB. Атрибуты D и E должны быть добавлены. Таким образом, AB+ = ABDE.
Другими словами, замыкание некоторого набора атрибутов содержит сам набор и все, зависимые от него, атрибуты.
Рассмотрим использование факта выводимости на следующем
простом примере.
Пример 16. Ответим на вопрос, можно ли вывести зависимости
B  D, B  CD и D  C из множества F = {B  C, C  D, A  D}?
Исследуем зависимость B  D.
26
По факту выводимости вычисляем замыкание атрибутов левой
части зависимости B  D по множеству F: B + = BCD.
Правая часть исследуемой зависимости (атрибут D) содержится
в замыкании, т. е. D  BCD, поэтому зависимость B  D выводится
из F. Как?
Множество F содержит две зависимости B  C и C  D, из которых по аксиоме транзитивности следует зависимость B  D.
Исследуем зависимость B  CD.
Замыкание атрибута левой части этой зависимости было вычислено выше и равно B + = BCD.
Правая часть исследуемой зависимости равна CD и CD  B +, поэтому зависимость B  CD выводится из F. Как?
В множестве F имеется зависимость B  C. Еще есть зависимость B  D, которая, как только что было доказано, выводится из
F. Используя правило объединения этих зависимостей по правым
частям, доказываем справедливость зависимости B  CD.
Исследуем зависимость D  C.
Замыкание левой части этой зависимости по множеству F: D+ = D.
Так как правая часть исследуемой зависимости C  D+, то по факту
выводимости зависимость D  C не выводится из F.
1.5. Алгоритмы нахождения первичного ключа
Следует разделять понятия первичного ключа отношения (таблицы) и универсального первичного ключа, который иначе называют суперключом.
Поскольку первичный ключ отношения (таблицы) является
идентифицирующим в этом отношении (таблице), то по определению функциональной зависимости первичный ключ отношения
функционально определяет все атрибуты этого отношения.
Первичный ключ, состоящий из минимального количества
атрибутов, называется минимальным ключом. Используя минимальные первичные ключи, легче обеспечивать связи между таблицами реляционной базы данных.
Аналогично универсальный первичный ключ функционально
определяет все атрибуты U всех отношений базы данных.
Заметим, что универсальный первичный ключ (суперключ) может совпадать с первичным ключом какого-либо отношения базы
данных.
Используя понятие замыкания атрибутов, можно дать формальное определение первичного ключа отношения и указать простой
27
способ, с помощью которого можно проверить, является ли заданный набор атрибутов первичным ключом отношения или нет [1], [7].
Для этого нужно вычислить замыкание атрибутов для заданного набора по множеству функциональных зависимостей, справедливых на данном отношении. И, если это замыкание включает все
атрибуты отношения, то такой набор может рассматриваться в качестве первичного ключа отношения. Если же замыкание любого
его подмножества не дает всех атрибутов отношения, то этот набор
является еще и минимальным первичным ключом.
Пример 17. Пусть база данных состоит из четырех отношений
(первичные ключи выделены):
Post (PN, PIM, GOR)
Det (DN, DIM, CENA)
PD (PN, DN, KOL)
Gorod(GOR, ST)
Эти отношения получены декомпозицией отношения PPD примера 1 из раздела 1.1. Все множество атрибутов базы данных определяется как
U = PN, PIM, ST, GOR, DN, DIM, CENA, KOL.
В разделе 1.3.1 были определены функциональные зависимости, которые справедливы на данном множестве атрибутов:
F = {PN  PIM, PN  GOR, PN  ST, GOR  ST, DN  DIM,
DN  CENA, (PN,DN)  KOL}.
Видно, что для отношения Post справедливо множество зависимостей:
FPost = {PN  PIM, PN  GOR}.
Атрибут PN действительно является первичным ключом отношения Post, так как
PN+ = PN, PIM, GOR (все множество атрибутов отношения Post).
Аналогично для отношения Det: FDet = {DN  DIM, DN  CENA}
и DN – первичный ключ отношения Det, так как DN+ = DN, DIM,
CENA.
Для отношения PD: FPD = {(PN, DN)  KOL} и (PN, DN)+ = PN, DN,
KOL. Для отношения Gorod: FGorod = {GOR  ST} и GOR+ = GOR, ST.
Универсальным первичным ключом в рассматриваемой базе
данных является набор атрибутов (PN, DN), так как замыкание
этого набора по множеству F равно полному набору атрибутов U:
28
(PN, DN) + = PN, DN, PIM, GOR, ST, DIM, CENA, KOL = U.
В рассматриваемом примере универсальный ключ совпадает с первичным ключом отношения PD. В общем случае это необязательно.
В настоящее время известны два алгоритма нахождения первичных ключей:
1. Алгоритм, основанный на последовательном исключении
атрибутов из полного набора атрибутов отношения и проверке полученного набора на ключ.
2. Алгоритм, основанный на полном переборе претендентов на
первичный ключ, начиная с одного, затем пар атрибутов и так далее.
Первый алгоритм имеет невысокую вычислительную сложность, решение находится быстро, но при этом не гарантируется
нахождение минимального первичного ключа.
Так как поиск первичного ключа по второму алгоритму может
свестись к полному перебору вариантов, то сложность его будет
выше сложности первого алгоритма. Однако данный алгоритм гарантирует нахождение минимального первичного ключа, что всегда лучше, так как упрощает реализацию базы данных за счет упрощения связей между таблицами.
Пример 18. Найдем первичный ключ отношения R = ABCDE, на
котором справедливо множество функциональных зависимостей:
F = {A  C, B  C, C  D, DE  C, CE  A}.
Алгоритм 1.
Выбираем первого претендента на первичный ключ, представляющего собой полный набор атрибутов отношения U = ABCDE.
Обозначим этот набор X = ABCDE. Удаляем из него один атрибут,
например A, и вычисляем замыкание полученного нового набора:
(X \ A)+ = (BCDE)+ = BCDEA = U.
Здесь символ «\» обозначает операцию вычитания атрибута A из
набора X.
Поскольку замыкание указанного набора атрибутов дает все
атрибуты U, то набор BCDE может быть ключом схемы отношения
R, если никакое его подмножество, в свою очередь, не может быть
ключом. Проверим это.
Итак, следующим претендентом на ключ является набор X = BCDE.
Удаляем из него, например, атрибут B и вычисляем замыкание атрибутов нового набора:
(X \ B)+ = (CDE)+ = CDEA  U.
29
Следовательно, набор CDE не может быть первичным ключом.
Возвращаем атрибут B и удаляем из набора X атрибут C. Вычисляем замыкание нового набора атрибутов:
(X \ C)+ = (BDE)+ = BDECA = U.
Следовательно, набор BDE может быть первичным ключом.
Проверим его на минимальность.
Итак, следующим претендентом на ключ является набор BDE,
т. е. X = BDE. Удаляем из него атрибут D и вычисляем замыкание
полученного набора атрибутов:
(X \ D)+ = (BE)+ = BECAD = U.
Следовательно, набор BE может быть первичным ключом. Проверим его на минимальность.
Итак, X = BE. После удаления атрибута E получим (X \ E)+ = B+ =
= BC  U, а после удаления атрибута B получим (X \ B)+ = E+ = E  U.
Отсюда следует, что атрибуты B и E не могут быть первичными
ключами. Поэтому в качестве первичного ключа можно взять последнего претендента – набор атрибутов BE. При этом мы не можем
гарантировать минимальность найденного ключа, так как при другой последовательности исключения атрибутов возможно нахождение ключа с меньшим количеством атрибутов.
Алгоритм 2.
Сначала проверяем на ключ одиночные атрибуты:
A+ = ACD U; B+ = BCD U; C+ = CD U; D+ = D U; E+ = E U.
Отсюда следует, что ни один одиночный атрибут отношения
R = ABCDE не может выступать в роли первичного ключа этого отношения.
Затем проверяем на ключ всевозможные пары атрибутов, затем
тройки атрибутов и так далее, пока не найдем набор, удовлетворяющий условиям первичного ключа. Очевидно, что найденный таким образом ключ будет минимальным.
AB+ = ABCD U; AC+ = ACD U; AD+ = ADC U; AE+ = AECD U;
BC+ = BCD U; BD+ = BDC U; BE+ = BECDA = U.
Таким образом, BE – минимальный первичный ключ исходного
отношения.
Очевидно, что приведенные выше алгоритмы также могут быть
использованы и для нахождения универсального ключа реляционной базы данных, состоящей из нескольких отношений.
30
1.6. Эквивалентность множеств функциональных
зависимостей
Понятие эквивалентности множеств функциональных зависимостей атрибутов часто используется при проектировании и анализе баз данных. Укажем хотя бы два случая, когда оно может использоваться [7].
Первый случай. При проектировании базы данных несколькими разработчиками редко удается получить одно и то же множество функциональных зависимостей на одном и том же множестве атрибутов U. Если полученные множества эквивалентны
друг другу, то проектирование, скорее всего, выполнено правильно
всеми разработчиками.
Второй случай. Полученное множество функциональных зависимостей может по каким-то причинам не устраивать разработчика. Тогда следует перейти к другому, но эквивалентному множеству зависимостей, которое отвечало бы требованиям разработчика, иначе будет нарушена семантика базы данных. Именно этот
случай мы имеем в алгоритме синтеза, который будет рассмотрен в
разделе 2.2.
Таким образом, можно считать, что только эквивалентные множества зависимостей, полученные на одном и том же множестве
атрибутов, определяют одну и ту же семантику (смысл) данных.
Пусть F и G – два множества функциональных зависимостей, заданных на одном и том же множестве атрибутов U.
Множества F и G называются эквивалентными (обозначаются
как F  G), если равны их замыкания, т. е. F+ = G+.
Чтобы проверить, являются ли два множества F и G эквивалентными, используют следующую процедуру [4], [7].
1. Для каждой зависимости (X  Y)  F проверяется ее принадлежность замыканию G+. Для этого используется факт выводимости одной зависимости из других (теорема 1 из раздела 1.4), а именно: вычисляется замыкание атрибутов X+ левой части зависимости
по множеству G и проверяется условие Y  X+. Если оно выполняется, то (X  Y)  G+.
Если каждая зависимость из F удовлетворяет этому условию, то
можно указать следующую цепочку вложений множеств:
F  F+  G+.
2. Аналогично для каждой зависимости (P  Q)  G проверяется
ее принадлежность F+. Если каждая зависимость из G удовлетво31
ряет условию (PQ)  F+, то можно указать следующую цепочку
вложений множеств:
G  G+  F+.
Очевидно обе цепочки вложений могут одновременно выполняться только при условии F+ = G+, т. е. множества функциональных зависимостей F и G эквивалентны.
Другими словами, два множества функциональных зависимостей F и G, определенные на одном и том же наборе атрибутов U,
эквивалентны тогда и только тогда, когда каждая зависимость из
F логически следует из G и наоборот, каждая зависимость из G логически следует из F.
Как только найдется зависимость, для которой это условие не
выполняется, дальнейшая проверка прекращается, и делается вывод о неэквивалентности заданных множеств зависимостей.
Пример 19. Проверим эквивалентность множеств функциональных зависимостей
F = {A  BC, A  D, CD  E} и G = {A  BCE, A  BD, CD  E}.
Прежде чем решать вопрос об эквивалентности заданных множеств зависимостей, нужно проверить на одном и том же множестве атрибутов, заданы ли данные множества или нет. Видно, что
множества F и G определены для одного и того же набора атрибутов U = ABCDE. Кроме того, зависимость CD  E присутствует как
в множестве F, так и в множестве G, поэтому из проверки может
быть исключена.
Как было сказано выше, эквивалентность множеств зависимостей проверяется за два шага.
1. Для каждой зависимости (X  Y)  F проверяем ее принадлежность замыканию G+, т. е. справедливость выражения (X  Y) 
 G+. Если это выражение справедливо, то исследуемая зависимость или содержится в G или выводится из G.
Для (A  BC)  F имеем A+(по G) = ABCED и BC  A+, поэтому
по факту выводимости (A  BC)  G+.
Для (A  D)  F имеем A+(по G) = ABCED и D  A+, поэтому
(A  D)  G+.
2. Для каждой зависимости (P  Q)  G проверяем справедливость выражения (P  Q)  F+.
Для (A  BCE)  G имеем A+(по F) = ABCDE и BCE  A+, поэтому
(A  BCE)  F+.
32
Нетрудно убедиться в принадлежности зависимости A  BD замыканию F+. Следовательно, F+ = G+ и множества F и G эквивалентны.
Пример 20. Проверим эквивалентность множеств функциональных зависимостей
F = {A  BC, A  D, CD  E} и G = {A  BE, A  B, C  ED}.
Убеждаемся, что множества зависимостей заданы на одном и
том же множестве атрибутов U = ABCDE. Делаем первый шаг.
1. Для каждой зависимости (X  Y)  F проверяем ее принадлежность замыканию G+, т. е. справедливость выражения (X  Y) 
 G+.
Для (A  BC)  F имеем A+(по G) = ABE и BC  A+, поэтому
(A  BC)  G+. Следовательно, дальнейшую проверку делать не
надо, а сразу делаем вывод о неэквивалентности заданных множеств функциональных зависимостей.
Понятие эквивалентности множеств функциональных зависимостей дает возможность замены исходного множества F другим,
эквивалентным ему множеством зависимостей G без искажения семантики данных.
1.7. Покрытия
Если множества F и G эквивалентны, то говорят, что F покрывает множество G, и наоборот, G покрывает F.
В теории реляционных структур рассматривается несколько видов покрытий:
– каноническое;
– неизбыточное, или безызбыточное;
– минимальное;
– минимальное каноническое.
Определим каждое из них.
Множество функциональных зависимостей F называется каноническим покрытием [5], [7], если:
1) правая часть каждой зависимости из F содержит единственный атрибут. Этого всегда можно добиться, используя правило декомпозиции правой части зависимости (см. раздел 1.3.2);
2) ни одна функциональная зависимость в F не является «лишней», т. е. ни для какой зависимости (X  Y)  F множества F и F \
{X  Y} не являются эквивалентными (здесь, как и прежде, знак
33
«\» означает вычитание, в данном случае вычитание зависимостей.
Очевидно, «лишней» будет зависимость, которую можно вывести
из остальных зависимостей;
3) ни один атрибут в левой части любой зависимости из F не
является «лишним». Зависимости без «лишних» атрибутов слева
называют элементарными. Так, например, если X = AZ, X  Z и
(F \ {X  Y})  {Z  Y}  F, то атрибут A в зависимости X  Y является «лишним» и его можно удалить.
Каноническое покрытие представляет только академический интерес, но не дает никаких преимуществ при реализации
базы данных. Использование же неизбыточного и минимального
покрытий при проектировании могут обеспечить эффективность
реализации базы данных. Рассмотрим их подробнее.
Множество функциональных зависимостей без «лишних» зависимостей называется неизбыточным покрытием исходного множества зависимостей F, которое будем обозначать F0.
Например, пусть F = {AB  C, A  B, B  C}. Можно показать,
что множество G = {AB  C, A  B, B  C, A  C} эквивалентно F,
но избыточно (зависимость A  C – «лишняя», так как транзитивно выводится из зависимостей A  B и B  C). Кроме того, «лишней» оказывается и зависимость AB  C, так как она выводится из
зависимостей A  B и B  C. Тогда множество F0 = {A  B, B  C}
является неизбыточным покрытием как F, так и G.
Множество функциональных зависимостей F называется минимальным, если оно содержит не больше F-зависимостей, чем любое
эквивалентное ему множество зависимостей [5].
В базах данных F-зависимости способствуют обеспечению целостности данных. Меньшее число F-зависимостей предпочтительнее, так как при этом используется меньший объем памяти и производится меньшее количество различных проверок при модификации данных, а потому гарантируется более быстрое исполнение
алгоритмов.
При проектировании базы данных методом синтеза, который будет подробно рассмотрен в разделе 2.2, каждая зависимость определяет отношение (таблицу) и стремление получить минимум зависимостей вполне оправдано.
Однако в литературе по базам данных не содержится указаний
не только на способы построения минимальных покрытий, но даже
34
на проверку минимальности. В работе [5] предлагается способ вычисления минимальных покрытий при одном частном виде функциональной определенности. Очевидно, в общем случае для построения минимальных покрытий, как и для получения оптимальных
решений, требуются алгоритмы высокой вычислительной сложности. На практике часто оптимальные решения заменяются подоптимальными, которые получить гораздо проще, а по своим характеристикам они часто незначительно уступают оптимальным решениям. При проектировании реляционных баз данных таким подоптимальным решением можно считать неизбыточное покрытие.
Однако использование неизбыточных покрытий – не единственный способ уменьшения таблиц в проектируемой базе данных.
Минимизировать количество таблиц реляционной базы данных
можно следующими способами:
построением неизбыточных покрытий;
удалением «лишних» атрибутов в левых частях зависимостей;
выявлением эквивалентных зависимостей.
Все перечисленные способы используются в методе синтеза, который будет изложен в разделе 2.2.
Рассмотрим каждый из этих способов подробнее.
1.7.1. Построение неизбыточных покрытий
Построение неизбыточного покрытия рассмотрим на следующем примере.
Пример 21. Пусть U = ABC и F = {A  B, B  A, C  A, A  C,
B  C}. Попытаемся построить неизбыточное покрытие F, т. е. множество без «лишних» зависимостей. Выберем направление просмотра зависимостей сначала слева – направо, а затем справа – налево
и покажем, что различный порядок просмотра зависимостей из F
может привести к разным результатам.
Просматриваем зависимости из F слева – направо. Для получения результата зависимости выводить не будем, а будем использовать факт выводимости конкретной зависимости из остальных зависимостей (теорема 1 из раздела 1.4).
Для зависимости A  B строим замыкание A+ (левой части этой зависимости) по множеству остальных зависимостей из F: F \ {A  B} =
= {B  A, C  A, A  C, B  C}. Здесь символ «\» означает вычитание,
в данном случае вычитание зависимостей. Получим A+ = AC. Так как
правая часть зависимости B  A+, то зависимость A  B не является
«лишней», т. е. она не выводится из остальных F-зависимостей.
35
Для зависимости B  A имеем B+ = BCA. Так как A  B+, то
зависимость B  A – «лишняя». Удалим ее из F. Получим новое
множество F1 = {A  B, C  A, A  C, B  C}.
Для зависимости C  A имеем C+ = C. Зависимость не является
«лишней».
Для зависимости A  C имеем A+ = ABC и C  A+. Зависимость
является «лишней». Удалим ее из F1. Получим F2 = {A  B, C  A,
B  C}.
Для зависимости B  C имеем B+ = B и C  B+. Зависимость не
является «лишней».
Таким образом, получили неизбыточное покрытие множества F
в виде
F0(слева – направо) = {A  B, C  A, B  C}.
Просматривая зависимости в исходном множестве F справа – налево и удаляя «лишние» зависимости, как было сделано выше, получим неизбыточное покрытие F в виде
F0(справа – налево) = {A  B, B  A, C  A, A  C}.
Видно, что полученные множества не совпадают и имеют разное
количество зависимостей, т. е. выбор направления просмотра зависимостей влияет на результат.
Существует ли процедура построения неизбыточного покрытия,
которая давала бы одинаковый результат независимо от направления просмотра зависимостей? Эта задача успешно решается, если
воспользоваться понятием расширенного множества зависимостей.
Расширение касается правых частей каждой зависимости из F.
Поскольку расширяется каждая зависимость, то количество зависимостей исходного и расширенного множеств одинаково.
Расширенное множество зависимостей ℱ строится по правилу:
 )  (X  Y )  F, Y
 = X + \ X },
ℱ = {(Xi  Y
i
i
i
i
i
i
где символ «» означает «при условии», а символом «\», как и всюду выше, обозначена операция вычитания (здесь имеется в виду

вычитание множеств атрибутов). Это означает, что правая часть Y
i
каждой зависимости расширенного множества содержит все атрибуты из U, зависимость которых от атрибутов левой части X следует из F. Поэтому, если левые части каких-либо зависимостей из F
совпадают, то и их правые части в расширенном множестве также
будут совпадать. Так удается легко выявить «лишние» зависимости с одинаковой левой частью. Вычеркнув найденные таким об36
разом «лишние» зависимости, получаем множество ℱ0, в котором
могут остаться лишние зависимости с разными левыми частями.
Поэтому множество ℱ0 будем называть условно неизбыточным или
псевдонеизбыточным покрытием F. Далее можно осуществить поиск в множестве ℱ0 «лишних» зависимостей так, как было сделано
в примере 21, результат которого уже не будет зависеть от направления просмотра зависимостей. Удаляя «лишние» зависимости,
получаем неизбыточное покрытие множества F, которое в общем
случае не является каноническим. В некоторых частных случаях
оно может быть и минимальным покрытием.
Если условно неизбыточное покрытие ℱ0 содержит большое количество зависимостей, то обычная процедура поиска «лишних»
зависимостей может оказаться утомительной. Можно показать,
что часть оставшихся «лишних» зависимостей будет находиться
среди так называемых эквивалентных зависимостей. Процедура с
использованием эквивалентных зависимостей будет подробно описана при изложении метода синтеза в разделе 2.2.
Построим расширенное множество зависимостей для примера 21.
Итак, исходное множество F = {A  B, B  A, C  A, A  C, B  C}.
Расширяем первую зависимость A  B. Для этого вычисляем
замыкание атрибутов левой части зависимости: A+ = ABC. Отсюда
следует (для обозначения следования, как и прежде, будем использовать символ ), что в расширенное множество будет включена
зависимость A  BC. Процедуру получения расширенной зависимости будем кратко записывать так: A+ = ABC  A  BC.
Для второй зависимости B  A: B+ = BAC  B  AC.
Для третьей зависимости C  A: C+ = CAB  C  AB.
Для четвертой зависимости A  C: A+ = ABC  A  BC.
Для пятой зависимости B  C: B+ = BAC  B  AC.
Таким образом, расширенное множество зависимостей будет
таким:
ℱ = {A  BC, B  AC, C  AB, A  BC, B  AC}.
В этом множестве легко определяются «лишние» зависимости
(подчеркнуты), и условно неизбыточное покрытие множества F будет включать три зависимости:
ℱ0 = {A  BC, B  AC, C  AB}.
Отметим, что это множество содержит также три зависимости,
как и минимальное покрытие F0(слева – направо), но не является каноническим.
37
1.7.2. Проверка зависимостей на элементарность
Зависимости без «лишних» атрибутов слева называются элементарными. Следующий пример показывает, как можно привести зависимости к элементарному виду.
Пример 22. Пусть множество функциональных зависимостей
F = {ABE  C, A  B, B  A} задано на множестве атрибутов U = ABCE.
Очевидно, анализу на элементарность должны подвергаться
зависимости, в левой части которых содержится несколько атрибутов. В данном примере такой зависимостью является ABE  C.
Остальные зависимости уже являются элементарными.
Попытаемся исключить атрибут A, т. е. проверим справедливость зависимости BE  C. Для этого, используя факт выводимости
зависимости, вычислим (BE)+ = BEAC. Правая часть этой зависимости C  (BE)+. Следовательно, зависимость BE  C выводится из
F, т. е. (BE  C)  F+, и атрибут A можно исключить. В результате множество F можно заменить на F1 = {BE  C, A  B, B  A}.
Рассмотрим теперь полученную зависимость BE  C и попытаемся
исключить из нее атрибут B. Чтобы это можно было сделать, установим справедливость зависимости E  C. Так как E+ = E и C  E+,
делаем вывод о невозможности исключения B.
Попытаемся теперь из зависимости BE  C исключить атрибут E, т. е. установить справедливость зависимости B  C. Так как
B+ = BA и C  B+, делаем вывод о невозможности исключения атрибута E. Таким образом, окончательно имеем
F1 = {BE  C, A  B, B  A}.
Множество F1 содержит только элементарные зависимости, но
количество зависимостей не уменьшилось.
Нетрудно показать, что множества F и F1 эквивалентны.
В рассмотренной процедуре порядок просмотра зависимостей
также влияет на результат. Формальная процедура, оптимизирующая этот процесс, в настоящее время неизвестна. Однако известна
рекомендация о первоочередном анализе на избыточность атрибутов той зависимости, которая содержит наибольшее количество
атрибутов в левой части.
В следующем примере показано, как приведение зависимостей
к элементарному виду может уменьшить их количество.
Пример 23. Пусть множество функциональных зависимостей
F = {L  KA, A  DOXZC, DEM  K, D  EK} справедливо на множестве атрибутов U = ACDEKLMOXZ.
38
Проанализируем зависимость DEM  K на элементарность.
Остальные зависимости уже являются элементарными.
Пытаемся из анализируемой зависимости исключить атрибут D.
Используя факт выводимости, установим справедливость зависимости EM  K. Так как EM+ = EM и K  EM+, делаем вывод о невозможности исключения D.
Пытаемся из зависимости DEM  K исключить атрибут E,
т. е. проверяем справедливость зависимости DMK. Так как
DM+ = DMEK и K  DM+, атрибут E можно исключить. В результате множество F можно заменить на F1 = {L  KA, A  DOXZC,
DM  K, D  EK}.
Продолжаем процесс исключения атрибутов теперь уже из зависимости DM  K.
Пытаемся исключить из этой зависимости атрибут M. Так как
D+ = DEK и K  D+, атрибут M можно исключить. В результате множество F1 можно заменить на F2 = {L  KA, A  DOXZC, D  K,
D  EK}. Поскольку зависимость D  K получается из декомпозиции правой части зависимости D  EK, D  K является лишней и
ее можно исключить из F2.
Таким образом, вместо F окончательно имеем множество F3 = {L 
KA, A  DOXZC, D  EK}, которое содержит меньше зависимостей, чем исходное множество F.
Несложно показать, что множества F и F3 эквивалентны.
1.7.3. Поиск эквивалентных зависимостей
Используя понятие эквивалентности зависимостей, можно также уменьшить количество зависимостей в исходном множестве.
Рассмотрим, почему это происходит.
Зависимости Xi  Yi и Xj  Yj будем называть эквивалентными, если (Xi  Yi) = (Xj  Yj). Например, эквивалентными будут
зависимости A  BCD и AB  CD. Набор эквивалентных между
собой зависимостей называют классом эквивалентности. Очевидно, зависимости из одного класса эквивалентности дадут схемы
отношений с одинаковым набором атрибутов. Если каждой зависимости будет соответствовать таблица в базе данных, то эквивалентные зависимости дадут таблицы с одинаковым набором
полей. Иметь в базе данных несколько таблиц с одинаковым набором полей бессмысленно. В этом случае целесообразно в каждом
классе эквивалентности оставлять одного (почти всегда любого)
представителя.
39
Пример 24. Пусть множество функциональных зависимостей
F = {A  BCD, CDА  B, C  EMK, KMС  E, E  B} справедливо
на множестве атрибутов U = ABCDEKM.
Видно, что множество F содержит два класса эквивалентности
(один класс выделен жирным шрифтом, другой – подчеркиванием).
Оставляем одного, в данном случае любого представителя в
каждом классе эквивалентности. Поскольку в методе синтеза левые части зависимостей определяют первичные ключи таблицы, то
в рассматриваемом примере оставляем в качестве представителей
классов эквивалентности зависимости с одиночными атрибутами в
левых частях. В результате получаем новое множество зависимостей: F1 = {A  BCD, C  EMK, E  B}, которое содержит меньше
зависимостей, чем исходное множество F.
Нетрудно показать, что множества F и F1 эквивалентны.
1.8. Декомпозиция схем отношений
1.8.1. Понятие декомпозиции
Декомпозицией схемы отношения R = A1,..., Ak называется замена ее совокупностью  = {R1, R2,..., RS} возможно пересекающихся подмножеств Rj  R, j = 1, 2,..., S, таких как R1  R2 ...  RS = R.
Каждое множество Rj   называется декомпозиционной подсхемой.
Декомпозиция – важная операция разбиения схемы отношения на множество декомпозиционных подсхем, которая может использоваться для исключения некоторых недостатков, присущих
исходной одной схеме отношения. Отметим основные недостатки
[2],[7] отношения PPD из примера 1 раздела 1.1. Итак, имеем отношение:
PPD (PN,
p1
p1
p2
p2
p3
PIM,
Иванов
Иванов
Петров
Петров
Кротов
ST,
80
80
40
40
100
GOR,
Москва
Москва
Самара
Самара
СПб
DN,
d1
d2
d1
d2
d2
DIM,
болт
гайка
болт
гайка
гайка
CENA,
80
100
80
100
100
KOL) кортежи
100
к1
150
к2
50
к3
100
к4
200
к5
1. Потенциальная избыточность.
Если на множестве атрибутов схемы отношения R справедлива
зависимость X Y, то по определению функциональной зависимости все кортежи отношения, совпадающие по значениям атрибутов
40
из набора X, должны совпадать и по значениям атрибутов из набора
Y. Например, в отношении PPD если номер поставщика PN = p1, то
значение атрибута PIM должно быть всегда «Иванов», поскольку
справедлива зависимость PN  PIM. Таким образом, если поставщик p1 поставляет более одного вида деталей, то его имя будет повторено много раз.
2. Потенциальная противоречивость.
Изменение в одном из кортежей значений атрибутов из набора
X  Y при наличии функциональной зависимости X  Y может
привести к нарушению этой зависимости в других кортежах отношения. Например, изменение в кортеже k1 значений атрибутов из
набора PN  PIM (номер поставщика изменим на p3 или имя поставщика изменим на «Сидоров») может привести к нарушению зависимости PN  PIM в кортеже k2 (если изменили значение PIM)
или в кортеже k5 (если изменили значение PN).
3. Аномалии включения.
Если на множестве атрибутов X0, X1, X2,Y в отношении R справедливы зависимости (X0  X1)  Y и (X0  X2)  Y, то при добавлении или изменении значений атрибутов из набора X0, X1, Y
или X0, X2, Y возникают проблемы проверки непротиворечивости
данных по наборам X0, X1, Y или X0, X2, Y соответственно. Эта же
проблема возникает, если на момент включения новых данных по
набору X0, X1, Y значения X2 не определены или – по набору X0,
X2, Y значения X1 не определены. Так, в отношение PPD нельзя
включить кортеж о новом поставщике, пока он не начнет поставлять какую-либо деталь.
4. Аномалии удаления.
Если на множестве атрибутов справедливы зависимости X  Y
и Y  Z, т. е. имеется транзитивная зависимость X  Z, то при удалении из отношения кортежей со значением, например y0 атрибута
Y, может возникнуть проблема сохранения соответствия значений
x0 и z0 атрибутов X и Z в зависимости X  Z. Например, в отношении PPD справедливы зависимости PN  GOR и GOR  ST, т. е.
имеется транзитивная зависимость PN  ST. При удалении из отношения двух кортежей k2 и k4 зависимость PN  ST может быть
потеряна. В таком случае нужны специальные средства поддержания всех существующих зависимостей, что вызывает определенные трудности.
Замена исходной схемы отношения R множеством  декомпозиционных подсхем позволяет исключить перечисленные выше недостатки исходной одной схемы отношения.
41
1.8.2. Свойства декомпозиции
Однако не всякую декомпозицию можно использовать. Любая декомпозиция схемы отношения должна обладать двумя свойствами:
соединением без потерь информации относительно заданного
множества функциональных зависимостей F;
сохранением исходного множества функциональных зависимостей на заданном множестве атрибутов U.
1.8.2.1. Свойство соединения без потерь информации
Декомпозиция  = {R1, R2,..., RS} схемы отношения R обладает
свойством соединения без потерь информации относительно множества функциональных зависимостей F, справедливых на схеме,
если каждый экземпляр схемы отношения R восстанавливается из
соединения проекций этого экземпляра на каждую декомпозиционную подсхему из  [7].
Выполнимость этого свойства необходима для получения релевантных многотабличному запросу ответов, в которых участвуют
атрибуты нескольких декомпозиционных подсхем по следующей
причине. Если выполнена декомпозиция исходной схемы отношения R, то данные хранятся в базе данных не в виде экземпляров
r(R), а в виде экземпляров декомпозиционных подсхем r(Ri). Для
получения ответов на многотабличные запросы необходимо выполнять операцию соединения соответствующих экземпляров декомпозиционных подсхем.
Невыполнимость свойства соединения без потерь информации
всегда приводит на каком-то экземпляре отношения к наличию
лишних кортежей в ответе на запрос, причем на каком экземпляре отношения это произойдет, сказать заранее нельзя. К каким последствиям это может привести?
Если база данных проектируется для систем бизнеса, то это может
привести только к материальным потерям, например, некоторые сотрудники получат лишнее вознаграждение или кто-то получит уведомление из налоговой инспекции о необходимости уплаты налогов,
хотя налоги уже уплачены или данный клиент вообще не подлежит
налогообложению. Если же база данных проектируется для систем
управления, то невыполнимость свойства соединения без потерь информации может привести к катастрофическим последствиям, причем когда это произойдет, заранее предсказать невозможно.
Проверка выполнимости свойства соединения без потерь информации на каждом экземпляре схемы отношения – дело практичес42
ки безнадежное. В настоящее время известны простые алгоритмы
проверки выполнимости этого свойства для любого заданного набора декомпозиционных подсхем.
В настоящее время известны два алгоритма проверки выполнимости свойства соединения без потерь информации [1], [4], [7]. Первый алгоритм используется для декомпозиции, состоящей из двух
декомпозиционных подсхем, а второй алгоритм – для любого количества декомпозиционных подсхем. Поскольку второй алгоритм
является универсальным с точки зрения количества декомпозиционных подсхем, здесь ограничимся его рассмотрением.
Пусть R = A1,..., An – схема отношения, на которой определено множество F и  = {R1, R2,..., Rk} – декомпозиция R. Построим
таблицу из n (количество атрибутов в схеме R) столбцов и k (количество декомпозиционных подсхем) строк так, чтобы j-й столбец
соответствовал атрибуту Aj, Aj  R, j = 1,2,..., n, а i-я строка – декомпозиционной подсхеме Ri, i = 1,2,..., k. Заполним таблицу следующим образом.
Поставим на пересечении i-й строки и j-го столбца символ «a»,
если атрибут Aj  Ri, и символ «bi» – иначе. Заполнив таким образом таблицу, начинаем ее видоизменять по следующему правилу.
Циклически просматривая в любом порядке множество F от
одной функциональной зависимости к другой, производим анализ каждой зависимости (X  Y)  F и вносим такие изменения в
таблицу, чтобы рассматриваемая зависимость выполнялась. Для
этого используем определение функциональной зависимости,
сформулированное в разделе 1.3.1. Например, для зависимости
X  Y из F находим в таблице такие строки, которые совпадают
по всем атрибутам (столбцам) набора X. По определению функциональной зависимости в найденных строках должны совпадать значения атрибутов набора Y. Если значение хотя бы одного
атрибута из набора Y есть «a», то делаем его равным «a» для Y
во всех найденных строках. Если ни одно значение не равно «a»,
то делаем его равным любому, но одинаковому, значению «bi».
Аналогично осуществляем анализ остальных зависимостей. Процесс заканчиваем, когда в таблице невозможно будет сделать никаких изменений, или какая-либо строка таблицы не станет состоять сплошь из символов «a». Наличие такой строки говорит о
выполнимости свойства соединения без потерь информации для
рассматриваемой декомпозиции, а отсутствие – о невыполнимости его. Доказательство корректности рассмотренного алгоритма
дано в работе [1].
43
Пример 25 [7]. Пусть R = ABCDELPS и F = {B  C, D  EL, B  PS,
A  CDPS, AP  S}. Выясним, обладает ли декомпозиция  = {AB,
ACDPS, BCPS, DEL} схемы отношения R свойством соединения без
потерь информации? Для этого строим и заполняем, как было изложено выше, табл. 1:
1.
AB
ACDPS
BCPS
DEL
A
a
a
b3
b4
B
a
b2
a
b4
C
b1
a
a
b4
D
b1
a
b3
a
E
b1
b2
b3
a
L P S
2.
b1 b1 b1
AB
b2 a a  ACDPS
b3 a a
BCPS
a b4 b4
DEL
A
a
a
b3
b4
B
a
b2
a
b4
C
b1a
a
a
b4
D E L P
b1a b1 b1 b1a
a b2a b2a a
b3 b3 b3 a
a a a b4
S
b1a
a
a
b4
Начинаем просмотр зависимостей из F. Для зависимости B  C в
исходной табл. 1 ищем строки, совпадающие по значению атрибута
B. Это – первая и третья строки со значением «a» (подчеркнуты в
табл. 1 и отмечены жирным шрифтом в табл. 2). Значит, по определению функциональной зависимости должны совпадать и значения в этих же строках и в столбце C. Так как в третьей строке это
значение равно «a», то делаем его равным «a» и в первой строке
(также отмечены жирным шрифтом в табл. 2).
Отметим, что для зависимостей, правые части которых содержат более одного атрибута, рекомендуется выполнить сначала декомпозицию правых частей, а затем уже производить соответствующие изменения в таблице.
Рассмотрим вторую зависимость D  EL из F. Поскольку правая часть зависимости содержит более одного атрибута, по правилу декомпозиции правой части зависимости (раздел 1.3.2) декомпозируем правую часть, и для удобства анализа вместо одной
зависимости D  EL рассматриваем две: D  E и D  L. В табл. 1
ищем в столбце D одинаковые значения. Это – символы «a» во второй и четвертых строках (подчеркнуты в табл. 1 и отмечены жирным шрифтом в табл. 2). Значит, по определению функциональной зависимости должны совпадать и значения в этих же строках
и в столбцах E и L. А они разные, но в четвертой строке в столбцах E и L есть символ «a». Поэтому делаем его равным «a» и во
второй строке этих столбцов (также отмечены жирным шрифтом
в табл. 2).
Аналогичные изменения делаем в табл. 2 для остальных зависимостей. Эти изменения отображены в табл. 2.
Табл. 2 соответствует первому циклу просмотра всех зависимостей из F. Видно, что в таблице нет строки, содержащей только
символы «a». Проверим, возможно ли и дальше видоизменять таб44
лицу. Для удобства дальнейших преобразований скопируем результат первого цикла просмотра зависимостей в табл. 3.
Обратимся к табл. 3 и начнем второй цикл просмотра множества
F, начиная опять с первой зависимости B  C. Для этой зависимости изменений в таблице не будет.
Рассмотрим зависимость D  EL. Одинаковые значения в столбце D имеют первая, вторая и четвертая строки. Вносим соответствующие изменения сначала в столбец E, а затем в столбец L.
3.
AB
ACDPS
BCPS
DEL
A
B
C
D
E
a
a
b3
b4
a
b2
a
b4
a
a
a
b4
a
a
b3
a
b1a b1a a
L
P
a a
b3 b3
a a
S
a
a a
a a
b4 b4
Процесс заканчиваем, так как получили первую строку (подчеркнута) табл. 3, состоящую сплошь из символов «a». Следовательно,
рассматриваемая декомпозиция обладает свойством соединения
без потерь информации.
Пример 26 [7]. Пусть R = ABCDEKM и F = {A  BC, A  D, D 
EK, AD  M, M  AK}. Задана декомпозиция исходной схемы
отношения в виде  = {ADME, EKC, ACE, DEB}. Проверим, обладает
ли данная декомпозиция свойством соединения без потерь информации относительно F.
Строим табл. 1, которую заполняем по правилу, изложенному в
алгоритме. Для удобства работы будем в таблице отображать только символы «a», а символы «bi» будем подразумевать и отображать
их в таблице только по необходимости.
1.
ADME
EKC
ACE
DEB
A
a
.
a
.
D
a
.
.
a
B
.
.
.
a
C
.
a
a
.
E
a
a
a
a
K
.
a
.
.
M
a
.
.
.
2.

A
a
.
a
.
D
a
.
a
a
B
b1
.
b1
a
C
a
a
a
.
E
a
a
a
a
K
b1
a
b1
b1
M
a
.
a
.
Анализируем первую зависимость A  BC из F. Одинаковые
значения в столбце A имеются в первой и третьей строках (символы «a» подчеркнуты в табл. 1). Следовательно, в этих же строках
в столбцах B и C должны стоять одинаковые значения, а они разные. Делаем их одинаковыми. В столбце B ни в первой, ни в третьей
строке нет символа «a», поэтому делаем их равными, например
«b1» или «b3», (важно сделать их одинаковыми). В табл. 2 отобра45
жены эти изменения. Так как в столбце C в третьей строке стоит
символ «a», то ставим символ «a» и в первой строке этого столбца.
Анализируем вторую зависимость A  D из F. В столбце A, как мы
только что выяснили, одинаковые символы стоят в первой и третьей
строках. Следовательно, и в столбце D в этих же строках должны стоять одинаковые значения, а они разные, как видно из табл. 1. Делаем
их одинаковыми. Так как в первой строке в столбце D стоит символ
«a», то ставим и в третьей строке в столбце D также символ «a».
Анализируем третью зависимость D  EK из F. Ищем одинаковые значения в столбце D. Поскольку в столбце уже были сделаны
изменения, то теперь уже обращаемся к табл. 2. Одинаковые значения в столбце D содержатся в первой, третьей и четвертой строках,
поэтому делаем одинаковыми значения в этих же строках в столбцах E и K. В столбце E они уже одинаковые, поэтому изменения
коснутся только столбца K. Очевидно, это будут символы «bi», например «b1».
Анализируем четвертую зависимость AD  M из F. Опять обращаемся к табл. 2. Так как в левой части зависимости стоит набор
из двух атрибутов, то ищем одинаковые пары значений в столбцах
AD. Пара значений «aa» имеется в первой и третьей строках, поэтому в этих строках в столбце M должны стоять одинаковые значения. Поскольку в первой строке в столбце стоит символ «a», то
ставим этот символ и в третьей строке столбца M. Из табл. 2 видно,
что последняя зависимость M  AK из F уже выполняется.
Проверив еще раз выполнимость каждой зависимости из F, убеждаемся, что в табл. 2 никаких изменений больше сделать нельзя, и
в то же время не получено строки, сплошь состоящей из символов
«a». Поэтому делаем вывод о том, что рассматриваемая декомпозиция не обладает свойством соединения без потерь информации относительно заданного множества функциональных зависимостей F.
Очевидно, описанный алгоритм можно использовать и для анализа декомпозиции, состоящей из двух декомпозиционных подсхем. К достоинствам алгоритма следует отнести легкость его автоматизации.
Порядок просмотра зависимостей из F не влияет на результат, а
определяет лишь скорость принятия решения.
1.8.2.2. Свойство сохранения функциональных
зависимостей
Свойство декомпозиции сохранять зависимости из исходного
множества F состоит в том, что при восстановлении схемы отноше46
ния R из декомпозиционных подсхем все зависимости, объявленные в F, должны автоматически выполняться и в восстановленной
схеме R. Определим это свойство формально.
Проекцией множества функциональных зависимостей F на
множество атрибутов Z  U, обозначаемое как Z (F), называется
такое множество зависимостей (X  Y)  F+, для которых XY  Z.
Например, для U = ABC и F = {A  B, B  C} проекция AB (F) =
= {A  B}, а AС(F) = {A  С}. Легко видеть, что зависимость
(A  C)  F, но следует из F по аксиоме транзитивности из зависимостей A  B и B  C. Следовательно, (A  C)  F+.
Декомпозиция  = {R1, R2,..., Rk} схемы отношения R сохраняет
множество функциональных зависимостей F, определенное на R,
если из объединения всех зависимостей, принадлежащих проекциям F на декомпозиционные подсхемы Ri, i = 1,2,..., k, логически
следуют все зависимости из F.
Тогда
æ k
ö+
çç È  (F)÷÷ = F+ т. е. имеет место эквивалентность множеств:
÷÷
ççèi=1 R i
ø
æ k
ö+
çç È  (F)÷÷ º F.
÷÷
ççèi=1 R i
ø
Пример 27 [7]. Пусть R = ABC и F = {A  B, B  C}.
Случай 1. Декомпозиция  = {AB, BC} схемы отношения R сохраняет зависимости из F, так как F1 = AB (F) = {A  B}, F2 = BC (F) =
= B  C} и (F1 F2) = {A  B, B  C} = F, а следовательно, и {A  B,
B  C}+ = F+.
Случай 2. Декомпозиция 1 = {AB, AC} не сохраняет зависимостей из F, так как F1 = AB (F) = {A  B}, F2 = AС (F) = {A  C}. Зависимость A  C выводится из исходного множества F по аксиоме
транзитивности. Тогда (F1 F2)+ = {A  B, A  C}+  F+. Зависимость
B  C не восстанавливается из объединения проекций.
Из приведенного примера с очевидностью вытекает условие достаточности того, в каком случае декомпозиция наверняка обладает свойством сохранения функциональных зависимостей на заданном множестве атрибутов, которое можно сформулировать следующим образом.
Достаточное условие сохранения декомпозицией функциональных зависимостей состоит в том, чтобы все атрибуты каждой зави47
симости из F целиком входили в какую-нибудь декомпозиционную
подсхему (как в случае 1). Тогда каждая зависимость из F наверняка окажется в проекции F на какую-нибудь декомпозиционную
подсхему, а раз так, то все зависимости из F обязательно восстановятся из объединения проекций. Однако это условие не является
необходимым, т. е. условие достаточности может быть не выполнено, а декомпозиция при этом сохраняет зависимости. Например,
для R = ABC и F = {A  B, B  A, A  C} декомпозиция  = {AB, BC}
сохраняет зависимости из F, несмотря на то, что условие достаточности не выполнено. Атрибуты AC зависимости A  C целиком не
входят ни в одну декомпозиционную подсхему, но F1 = AB (F) =
= {A  B, B  A}, F2 = BС (F) = {B  C} и F1 F2 = {A  B, B  A,
B  C}. Зависимость A  C транзитивно выводится из зависимостей A  B и B  C, поэтому (F1 F2)+ = F+.
Будем в дальнейшем называть применимыми к некоторой декомпозиционной подсхеме те функциональные зависимости, все
атрибуты которых целиком находятся среди атрибутов декомпозиционной подсхемы.
Например, зависимость A  B будет применима к декомпозиционным подсхемам AB, ABC, ABCD, DAHRB и так далее.
Иногда, если условие достаточности не выполняется, построение
проекций множества функциональных зависимостей F на декомпозиционные подсхемы вызывает те же трудности, что и вычисление
замыкания F+. Чтобы их избежать, можно воспользоваться, по
крайней мере, двумя способами:
Способ 1 использует алгоритм синтеза множества зависимостей, входящих в проекции R (F), где i = 1,2,...,k.
i
Способ 2 основан на простых рассуждениях, использующих
понятия расширенного множества зависимостей и условия достаточности.
Рассмотрим эти способы. Способ 1 подробно изложен в работах
[4], [7]. Способ 2, по мнению авторов, проще, поэтому ограничимся
рассмотрением именно этого способа.
Пример 28 [7]. Пусть R = ABCDEM и F = {A  B, CD  A,
CB  D, AE  M, CE  D}. Рассмотрим декомпозицию  = {R1, R2},
где R1 = AEM и R2 = ABCDE. На основе простых рассуждений выясним, обладает ли заданная декомпозиция  свойством сохранения
функциональных зависимостей на заданном множестве атрибутов
U = ABCDEM. Попробуем получить ответ на этот вопрос, используя
только свойство достаточности.
48
Строим таблицу из двух столбцов. В один столбец будем записывать функциональные зависимости из F, которые точно восстанавливаются из объединения проекций по условию достаточности, а в
другой – остальные, которые необходимо дополнительно исследовать. Очевидно, точно восстанавливаются те зависимости, которые
по условию достаточности применимы к какой-либо декомпозиционной подсхеме:
Восстанавливаются
A  B (применима к
подсхеме R2= ABCDE)
CD  A (применима к ABCDE)
CB  D (применима к ABCDE)
CE  D (применима к ABCDE)
AE  M (применима к AEM)
Остальные
__
Из таблицы видно, что все зависимости из исходного множества
F восстанавливаются. Поэтому заданная декомпозиция обладает
свойством сохранения функциональных зависимостей на заданном
множестве атрибутов.
Если в столбце «Остальные» останутся зависимости, то они требуют дополнительного исследования. Какого? Рассмотрим примеры.
Пример 29. Пусть R = ABCDEKX и F = {A  BC, A  D, C  B,
D  EK, AD  X, X  AK, E  K, A  K}.
Рассмотрим декомпозицию  = {ADEX, EKC, ACEK, DEBC} схемы R.
Пытаемся ограничиться только свойством достаточности. Строим таблицу:
Восстанавливаются
A C
(применима к ACEK)
A D
(применима к ADEX)
CB
(применима к DEBC)
DE
(применима к DEBC)
AD  X (применима к ADEX)
X A
(применима к ADEX)
E K
(применима к EKC)
A K
(применима к ACEK)
Остальные
A B
DK
X K
Теперь попытаемся вывести остальные зависимости из тех зависимостей, которые восстанавливаются. Так, зависимость A  B
49
выводится транзитивно из зависимостей A  C и C  B, зависимость D  K аналогично выводится из зависимостей D  E и E  K,
зависимость X  K – из зависимостей X  A и A  K. Таким образом, все зависимости из F восстанавливаются и свойство сохранения функциональных зависимостей для заданной декомпозиции
выполняется. Однако так просто бывает не всегда. Иногда свойство
достаточности дает отрицательный результат, а на самом деле свойство сохранения зависимостей выполняется. В этом случае предлагается получить дополнительные, выводимые из F зависимости,
которые дадут возможность опять воспользоваться свойством достаточности. Эти дополнительные зависимости можно получить из
расширенного множества F- зависимостей.
Пример 30. Пусть R = ABC и F = {A  B, B  A, A  C}.
Рассмотрим декомпозицию  = {AB, BC} схемы R. Воспользуемся
только что предложенной процедурой. Для этого строим таблицу:
Восстанавливаются
A B
(применима к AB)
BA
(применима к AB)
Остальные
A C
Из таблицы видно, что зависимость A  C неприменима ни к
подсхеме AB, ни к подсхеме BC, поэтому она требует дополнительного исследования, которое может заключаться в следующем. Из
левого столбца таблицы видно, что A функционально определяет B.
Попробуем найти дополнительную зависимость, в которой B может
функционально определять C, поскольку C является правой частью
исследуемой зависимости. Для этого строим расширенное множество F- зависимостей:
ℱ = {A  BC, B  AC, A  CB}.
Поскольку расширенное множество содержит все зависимости,
принадлежащие F и выводимые из F, то в качестве дополнительной
зависимости можно использовать B  C, которая получается из зависимости B  AC по правилу декомпозиции ее правой части и которая применима к декомпозиционной подсхеме BC.
Добавляем полученную дополнительную зависимость в таблицу:
Восстанавливаются
A B
(применима к AB)
BA
(применима к AB)
BC
(применима к BC)
50
Остальные
A C
Теперь зависимость A  C транзитивно выводится из зависимостей A  B и B  C, поэтому свойство сохранения зависимостей для
рассматриваемой декомпозиции выполняется.
Пример 31. Пусть R = ABCDEKMNLX и F = {A  CD, C  KML,
A  BD, D  XNC, X  D, K  L, LB  E}. Рассмотрим декомпозицию  = {ABCDE, DX, XE, CKMNL, KM}. Выясним, обладает ли заданная декомпозиция  свойством сохранения функциональных зависимостей на заданном множестве атрибутов U = ABCDEKMNLX.
Строим таблицу:
Восстанавливаются
A  CD (применима к ABCDE)
A  BD (применима к ABCDE)
(применима к ABCDE)
D C
C  KML (применима к CKMNL)
K L
(применима CKMNL)
D X
(применима к DX)
X D
(применима к DX)
Остальные
D N
LB  E
Две зависимости в столбце «Остальные» требуют дополнительного исследования. Используя аксиомы и правила вывода функциональных зависимостей (раздел 1.3), а также факт выводимости зависимости (теорема 1 из раздела 1.4), можно выяснить, что зависимости
D  N и LB  E не выводятся из восстанавливаемых зависимостей.
Попробуем воспользоваться расширенным множеством зависимостей.
ℱ = {A  CDKMLBXNE, C  KML, A  CDKMLBXNE,
D  XNCKML, X  DNCKML, K  L, LB  E}.
Исследуя множество ℱ, приходим к выводу об отсутствии нужной дополнительной зависимости, которая позволила бы вывести
зависимость LB  E. Если такая зависимость и нашлась бы, то она
была бы неприменима ни к одной декомпозиционной подсхеме. Таким образом, делаем вывод о невыполнимости свойства сохранения
функциональных зависимостей для заданной декомпозиции.
Декомпозиция может обладать или не обладать обоими свойствами, а также может обладать одним из них и не обладать другим.
1.9. Нормальные формы
Не всегда спроектированная реляционная база данных является
«хорошей». Она может обладать рядом серьезных недостатков, на51
пример содержать информационную избыточность, и (или) в процессе обработки данных могут возникать различные аномалии, которые были рассмотрены в разделе 1.8. Чтобы устранить эти недостатки, т. е. сделать базу данных «хорошей», необходимо привести
все отношения базы данных к «сильным» нормальным формам.
В настоящее время известно несколько нормальных форм, самой «слабой» из которых является первая нормальная форма (будем обозначать 1НФ), далее – по мере «усиления» – 2НФ, 3НФ,
нормальная форма Бойса – Кодда (НФБК), 4НФ и 5НФ. Практика
показывает, что приведение базы данных хотя бы к 3НФ позволяет
избежать в большинстве случаев почти всех недостатков.
Дальнейшая нормализация требуется не всегда.
Строго говоря, нормализованным считается отношение, находящееся в 1НФ. Тогда под нормализацией понимается процесс приведения ненормализованного отношения к 1НФ [2]. Однако в литературе под нормализацией часто понимают процесс приведения
отношения к «сильной» нормальной форме (хотя бы к третьей).
Из рис. 1 следует, что все нормализованные отношения находятся в 1НФ, некоторые из них находятся также и во 2НФ. Некоторые
отношения, находящиеся во 2НФ, также находятся и в 3НФ, и так
далее.
Первые три нормальные формы были определены Коддом [11].
Пространство ненормализованных отношений
Отношения в 1НФ (нормализованные отношения)
Отношения во 2НФ
Отношения в 3НФ
Отношения в НФБК
Отношения в 4НФ
Отношения в 5НФ
Рис. 1. Нормальные формы
52
1.9.1. Первая нормальная форма (1НФ)
Отношение со схемой R и множеством функциональных зависимостей F находится в 1НФ, если любой экземпляр схемы R удовлетворяет следующим условиям [1], [7], [8]:
Каждый атрибут схемы R имеет уникальное имя. Одинаковые имена атрибутов возможны только в разных отношениях.
Элементы кортежей с одним и тем же именем должны быть
определены на одном и том же домене. Например, нельзя в одном и
том же столбце для номера поставщика задавать значения так:
PN
1
2
p3
. . .,
поскольку значения 1, 2,... принадлежат домену целых чисел, а
значение p3 – домену, определяющему цепочки символов.
Элементы домена должны быть атомарными, т. е. не представлять некоторую совокупность значений. Определить понятие
атомарности подчас бывает трудно, так как значение, атомарное в
одном приложении, может быть не атомарно в другом [5]. Можно
руководствоваться следующим соображением. Значение не атомарно, если в приложении оно используется по частям. Например,
пусть дано отношение РОЖДЕНИЕ с атрибутами ИМЯ и ДАТА_
РОЖД следующего вида:
РОЖДЕНИЕ (ИМЯ,
Иванов
Петров
Смирнов
ДАТА_РОЖД)
7 июня 1961
21 марта 1970
30 апреля 1956
Если бы потребовалось указать только месяц или год рождения,
то это отношение не находилось бы в 1НФ, так как требуемые значения (месяц или год рождения) являются только частью значений
атрибута ДАТА_РОЖД. Чтобы указанное отношение находилось в
1НФ в этом случае, атрибут ДАТА_РОЖД нужно разбить на части,
например, так:
РОЖДЕНИЕ (ИМЯ,
ДЕНЬ_РОЖД,
Иванов
7
Петров
21
Смирнов
30
МЕСЯЦ_РОЖД, ГОД_РОЖД)
июнь
1961
март
1970
апрель
1956
53
Каждый элемент кортежа должен иметь одно значение. Повторяющиеся группы значений недопустимы, т. е. на пересечении
каждой строки и каждого столбца должно находиться одно значение. Например, повторяющиеся значения атрибута ПРОФЕССИЯ
(два значения на пересечении первой строки и второго столбца
в табл. 1 должны отображаться для реляционных структур, как
в табл. 2):
1. …
ИМЯ, ПРОФЕССИЯ, ...
Иванов токарь, слесарь
Петров водитель, повар
2. … ИМЯ, ПРОФЕССИЯ, ...
Иванов
токарь
Иванов
слесарь
Петров
водитель
Петров
повар
В отношении не должно быть повторяющихся (одинаковых)
кортежей.
Отношение, не находящееся в 1НФ, называется ненормализованным.
Рассмотрим процесс нормализации ненормализованного отношения до первой нормальной формы.
Пусть имеем схему отношения R = PN, ST, GOR, DN, KOL, где
PN, ST, GOR – номер, статус и город поставщика;
DN – номер поставляемой детали;
KOL – количество поставляемых поставщиком деталей.
Пусть на схеме R определено множество функциональных зависимостей:
F = {PN  GOR, GOR  ST, PN  ST, (PN, DN)  KOL}
Экземпляр схемы r(R), определенный ниже, не удовлетворяет
условиям 1НФ, так как содержит повторяющиеся группы значений для атрибутов DN и KOL (выделены).
Ненормализованное отношение:
r (R) = PN
p1
p2
p3
p4
ST GOR
80 Москва
40 Самара
80 Москва
100 СПб
DN
d1
d2
d1
d2
d2
d2
KOL
100
100
300
40
200
150
Нормализованное отношение (1НФ):
r1(R) = PN
p1
p1
p2
p2
p3
p4
ST GOR
80 Москва
80 Москва
40 Самара
40 Самара
80 Москва
100 СПб
DN KOL
d1 100
d2 100
d1 300
d2 40
d2 200
d2 150
Отношение, имеющее структуру экземпляров r(R), является ненормализованным. Чтобы оно стало нормализованным, надо привести структуру его экземпляров к виду r1(R). Теперь отношение
54
R со структурой экземпляров r1(R) будет находиться в первой нормальной форме.
Отношению R, находящемуся в 1НФ, присущи следующие недостатки:
1) информационная избыточность (город и статус поставщика
повторяются для каждого поставляемого вида деталей);
2) аномалии операций обработки данных:
добавление (в экземпляр r1(R) нельзя включить нового поставщика, пока он не начнет поставлять какую-либо деталь);
удаление (нельзя удалить сведения только о поставках, так
как можно удалить всю информацию о поставщике. Кроме того,
удаление кортежа с поставщиком p4 приведет к потере статуса для
Петербурга, что может нарушить целостность данных);
корректировка (при изменении значения города, например у
поставщика p1, можно получить противоречивые данные, если сделать эти изменения не во всех кортежах с поставщиком p1).
Одной из причин наличия этих недостатков может быть отсутствие полной функциональной зависимости некоторых неключевых атрибутов от возможных первичных ключей.
Чтобы избавиться от этих недостатков, надо продолжить нормализацию исходного отношения R до второй нормальной формы.
1.9.2. Вторая нормальная форма (2НФ)
Пусть X,Y – наборы атрибутов схемы отношения R = PN, ST,
GOR, DN, KOL, которое находится в 1НФ и на котором справедливо множество функциональных зависимостей F = {PN  GOR,
GOR  ST, PN  ST, (PN, DN)  KOL}.
Можно сказать, что Y находится в полной функциональной зависимости от X, если Y функционально зависит от X и не зависит
от любого собственного подмножества X.
Пусть X = {PN, DN}, Y = {KOL}. Выясним, находится ли Y в полной функциональной зависимости от X. Анализируя данный экземпляр, делаем вывод о том, что ни одно подмножество набора X
функционально не определяет Y. Действительно, атрибут PN функционально не определяет KOL (PN ↛ KOL), и атрибут DN также
функционально не определяет KOL (DN ↛ KOL), но набор атрибутов
X = {PN, DN} функционально определяет KOL, т. е. (PN,DN)  KOL.
Следовательно, набор атрибутов{PN, DN } функционально полно
определяет атрибут KOL:
55
..
(PN, DN)  KOL
Если определить X = {PN,DN} и Y = {GOR}, то в этом случае простая функциональная зависимость между X и Y имеет место, так
как {PN,DN}  GOR, но существует также зависимость PN  GOR,
поэтому
. .
{PN, DN} ↛ GOR.
Аналогично можно показать, что нет функционально полной зависимости между атрибутом ST и набором {PN, DN}.
Очевидно, если левая часть простой функциональной зависимости представляет собой одиночный атрибут, то такая зависимость
всегда будет функционально полной. Всюду ниже запись X  Y будем понимать как функционально полную зависимость и для наборов и для одиночных атрибутов.
Как было показано в разделе 1.3.1, первичным ключом отношения R является набор атрибутов (PN, DN), так как (PN, DN)+ = PN,
DN, ST, GOR, KOL = U (все атрибуты схемы R), но PN+ = (PN, ST,
GOR)  U и DN+ = DN  U. Альтернативного первичного ключа в
отношении R нет.
Атрибуты PN и DN, входящие в состав первичного ключа, являются ключевыми, остальные атрибуты ST, GOR, KOL – неключевыми.
Выше было показано, что атрибут KOL функционально полно
зависит от ключа (PN, DN), чего нельзя сказать о неключевых
атрибутах ST и GOR.
Улучшить схему отношения R, сделав все зависимости функционально полными от ключа, можно, используя декомпозицию исходного отношения R на две декомпозиционные подсхемы. Рассмотрим декомпозицию 1 = {R1, R2} схемы R, где
R1 = PN, ST, GOR и R2 = PN, DN, KOL
Первичные ключи в подсхемах выделены.
Теперь неключевые атрибуты ST и GOR в подсхеме R1 также
функционально полно зависят от первичного ключа PN, так как
первичный ключ – одиночный атрибут.
Остается проверить, обладает ли декомпозиция 1 двумя свойствами.
Проверяем свойство соединения без потерь информации. Для
этого воспользуемся алгоритмом из раздела 1.8.2.1. Строим матрицу, столбцами которой являются атрибуты отношения R, а строками – декомпозиционные подсхемы R1 и R2. Заполняем матрицу
56
символами «а» и «bi» по правилу, изложенному в разделе 1.8.2.1.
Просматривая зависимости из F, например в направлении слева –
направо, после анализа зависимостей PN  ST и PN  GOR получим в нижеприведенной таблице строку, сплошь состоящую из
символов «a»:
PN ST
PN, ST, GOR a
a
PN, DN, KOL a
ba
2
GOR
a
ba
2
DN KOL
b1
b1
a
a
Следовательно, рассматриваемая декомпозиция обладает свойством соединения без потерь информации.
Декомпозиция 1 также обладает и свойством сохранения функциональных зависимостей, так как F1 = R (F) = {PN  GOR, GOR  ST,
1
PN  ST}, F2 = R (F) = {(PN,DN)  KOL} и (F1 F2)+ = F+ (см. раз2
дел 1.8.2.2).
Таким образом исходное отношение R может быть заменено двумя отношениями R1 = PN, ST, GOR и R2 = PN, DN, KOL, в которых
неключевые атрибуты функционально полно зависят от ключа и на
которых справедливы множества функциональных зависимостей:
на R1 – множество F1 и на R2 – множество F2.
Отношение со схемой R и множеством функциональных зависимостей F находится в 2НФ, если оно находится в 1НФ, и каждый
неключевой атрибут функционально полно зависит от любого возможного первичного ключа схемы отношения R.
Таким образом, полученные отношения R1 и R2 находятся во
второй нормальной форме.
1.9.3. Третья нормальная форма (3НФ)
Отношение, находящееся в 2НФ, также может иметь недостатки, обусловленные наличием транзитивных зависимостей, которые могут приводить к нежелательным последствиям при удалении данных.
Продолжаем рассмотрение примера.
Видно, что зависимость PN  ST в отношении R1 выводится
транзитивно из зависимостей PN  GOR и GOR  ST.
Разорвем эту транзитивную зависимость, используя декомпозицию 2 = {R11, R12} схемы отношения R1, где R11 = PN, GOR и
R12 = GOR, ST. Первичные ключи в подсхемах выделены.
57
Такая декомпозиция обладает как свойством соединения без потерь информации, так и свойством сохранения функциональных
зависимостей атрибутов. В отношении R11 будет справедлива зависимость F11 = R (F1) = {PN  GOR}, а в отношении R12 – зависи11
мость F12 = R (F2) = {GOR  ST}. Видно, что множества F11 и F12
12
не содержат транзитивных зависимостей.
Отношение R с множеством функциональных зависимостей F
находится в 3НФ, если оно находится в 2НФ, и каждый неключевой атрибут прямо, а не транзитивно зависит от любого возможного первичного ключа схемы отношения, а также все неключевые
атрибуты отношения взаимно независимы (если они есть вообще).
Это определение было сформулировано в работе [12].
Легко убедиться, что все три декомпозиционные подсхемы R11,
R12 и R2, полученные в предыдущих разделах, находятся в 3НФ.
Таким образом, исходное отношение R = PN, ST, GOR, DN, KOL,
находящееся в 1НФ, путем декомпозиции  = {R11, R12, R2} заменено совокупностью из трех декомпозиционных подсхем, каждая
из которых находится в 3НФ. В этом случае и вся база данных
БД = {R11, R12, R2} находится в третьей нормальной форме.
1.9.4. Нормальная форма Бойса – Кодда (НФБК)
Однако 3НФ также может иметь недостатки, связанные с ключевыми атрибутами. В приведенном выше примере полученная
3НФ не вызывает аномалий при обработке данных, так как в результирующих декомпозиционных подсхемах отсутствуют зависимости одних ключевых атрибутов от других ключевых атрибутов. Если это условие нарушается (это бывает при составных
ключах), то возможны аномалии обработки данных. Например,
отношение R = ABC с множеством функциональных зависимостей F = {AC  B, B  C} содержит два возможных первичных
ключа K1 = AB и K2 = AC, так как AB+ = ABC и AC+ = ABC, но
A+ = A ABC, B+ = BC ABC, C+ = C ABC. Таким образом, все
атрибуты схемы R являются ключевыми, и по определению третьей нормальной формы отношение R находится в 3НФ. Но в нем
имеются зависимости между ключевыми атрибутами, что может
привести к аномалиям обработки. Так, определить пару атрибутов BC можно только тогда, когда определен атрибут A. На практике для разрешения коллизий в этом случае поддерживают еще
и отношение BC.
58
К. Дж. Дейт [2] указал следующие условия, для которых данное
Коддом определение третьей нормальной формы не всегда является
корректным:
– отношение имеет два или более потенциальных (альтернативных, возможных) ключа;
– два потенциальных ключа являются составными;
– потенциальные ключи имеют хотя бы один общий атрибут.
В связи с этим определение Кодда впоследствии было заменено
более строгим определением Бойса – Кодда [7].
Отношение R с множеством зависимостей F находится в НФБК,
если левая часть каждой зависимости (X  A)  F, где A  X, есть
первичный или возможный (потенциальный, альтернативный)
первичный ключ.
Например, отношение R = ABCD с множеством функциональных зависимостей F = {AB  C, AB  D, BC  A} находится в
НФБК, так как AB и BC – ключи (AB+ = ABCD и BC+ = BCAD).
Можно доказать [5], [1], что отношение, находящееся в НФБК,
находится и в 3НФ. Обратное утверждение в общем случае неверно.
Так, отношение R = ABC с множеством зависимостей F = {AC  B,
B  C} находится в 3НФ, но не в НФБК, так как атрибут B не является ключом, а отношения R11, R12 и R2, полученные в предыдущих разделах, находятся не только в третьей нормальной форме,
но и в нормальной форме Бойса – Кодда.
В теории реляционных баз данных доказано, что любое отношение может быть заменено набором декомпозиционных подсхем,
каждая из которых будет находиться в 3НФ, а декомпозиция будет
обладать как свойством соединения без потерь информации, так и
свойством сохранения исходного множества функциональных зависимостей. При приведении же к НФБК в общем случае не гарантируется выполнимость всех свойств декомпозиции.
1.9.5. Нормальные формы более высоких порядков
В том случае, когда в третьей нормальной форме выявляются
так называемые многозначные зависимости, требуется дальнейшая нормализация до четвертой нормальной формы (4НФ). Если
же в 4НФ выявляются так называемые зависимости соединения, то
требуется дальнейшая нормализация до 5НФ.
Сначала рассмотрим пример многозначной зависимости. Формальное определение многозначных зависимостей дано в работах [2], [7].
59
Пример 32. Рассмотрим экземпляр отношения R = {РЕЙС,
ДЕНЬ, САМОЛЕТ}:
r (R) = РЕЙС
ДЕНЬ САМОЛЕТ
2215
среда ТУ-154
2215
четверг ТУ-134
2215
среда ТУ-134
2215
четверг ТУ-154
2333
среда ТУ-134
.......................
Очевидно, R находится в 3НФ и даже в НФБК, так как первичным
ключом отношения является набор из всех атрибутов K = (РЕЙС,
ДЕНЬ, САМОЛЕТ). Таким образом, все атрибуты схемы являются
ключевыми, и отношение R удовлетворяет условиям 1НФ, и 2НФ, и
3НФ, и НФБК. В то же время отношение R обладает недостатками
(избыточность, потенциальная противоречивость и так далее), которые и определяются наличием многозначных зависимостей.
В отношении R определяются многозначные зависимости (мультизависимости): РЕЙС ↠ ДЕНЬ или РЕЙС ↠ САМОЛЕТ, когда одному значению рейса (левая часть зависимости) соответствует фиксированное множество значений дней недели или типов самолетов
(правые части зависимостей). В работе [13] показано, что для данного отношения R = ABC многозначная зависимость A ↠ B выполняется тогда и только тогда, когда также выполняется многозначная
зависимость A ↠ C, т. е. многозначные зависимости всегда образуют
связанные пары и часто их обозначают так: A ↠ BC.
В этом случае рекомендуется декомпозировать схему R на две
декомпозиционные подсхемы так, чтобы одна многозначная зависимость была определена на одной декомпозиционной подсхеме, а
вторая – на другой. В данном примере можно использовать декомпозиции  = {R1, R2}, где R1 = {РЕЙС, ДЕНЬ} и R2 = {РЕЙС, САМОЛЕТ}. Тогда избыточность будет сведена к минимуму и уменьшится вероятность аномалий при обработке данных. Ниже приведены
экземпляры декомпозиционных подсхем, полученные проектированием экземпляра схемы r(R) на декомпозиционные подсхемы:
r (R 1) = REIS
2215
2215
DN
;
среда
четверг
r (R2) = REIS
2215
2215
TS
ТУ-154
ТУ-134
Заметим, что исходное отношение R может быть восстановлено
без потерь с помощью естественного соединения проекций, поэтому
данная декомпозиция выполняется без потерь информации.
60
При наличии многозначных зависимостей также возможно выполнение декомпозиции схем отношений и также декомпозиция
должна обладать необходимыми свойствами.
Подробную информацию об этом можно найти в работах [2], [7].
Было замечено, что существуют отношения, для которых нельзя выполнить декомпозицию без потерь информации на две декомпозиционные подсхемы, но которые можно декомпозировать
без потерь на три или более декомпозиционные подсхемы. Такие
отношения К. Дж. Дейт [2] определил как «n-декомпозируемые
отношения» для некоторого n>2, а Д. Мейер [5] доказал, что эти
отношения удовлетворяют только тривиальным многозначным зависимостям.
Поскольку приведение отношений к нормальным формам порядка 4НФ и выше в учебных базах встречаются крайне редко, в
данном учебном пособии эти вопросы не рассматриваются. Заинтересованному читателю можно рекомендовать работы [1], [2], [5], [7].
61
2. МЕТОДЫ ПРОЕКТИРОВАНИЯ
РЕЛЯЦИОННЫХ БАЗ ДАННЫХ
Для построения «хорошей» базы данных, которая находилась
хотя бы в третьей нормальной форме, можно использовать следующие методы [7]:
метод пошаговой декомпозиции, заключающийся в последовательном разбиении исходной и промежуточных схем отношений до
тех пор, пока результирующие отношения не будут удовлетворять
заданным свойствам;
метод синтеза, состоящий в конструировании (синтезе) набора декомпозиционных подсхем, удовлетворяющих определённым
свойствам, из заданного множества атрибутов выбранной предметной области на основе заданного множества функциональных зависимостей, связывающих эти атрибуты;
метод ER-диаграмм (метод «сущность-связь»), широко применяемый в средствах автоматизированного проектирования баз данных и информационных систем;
комбинация последних двух из перечисленных методов.
Все перечисленные методы должны обеспечивать выполнимость
как свойства соединения без потерь информации, так и свойства сохранения функциональных зависимостей для результирующей декомпозиции.
При использовании метода декомпозиции нужно проверять выполнимость этих свойств на каждом шаге декомпозиции. Метод
синтеза почти всегда гарантирует выполнимость указанных выше
свойств декомпозиции. Метод же ER-диаграмм не гарантирует выполнимость свойства соединения без потерь информации. Однако
ниже будет предложен способ, позволяющий почти всегда обеспечить выполнимость этого свойства.
2.1. Метод декомпозиции
В разделах 1.9.2–1.9.4 была успешно использована декомпозиция с целью приведения исходного отношения R = PN, ST, GOR,
DN, KOL с множеством зависимостей
F = {PN  GOR, GOR  ST, PN  ST, (PN, DN)  KOL}
к нормальной форме Бойса – Кодда. Однако эта операция не всегда
бывает успешной.
Метод декомпозиции имеет недостатки, основными из которых
являются [2]:
62
Сложность алгоритма, которая объясняется тем, что на какомто шаге декомпозиция может не обладать хотя бы одним свойством.
Тогда надо использовать другую декомпозицию, и, если опять не удается обеспечить выполнимость хотя бы одного свойства, приходится
вернуться на шаг назад. И так можно долго «ходить по кругу».
Число результирующих декомпозиционных подсхем может оказаться больше, чем необходимо. А каждая подсхема – это таблица в БД.
В процессе декомпозиции могут возникнуть частичные зависимости неключевых атрибутов от ключа, что не усиливает, а ослабляет нормальную форму.
Несмотря на отмеченные недостатки, от метода декомпозиции отказываться не стоит. Метод декомпозиции все же иногда предпочтительнее в очевидных случаях при конструировании простых баз данных. Кроме того, переход к нормальным формам более высоких порядков (4НФ, 5НФ) осуществляется только методом декомпозиции.
Метод синтеза лишен перечисленных выше недостатков.
2.2. Метод синтеза
Метод синтеза, в отличие от декомпозиции, дает сразу весь набор результирующих декомпозиционных подсхем. Ниже изложен
алгоритм синтеза, основанный на идеях, изложенных в работе [14],
и усовершенствованный Д. Мейером [5] и В. И. Дьяковым [3].
Исходными данными для работы алгоритма являются множество атрибутов U и множество функциональных зависимостей F,
определенное на U. Результатом работы алгоритма является схема
БД в виде набора декомпозиционных подсхем БД = {R1, R2,..., RP},
удовлетворяющих следующим условиям.
1. Будем рассматривать такую структуру зависимостей из F+, которые применимы к декомпозиционным подсхемам. В левой части
каждой зависимости находится ключ подсхемы RI. Осуществляем
переход от множества F к эквивалентному множеству G:
F  G, где G = {KI RI  RI  БД, KI – ключ RI}.
Это автоматически по условию достаточности (см. подраздел
1.8.2.2) обеспечивает декомпозиции = {R1, R2,..., RP} – выполнимость свойства сохранения функциональных зависимостей.
2. Каждая подсхема RI  БД должна находиться хотя бы в 3НФ
относительно множества функциональных зависимостей F и соответственно G, а может быть и в НФБК, что легко проверить, используя множество G.
63
3. Синтезируемая БД содержит минимальный набор декомпозиционных подсхем RI, где I = 1,..., P. Это условие защищает БД от
избыточности.
4. Для любого экземпляра r(БД), удовлетворяющего F, выполняется соотношение r = R (r) 
...  R (r). Это условие гаран1
P
тирует выполнимость свойства соединения без потерь информации.
Схема БД, удовлетворяющая условиям 1, 2 и 3, называется полной схемой БД.
Рассматриваемый алгоритм состоит из восьми шагов. На самом
деле некоторые шаги можно опустить, о чем будет сказано ниже.
Пример 33. Опишем алгоритм синтеза на простом примере данных из предметной области ПОСТАВКА_ДЕТАЛЕЙ. Однако будем
использовать более полный набор атрибутов, чем в методе декомпозиции.
Исходные данные для работы алгоритма:
U = PN, PIM, ST, GOR, DN, DIM, CENA, KOL.
Здесь PIM – имя поставщика, DIM – название детали, CENA –
цена детали. Остальные атрибуты такие же, как в методе декомпозиции.
На заданном множестве атрибутов, очевидно, будут справедливы зависимости:
F = {PN  ST, PN  PIM, PN  GOR, GOR  ST, DN  DIM,
DN  CENA, (PN, DN)  KOL}.
Результат работы алгоритма: БД (R1, R2, …, RP).
Шаг 1. Строим расширенное множество зависимостей ℱ по пра ) (X  Y )  F, Y
 = X + \ X },
вилу (см. подраздел 1.7.1): ℱ = {(Xi  Y
i
i
i
i
i
i
где символ «\» означает операцию вычитания атрибутов.
Этот шаг делается для того, чтобы исключить «лишние» (выводимые из других) зависимости с одинаковыми левыми частями.
Расширяем каждую зависимость из F, добавляя в правую часть все
зависимые атрибуты.
Расширяем первую зависимость из F:
PN+ = PN, PIM, ST, GOR Ю PN  PIM, ST, GOR.
Расширяем вторую зависимость из F. Так как левая часть этой
зависимости PN совпадает с левой частью первой зависимости, то и
правая часть также будет совпадать, что обозначено многоточием
в правой части первой расширенной зависимости:
64
PN+ = ..........
Аналогично для третьей зависимости:
PN+ = ..........
и так далее:
GOR+ = GOR, ST  GOR  ST;
DN+ = DN, DIM, CENA  DN  DIM, CENA;
DN+ = .........  DN ...;
(PN, DN)+ = PN, DN, PIM, ST, GOR, DIM, CENA, KOL 
(PN, DN)  U\(PN, DN).
Тогда расширенное множество зависимостей будет таким
ℱ = {PN  (PIM, ST, GOR), PN ..., PN ..., GOR  ST,
DN  (DIM, CENA), DN ..., (PN, DN)  U\(PN, DN)}.
Шаг 2. Отбрасывая «лишние» зависимости с многоточиями в
правой части, получим условно- или псевдонеизбыточное покрытие расширенного множества зависимостей:
ℱ0 = {(PN  (PIM, ST, GOR), GOR  ST, DN 
(DIM, CENA), (PN, DN)  U\(PN, DN)}.
Шаг 3. Если среди оставшихся зависимостей нет зависимости с
полным набором атрибутов U, то добавляем тривиальную зависимость U   (правая часть – пустое множество). Этот шаг делается
для того, чтобы гарантированно обеспечить выполнимость свойства соединения без потерь информации для результирующей декомпозиции [7].
В рассматриваемом примере такая зависимость есть (PN, DN) 
 U\(PN, DN). Поэтому тривиальную зависимость добавлять не надо.
Шаг 4. Разбиваем оставшиеся зависимости на классы эквивалентности (см. подраздел 1.7.3) и в каждом классе оставляем одного представителя.
Это делается с целью минимизации количества результирующих декомпозиционных подсхем (таблиц БД).
В рассматриваемом примере нет эквивалентных зависимостей,
поэтому каждая зависимость является единственным представителем своего класса эквивалентности.
Шаг 5. Преобразуем оставшиеся зависимости к элементарному
виду, т. е. без лишних атрибутов слева (см. подраздел 1.7.2). Этот
шаг можно опустить и, если останутся неэлементарные зависимо65
сти, то это обязательно проявится на последующих шагах синтеза,
как показано в примере 36.
Шаг 6. Ранжируем оставшиеся зависимости по следующему
правилу: rang (XI  YI)>rang (XJ  YJ), если (XI  YI)  (XJ  YJ),
т. е. минимальный ранг имеет зависимость с полным набором атрибутов. Ранги зависимостей указаны в табл. 1.
Шаг 7. Строим ранжированную диаграмму зависимостей, на которой выполняем операцию транзитивной редукции зависимостей
с большим рангом на зависимости с меньшим рангом, которая заключается в следующем [7].
Двигаясь по диаграмме снизу – вверх (от зависимостей с большим рангом к зависимостям с меньшим рангом), для каждой текущей зависимости фиксируем атрибуты ее правой части и исключаем из правых частей всех зависимостей, расположенных выше
по цепочке вхождений, те атрибуты, которые содержатся в правой
части текущей зависимости. Для тривиальной зависимости исключаем атрибуты из левой части.
Операцию транзитивной редукции можно считать обратной операции расширения функциональных зависимостей. При расшиТаблица 1
Ранги функциональных зависимостей
XY
XY
rang
PN  PIM, ST, GOR
GOR  ST
DN  DIM, CENA
(PN, DN)  U\(PN, DN)
PN, PIM, ST, GOR
GOR, ST
DN, DIM, CENA
U
3
4
2
1
1
2
PN, PIM, ST, GOR, DN, DIM, CENA o KOL
DN o DIM, CENA
3
PN o PIM, ST, GOR
4 GOR o ST
Рис. 2. Результат выполнения операции транзитивной редукции
на ранжированной диаграмме зависимостей
66
рении мы как бы «утяжеляем» правые части зависимости, а при
транзитивной редукции – «облегчаем» их (рис. 2).
Шаг 8. Учитывая на диаграмме не вычеркнутые атрибуты (выделены жирным шрифтом), получаем результирующую декомпозицию в виде четырех отношений (левая часть каждой зависимости на диаграмме определяет первичный ключ соответствующего
отношения):
R1 = PN, DN, KOL
R2 = DN, DIM, CENA
R3 = PN, PIM,GOR
R4 = GOR, ST
Все отношения находятся в нормальной форме Бойса – Кодда.
Следовательно, полученная база данных состоит из четырех таблиц
и также находится в нормальной форме Бойса – Кодда.
Пример 34. Рассмотрим более сложный пример формальных
данных.
Пусть U = AEKGINPRSTV и F = {N  A, NG  K, NK  T,
NK  I, K  R, NV  E, NEV  K, NV  S, N  P}.
Спроектируем реляционную базу данных методом синтеза.
Шаг 1. Расширяем зависимости из F:
N+ = NAP  N  AP;
NG+ = NGKATIRP  NG  KATIRP;
NK+ = NKATIRP  NK  ATIRP;
NK+ = …  NK  … (зависимость совпадает с предыдущей);
K+ = KR  K  R;
NV+ = NVAEKSPIRT  NV  AEKSPIRT;
NEV+ = NEVAKSPIRT  NEV  AKSPIRT;
NV+ = …  NV  …;
N+ = …  N  …;
Получаем расширенное множество зависимостей:
ℱ = {N  AP, NG  KATIRP, NK  ATIRP, NK  …, K  R,
NV  AEKSPIRT, NEV  AEKSPIRT, NV  …, N  …}
Шаг 2. Отбрасывая одинаковые зависимости (с многоточиями в
правой части), получим условно- или псевдонеизбыточное множество зависимостей:
ℱ0 = {N  AP, NG  KATIRP, NK  ATIRP, K  R,
NV  AEKSPIRT, NEV  AKSPIRT}
67
Шаг 3. Поскольку полученное множество зависимостей не содержит зависимости с полным набором атрибутов, то добавляем
тривиальную зависимость U  . Это делается для того, чтобы результирующая декомпозиция обладала свойством соединения без
потерь информации.
Д. Мейер показал [5], что, если некоторая подсхема схемы базы
данных R содержит универсальный ключ, или суперключ (не обязательно минимальный), то результирующая декомпозиция будет обладать свойством соединения без потерь информации относительно
заданного множества F-зависимостей, и обратно. Как будет продемонстрировано ниже, декомпозиционная подсхема, полученная из
тривиальной зависимости U  , всегда содержит суперключ или
его часть (как в примере 38). Кроме того, дополнительная подсхема
играет еще одну важную роль, а именно, она обеспечивает взаимосвязь подсхем (таблиц базы данных). Таким образом, выполнимость
свойства соединения без потерь информации обеспечивается добавлением лишней подсхемы, содержащей, как правило, универсальный ключ.
Однако наличие суперключа является необходимым, но недостаточным условием, т. е. наличие суперключа в какой-либо декомпозиционной подсхеме не гарантирует во всех случаях выполнимость свойства соединения без потерь информации. Этот факт
подтверждает пример 37. Поэтому рекомендуется всегда проводить
дополнительное исследование результирующей декомпозиции,
как это сделано в примерах, приведенных ниже.
Шаг 4. Разбиваем оставшиеся зависимости на классы эквивалентности и в каждом классе оставляем одного представителя.
Среди оставшихся зависимостей имеются две эквивалентные зависимости, выделенные жирным курсивом. В принципе можно удалить любую из них. Однако предпочтительно удалить ту, которая
содержит в левой части больше атрибутов. Это объясняется тем,
что каждая зависимость в методе синтеза дает отношение (таблицу), причем слева стоит ключ. Связь по ключу с другой таблицей в
схеме данных будет проще, если ключ содержит как можно меньше атрибутов, поэтому в качестве представителя рассматриваемого
класса эквивалентности оставляем зависимость NV  AEKSPIRT.
Шаг 5. Приведем оставшиеся зависимости к элементарному
виду, т. е. без лишних атрибутов слева. Этот шаг можно опустить.
Однако заметим, что все оставшиеся зависимости в рассматриваемом примере являются элементарными.
Шаг 6. Ранжируем оставшиеся зависимости (табл. 2).
68
Таблица 2
Ранги функциональных зависимостей
XY
XY
rang
N  AP
NG  KATIRP
NK  ATIRP
NV  AEKSPIRT
KR
U
NAP
NGKATIRP
NKATIRP
NVAEKSPIRT
KR
U
5
3
4
2
6
1
Шаг 7. Строим ранжированную диаграмму зависимостей, на которой выполняем операцию транзитивной редукции зависимостей
с большим рангом на зависимости с меньшим рангом (рис. 3).
Шаг 8. Учитывая на диаграмме не вычеркнутые атрибуты (выделены жирным шрифтом), получаем результирующую декомпозицию в виде шести отношений:
R1 = GNV
R2 = NVEKS
R3 = NGK
R4 = NKTI
R5 = NAP
R6 = KR
Отметим, что в примере 33 подсхема R1 = PN, DN, KOL содержит суперключ (PN, DN), так как (PN, DN)+ = PN, DN, PIM, ST,
GOR, DIM, CENA, KOL = U, а в данном примере подсхема R1 = GNV
содержит суперключ, так как GNV+ = GNVKTIREASP = U.
В примерах 33 и 34 метод синтеза был рассмотрен подробно. В реальных условиях проектирование часто приходится многократно
повторять, поскольку сразу все тонкости учесть не всегда возможно.
AEK G IN PRST V o ‡
1
2
3
NVo AEKSPIRT
4
5
NG o K ATIRP
NK o AT RP
N o AP
6
Ko R
Рис. 3. Результат выполнения операции транзитивной редукции
на ранжированной диаграмме зависимостей
69
В этом случае можно некоторые шаги алгоритма синтеза опустить,
тем самым ускорив проектирование. Кроме того, вместо имен атрибутов удобно использовать их буквенные или числовые обозначения, например, так, как это сделано в табл. 3 примера 35.
Для уменьшения количества атрибутов неключевые атрибуты целесообразно обозначать одной буквой, как это сделано в табл. 3. Тем
самым при проектировании можно значительно сократить количество используемых атрибутов, что позволяет выполнить проектирование базы данных вручную даже при большом количестве атрибутов.
Отдельные обозначения следует ввести только для тех неключевых атрибутов, которые участвуют в функциональных связях с
другими неключевыми атрибутами, как это сделано в примере 45.
Пример 35. Спроектируем ускоренным синтезом базу данных
для предметной области ВСТУПИТЕЛЬНЫЕ ЭКЗАМЕНЫ В ВУЗ.
Исходными данными для проектирования являются множество
атрибутов U и множество функциональных зависимостей F, которые справедливы на множестве атрибутов.
Если атрибутов достаточно много, например, больше тридцати,
то рекомендуется их искусственно уменьшить, переобозначив и
связав их с сущностями, как показано в табл. 3.
Сущностями являются АБИТУРИЕНТЫ, ПРЕПОДАВАТЕЛИ,
СПЕЦИАЛЬНОСТИ и ЭКЗАМЕНЫ.
В табл. 3 первичные ключи сущностей выделены.
Таблица 3
Сущности и их атрибуты
Сущности
АБИТУРИЕНТЫ
Атрибуты сущностей Первичный ключ
НомерАбитур
ФиоАбитур
Адрес
Телефон
Льгота
ПРЕПОДАВАТЕЛИ НомерПрепод
ФиоПрепод
Должность
СПЕЦИАЛЬОСТИ КодСпец
НазваниеСпец
ЭКЗАМЕНЫ
70
ПроходнойБалл
НомерЭкзам
Предмет
ДатаЭкзам

B
С
да



Обозначение
А
да
D
E
да
K
M
да
N
Таким образом, имеем множество атрибутов U = ABCDEKMN,
на котором справедливы зависимости F = {A  BE, C D, E  K,
M  N}, так как первичный ключ функционально определяет все
атрибуты сущности (см. раздел 1.3.1).
Выполним ускоренный синтез базы данных.
Строим расширенное множество зависимостей
ℱ = {A  BEK, C D, E  K, M  N}
Поскольку в расширенном множестве нет одинаковых зависимостей, то условно неизбыточное покрытие ℱ0 совпадает с ℱ. Эквивалентных зависимостей нет.
Поскольку нет зависимости с полным набором атрибутов, добавляем тривиальную зависимость U  .
Строим диаграмму зависимостей (рис. 4), в которой учитываем
непосредственное вхождение атрибутов нижестоящей зависимости
в вышестоящую зависимость. Например, атрибуты зависимости
E  K непосредственно входят в зависимость A  BEK, а атрибуты зависимости A  BEK в свою очередь непосредственно входят в
тривиальную зависимость. Атрибуты зависимостей M  N и C  D
непосредственно входят только в тривиальную зависимость U  .
Такая же диаграмма получится, если ранжировать зависимости.
Выполняем на диаграмме операцию транзитивной редукции.
Учитывая на диаграмме не вычеркнутые атрибуты (выделены жирным шрифтом), получаем результирующую декомпозицию:
R1 = ACM
R2 = MN
R3 = ABE
R4 = CD
R5 = EK
Подсхема R1 = ACM содержит суперключ, так как ACM+ =
= ACMBEDKN = U.
1
2
Mo N
AB C DEKMN o‡
A o BEK
3
5
4
C oD
E oK
Рис. 4. Результат выполнения операции транзитивной редукции
на диаграмме зависимостей
71
Перейдя к реальным данным, получим следующий набор таблиц проектируемой базы данных:
R1 (Абитур_Препод_Экзам) = (НомерАбитур, НомерПрепод,
НомерЭкзам);
R2 (Экзамены) = (НомерЭкзам, Предмет, ДатаЭкзам);
R3 (Абитуриенты) = (НомерАбитур, ФиоАбитур, Адрес, Телефон, Льгота, КодСпец);
R4 (Преподаватели) = (НомерПрепод, ФиоПрепод, Должность)
R5 (Специальности) = (КодСпец, НазваниеСпец, ПроходнойБалл);
При изложении алгоритма синтеза было сказано, что проверку
зависимостей на элементарность – шаг 5 (раздел 2.2) можно опустить, и если при этом останутся неэлементарные зависимости, то
это обязательно проявится на последующих шагах. Как? Покажем
это на следующем примере.
Пример 36. Рассмотрим на условиях примера 23, к чему может
привести отказ от проверки зависимостей на элементарность.
Как было получено в примере 23, множество функциональных
зависимостей F = {L  KA, A  DOXZC, DEM  K, D  EK} справедливо на множестве атрибутов U = ACDEKLMOXZ. Выполним
ускоренный синтез.
Строим расширенное множество зависимостей:
ℱ = {L  KADOXZCE, A  DOXZCEK, DEM  K, D  EK}
Анализируем множество ℱ. Оно не содержит эквивалентных зависимостей, но содержит зависимость DEM  K, которую требуется проверить на элементарность. Опускаем эту проверку и продолжаем синтез.
Очевидно, условно неизбыточное покрытие ℱ0 совпадает с ℱ.
В множестве ℱ нет зависимости с полным набором атрибутов, поэтому добавляем тривиальную зависимость U  .
Строим диаграмму зависимостей, на которой выполняем операцию транзитивной редукции зависимостей (рис. 5).
В результате выполнения операции транзитивной редукции,
как видно из рис. 5, зависимость DEM  K «осталась» без правой
части. Так случилось потому, что эта зависимость не элементарная.
Для проверки снова обратимся к исходному множеству зависимостей F = {L  KA, A  DOXZC, DEM  K, D  EK}.
В примере 23 было показано, что зависимость DEM  K не элементарная, и ее можно заменить зависимостью D  K. Тогда множество F-зависимостей можно заменить множеством
F1 = {L  KA, A  DOXZC, D  K, D  EK}.
72
1
ACDEKLMOXZ o ‡
3
DEM o K
2
L o KADOXZCE
4
5
A o DOXZCEK
D o EK
Рис. 5. Результат выполнения операции транзитивной редукции
на диаграмме зависимостей
Расширяем множество F1:
ℱ1 = {L  KADOXZCE, A  DOXZCEK, D  KE, D  EK}.
Получили две одинаковые зависимости (выделены), одна из которых, очевидно, «лишняя». Поэтому условно неизбыточное покрытие множества ℱ будет таким:
ℱ10 = {L  KADOXZCE, A  DOXZCEK, D  KE}.
Так как среди оставшихся зависимостей нет зависимости с полным набором атрибутов, то добавляем тривиальную зависимость
U  .
На рис. 6 показана модифицированная диаграмма зависимостей,
на которой выполнена операция транзитивной редукции.
1
ACDEKLMOXZ o ‡
Lo KADOXZCE
2
3
4
A o DOXZCEK
D o EK
Рис. 6. Модифицированная диаграмма зависимостей
73
Результирующая декомпозиция будет такой (первичные ключи
выделены):
R1 = LM;
R2 = LA;
R3 = ADOXZC;
R4 = DEK.
Подсхема R1 = LM содержит суперключ LM, так как LM+ =
= LMKADOXZCE = U.
Как было сказано выше, наличие суперключа хотя бы в одной
подсхеме результирующей декомпозиции является необходимым,
но недостаточным условием, т. е. суперключ есть, но свойство соединения без потерь информации не выполняется. Это может случиться тогда, когда в множестве F выявляются несколько возможных суперключей, которые, естественно, функционально определяют друг друга. Поясним эту ситуацию на следующем примере.
Пример 37. [3]. Пусть множество функциональных зависимостей F = {C  A, A  E, KG  CD, CD  KG, EK  B, BG  C, AC 
 E} справедливо на множестве атрибутов U = ABCDEKG.
Из расширенного множества ℱ, приведенного ниже, будет видно, что KG и CD – суперключи, которые функционально определяют друг друга.
Выполним ускоренный синтез.
Расширяем множество F:
ℱ = {C  AE, A  E, KG  CDAEB, CD  KGAEB, EK  B,
BG  CAE, AC  E}.
Получили два класса эквивалентности: (C  AE, AC  E) и
(KG  CDAEB и CD  KGAEB). В каждом классе оставляем одного
представителя, причем в классе эквивалентности для суперключей небезразличен выбор представителя. Попробуем выбрать представителем зависимость KG  CDAEB. Тогда условно неизбыточное покрытие будет таким: ℱ0 = {C  AE, A  E, KG  CDAEB,
EK  B, BG  CAE}.
Тривиальную зависимость добавлять не надо, так как зависимость KG  CDAEB содержит полный набор атрибутов U.
На рис. 7 показана диаграмма зависимостей, на которой выполнена операция транзитивной редукции.
Результирующая декомпозиция будет такой (первичные ключи
выделены):
R1 = KGD;
R2 = BGC;
R3 = EKB;
R4 = CA;
R5 = AE.
Подсхема R1 = KGD содержит суперключ KG, так как KG+ =
= KGCDAEB = U.
74
1
2
BG o CAE
4
C o AE
5
A oE
KG o CDAEB
3
EKo B
Рис. 7. Диаграмма зависимостей с корневой вершиной
KG  CDAEB
Однако проверка показала, что свойство соединения без потерь
информации не выполняется.
Если же в классе эквивалентности (KG  CDAEB и CD  KGAEB)
оставить вторую зависимость CD  KGAEB в качестве представителя класса, то диаграмма зависимостей будет такой, как показано на
рис. 8.
После выполнения на диаграмме операции транзитивной редукции зависимостей получим результирующую декомпозицию в виде:
R1 = CDKG; R2 = BGC;
R3 = EKB;
R4 = CA;
R5 = AE.
Нетрудно убедиться, что такая декомпозиция обладает свойством соединения без потерь информации.
1
2
BG o CAE
4
C o AE
5
A oE
CD o KGAEB
3
EK o B
Рис. 8. Диаграмма зависимостей с корневой вершиной
CD  KGAEB
75
В данном случае мы имеем два суперключа CD и KG, которые
функционально определяют друг друга:
CD+ = KGAEB = U и KG+ = CDAEB = U.
Что делать, если ни одна из подсхем результирующей декомпозиции не содержит суперключа, т. е. не выполнено условие необходимости. Рассмотрим такой пример.
Пример 38. Пусть множество функциональных зависимостей
F = {AB  C, DE  A, G  L, KA  LG, C  KDG} справедливо на
множестве атрибутов U = ABCDELKG.
Выполним ускоренный синтез.
Расширяем множество F:
ℱ = {AB  CKDGL, DE  A, G  L, KA  LG, C  KDGL}.
Поскольку расширенное множество не содержит «лишних» зависимостей с одинаковой левой частью, то условно неизбыточное
покрытие ℱ0 совпадает с ℱ.
Так как среди оставшихся зависимостей нет зависимости с полным
набором атрибутов, то добавляем тривиальную зависимость U  .
На рис. 9 показана диаграмма зависимостей, на которой выполнена операция транзитивной редукции.
Результирующая декомпозиция будет такой (первичные ключи
выделены):
R1 = BE; R2 = ABC; R3 = DEA; R4 = CKDG; R5= KAG; R6= GL
Проверка показала, что свойство соединения без потерь информации не выполняется. Проанализируем результирующую декомпозицию на наличие суперключа:
BE+ = BE  U; ABC+ = ABCKDL  U; CKDG+ = CKDGL  U;
DEA+ = DEA  U; KAG+ = KAGL  U; GL+ = GL  U.
Видно, что ни одна декомпозиционная подсхема не содержит суперключа. Что делать? Очевидно, нужно какую-нибудь подсхему
дополнить атрибутами до суперключа, тем самым выполнив условие необходимости. Практика показывает, что легче всего суперключ можно найти из зависимости, включающей полный набор
атрибутов. В данном примере – из зависимости, которая определяет подсхему R1. Добавив в нее атрибут D, получим суперключ BED,
так как BED+ = BEDACKGF = U. Тогда R1 = BED и теперь свойство
соединения без потерь информации будет выполняться.
Выполнив проектирование базы данных методом синтеза, нужно проанализировать полученные результаты. При этом можно
воспользоваться следующими рекомендациями.
76
ABCDELGK o ‡
1
2
4
AB o CKDGL
C o KDGL
6
5
3
DE o A
KA o LG
GoL
Рис. 9. Диаграмма зависимостей
1. Прежде, чем выполнять проектирование, желательно уменьшить количество атрибутов, например как это сделано в табл. 3.
2. При выполнении проектирования проверку функциональных
зависимостей на элементарность можно опустить. Это обязательно
проявится на диаграмме при выполнении операции транзитивной
редукции зависимостей. Например, в правой части неэлементарной зависимости будут вычеркнуты все атрибуты, как в примере
36. Тогда нужно выполнить проверку этой зависимости на элементарность.
3. Свойство соединения без потерь информации выполняется
для результирующей декомпозиции, если обеспечено условие необходимости (наличие суперключа в какой-нибудь декомпозиционной подсхеме [5]). Обычно суперключ остается после выполнения
операции транзитивной редукции в зависимости с полным набором
атрибутов, если такая зависимость есть, или в добавленной тривиальной зависимости U  . Если условие необходимости все же не
выполнено, то нужно добиться его выполнения, например, как это
сделано в примере 38.
4. Наличие суперключа в какой-нибудь декомпозиционной
подсхеме является необходимым, но не достаточным условием
выполнимости свойства соединения без потерь информации, т. е.
суперключ присутствует, а декомпозиция не обладает этим свойством. Такая ситуация может возникнуть, если имеется несколько
возможных суперключей, которые, естественно, функционально
определяют друг друга. Тогда при построении расширенного множества такие зависимости войдут в один класс эквивалентности,
и потребуется дополнительные усилия по выбору представителя
класса эквивалентности, как в примере 37.
77
2.3. Метод ER-диаграмм («сущность-связь»)
В настоящее время хорошо известен метод проектирования реляционных баз данных, основанный на использовании диаграмм,
одной из которых является так называемая ER-диаграмма (Entity –
сущность, Relationship – связь). Данный метод, называемый иначе методом «сущность-связь», широко используется в средствах
автоматизированного проектирования. Метод прост, основан на
здравом смысле и, в отличие от декомпозиции и синтеза, не требует
никаких теоретических знаний. Метод основан на небольшом количестве правил и при их использовании требует достаточно простых рассуждений. Естественно, проектировщик базы должен досконально представлять семантику данных предметной области.
При проектировании методом ER-диаграмм обычно используют
два вида диаграмм:
– диаграммы ER-экземпляров;
– диаграммы ER-типа, или просто ER-диаграммы. В данном
учебном пособии будем диаграммы ER-типа называть ER-диаграммами.
ER–диаграммы строятся на основе диаграмм ER-экземпляров.
Например, для сущностей ПОСТАВЩИКИ и ДЕТАЛИ из предметной области ПОСТАВКА_ДЕТАЛЕЙ диаграмма ER-экземпляров
может быть задана в виде табл. 4.
Как видно из таблицы, диаграмма ER-экземпляров отображает связь между парой сущностей (бинарная связь). В столбце «Поставляет» – имя связи, а в столбцах «Поставщик» и «Деталь» даны
экземпляры первичных ключей соответствующих сущностей.
При проектировании базы данных используются две характеристики:
множественность связи: 1:1, 1:М, М:1, М:М;
Таблица 4
Диаграмма ER-экземпляров
Поставщик
78
Поставляет
Деталь
P1
D1
P2
D2
P3
D3
P4
D4
P5
D5
класс принадлежности сущности КП: О – обязательный (для
рассматриваемой пары сущностей предметной области каждый экземпляр одной сущности обязательно связан с каким-то экземпляром другой сущности) и Н – необязательный (какой-то экземпляр
одной сущности может быть не связан ни с одним экземпляром другой сущности).
Например, в табл. 4 поставщики P2 и P5 не поставляют деталей, поэтому для сущности ПОСТАВЩИК определим КП–Н (необязательный). Аналогично для сущности ДЕТАЛЬ также определим КП–Н, так как деталь D3 не поставляется поставщиками.
Поставщик P3 поставляет детали D1 и D4. Поэтому для деталей
множественность связи обозначим «М». Каждая деталь поставляется только одним поставщиком, поэтому для поставщиков множественность связи – «1».
На ER-диаграмме сущность (в нотации, близкой к нотации
П. Чена [15]) изображается в виде прямоугольника, а связь – в виде
ромба. Соответствующие имена пишутся внутри фигур. Например,
ER-диаграмма, построенная на основе диаграммы ER-экземпляров
табл. 4, показана на рис. 10.
Для сущности с КП – Н принято точку изображать за пределами прямоугольника, как это сделано на рис. 10, а для сущности с
КП – О точку изображают внутри прямоугольника, как на рис. 11.
Использование описанной нотации даже для небольших баз данных может привести к громоздким и плохо обозримым диаграммам. Гораздо проще не рисовать диаграммы, а их описывать. Так,
описание ER-диаграммы для рассматриваемого примера можно
дать в виде:
ПОСТАВШИКИ (1, Н) поставляют (М, Н) ДЕТАЛИ
1
Поставщик
М
Поставляет
Деталь
Рис. 10. ER-диаграмма для связи 1: М и КП: Н – Н
Преподаватель
Рис. 11. Фрагмент ER-диаграммы
для сущности с КП: О
79
2.3.1. Этапы проектирования
При проектировании реляционных баз данных методом ERдиаграмм выделяют следующие этапы [7]:
1. Выбор предметной области, выделение в ней сущностей с указанием возможных первичных ключей для каждой сущности. Иногда сначала задают атрибуты сущностей, а затем на их основе определяют сами сущности.
2. Описание ER-диаграмм с указанием правила, которое должно
быть использовано для каждой задействованной пары сущностей.
3. Формирование набора предварительных отношений с указанием первичного ключа для каждого отношения и с учетом указанных на этапе 2 правил.
4. Добавление неключевых атрибутов в предварительные отношения.
5. Анализ предварительных отношений на предмет «сильных»
нормальных форм (начиная с 3НФ). Если отношения не находятся
в «сильной» нормальной форме, то необходимо проведение дальнейшей нормализации с целью получения окончательного набора
отношений, находящихся в «сильной» нормальной форме.
6. Проверка выполнимости свойства соединения без потерь информации для окончательного набора отношений. Данный этап
обычно опускается, однако этого делать не следует, так как метод
не гарантирует выполнимость указанного свойства. Если свойство
соединения без потерь информации не выполняется, то необходимо
добиться выполнимости этого свойства, используя суперключ, как
будет показано в примере 40.
2.3.2. Правила формирования отношений
В литературе описаны восемь правил формирования отношений. Чаще всего используются шесть правил, которые позволяют
последовательно сформировать отношения результирующей декомпозиции. В работе [8] даны упрощенные правила, которые в данном
пособии мы не будем использовать. Перечислим правила, ориентируясь на более полный вариант, изложенный в работах [6], [7]:
Правило 1. Если множественность связи между парой сущностей 1:1 и КП: О – О, то формируется одно отношение, первичным
ключом которого может быть выбран первичный ключ одной из
сущностей этой пары (любой). Первичный ключ второй сущности
будет выступать в роли альтернативного (возможного) ключа.
80
Описание ER-диаграммы для этого правила может быть таким (С1
и С2 – сущности): С1 (1, О) связана_с (1, О) С2, что означает, каждый экземпляр сущности С1 обязательно связан только с одним экземпляром сущности С2, и наоборот, каждый экземпляр сущности
С2 обязательно связан только с одним экземпляром сущности С1.
Пусть К1 – первичный ключ сущности С1, а К2 – первичный
ключ сущности С2. Тогда по правилу 1 должно быть сформировано
отношение R1(К1, К2,...) или отношение R2(К2, К1,...), где первичный ключ отмечен жирным шрифтом с подчеркиванием, а альтернативный ключ просто подчеркнут.
Правило 2. Если множественность связи между парой сущностей 1:1 и КП: О – Н или Н – О, то под каждую сущность формируется отношение с первичными ключами, являющимися таковыми для соответствующих сущностей. А далее, к отношению
О-сущности добавляется в качестве альтернативного ключа первичный ключ Н-сущности.
Описание ER-диаграммы для этого правила может быть таким:
С1 (1, О) связана_с (1, Н) С2
или
С1 (1, Н) связана_с (1, О) С2.
Будут сформированы пары отношений:
R1(К1, К2,...), R2(К2,...) или
R1(К1,...), R2(К2, К1,...) соответственно.
Правило 3. Если множественность связи между парой сущностей 1:1 и КП: Н – Н, то формируются три отношения. Два отношения будут соответствовать связываемым сущностям со своими
первичными ключами, а третье – для связи. В качестве первичного ключа третьего отношения может выступать первичный ключ
любой из этих двух сущностей. Второй же ключ будет выступать
в роли возможного (альтернативного) ключа в отношении-связи.
Описание ER-диаграммы для этого правила может быть таким:
С1 (1, Н) связана_с (1, Н) С2.
Будут сформированы отношения:
R1(К1,...), R2(К2,...), R3(К1, К2,...) или
R1(К1,...), R2(К2,...), R3(К2, К1,...)
81
Правило 4. Если множественность связи между парой сущностей 1:М или М:1 и КП:О для М-сущности, то формируются два
отношения (по одному на каждую сущность). А далее первичный
ключ 1-связной сущности добавляется как простой атрибут в отношение М-связной сущности.
Описание ER-диаграммы для этого правила может быть таким:
С1 (1, любой) связана_с (М, О) С2
или
С1 (М, О) связана_с С2 (1, любой).
Будут сформированы отношения:
R1(К1,...), R2(К2, К1,...) или
R1(К1, К2,...), R2(К2,...) соответственно.
Правило 5. Если множественность связи между парой сущностей 1:М или М:1 и КП:Н для М-сущности, то формируются три
отношения. Два из них будут соответствовать связываемым сущностям со своими первичными ключами, а третье – для связи. Первичным ключом отношения-связи должен быть первичный ключ
М-связной сущности, а первичный ключ 1-связной сущности должен присутствовать в отношении связи как простой атрибут.
Описание ER-диаграммы для этого правила может быть таким:
С1 (1, любой) связана_с (М, Н) С2
или
С1 (М, Н) связана_с С2 (1, любой).
Будут сформированы отношения:
R1(К1,...), R2(К2,...), R3(К2, К1,...) или
R1(К1,...), R2(К2,...), R3(К1, К2,...) соответственно.
Правило 6. Если множественность связи между парой сущностей М:М, то всегда формируются три отношения. Два отношения
будут соответствовать связываемым сущностям со своими первичными ключами, а третье отношение – для связи. Первичный ключ
отношения-связи будет составлен из первичных ключей обеих
сущностей (составной первичный ключ).
Описание ER-диаграммы для этого правила может быть таким:
С1 (М, любой) связана_с (М, любой) С2
82
Будут сформированы отношения:
R1(К1,...), R2(К2,...), R3(К1, К2,...).
Пример 39.
Этап 1. Выберем предметную область ПОСТАВКА ДЕТАЛЕЙ.
Определим сущности с указанием первичных ключей для каждой сущности:
ПОСТАВЩИКИ (PN,...);
ДЕТАЛИ (DN,...);
ГОРОДА (GOR,...);
СТАТУСЫ (ST,...).
Статусы можно не определять, как сущность.
Многоточиями обозначены неключевые атрибуты сущности.
Этап 2. На основе здравого смысла опишем ER-диаграмму.
ПОСТАВЩИКИ (М, Н) поставляют (М, Н) ДЕТАЛИ (правило 6),
ПОСТАВЩИКИ (М, О) проживают_в (1, Н) городах (правило 4),
ПОСТАВЩИКАМ (М, О) присваиваются (1, Н) СТАТУСЫ (правило 4),
ГОРОДА (М, О) имеют (1, Н) СТАТУСЫ (правило 4).
Такое описание ER-диаграммы нужно понимать следующим образом:
Каждый поставщик может поставлять, а может не поставлять
(«Н» у поставщика) несколько разных типов деталей («М» у детали). Каждая деталь может поставляться, а может не поставляться
(«Н» у детали) несколькими поставщиками («М» у поставщика).
Каждый поставщик обязательно («О» у поставщика) проживает
только в одном городе («1» у города). В конкретном городе может
и не быть поставщика («Н» у города), однако в одном городе могут
проживать несколько поставщиков («М» у поставщика).
Каждому поставщику обязательно («О» у поставщика) присваивается только один статус («1» у статуса). Каждое значение статуса
(целое число), например 50, может быть не связано ни с каким поставщиком («Н» у статуса). Нескольким поставщикам может быть
присвоен одинаковый статус, например если они проживают в одном городе («М» у поставщика).
Каждый конкретный город имеет всегда один и тот же статус
(«1» у статуса), причем город обязательно имеет статус («О» у города). Каждому значению статуса может соответствовать несколько
городов, например Санкт-Петербург и все города Ленинградской
области (Кириши, Зеленогорск и пр.) имеют статус «М» у города.
83
Причем, могут быть такие значения статуса, которые не связаны
ни с каким городом («Н» у статуса).
Этап 3. Формируем набор предварительных отношений в соответствии с описанием ER-диаграммы и перечисленными выше правилами.
Для связи поставляют (правило 6):
Поставщики (PN,...)
Детали (DN,...)
Поставщики_Детали (PN, DN,...)
Для связи проживают_в (правило 4):
Поставщики (PN, GOR,...). Здесь GOR добавлен по правилу 4
как простой атрибут.
Города (GOR,...)
Для связи присваиваются (правило 4):
Поставщики (PN, GOR, ST,...). Здесь ST добавлен по правилу 4
как простой атрибут.
Обратите внимание на то, что отношение «Поставщики» надо
использовать с максимально полученными атрибутами на предыдущих шагах анализа связей между сущностями. Поэтому используем отношение «Поставщики» (PN, GOR,...), а затем уже к нему
добавляем по правилу 4 атрибут ST.
Статусы (ST,...)
Для связи имеют (правило 4):
Города (GOR, ST,...). Здесь ST добавлен по правилу 4 как простой атрибут.
Статусы (ST,...).
Этап 4. Добавляем в полученные отношения неключевые атрибуты. В результате получаем следующий набор отношений (таблиц):
1. Поставщики (PN, PIM, GOR, ST), где PIM – имя поставщика
(добавленный неключевой атрибут).
2. Детали (DN, DIM, CENA), где DIM – имя, а CENA – цена детали (добавленные неключевые атрибуты).
3. Поставщики_Детали (PN, DN, КOL), где КOL – количество
поставляемых деталей (добавленный неключевой атрибут). По
смыслу эта таблица будет содержать информацию о поставках, поэтому ее можно назвать не «Поставщики_Детали», а «Поставки».
4. Города (GOR, ST).
5. Статусы (ST). Получили отношение с одним атрибутом (таблицу с одним столбцом), что бессмысленно. Атрибут ST присутствует в других отношениях. Поэтому полученное отношение можно отбросить.
84
Этап 5. Этот этап проектировщики базы данных часто не выполняют [6], а напрасно, так как полученные отношения могут не
находится в «сильной» (хотя бы в третьей) нормальной форме, что
и оказалось в рассматриваемом примере. Для этого надо на заданном множестве атрибутов построить множество функциональных
зависимостей или рассмотреть каждое отношение и в нем найти
функциональные зависимости.
Так, для отношения «Поставщики» справедливо множество зависимостей
FПоставщики = {PN  PIM, PN  GOR, PN  ST, GOR  ST}.
Анализ этих зависимостей показывает, что зависимость PN  ST
(подчеркнута) транзитивно следует из зависимостей: PN  GOR и
GOR  ST, поэтому отношение «Поставщики» не находится в третьей нормальной форме. Что делать?
В этом случае рекомендуется «разорвать» транзитивную зависимость, декомпозируя отношение на два отношения, например, таких:
Поставщики (PN, PIM, GOR) и Города (GOR, ST).
Выполнив декомпозицию, нужно проверить, обладает ли она свойством соединения без потерь информации и свойством сохранения
функциональных зависимостей, как это было сделано в разделе 1.8.2.1.
Предложенная декомпозиция обладает этими свойствами. Кроме того,
отношение Города (GOR, ST) уже было получено ранее.
Теперь оба отношения находятся в нормальной форме Бойса–Кодда.
Почему же такое случилось с отношением «Поставщики»?
Это произошло оттого, что здравый смысл иногда нас поводит.
В описании ER-диаграммы мы перестарались и дали лишнюю
связь, которая появилась из-за лишней сущности СТАТУСЫ:
ПОСТАВЩИКАМ (М, О) присваиваются (1, Н) СТАТУСЫ
(правило 4).
Если этой связи не было бы, то все было бы хорошо.
Такая ситуация довольно часто встречается при проектировании баз данных, так как выделение сущностей предметной области – задача, не всегда имеющая единственное решение.
Легко убедиться в том, что остальные отношения также находятся в нормальной форме Бойса – Кодда.
Таким образом получаем окончательный набор отношений (таблиц), который совпадает с набором отношений, полученным по методу синтеза для этой же предметной области:
85
R1: Поставщики (PN, PIM, GOR);
R2: Детали (DN, DIM, CENA);
R3: Поставки (PN, DN, КOL);
R4: Города (GOR, ST).
Этап 6. Поскольку результат проектирования совпадает с результатом, полученным по методу синтеза, то свойство соединения
без потерь информации выполняется.
Пример 40. Спроектируем методом ER-диаграмм базу данных
для предметной области ВСТУПИТЕЛЬНЫЕ ЭКЗАМЕНЫ В ВУЗ.
В примере 35 эта база данных была спроектирована методом синтеза.
Этап 1.
Итак, из табл. 3 примера 35 имеем следующие сущности с указанием их первичных ключей:
АБИТУРИЕНТЫ (НомерАбитур,...);
ПРЕПОДАВАТЕЛИ (НомерПрепод,...);
ЭКЗАМЕНЫ (НомерЭкзам,...);
СПЕЦИАЛЬНОСТИ (КодСпец,...).
Этап 2. Описание ER-диаграммы:
АБИТУРИЕНТЫ (М, Н) сдают (М, Н) ЭКЗАМЕНЫ (правило 6);
АБИТУРИЕНТЫ (М, О) выбирают (1, О) СПЕЦИАЛЬНОСТИ
(правило 4);
ПРЕПОДАВАТЕЛИ (М, Н) принимают (М, О) ЭКЗАМЕНЫ
(правило 6).
Этап 3. В соответствии с правилами формируем набор предварительных отношений:
Для связи сдают (правило 6):
АБИТУРИЕНТЫ (НомерАбитур,...);
ЭКЗАМЕНЫ (НомерЭкзам,...);
АБИТУРИЕНТЫ_ЭКЗАМЕНЫ (НомерАбитур,НомерЭкзам,...).
Для связи выбирают (правило 4):
АБИТУРИЕНТЫ (НомерАбитур, КодСпец...). Здесь КодСпец
добавлен по правилу 4 как простой атрибут;
СПЕЦИАЛЬНОСТИ (КодСпец,...).
Для связи принимают (правило 6):
ПРЕПОДАВАТЕЛИ (НомерПрепод,...);
ЭКЗАМЕНЫ (НомерЭкзам,...);
ПРЕПОДАВАТЕЛИ_ЭКЗАМЕНЫ (НомерПрепод, НомерЭкзам,..).
Этап 4. Добавляем в полученные отношения неключевые атрибуты из табл. 3 примера 35. Получим набор результирующих отношений (таблиц):
86
R1: АБИТУРИЕНТЫ (НомерАбитур, ФиоАбитур, Адрес, Телефон, КодСпец, Льгота);
R2: ЭКЗАМЕНЫ (НомерЭкзам, предмет, Дата);
R3: АБИТУРИЕНТЫ_ЭКЗАМЕНЫ (НомерАбитур,НомерЭкзам);
R4: СПЕЦИАЛЬНОСТИ (КодСпец, НазваниеСпец, Проходной_
балл);
R5: ПРЕПОДАВАТЕЛИ (НомерПрепод, ФиоПрепод, Должность);
R6: ПРЕПОДАВАТЕЛИ_ЭКЗАМЕНЫ (НомерПрепод, Номер
Экзам) или в обозначениях табл. 3 из примера 35:
R1= ABE
R2 = MN
R3 = AM
R4 = EK
R5 = CD
R6 = CM.
Для проверки свойства соединения без потерь информации воспользуемся множеством функциональных зависимостей из того же
примера:
F = {A  BE, C D, E  K, M  N}.
Проверка показала, что свойство соединения без потерь информации не выполняется. Что надо сделать, чтобы это свойство выполнялось?
Как было сказано ранее, Д. Мейер показал [5], что необходимым
условием выполнимости свойства соединения без потерь информации является наличие суперключа (не обязательно минимального)
хотя бы в одной декомпозиционной подсхеме из результирующей
декомпозиции.
Задача поиска суперключа может быть решена по одному из алгоритмов, изложенных в разделе 1.5.
Добавив в результирующий набор еще одно отношение, содержащее суперключ, можно добиться выполнимости свойства соединения без потерь информации.
В рассматриваемом примере таким ключом является набор
атрибутов ACM, так как ACM+ = ACMBEKDN = U. Таким образом,
добавление к полученному набору отношение R7 = ACM или с реальными данными:
R7: АБИТУРИЕНТЫ_ПРЕПОДАВАТЕЛИ_ЭКЗАМЕНЫ (НомерАбитур, НомерПрепод, НомерЭкзам), как показала проверка,
успешно решает проблему.
Перечисленные выше шесть правил сформулированы для бинарных связей, т. е. для связей между парами сущностей.
В работе [6] предложены еще два правила, которые используют
связи более высоких порядков. Рассмотрим их подробнее.
87
Поток
Преподаватель
Читает
Дисциплина
Рис. 12. ER-диаграмма для связи-триплета
Правило 7 сформулировано для случая, когда связываются одновременно три сущности. Такая связь названа триплетом. На
рис. 12 приведен пример ER-диаграммы связи-триплета.
Пример 41 [6]. В качестве предметной области выбран ВУЗ.
Имеются преподаватели, которые читают лекции потокам студентов. Выделим три сущности: ПРЕПОДАВАТЕЛЬ, ДИСЦИПЛИНА
и ПОТОК с первичными ключами Номер_преподавателя, Название_дисциплины и Номер_потока соответственно. Пусть лекции
по одному и тому же предмету могут читать несколько преподавателей. Одному преподавателю разрешается читать несколько предметов. На рис. 12 изображена ER-диаграмма для этого случая.
Правило 7 [6]. В случае М-сторонней связи необходимо сгенерировать М + 1 предварительное отношение – по одному отношению
на каждую из М сущностей с ключами, совпадающими с ключами
сущностей, и одно отношение для связи с составным ключом, составленным из первичных ключей связываемых сущностей. Классы принадлежности (КП) сущностей не имеют значения.
Здесь под М-сторонней связью понимается связь М:М между каждой парой сущности (Преподаватель – Поток, Преподаватель – Дисциплина и Поток –Дисциплина). Так, для рассматриваемого примера, изображенного на рис. 12, должны быть сформированы согласно
правилу 7 четыре отношения (первичные ключи выделены):
R1 (Номер преподавателя,...);
R2 (Название дисциплины,...);
R3 (Номер_потока,...);
R4 (Номер преподавателя, Название дисциплины, Номер_потока,...).
Далее, логически рассуждая, автор этого примера приходит к
выводу, что в отношении R4 можно оставить в качестве первичного
ключа только два атрибута, а третий атрибут «Номер преподавателя сделать неключевым»:
R4 (Название дисциплины, Номер_потока, Номер преподавателя,...)
88
И в этом автор прав, что можно легко доказать [7], используя
для проектирования формальный метод синтеза, рассмотренный в
разделе 2.2.
Проведем для сравнения проектирование методом синтеза, добавив для каждой сущности хотя бы по одному неключевому атрибуту.
Итак, пусть имеем исходный набор атрибутов U = ABCDEKL, где:
A – номер преподавателя;
B – номер кафедры, на которой работает преподаватель;
C – стаж работы преподавателя;
D – название дисциплины, которую читает преподаватель;
E – количество часов, отводимых на дисциплину;
K – номер потока, которому читается дисциплина;
L – количество групп в потоке.
Предположим, что для каждого предмета отведено фиксированное количество часов. Такое предположение можно сделать, не нарушая строгости данного случая.
На множестве атрибутов U можно определить функциональные
зависимости: F = {A  BC, DK  A, K  L, D  E}.
Условно неизбыточное покрытие ℱ0 расширенного множества зависимостей будет таким: ℱ0 = {A  BC, DK  ABCEL, K  L, D  E}.
Поскольку в полученном множестве имеется зависимость с полным набором атрибутов (подчеркнута), тривиальную зависимость
U   добавлять не надо.
Проверку зависимостей на элементарность опускаем.
Из диаграммы (рис. 13) получим результирующую декомпозицию:
R1 = ABC соответствует отношению R1 (Номер преподавателя,...);
R2 = DE соответствует отношению R2 (Название дисциплины,...);
R3 = KL соответствует отношению R3 (Номер потока,...);
R4 = DKA соответствует отношению R4 (Название дисциплины,
Номер потока, Номер_преподавателя).
DK o ABCEL
1
2
A o BC
3
DoE
4
Ko L
Рис. 13. Результирующая диаграмма зависимостей
89
Видно, что набор атрибутов DK является суперключом, причем
минимальным, так как DK+ = DKABCLE = U, но D+ = DE  U и K+ =
= KL  U. Это обстоятельство и позволило заменить первичный
ключ в отношении R4 (Номер преподавателя, Название дисциплины, Номер_потока,...) на набор из двух атрибутов:
R4 (Название дисциплины, Номер_потока, Номер преподавателя,...).
Следует отметить, что в некоторых случаях использование правила 7 позволяет уменьшить количество таблиц в реляционной
базе данных. В данном случае количество таблиц при проектировании методом ER-диаграмм совпадает с количеством таблиц, полученных при проектировании методом синтеза, однако синтез сразу
дает ключ в таблице R4, состоящий из двух атрибутов вместо трех.
Правило 7 было сформулировано для случая, когда связываются
одновременно три сущности. Такая связь названа в работе [5] триплетом. Однако можно это правило обобщить на случай большего
количества М-сторонних связей между сущностями. Кроме того,
модификация этого правила позволила найти процедуру уменьшения таблиц в результирующей декомпозиции, полученной только с
использованием шести правил. Эта процедура будет подробно описана в разделе 2.6. Здесь же рассмотрим процедуру для триплета.
Поскольку между сущностями ПРЕПОДАВАТЕЛИ, ПОТОКИ
и ДИСЦИПЛИНЫ существуют только М-сторонние связи, то независимо от класса принадлежности сущностей по правилу 6 для
каждой М-сторонней связи должно быть получено по три таблицы.
В этом случае описание ER-диаграммы будет таким:
ПРЕПОДАВАТЕЛИ (М) читают (М) ДИСЦИПЛИНЫ;
ДИСЦИПЛИНЫ (М) читаются (М) ПОТОКАМ;
С ПОТОКАМИ (М) работают (М) ПРЕПОДАВАТЕЛИ;
Результирующие таблицы будут такими:
R1: ПРЕПОДАВАТЕЛИ (Номер преподавателя,...);
R2: ДИСЦИПЛИНЫ (Название дисциплины,...);
R3: ПРЕПОДАВАТЕЛИ_ДИСЦИПЛИНЫ (Номер преподавателя, Название дисциплины);
R4: ПОТОКИ (Номер_потока,...);
R5: ДИСЦИПЛИНЫ_ПОТОКИ (Название дисциплины,Номер_
потока);
R6: ПРЕПОДАВАТЕЛИ_ПОТОКИ (Номер преподавателя, Номер_потока).
Спроектированная база данных содержит 6 таблиц.
90
Если теперь удалить таблицы R3, R5 и R6 и вместо них добавить таблицу R7: ПРЕПОДАВАТЕЛИ_ДИСЦИПЛИНЫ_ПОТОКИ
(Номер преподавателя, Название дисциплины, Номер_потока,...),
как показано на рис. 14, то результат проектирования будет такой
же, как и при использовании правила 7.
На рис. 14 видно, что М-связанные сущности ПРЕПОДАВАТЕЛИ, ДИСЦИПЛИНЫ и ПОТОКИ образуют кольцо, причем добавленная таблица R7 содержит не минимальный суперключ (Номер
преподавателя, Название дисциплины, Номер_потока) или в обозначениях, данных выше, – набор атрибутов ADK. Минимальным
суперключом является набор атрибутов DK. Поэтому в таблице R7
в качестве первичного ключа можно оставить набор атрибутов DK,
а атрибут A сделать неключевым, как интуитивно предложено в работе [5]. Тогда таблица R7 будет такой:
R7: ПРЕПОДАВАТЕЛИ_ДИСЦИПЛИНЫ_ПОТОКИ (Название
дисциплины, Номер_потока, Номер преподавателя,...)
Теперь база данных, спроектированная по методу ER-диаграмм,
состоящая из таблиц R1, R2, R4, R6, R7, полностью совпадает с результатами проектирования по методу синтеза.
В работе [5] предлагается еще использовать правило 8, учитывающее ролевые связи между сущностями. Этот случай, как правило,
не дает выигрыша по количеству результирующих таблиц, однако
делает прозрачной структуру таблиц. Метод синтеза для этого случая дает меньше таблиц. Продемонстрируем этот факт примером.
R3
M
Преподаватели
A
R5
M
M
Дисциплины
D
M
Потоки
K
M
M
R7(DKA)
R6
Рис. 14. Операция уменьшения количества таблиц
в базе данных для триплета
91
Пример 42. [6] Развивая предыдущий пример о преподавателях,
предположим, что некоторые из них являются заведующими кафедр, т. е. руководителями для других (обычных) преподавателей.
Графически это показано на рис. 15.
Пусть ключом сущности ПРЕПОДАВАТЕЛЬ является Таб_номер. Экземпляры данной сущности могут играть роль либо заведующего кафедрой, либо обычного преподавателя. Два ролевых набора ЗАВ_КАФЕДРОЙ и ОБЫЧН_ПРЕПОД соединяются связью
руководит.
На ER-диаграмме ролевая связь изображается стрелками от
сущности, порождающей роли (ПРЕПОДАВАТЕЛЬ), к ролевым
сущностям (ЗАВ_КАФЕДРОЙ и ОБЫЧН_ПРЕПОД). Ключи всех
этих сущностей принадлежат одному домену.
Кроме того, множество значений ключа каждого из ролевых
элементов является подмножеством значений ключа сущности, порождающей роли.
На рис.16 приведен общий случай ER-диаграммы для ролевой
связи.
Преподаватель
Таб_ номер...
1
М
Зав_Кафедрой
Руководит
Таб_ номер 1...
Преподаватель
Таб_ номер 2...
Рис. 15. Пример ER-диаграммы для ролевой связи
Сущность,
порождающая роли
Ключ
Ролевой
элемент 1
Ролевой
элемент 2
Ролевой
элемент 3
Ключ_ 1
Ключ_ 2
Ключ_ 3
...
Ролевой
элемент К
Ключ_ К
Рис. 16. Общий вид ER-диаграммы ролевой связи
92
Правило 8. [5] Исходная сущность, порождающая роли, является источником одного предварительного отношения, причем ключ
этой сущности служит ключом отношения. Ролевые элементы порождают еще по одному отношению с теми же ключами, что и исходная сущность. Связи, соединяющие ролевые отношения, генерируют столько отношений, сколько требуется для данного вида
связи по соответствующим правилам.
Таким образом, согласно правилу 8 для ER-диаграммы, изображенной на рис. 16, необходимо иметь следующий набор предварительных отношений:
R (Ключ,...) – соответствует сущности, порождающей роли;
R1 (Ключ_1,...) – соответствует сущности для первого ролевого
элемента;
R2 (Ключ_2,...) – соответствует сущности для второго ролевого
элемента, и так далее;
R_К (Ключ_К,...) – соответствует сущности для К-го ролевого
элемента.
Применяя правило 8 для ER–диаграммы (см. рис. 15), получим
следующий набор предварительных отношений:
R1 (Таб_номер,...) – соответствует сущности ПРЕПОДАВАТЕЛЬ, порождающей роли;
R2 (Таб_номер1,...) – соответствует ролевому элементу ЗАВ_
КАФЕДРОЙ;
R3 (Таб_номер2, Таб_номер1,...) – соответствует ролевому элементу ОБЫЧН_ПРЕПОД.
Отношение R3 содержит в качестве простого атрибута первичный ключ ролевого элемента ЗАВ_КАФЕДРОЙ (по правилу 4).
При наличии ролевых связей метод синтеза может дать меньшее
количество таблиц. Покажем это на том же примере.
Итак, пусть имеем исходный набор атрибутов U = ABCDE, где:
A – Таб_номер_преподавателя;
B – Номер_кафедры, на которой работает преподаватель;
C – ФИО преподавателя;
D – Номер_трудовой_книжки преподавателя;
E – Номер заведующего кафедрой (совпадает с номерами Таб_
номер преподавателя для заведующих кафедрами).
На множестве атрибутов U можно определить функциональные
зависимости: F = {A  BCD, B  E}.
Условно неизбыточное покрытие ℱ0 расширенного множества
зависимостей будет таким: ℱ0 = {A  BCDE, B  E}.
93
A → BCDE
B→E
Рис. 17- Результирующая диаграмма
зависимостей
Поскольку в полученном множестве имеется зависимость с полным набором атрибутов (подчеркнута), тривиальную зависимость
U   добавлять не надо.
На рис. 17 приведена ранжированная диаграмма, на которой
проведена операция транзитивной редукции зависимостей.
Из диаграммы получим результирующую декомпозицию
R1 = ABCD и R2 = BE или в терминах реальных данных:
R1 (Таб_номер, Кафедра, ФИО, Номер_труд_книжки) – таблица Преподаватели;
R2 (Кафедра, Таб_номер) – таблица Заведующие.
Тогда получить сведения о преподавателе, являющемся заведующим заданной кафедры, можно, например, с помощью запроса с
параметром вида (в стандарте JET-SQL):
SELECT Преподаватели.*
FROM Заведующие INNER JOIN Преподаватели ON
Заведующие.каф. = Преподаватели.каф.
WHERE ((Заведующие.каф.) = [кафедра?]) AND (Преподаватели.таб_номер)
In (select Таб_номер From Заведующие);
В этом случае метод синтеза дает меньше таблиц.
2.4. Сравнение методов синтеза и ER-диаграмм
Оба метода основаны на доскональном знании особенностей
предметной области, семантики данных, а также связей между
сущностями.
Достоинства метода синтеза:
– метод синтеза – формализованный метод проектирования, который выполняется по алгоритму, легко поддающемуся автоматизации;
– метод всегда гарантирует выполнимость свойства сохранения
функциональных зависимостей атрибутов для результирующей
94
декомпозиции и почти всегда – свойства соединения без потерь информации. Существует несколько особых случаев, когда требуется
дополнительное исследование результирующей декомпозиции на
выполнимость свойства соединения без потерь информации. Такие
случаи редки и исследование их выполняется достаточно просто
(см. примеры 37 и 38);
– результирующая декомпозиция содержит минимум декомпозиционных подсхем, а, следовательно, база данных содержит минимум таблиц, что может привести к повышению производительности;
– метод прост даже для достаточно большого количества атрибутов из выбранной предметной области;
– метод обеспечивает «сильные» нормальные формы для подсхем результирующей декомпозиции.
Недостатки метода синтеза:
– для выполнения синтеза требуются знания основ теории реляционных структур данных;
– метод требует достаточно трудоемкого этапа построения множества функциональных зависимостей, который можно упростить, используя комбинированный метод проектирования (синтез
+ метод ER-диаграмм), который будет изложен в разделе 2.5.
Достоинства метода ER-диаграмм:
– метод выполняется на основе здравого смысла и не требует
знаний основ теории реляционных структур данных;
– метод основан на применении небольшого количества правил,
которые позволяют сконструировать результирующие отношения
(таблицы базы данных);
– простота алгоритма позволяет использовать метод в программных средствах автоматизации проектирования, например таких,
как ERwin, Rational Rose и других.
Недостатки метода ER-диаграмм:
– метод часто дает больше подсхем в результирующей декомпозиции, чем метод синтеза, хотя, используя процедуру, которая будет описана в разделе 2.6, можно уменьшить количество таблиц в
результирующей декомпозиции;
– метод требует проведения анализа результирующего набора
отношений на предмет «сильных» нормальных форм, а это требует
построения множества функциональных зависимостей, правда не
полного, а только для атрибутов отдельных отношений. Конечно,
такая задача решается значительно легче, чем задача построения
полного множества зависимостей;
95
– метод не гарантирует выполнимость свойства соединения без
потерь информации для результирующего набора декомпозиционных подсхем, поэтому всегда требуется проверка выполнимости этого свойства, что вынуждает разработчика все равно строить
полное множество функциональных зависимостей. А, имея полное
множество зависимостей, проще воспользоваться методом синтеза;
– реализация правил в средствах автоматизированного проектирования баз данных выполняется не совсем «по правилам», поэтому требуется доработка результирующих моделей вручную, как
показано в работе [7].
Конечно, было бы хорошо, если бы разработчик базы данных владел всеми методами проектирования (декомпозиция, синтез, ERдиаграммы) и использовал их комбинацию при разработке конкретной базы данных. Тогда результат проектирования может быть вполне
удовлетворительным, и в процессе эксплуатации такой базы данных
можно гарантировать релевантность ответов на все запросы к данным.
Процедура поиска множества функциональных зависимостей F,
справедливых на заданном множестве атрибутов, может оказаться
довольно сложной. В ряде случаев может помочь комбинированный метод проектирования базы данных.
2.5. Комбинированный метод проектирования
Функциональные зависимости атрибутов от первичного ключа
сущности находятся легко, а именно, первичный ключ сущности
функционально определяет все ее атрибуты. Комбинированный
метод может помочь в отыскании так называемых «перекрестных»
зависимостей между сущностями. Рассмотрим примеры.
Пример 43. Спроектируем комбинированным методом базу данных для предметной области МАГАЗИНЫ (табл. 5).
На заданном множестве атрибутов U = ABCDESKLMN для каждой сущности будут справедливы зависимости F = {A  B, C D,
E  S, K  L, M  N,...}. Многоточия должны быть заменены «перекрестными» зависимостями между сущностями. Найдем их из
описания ER-диаграммы, причем для поиска «перекрестных» зависимостей класс принадлежности сущности не имеет значения:
1. ПОСТАВЩИКИ (М) поставляют (М) ТОВАРЫ;
2. ТОВАРЫ (М) продаются_в (М) МАГАЗИНАХ;
3. МАГАЗИНЫ (1) содержат (М) ОТДЕЛЫ;
4. ТОВАРЫ (М) поступают_в (1) ОТДЕЛЫ;
5. ТОВАРЫ (М) имеют (1) ТИПЫ.
96
Таблица 5
Сущности и их атрибуты предметной области МАГАЗИНЫ
Сущности
ПОСТАВЩИКИ
Атрибуты сущностей
Директор
НомерТовара
да
Фио
Адрес
Телефон
ТОВАРЫ

НомерМагазина
да
Адрес

КодОтдела
да
НазваниеМагазина
ОТДЕЛЫ
Заведующий

КодТипа
да
НазваниеОтдела
ТИПЫ_ТОВАРОВ
НазваниеТипа
Обозначение
А
да
Цена
НаименованиеТовара
МАГАЗИНЫ
Первичный ключ

НомерПоставщика
B
С
D
E
S
K
L
M
N
По определению функциональных зависимостей, данному в разделе 1.3.1, каждому значению набора атрибутов в левой части зависимости в каждый момент времени соответствует точно одно значение атрибута в правой части зависимости. Отсюда следует, что
только выделенные связи могут быть использованы для получения
«перекрестных» зависимостей. Связь 3 даст зависимость ОТДЕЛЫ 
МАГАЗИНЫ или, используя первичные ключи, K  E. Аналогично связь 4 даст зависимость ТОВАРЫ  ОТДЕЛЫ или C  K,
связь 5 – зависимость ТОВАРЫ  ТИПЫ или C  M.
Заменяем многоточия этими зависимостями. В результате получаем
F = {A  B, C D, E  S, K  L, M  N, K  E, C  K, C  M}
или, используя правило объединения зависимостей по правым частям (см. раздел 1.3.2):
F = {A  B, C DKM, E  S, K  LE, M  N}.
97
Таким образом, имеем исходные данные для проектирования базы
данных методом синтеза: множество атрибутов U = ABCDESKLMN
и множество функциональных зависимостей F, справедливое на
множестве U. Выполним ускоренный синтез.
Строим расширенное множество зависимостей:
ℱ = {A  B, C DKMLESN, E  S, K  LES, M  N}.
Условно неизбыточное покрытие ℱ0 = ℱ.
Добавляем тривиальную зависимость U   и строим диаграмму зависимостей, на которой выполняем операцию транзитивной
редукции зависимостей. Результат показан на рис. 18.
Получаем результирующую декомпозицию отношений:
R1 = AC;
R2 = C DKM;
R3 = AB;
R4 = KLE;
R5 = M N;
R6 = ES;
или для реальных данных:
R1: Поставщики_Товары или Поставки (НомерПоставщика, НомерТовара);
R2: Товары (НомерТовара, НаименованиеТовара, Цена, КодОтдела, КодТипа);
R3: Поставщики (НомерПоставщика, ФИО, Адрес, Телефон, Директор);
R4: Отделы (КодОтдела, НазваниеОтдела, Заведующий, НомерМагазина);
R5: Типы_Товаров (КодТипа, НазваниеТипа);
R6: Магазины (НомерМагазина, НазваниеМагазина, Адрес).
Набор атрибутов AC является минимальным суперключом, так как
AC+ = U, но A+  U и C+  U.
1 ABC DESKLMN ĺ ∅
2
4
6
C → DKM LESN
K → LES
5
3
A→ B
M→N
E→S
Рис. 18. Диаграмма зависимостей для предметной области
МАГАЗИНЫ
98
Пример 44. Для предметной области АВТОВОКЗАЛ в табл. 6
перечислены сущности и их атрибуты.
Поскольку первичные ключи функционально определяют все
атрибуты сущностей, включим эти зависимости в множество F:
F = {A  B, C  D, E  K, P  L,...}
Здесь многоточия должны быть заменены «перекрестными» зависимостями между сущностями, которые можно найти из описания ER-диаграммы:
1. ВОДИТЕЛИ (М) ведут (1) АВТОБУСЫ;
2. АВТОБУСЫ (М) отправляются_в (М) РЕЙСЫ;
3. ВОДИТЕЛИ (М) назначаются_на (М) РЕЙСЫ;
4. ПАССАЖИРЫ (М) отправились_в (1) РЕЙСЫ.
По определению функциональных зависимостей, данному в подразделе 1.3.1, каждому значению набора атрибутов в левой части
зависимости в каждый момент времени соответствует точно одно
значение атрибута в правой части зависимости. Отсюда следует,
что только выделенные связи используются для получения «перекрестных» зависимостей. Связь 1 даст зависимость ВОДИТЕЛИ 
 АВТОБУСЫ или, используя первичные ключи, A  C. АналоТаблица 6
Сущности и их атрибуты для предметной области АВТОВОКЗАЛ
Сущности
ВОДИТЕЛИ
АВТОБУСЫ
РЕЙСЫ
ПАССАЖИРЫ
Атрибуты
IDВодителя
ФиоВодителя
Адрес
Телефон
Возраст
ГосНомер
Тип
Модель
IDРейса
НомерРейса
Куда
ДатаВремяОтправ
IDПассажира
ФиоПас
АдресЭлПочты
Первичный ключ

B
С
да

D
E
да

K
Р
да

Обозначение
А
да
L
99
гично связь 4 даст зависимость P  E. Заменяя многоточия этими
зависимостями, получим
F = {A  B, C  D, E  K, P  L, A  C, P  E}
или, используя правило объединения зависимостей по правым частям (см. раздел 1.3.2):
F = {A  BC, C  D, E  K, P  LE}.
Таким образом, имеем исходные данные для проектирования
базы данных методом синтеза: множество атрибутов U = ABCDEKPL
и множество функциональных зависимостей F, определенное на U.
Выполним ускоренный синтез.
Строим расширенное множество зависимостей:
ℱ = {A  BCD, C  D, E  K, P  LEK}.
Условно неизбыточное покрытие ℱ0 = ℱ.
Добавляем тривиальную зависимость ABCDEKPL   и строим
диаграмму зависимостей, изображенную на рис. 19, на которой выполняем операцию транзитивной редукции зависимостей.
Результирующая декомпозиция будет такой (первичные ключи
выделены):
R1 = AP;
R2 = PLE;
R3 = ABC;
R4 = EK;
R5 = C D
или для реальных данных:
R1: Водители_Пассажиры (IDВодителя, IDПассажира);
R2: Пассажиры (IDПассажира, ФиоПас, АдресЭлПочты, IDРейса);
R3: Водители (IDВодителя, ФиоВодителя, Адрес, Телефон, ГосНомер);
R4: Рейсы (IDРейса, НомерРейса, Куда, ДатаВремяОтправ);
R5: Автобусы (ГосНомер, Тип, Модель).
1
4
ABCDEK PL → ∅
P → LE K
3
A → BCD
E→K
5
C→ D
Рис. 19. Диаграмма зависимостей для предметной области
АВТОВОКЗАЛ
100
Заметим, что набор атрибутов AP является минимальным суперключом, так как
AP+ = APBCDEKL = U и A+ = ABCD  U; P+ = PLEK U.
Если для какой-либо сущности существует возможный первичный ключ, то его нужно отделить от остальных атрибутов сущности, как это сделано в примере 45.
Пример 45. Предметная область выбрана такая же, как в примере 44, где добавлена еще одна сущность БИЛЕТЫ, а для сущности
ПАССАЖИРЫ определен возможный первичный ключ НомерПаспорта, который выделен из набора неключевых атрибутов L отдельным обозначением S (табл. 7).
Следует отметить, что отдельные обозначения целесообразно назначать не только для возможных первичных ключей, но и для зависимых атрибутов, не являющихся первичными или возможными
первичными ключами. Например, если мы хотим связать функциональной зависимостью атрибуты «Цена» и «МестоВАвтобусе»
Таблица 7
Сущности и их атрибуты для предметной области АВТОВОКЗАЛ
Сущности
Атрибуты
ID_водителя
ФиоВодителя
Адрес
Телефон
Возраст
ГосНомер
АВТОБУСЫ
Тип
Модель
IDРейса
РЕЙСЫ
НомерРейса
Куда
ДатаВремяОтправ
ПАССАЖИРЫ ID_пассажира
ФиоПас
АдресЭлПочты
ВОДИТЕЛИ
НомерПаспорта
БИЛЕТЫ
НомерБилета
Цена
МестоВАвтобусе
Первичный ключ

B
С
да

D
E
да

K
P
да

Обозначение
А
да
L
Возможный перS
вичный ключ
O
да
X
Y
101
(«Цена» зависит от атрибута «МестоВАвтобусе»), как показано в
табл. 6, то этим атрибутам также нужно дать отдельные обозначения X и Y соответственно. Поскольку первичный и возможный первичный ключи определяют все атрибуты сущности, можно написать
часть функциональных зависимостей, входящих в множество F:
F = {A  B, C D, E  K, P  L, P  S, S  P, S  L, O  X,
O  Y, Y  X,... }
В это множество нужно добавить «перекрестные» зависимости,
которые легко определяются из соответствующего описания ERдиаграммы:
1. АВТОБУСЫ (М) отправляются в (М) РЕЙСЫ;
2. ВОДИТЕЛИ (М) ведут (1) АВТОБУСЫ;
3. ПАССАЖИРЫ (1) купили (1) БИЛЕТЫ;
4. ПАССАЖИРЫ (М) отправились в (1) РЕЙСЫ;
5. БИЛЕТЫ (М) куплены на (1) РЕЙСЫ;
6. ВОДИТЕЛИ (М) назначены на (М) РЕЙСЫ.
По определению функциональной зависимости атрибутов для
поиска «перекрестных» зависимостей связи М:М из рассмотрения
исключаются. Связи, в которых проявляются функциональные зависимости, выделены жирным шрифтом.
Связь 2 даст зависимость ВОДИТЕЛИ  АВТОБУСЫ или A  C,
связь 3 –зависимость ПАССАЖИРЫ  БИЛЕТЫ и БИЛЕТЫ 
 ПАССАЖИРЫ или P  O и O  P, связь 4 – зависимость ПАССАЖИРЫ  РЕЙСЫ или P  Е, связь 5 – зависимость БИЛЕТЫ 
 РЕЙСЫ или О  Е.
Добавляя указанные здесь зависимости в множество F, получаем
F = {A  B, C D, E  K, P  L, P  S, S  P, S  L, O  X,
O  Y, Y  X, A  C, P  O, O  P, P  Е, О  Е}
или, воспользовавшись правилом объединения правых частей
функциональных зависимостей (см. раздел 1.3.2), множество F
можно привести к виду:
F = {A  BC, C D, E  K, P  LSOE, S  PL, O  XYPE, Y  X}.
Далее продолжаем синтез. Строим расширенное множество зависимостей:
ℱ = {A  BCD, C D, E  K, P  LSOEXYK, S  PLOEKXY,
O XYPELSK, Y  X}
и условно неизбыточное покрытие ℱ0 = ℱ.
102
1 ABCDEKPLSOXY → ∅
2
4
E→K
P → LSOEXYK
5
Y→ X
3
A → BCD
6
C→D
Рис. 20. Диаграмма зависимостей для предметной области
АВТОВОКЗАЛ с сущностью БИЛЕТЫ и с альтернативным
первичным ключом для одной из сущностей
Выделенные жирным шрифтом зависимости эквивалентны.
Оставляем одного представителя, например, первую из эквивалентных зависимостей.
Добавляя тривиальную зависимость U  , строим диаграмму
зависимостей, на которой выполняем операцию транзитивной редукции зависимостей (рис. 20).
Получаем результирующую декомпозицию отношений:
R1 = AP;
R2 = PLSOEY;
R3 = ABС;
R4 = EK;
R5 = YX;
R6 = C D;
или для реальных данных:
R1: Водители_Пассажиры (ID_водителя, ID_пассажира);
R2: Пассажиры (ID_пассажира, ФиоПас, АдресЭлПочты, НомерПаспорта, НомерБилета, IDРейса, МестоВАвтобусе);
R3: Водители (ID_водителя, ФиоВодителя, Адрес, Телефон,
Возраст, ГосНомер);
R4: Рейсы (IDРейса, НомерРейса, Куда, ДатаВремяОтправ);
R5: Место_Цена (МестоВАвтобусе, Цена);
R6: Автобусы (ГосНомер, Тип, Модель).
Как и в примере 44, набор атрибутов AP является минимальным
суперключом.
2.6. Процедура уменьшения количества таблиц
в результирующей декомпозиции,
полученной по методу ER-диаграмм
Как было отмечено в разделе 2.4, метод ER-диаграмм, широко используемый при проектирования реляционных баз данных,
часто дает больше подсхем (таблиц) в результирующей декомпозиции, чем метод синтеза, что приводит к потере производитель103
ности при выполнении многотабличных запросов. Кроме того, он
не гарантирует выполнимости свойства соединения без потерь для
результирующей декомпозиции. Для выполнимости этого свойства
можно попытаться добавить в результирующую декомпозицию таблицу, содержащую суперключ, что обычно приводит к желаемому
результату.
Для уменьшения же количества результирующих таблиц можно предложить для М-связных сущностей простую процедуру, которая будет рассмотрена в данном разделе.
При этом рассмотрим следующие случаи.
Случай 1. Отсутствие или наличие только одной М-связи между
сущностями. В этом случае результаты проектирования по методам
синтеза и ER-диаграмм могут сразу полностью совпасть (пример
46), или не совпасть (пример 47), или могут полностью совпасть после обеспечения выполнимости свойства соединения без потерь информации в методе ER-диаграмм (пример 48).
Пример 46. Рассмотрим предметную область АПТЕКА (табл. 8).
Поскольку первичные ключи функционально определяют все
атрибуты сущностей, включим эти зависимости в множество F:
F = {A  B, C  D, E  K, L  M,...}
Таблица 8
Сущности и их атрибуты для предметной области АПТЕКА
Сущности
Атрибуты
IDПрепарата
Название
Категория
Цена
Противопоказания
ПОСТАВЩИКИ IDПоставщика
Адрес
Телефон
IDНазначения
НАЗНАЧЕНИЯ Тип
Характеристика
СОТРУДНИКИ IDСотрудника
Фио
АдресЭлПочты
Телефон
ПРЕПАРАТЫ
104
Первичный ключ

B
С
да

D
E
да

K
L
да

Обозначение
А
да
M
Здесь многоточия, как и в предыдущих примерах, должны быть
заменены «перекрестными» зависимостями между сущностями,
которые можно найти из описания ER-диаграммы:
1. ПРЕПАРАТЫ (М, О) поставляют (1,О) ПОСТАВЩИКИ
(правило 4).
2. ПРЕПАРАТЫ (М, О) имеют (1, О) НАЗНАЧЕНИЯ (правило 4).
3. СОТРУДНИКИ (М, Н) заказывают (М, О) ПРЕПАРАТЫ
(правило 6).
Из выделенных связей будут справедливыми следующие «перекрестные» зависимости:
ПРЕПАРАТЫ  ПОСТАВЩИКИ или A  C;
ПРЕПАРАТЫ  НАЗНАЧЕНИЯ или A  E,
Добавляя «перекрестные» зависимости, получим F = {A  BCE,
C  D, E  K, L  M}. Выполняем ускоренный синтез. Расширенное
множество зависимостей: ℱ = {A  BCEDK, C  D, E  K, L  M}.
Поскольку расширенное множество не содержит «лишних» зависимостей с одинаковой левой частью, то условно неизбыточное
покрытие ℱ0 совпадает с ℱ.
Добавляя тривиальную зависимость U  , строим диаграмму
зависимостей, на которой выполняем операцию транзитивной редукции зависимостей (рис. 21):
Получаем результирующую декомпозицию отношений.
R1 = AL; R2 = ABCE; R3 = LM; R4 = CD; R5 = EK или для реальных данных:
R1: Препараты_Сотрудники или Заказы (IDПрепарата,
IDСотрудника);
R2: Препараты (IDПрепарата, Название, Категория, Цена, Противопоказания, IDПоставщика, IDНазначения);
R3: Сотрудники (IDСотрудника, Фио, АдресЭлПочты, Телефон);
R4: Поставщики (IDПоставщика, Адрес, Телефон);
ABCDEKLM → ∅
1
2
4
C→D
A → BCE DK
5
3
L→M
E→K
Рис. 21. Диаграмма зависимостей
для предметной области АПТЕКА
105
R5: Назначения (IDНазначения, Тип, Характеристика).
Видно, что набор атрибутов AL является минимальным суперключом, так как AL+ = U, а A+  U и L+  U.
Результирующая декомпозиция, полученная по методу ERдиаграмм, будет такой:
R1: Препараты (IDПрепарата, Название, Категория, Цена, ПроIDПоставщика, IDНазначения);
добавлены по правилу 4;
тивопоказания,
R2: Поставщики (IDПоставщика, Адрес, Телефон);
R3: Назначения (IDНазначения, Тип, Характеристика);
R4: Сотрудники (IDСотрудника, Фио, АдресЭлПочты, Телефон).
R5: Препараты_Сотрудники или Заказы (IDПрепарата,
IDСотрудника).
Следовательно, результаты проектирования по методам синтеза
и ER-диаграмм полностью совпадают.
Пример 47. Рассмотрим предметную область КУРСЫ ИНОСТРАННЫХ ЯЗЫКОВ (табл. 9).
Поскольку первичные ключи функционально определяют все
атрибуты сущностей, включим эти зависимости в множество F:
F = {A  B, C  D, E  K, L  M, N  S,...}.
Таблица 9
Сущности и их атрибуты
Сущности
СЛУШАТЕЛИ
Атрибуты
IDСлушателя
Фио
Адрес
Телефон
АдресЭлПочты
ПРЕПОДАВАТЕЛИ IDПреподавателя
Адрес
Телефон
IDФилиала
ФИЛИАЛЫ
Адрес
Телефон
ГРУППЫ
IDГруппы
Язык
Начало занятий
Количество слушателей
КУРСЫ
IDКурса
Характеристика
106
Первичный ключ Обозначение

А
да
B
С
да


D
E
да
K
L
да

M
N
да
S
Здесь многоточия, как и в предыдущих примерах, должны быть
заменены «перекрестными» зависимостями между сущностями,
которые можно найти из описания ER-диаграммы:
1. ПРЕПОДАВАТЕЛИ (1, О) работают_с (М,О) ГРУППАМИ
(правило 4).
2. СЛУШАТЕЛИ (М, О) обучаются_в (1, О) ГРУППАХ (правило 4).
3. ФИЛИАЛЫ (1, О) набирают (М, О) ГРУППЫ (правило 4).
4. КУРСЫ (М, О) имеют (М, О) ФИЛИАЛЫ (правило 6).
Из выделенных связей будут справедливыми следующие «перекрестные» зависимости:
ГРУППЫ  ПРЕПОДАВАТЕЛИ или L  C,
СЛУШАТЕЛИ  ГРУППЫ или A  L,
ГРУППЫ  ФИЛИАЛЫ или L  E.
Добавляя «перекрестные» зависимости, получим F = {A  BL,
C  D, E  K, L  MEC, N  S}. Выполняем ускоренный синтез. Расширенное множество зависимостей: ℱ = {A  BLMCEDK,
C  D, E  K, L  MCEDK, N  S}.
Поскольку расширенное множество не содержит «лишних» зависимостей с одинаковой левой частью, то условно неизбыточное
покрытие ℱ0 совпадает с ℱ.
Добавляя тривиальную зависимость U  , строим диаграмму
зависимостей, на которой выполняем операцию транзитивной редукции зависимостей (рис. 22):
Получаем результирующую декомпозицию отношений:
R1 = AN;
R2 = ABL;
R3 = NS;
R4 = LMCE;
R5 = C D;
R6 = EK
или для реальных данных:
ABCDEKLMNS → ∅
1
2
4
5
A → BLMCEDK
3
N→ S
L → MCEDK
C→D
6
E →K
Рис. 22. Диаграмма зависимостей
107
R1: Слушатели_Курсы (IDСлушателя, IDКурса);
R2: Слушатели (IDСлушателя, Фио, Адрес, Телефон, АдресЭлПочты, IDГруппы);
R3: Курсы (IDКурса, Характеристика);
R4: Группы (IDГруппы, Язык, Начало занятий, Количество слушателей, IDПреподавателя, IDФилиала);
R5: Преподаватели (IDПреподавателя, Адрес, Телефон);
R6: Филиалы (IDФилиала, Адрес, Телефон);
Видно, что набор атрибутов AN является минимальным суперключом, так как AN+ = U, а A+  U и N+  U.
Спроектированная по методу синтеза база данных состоит из
шести таблиц.
Результирующая декомпозиция, полученная по методу ERдиаграмм, будет такой:
R1: Преподаватели (IDПреподавателя, Адрес, Телефон);
R2: Группы (IDГруппы, Язык, Начало занятий, Количество слуIDПреподавателя, IDФилиала);
шателей, добавлены по правилу 4
R3: Слушатели (IDСлушателя, Фио, Адрес, Телефон, АдресЭлПочты, IDГруппы добавлен по правилу 4);
R4: Филиалы (IDФилиала, Адрес, Телефон);
R5: Курсы (IDКурса, Характеристика);
R6: Курсы_Филиалы (IDКурса, IDФилиала); или в обозначениях табл. 9:
R1 = CD; R2 = LMCE; R3 = ALB; R4 = EK;
R5 = NS;
R6 = EN.
Спроектированная по методу ER-диаграмм база данных состоит
из шести таблиц, которые не совпадают с таблицами, полученными
по методу синтеза.
Кроме того, проверка показала, что декомпозиция из шести таблиц не обладает свойством соединения без потерь информации.
Чтобы это свойство выполнялось, добавим седьмую таблицу с суперключом AN или для реальных данных:
R7: Слушатели_Курсы (IDСлушателя, IDКурса);
В рассматриваемом примере результаты проектирования по методам синтеза и ER-диаграмм не совпадают.
Совпадение результатов проектирования может быть полным
после добавления суперключа в результирующую декомпозицию,
полученную по методу ER-диаграмм, что подтверждается примером 48.
108
Пример 48. Рассмотрим предметную область ЗАКАЗЫ КОМПЛЕКТУЮЩИХ ДЛЯ КОМПЬЮТЕРОВ (табл. 10).
Спроектируем базу данных комбинированным методом. Множество функциональных зависимостей: F = {A  B, C  D, E  K,
L  M, N  S,...}.
Здесь многоточия, как и в предыдущих примерах, должны быть
заменены «перекрестными» зависимостями между сущностями,
которые можно найти из описания ER-диаграммы:
1. ПОСТАВЩИКИ (1, О) поставляют (М,О) КОМПЛЕКТУЮЩИЕ (правило 4).
2. КЛИЕНТЫ (1, О) делают (М, О) ЗАКАЗЫ (правило 4).
3. СОТРУДНИКИ (1, О) выполняют (М, О) ЗАКАЗЫ (правило 4).
Из выделенных связей будут справедливыми следующие «перекрестные» зависимости:
КОМПЛЕКТУЮЩИЕ  ПОСТАВЩИКИ или E  C;
ЗАКАЗЫ  КЛИЕНТЫ или N  A;
ЗАКАЗЫ  СОТРУДНИКИ или N  L.
Таблица 10
Сущности и их атрибуты
Сущности
Атрибуты
IDКлиента
Фио
Адрес
Телефон
АдресЭлПочты
IDПоставщика
ПОСТАВЩИКИ
Адрес
Телефон
IDКомплектующего
КОМПЛЕКТУЮЩИЕ Название
Параметры
IDСотрудника
СОТРУДНИКИ
Фио
Адрес
Телефон
IDЗаказа
ЗАКАЗЫ
ДатаЗаказа
Стоимость
КЛИЕНТЫ
Первичный ключ Обозначение
А
да

B
С
да

D
E
да

K
L
да

M
N
да

S
109
Добавляя «перекрестные» зависимости, получим F = {A  B,
C  D, E  KC, L  M, N  SAL}. Выполняем ускоренный синтез. Расширенное множество зависимостей: ℱ = {A  B, C  D,
E  KCD, L  M, N  SALBM}.
Поскольку расширенное множество не содержит «лишних» зависимостей с одинаковой левой частью, то условно неизбыточное
покрытие ℱ0 совпадает с ℱ.
Добавляя тривиальную зависимость U  , строим диаграмму
зависимостей, на которой выполняем операцию транзитивной редукции зависимостей (рис. 23):
Получаем результирующую декомпозицию отношений:
R1 = EN; R2 = NSAL; R3 = EKC; R4 = LM; R5 = AB; R6 = CD; или
для реальных данных:
R1: Комплектующие_Заказы (IDКомплектующего, IDЗаказа);
R2: Заказы (IDЗаказа, ДатаЗаказа, Стоимость, IDКлиента,
IDСотрудника);
R3: Комплектующие (IDКомплектующего, Название, Параметры, IDПоставщика);
R4: Сотрудники (IDСотрудника, Фио, Адрес, Телефон);
R5: Клиенты (IDКлиента, Фио, Адрес, Телефон, АдресЭлПочты);
R6: Постащики (IDПоставщика, Адрес, Телефон).
Видно, что набор атрибутов EN является минимальным суперключом, так как EN+ = U, а E+  U и N+  U.
Спроектированная по методу синтеза база данных состоит из
шести таблиц. Результирующая декомпозиция, полученная по методу ER-диаграмм, будет такой:
R1: Поставщики (IDПоставщика, Адрес, Телефон);
R2: Заказы (IDЗаказа, ДатаЗаказа, Стоимость, IDКлиента,
IDСотрудника); TDКлиента и IDСотрудника добавлены по правилу 4;
ABCDE KLMNS → ∅
1
2
4
N → SALBM
L→M
5
3
A→ B
E → KCD
6
C→D
Рис. 23. Диаграмма зависимостей
110
R3: Комплектующие (IDКомплектующего, Название, Параметры, IDПоставщика); IDПоставщика добавлены по правилу 4;
R4: Клиенты (IDКлиента, Фио, Адрес, Телефон, АдресЭлПочты);
R5: Сотрудники (IDСотрудника, Фио, Адрес, Телефон).
Спроектированная по методу ER-диаграмм база данных состоит из пяти таблиц, которые совпадают с таблицами, полученными
по методу синтеза, но результирующая декомпозиция не обладает
свойством соединения без потерь информации.
Чтобы это свойство выполнялось, добавим шестую таблицу с суперключом EN или для реальных данных:
R6: Комплектующие_Заказы (IDКомплектующего, IDЗаказа)
или в обозначениях табл. 10:
R1 = CD; R2 =NSAL; R3 = EKC; R4 = AB; R5 =LM; R6 =EN.
Теперь результаты проектирования по обоим методам полностью совпадают.
Случай 2. Больше двух М-связных сущностей образуют кольцо
или цепочку сущностей без ответвлений. В этом случае после использования простой процедуры уменьшения количества таблиц,
полученных по методу ER-диаграмм, можно получить полное совпадение с результатами проектирования по методу синтеза. Кольцо М-сущностей без ответвлений для триплета было рассмотрено
в примере 41.
Рассмотрим пример, в котором М-связные сущности образуют
цепочку сущностей без ответвлений.
Пример 49. Спроектируем базу данных для предметной области
ПРОДАЖА МЕБЕЛИ (табл. 11).
Спроектируем базу данных комбинированным методом. Множество функциональных зависимостей будет таким: F = {A  B,
C  D, L  S, M  N,...}.
Здесь многоточия, как и в предыдущих примерах, должны быть
заменены «перекрестными» зависимостями между сущностями,
которые можно найти из описания ER-диаграммы:
1. МАГАЗИНЫ (М, О) заказывают (М,О) МЕБЕЛЬ (правило 6).
2. СОТРУДНИКИ (М, О) работают_в (1, О) МАГАЗИНАХ (правило 4).
3. СКЛАДЫ (1, О) содержат (М, О) МЕБЕЛЬ (правило 4).
4. СОТРУДНИКИ (М, О) продают (М, О) МЕБЕЛЬ (правило 6).
5. МАГАЗИНЫ (М, Н) связаны_со (М, О) СКЛАДАМИ (правило 6).
111
Таблица 11
Сущности и их атрибуты
Сущности
Атрибуты сущностей
IDМагазина
Название
Адрес
Телефон
АдресЭлПочты
IDМебели
МЕБЕЛЬ
Наименование
Цена
СОТРУДНИКИ IDСотрудника
Фио
Адрес
IDСклада
СКЛАДЫ
Адрес
МАГАЗИНЫ
Первичный ключ

B
С
да

D
L
да

Обозначение
А
да
S
M
да
N
Из выделенных связей будут справедливыми следующие «перекрестные» зависимости:
СОТРУДНИКИ  МАГАЗИНЫ или L  A,
МЕБЕЛЬ  СКЛАДЫ или C  M,
Добавляя «перекрестные» зависимости, получим F = {A  B,
C  D, L  S, M  N, L  A, C  M} или F = {A  B, C  DM,
L  SA, M  N}. Выполняем ускоренный синтез для U = ABCDLSMN.
Расширенное множество зависимостей: ℱ = {A  B, C  DMN,
L  SAB, M  N}.
Поскольку расширенное множество не содержит «лишних» зависимостей с одинаковой левой частью, то условно неизбыточное
покрытие ℱ0 совпадает с ℱ.
Добавляя тривиальную зависимость U  , строим диаграмму
зависимостей, на которой выполняем операцию транзитивной редукции зависимостей (рис. 24):
Получаем результирующую декомпозицию отношений:
R1 = CL;
R2 = CDM;
R3 = LSA;
R4 = MN;
R5 = AB или для реальных данных:
R1: Мебель_Сотрудники (IDМебели, IDСотрудника);
R2: Мебель (IDМебели, Наименование, Цена, IDСклада);
R3: Сотрудники (IDСотрудника, Фио, Адрес, IDМагазина);
R4: Склады (IDСклада, Адрес);
112
1
ABCDLSMN → ∅
2
C → DMN
3
L → SAB
4
M→N
5
A→ B
Рис. 24. Диаграмма зависимостей
R5: Магазины (IDМагазина, Название, Адрес, Телефон, Адрес
ЭлПочты).
Видно, что набор атрибутов CL является минимальным суперключом, так как CL+ = U, а C+  U и L+  U.
Спроектированная по методу синтеза база данных состоит из
пяти таблиц.
Результирующая декомпозиция, полученная по методу ERдиаграмм, будет такой:
R1= AB; R2 = CDM; R3 = AC; R4 = LSA; R5 = MN; R6 = CL;
R7= AM или для реальных данных
R1: Магазины (IDМагазина, Название, Адрес, Телефон, Адрес
ЭлПочты);
R2: Мебель (IDМебели, Наименование, Цена, IDСклада);
IDСклада добавлен по правилу 4;
R3: Магазины_Мебель (IDМагазина, IDМебели);
R4: Сотрудники (IDСотрудника, Фио, Адрес, Телефон, АдресЭлПочты, IDМагазина) добавлен по правилу 4;
R5: Склады (IDСклада, Адрес);
R6: Мебель_Сотрудники (IDМебели, IDСотрудника);
R7: Магазины_Склады (IDМагазина, IDСклада).
Спроектированная база данных состоит из семи таблиц: R1 – R7.
Из рис. 25 видно, что М-связные сущности СКЛАДЫ, МАГАЗИНЫ, МЕБЕЛЬ и СОТРУДНИКИ образуют цепочку сущностей.
Если теперь удалить таблицы R7, R3 и R6 и вместо них добавить
таблицу R8: Склады_Магазины_Мебель_Сотрудники (IDСклада,
IDМагазина, IDМебели, IDСотрудника), как показано на рис. 25,
то удастся уменьшить количество таблиц в базе данных, спроектированной по методу ER-диаграмм. Теперь база данных состоит
из пяти таблиц: R1, R2, R4, R5, R8. Причем добавленная таблица содержит не минимальный суперключ (IDСклада, IDМагазина,
113
R7
M
Склады
M
R6
R3
M
M
M
Магазины
A
M
Мебель
C
M
M
Сотрудники
L
R8(MACL)
Рис. 25. Операция уменьшения количества таблиц в базе данных,
спроектированной по методу ER-диаграмм
IDМебели, IDСотрудника) или в принятых выше обозначениях
атрибутов – ACML. Выше было показано, что минимальным суперключом является набор атрибутов CL. Поэтому в таблице R8 в
качестве первичного ключа можно оставить набор атрибутов CL, а
атрибуты A и M сделать неключевыми [5]. Тогда таблица R8 будет
такой:
R8: Мебель_Сотрудники (IDМебели, IDСотрудника, IDСклада,
IDМагазина), и результирующая декомпозиция в обозначениях таблицы 11 будет такой:
R1= AB; R2 = CDM; R4 = LSA; R5 = MN; R8 = CLAM;
Теперь базы данных, спроектированные по методам синтеза и
ER-диаграмм, почти совпадают, за исключением таблиц R6 (синтез)
и R8 (ER-диаграммы с процедурой уменьшения количества таблиц).
Рассмотренные примеры позволяют сделать вывод о том, что,
если М-связные сущности образуют кольцо или цепочку без ответвлений, то метод ER-диаграмм с использованием простой процедуры уменьшения таблиц в результирующей декомпозиции столь же
эффективен, как и метод синтеза, и добавляемая таблица всегда содержит суперключ (возможно не минимальный). Поэтому в такой
базе данных всегда выполняется свойство соединения без потерь
информации.
Случай 3. Более двух М-связных сущностей образуют кольцо
или цепочку сущностей с ответвлениями. При этом после использования процедуры уменьшения количества таблиц, полученных
по методу ER-диаграмм, можно не получить (пример 50), а можно
получить (пример (51) суперключ в добавляемой таблице. Покажем это.
114
Пример 50. Вернемся к рассмотрению условий примера 44. Для
предметной области АВТОВОКЗАЛ была спроектирована комбинированным методом база данных, состоящая из пяти таблиц, которые в обозначениях табл. 6 имеют вид:
R1 = AP;
R2 = PLE;
R3 = ABC; R4 = EK; R5 = C D,
причем AP – минимальный суперключ.
Выполним проектирование базы данных методом ER-диаграмм,
а затем попытаемся уменьшить количество полученных таблиц с
помощью процедуры, описанной в предыдущих примерах. Напомним описание ER-диаграммы:
1. ВОДИТЕЛИ (М, Н) ведут (1,О) АВТОБУСЫ (правило 4).
2. АВТОБУСЫ (М, Н) отправляются_в (М, О) РЕЙСЫ (правило 6).
3. ВОДИТЕЛИ (М, Н) назначаются_на (М, О) РЕЙСЫ (правило 6).
4. ПАССАЖИРЫ (М, О) отправились_в (1, О) РЕЙСЫ (правило 4).
В результате проектирования получим следующие таблицы:
R1: Водители (IDВодителя, ФиоВодителя, Адрес, Телефон,
Возраст, ГосНомер).
ГосНомер добавлен по правилу 4;
R2: Автобусы (ГосНомер, Тип, Модель);
R3: Рейсы (IDРейса, НомерРейса, Куда, ДатаВремяОтправ);
R4: Автобусы_Рейсы (ГосНомер, IDРейса);
R5: Водители_Рейсы (IDВодителя, IDРейса);
R6: Пассажиры (IDПассажира, ФиоПас, АдресЭлПочты, IDРейса).
IDРейса добавлен по правилу 4
или в обозначениях табл. 6:
R1= ABC; R2 = CD; R3 = EK; R4 = CE ; R5 = AE; R6 = PLE.
Спроектированная база данных содержит 6 таблиц, ни одна из
которых не содержит супеключа, следовательно, свойство соединения без потерь информации не выполняется. Из рис. 26 видно, что
М-связные сущности АВТОБУСЫ, РЕЙСЫ и ВОДИТЕЛИ образуют
цепочку, причем сущность РЕЙСЫ имеет ответвление к сущности
ПАССАЖИРЫ типа 1:М.
Если теперь удалить таблицы R4, R5 и вместо них добавить таблицу
R7: Автомобили_Рейсы_Водители (IDАвтомобиля, IDРейса,
IDВодителя) или R7 = СЕА, как показано на рис. 26, то удастся
уменьшить количество таблиц в базе данных, спроектированной по
методу ER-диаграмм. Теперь база данных состоит из пяти таблиц:
115
Пассажиры
P
M
R5
R4
M
Автобусы
C
M
1
Рейсы
E
M
M
Водители
A
R7(CEA)
Рис. 26. Операция уменьшения количества таблиц в базе данных,
спроектированной по методу ER-диаграмм
R1, R2, R3, R6, R7. Однако добавленная таблица R7 не содержит
суперключа, который был определен в примере 44 как набор атрибутов AP. Чтобы результирующая декомпозиция R1, R2, R3, R6,
R7 обладала свойством соединения без потерь информации, можно
добавить в таблицу R7 атрибут P – первичный ключ ответвленной
сущности.
Тогда R7 = CEAP, AP объявить первичным ключом, а атрибуты CE тогда будут неключевыми, т. е. R7 = APCE или на реальных
данных
R7: Водители_Пассажиры (IDВодителя, IDПассажира, ГосНомер, IDРейса).
В этом случае результирующая декомпозиция будет обладать
свойством соединения без потерь информации, количество таблиц
совпадет с таковым, полученным методом синтеза.
Пример 51. Выполним проектирование базы данных для предметной области КОНЦЕРТЫ МУЗЫКАЛЬНЫХ ГРУПП. Сущности
и их атрибуты даны в таблице 12.
Спроектируем базу данных комбинированным методом. Множество функциональных зависимостей будет следующим:
F = {A  B, C  D, E  K, L  M, N  S, G  H,...}.
Здесь многоточия, как и в предыдущих примерах, должны быть
заменены «перекрестными» зависимостями между сущностями,
которые можно найти из описания ER-диаграммы:
1. ГРУППЫ (М, О) дают (М,Н) КОНЦЕРТЫ (правило 6).
2. КОНЦЕРТЫ (М, Н) проходят_на (М, О) РАДИО (правило 6).
116
Таблица 12
Сущности и их атрибуты
Сущности
Атрибуты
IDКонцерта
МестоПроведения
Статус
IDРадиоПрограммы
РАДИО
ВремяВыступления
ОтведенноеВремя
IDЗала
Название
ЗАЛЫ
Адрес
ЦенаБилета
IDПрессы
ПРЕССА
Название
ДатаПубликации
АвторПубликации
ЖУРНАЛИСТЫ IDЖурналиста
Фио
Тематика
IDГруппы
НазваниеГруппы
ГРУППЫ
ГородГруппы
Сайт
КОНЦЕРТЫ
Первичный ключ

B
С
да

D
E
да


K
L
да
M
N
да

S
G
да

Обозначение
А
да
H
3. КОНЦЕРТЫ (М, О) проходят_в (1, О) ЗАЛАХ (правило 4).
4. ЖУРНАЛИСТЫ (1, О) отзываются_о (М, О) КОНЦЕРТАХ
(правило 4).
5. ЖУРНАЛИСТЫ (М, Н) информируют_о (М, О) ГРУППАХ
(правило 6).
6. ЖУРНАЛИСТЫ (М, О) пишут_в (М, Н) ПРЕССУ (правило 6).
Из выделенных связей будут справедливыми следующие «перекрестные» зависимости:
КОНЦЕРТЫ  ЗАЛЫ или A  E;
КОНЦЕРТЫ  ЖУРНАЛИСТЫ или A  N.
Добавляя «перекрестные» зависимости, получим
F = {A  B, C  D, E  K, L  M, N S, G  H, A  E, A  N} или
F = {A  BEN, C  D, E  K, L  M, N  S, G  H}.
117
Выполняем ускоренный синтез. U = ABCDEKLMNSGH. Расширенное множество зависимостей будет таким:
ℱ = {A  BENKS, C  D, E  K, L  M, N  S, G  H}.
Поскольку расширенное множество не содержит «лишних» зависимостей с одинаковой левой частью, то условно неизбыточное
покрытие ℱ0 совпадает с ℱ.
Добавляя тривиальную зависимость U  , строим диаграмму
зависимостей, на которой выполняем операцию транзитивной редукции зависимостей (рис. 27):
Получаем результирующую декомпозицию отношений:
R1= ACLG;
R2 = ABEN;
R3 = CD;
R4 = LM;
R5 = GH;
R6 = EK;
R7 = NS; или для реальных данных:
R1: Концерты_Радио_Пресса_Группы (IDКонцерта, IDРадио,
IDПрессы, IDГруппы,);
R2: Концерты (IDКонцерта, МестоПроведения, Статус, IDЗала,
IDЖурналиста);
R3: Радио (IDРадио, ВремяВыступления, ОтведенноеВремя);
R4: Пресса (IDПрессы, Название, ДатаПубликации, АвторПубликации);
R5: Группы (IDГруппы, НазваниеГруппы, ГородГруппы, Сайт);
R6: Залы (IDЗала, Название, Адрес, ЦенаБилета);
R7: Журналисты (IDЖурналиста, Фио, Тематика).
Видно, что набор атрибутов ACLG является минимальным суперключом, так как ACLG+ = U, и замыкание никакого собственного подмножества этого набора атрибутов не равно U.
Спроектированная по методу синтеза база данных состоит из
семи таблиц.
1
A → BENKS
2
6
E →K
3
7
ABCDEKLMNSG H → ∅
C→D
4
L→M
N→ S
Рис. 27. Диаграмма зависимостей
118
5
G→ H
Результирующая декомпозиция, полученная по методу ERдиаграмм, будет такой:
R1= GH; R2 = ABEN; R3 = AG; R4 = CD; R5 = AC ; R6= NS;
R7= NG; R8 = LM;
R9= LN; R10 = EK или на реальных данных:
R1: Группы (IDГруппы, НазваниеГруппы, ГородГруппы, Сайт);
R2: Концерты (IDКонцерта, МестоПроведения, Статус, IDЗала,
IDЖурналиста);
R3: Концерты_Группы (IDКонцерта, IDГруппы);
R4: Радио (IDРадио, ВремяВыступления, ОтведенноеВремя);
R5: Концерты_Радио (IDКонцерта, IDРадио);
R6: Журналисты (IDЖурналиста, Фио, Тематика);
R7: Журналисты_Группы (IDЖурналиста, IDГруппы);
R8: Пресса (IDПрессы, Название, ДатаПубликации, АвторПубликации);
R9: Пресса_Журналисты (IDПрессы, IDЖурналиста);
R10: Залы (IDЗала, Название, Адрес, ЦенаБилета).
Спроектированная база данных по методу ER-диаграмм содержит десять таблиц, ни одна из которых не содержит суперключа,
следовательно, свойство соединения без потерь информации не
выполняется. На рис. 28 видно, что М-связные сущности ПРЕССА, ЖУРНАЛИСТЫ, ГРУППЫ, КОНЦЕРТЫ и РАДИО образуют
цепочку, причем сущность ЖУРНАЛИСТЫ имеет ответвление к
сущности КОНЦЕРТЫ типа 1:М, а сущность КОНЦЕРТЫ – к сущности ЗАЛЫ типа М:1.
Концерты
A
Залы
E
M
1
R9
M
Пресса
L
M
R3
R7
1
M
M
Журналисты
N
M
M
Группы
G
M
Концерты
A
M
R11 (LNGAC)
R5
M
Радио
С
Рис. 28. Операция уменьшения количества таблиц в базе данных,
спроектированной по методу ER-диаграмм
119
Если теперь удалить таблицы R3, R5, R7, R9 и вместо них добавить таблицу
R11: Пресса_Журналисты_Группы_Концерты_Радио
(IDПрессы, IDЖурналиста, IDГруппы, IDКонцерта, IDРадио),
как показано на рис. 28, то удастся уменьшить количество таблиц
в базе данных. Теперь база данных состоит из семи таблиц: R1, R2,
R4, R6, R8, R10 и R11. Добавленная таблица R11 содержит не минимальный суперключ – набор атрибутов LNGАС. В этой таблице
набор атрибутов LGАС, соответствующий минимальному суперключу, можно объявить первичным ключом, а атрибут N оставить
неключевым. Тогда для реальных данных добавленная таблица
R11 будет такой:
R11: Пресса_Группы_Концерты_Радио (IDПрессы, IDГруппы,
IDКонцерта, IDРадио IDЖурналиста) или в обозначениях табл. 12:
R1 = GH; R2 = ABEN; R4 = CD; R6 = NS;
R8 = LM;
R10 = EK;
R11 = ACLGN.
Тогда результирующая декомпозиция будет обладать свойством
соединения без потерь информации, а количество таблиц совпадет
с таковым, полученным методом синтеза.
На основании изложенного в данном разделе материала можно
дать следующие рекомендации.
Если больше двух М-связных сущностей образуют кольцо или
цепочку сущностей без ответвлений, то для проектирования реляционной базы данных рекомендуется использовать метод ERдиаграмм (случай 2) с использованием простой процедуры уменьшения количества таблиц в результирующей декомпозиции.
Во всех остальных случаях рекомендуется использовать метод
синтеза или комбинированный метод проектирования базы данных.
120
ПРИЛОЖЕНИЕ
Основные термины и определения
Предметная область – часть реального мира, интересующая пользователя (транспорт, министерство, банк, вуз, больница, процесс, предприятие
или его часть: бухгалтерия, цех,...).
Сущность – объект и (или) факт предметной области, информацию о которых необходимо хранить в базе данных.
Атрибут – поименованная характеристика сущности. Например, в
предметной области ПРЕДПРИЯТИЕ объект по имени СЛУЖАЩИЙ можно описать атрибутами с именами ТАБ_НОМЕР, ФИО, НОМЕР_ОТДЕЛА,
ДОЛЖНОСТЬ,..., а факт НАЗНАЧЕНИЕ – атрибутами: ПРОЕКТ, ФИО_
СЛУЖАЩЕГО.
Для каждого атрибута определяются:
имя (ТАБ_НОМЕР, ФИО,...);
тип (числовой, символьный,...);
значение или экземпляр (2, Иванов С.И.,...);
роль, которую играет атрибут в приложении (прикладной программе) пользователя.
Аналогично для сущности определяется имя и экземпляр. Экземпляр
сущности определяется набором экземпляров всех ее атрибутов. Например, экземпляром для сущности СЛУЖАЩИЙ (ТАБ_НОМЕР, ФИО, НОМЕР_ОТДЕЛА, ДОЛЖНОСТЬ,...) может быть
10, Иванов С.И., 4, инженер
или
20, Петров И.С., 3, механик
.........................
Атрибут может выступать в роли первичного, возможного первичного,
ключевого, неключевого, ключа связи (внешнего ключа).
Первичный (идентифицирующий) ключ (Primary Key) – атрибут или
набор атрибутов, однозначно определяющий экземпляр сущности. Так,
если все служащие имеют различные табельные номера, то атрибут ТАБ_
НОМЕР может выступать в роли первичного ключа для сущности СЛУЖАЩИЙ. Первичный ключ может быть простым (один атрибут) или составным (несколько атрибутов).
Возможный первичный ключ – атрибут или набор атрибутов, который
также однозначно определяет экземпляр сущности. Поскольку для сущности может быть определен только один первичный ключ, то второй называется возможным первичным ключом (уникальным). Например, если
ТАБ_НОМЕР объявляется первичным ключом, то НОМЕР_ПАСПОРТА
будет возможным первичным ключом или наоборот.
Ключевой атрибут – атрибут, выступающий в роли первичного или возможного первичного ключа или входящий в их состав.
Неключевой атрибут – атрибут, который не является первичным ключом и не входит в состав первичного или возможного первичного ключа.
121
Внешний ключ – атрибут, который используется для связи одной сущности с другой.
База данных (БД) – это именованная совокупность хранимых данных,
отображающая состояние сущностей и их отношений в рассматриваемой
предметной области.
Система управления базой данных (СУБД) – это комплекс языковых и
программных средств для создания и ведения баз данных. Термин «ведение» подразумевает управление (манипулирование) данными.
Реляционная база данных (relation – отношение) состоит из набора
взаимосвязанных таблиц (отношений). Таблица и отношение – слова синонимы.
Универсальный ключ, или суперключ – это, как правило, набор атрибутов, который определяет все атрибуты базы данных.
122
Библиографический список
1. Гарсиа-Молина Г., Ульман Дж., Уидом Дж. Системы баз
данных. Полный курс.: пер. с англ. – М.: Издательский дом «Вильямс», 2003.
2. Дейт К. Дж. Введение в системы баз данных, 8-е издание.:
пер. с англ. – М.: Издательский дом «Вильямс», 2005.
3. Дьяков В. И. Разработка системы проектирования реляционных баз данных на основе функциональных зависимостей: дис. ...
канд. тех. наук. – Л., 1986.
4. Кубрак В. А. Основы проектирования баз данных: учеб. пособие. Л.: ЛИАП, 1985.
5. Мейер Д. Теория реляционных баз данных. М.: Мир, 1987.
6. Мирошниченко Г. А. Реляционные базы данных: практические приемы оптимальных решений. – СПб.: БХВ-Петербург, 2005.
7. Преснякова Г. В. Проектирование интегрированных реляционных баз данных. – М.: КДУ; СПб.: Петроглиф, 2007.
8. Хомоненко А. Д., Цыганков В. М., Мальцев М. Г. Базы данных:
учеб. для высших учебных заведений; под ред. проф. А. Д. Хомоненко. – 6-е изд. доп. – СПб.: КОРОНА-Век, 2009.
9. Bernstan P.A. Syntheciring Third Normal Form Relations from
Functional Dependencies. – ACM Trans. On Database Syst., 1976, 1,
№ 4, p. 277–298.
10. Chen P. P-S. The entity-Relationship Modell. Toward a Unifed
View of Data. // ACM Transactions on Database Systems. – vol. 1,
№ 1, March, 1976.
11. Codd E.F. Further Normalization of the Data Base Relation
Model // Data Base Systems, Courant Computer Science Symposia Series 6. – Englewood Cliffs, N.J.: Prentice-Hall, 1972.
12. Codd E. F. Recent Investigation into Relational Data Base Systems // Proc. IFIP Congress. – Stockholm, Sweden, 1974.
13. Fagin R. Multivalued Dependencies and a New Normal Form
For Relational Databases // ACM TODS. – 1977. – № 3.
14. Isloor S. S. An Algorithm with Logical Symlicity for Desighing
Third Normal Form Relational Data Base Schema from Functional Dependencies. – In: Proc. ACM SIGMOD Int. Conf. Manag. Data, Milano,
1978, p. 31–50.
15. Chen P. P-S. The entity-Relationship Modell. Toward a Unifed
View of Data. – ACM Transactions on Database Systems, vol. 1, № 1,
March, 1976.
123
СОДЕРЖАНИЕ
Введение ..........................................................................
1. Основы теории реляционных структур данных ..................
1.1. Определение отношения ...........................................
1.2. Основы реляционной алгебры ....................................
1.2.1. Основные операции реляционной алгебры .........
1.2.2. Дополнительные операции реляционной
алгебры .................................................................
1.2.3. Примеры запросов ..........................................
1.3. Функциональные зависимости атрибутов ....................
1.3.1. Основные определения ....................................
1.3.2. Аксиомы и правила вывода функциональных
зависимостей ..........................................................
1.4. Замыкания .............................................................
1.5. Алгоритмы нахождения первичного ключа .................
1.6. Эквивалентность множеств функциональных
зависимостей ................................................................
1.7. Покрытия ...............................................................
1.7.1. Построение неизбыточных покрытий ................
1.7.2. Проверка зависимостей на элементарность.........
1.7.3. Поиск эквивалентных зависимостей .................
1.8. Декомпозиция схем отношений .................................
1.8.1. Понятие декомпозиции ...................................
1.8.2. Свойства декомпозиции...................................
1.8.2.1. Свойство соединения без потерь
информации ..................................................
1.8.2.2. Свойство сохранения функциональных
зависимостей .................................................
1.9. Нормальные формы .................................................
1.9.1. Первая нормальная форма (1НФ) ......................
1.9.2. Вторая нормальная форма (2НФ) ......................
1.9.3. Третья нормальная форма (3НФ) ......................
1.9.4. Нормальная форма Бойса – Кодда (НФБК) .........
1.9.5. Нормальные формы более высоких порядков......
2. Методы проектирования реляционных баз данных ............
2.1. Метод декомпозиции ................................................
2.2. Метод синтеза .........................................................
2.3. Метод ER-диаграмм («сущность-связь»)......................
2.3.1. Этапы проектирования ....................................
2.3.2. Правила формирования отношений ..................
124
3
4
4
5
6
9
14
17
17
19
25
27
31
33
35
38
39
40
40
42
42
46
51
53
55
57
58
59
62
62
63
78
80
80
2.4. Сравнение методов синтеза и ER-диаграмм ..................
2.5. Комбинированный метод проектирования ...................
2.6. Процедура уменьшения количества таблиц
в результирующей декомпозиции, полученной
по методу ER-диаграмм ..................................................
Приложение. Основные термины и определения ...................
Библиографический список ................................................
94
96
103
121
123
125
Учебное издание
Преснякова Галина Владимировна
Шахомиров Андрей Викторович
ПРОЕКТИРОВАНИЕ
РЕЛЯЦИОННЫХ БАЗ ДАННЫХ
Учебное пособие
Редактор Л. А. Яковлева
Компьютерная верстка С. Б. Мацапуры
Сдано в набор 00.00.15. Подписано к печати 22.06.15.
Формат 6084 1/16. Бумага офсетная. Усл. печ. л. 7,2.
Уч.-изд. л. 7,8. Тираж 100 экз. Заказ № 218.
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б. Морская ул., 67
Документ
Категория
Без категории
Просмотров
2
Размер файла
1 928 Кб
Теги
presnyakovshakhomirov
1/--страниц
Пожаловаться на содержимое документа