1. Традиционные операции над множествами: объединение, пересечение, вычитание и декартово произведение (модифицированные с учетом того, что их операндами являются отношения, а не произвольные множества).

2. Специальные реляционные операции: выборка, проекция, соединение и деление.

4.2 Замкнутость в реляционной алгебре

Результат каждой операции над отношением (или реляционной операции) также является отношением. Это реляционное свойство называется свойством замкнутости. Поскольку результат любой операции имеет тот же тип, что и исходные объекты (отношения), то результат одной операции может использоваться в качестве исходных данных для другой. Таким образом, имеется возможность, например, взять или проекцию от объединения, или соединение от двух выборок, или объединение соединения и пересечения и т.д.

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

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

4.3 Традиционные операции над множествами

4.3.1 Объединение

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

Будем говорить, что два отношения совместимы по типу, если у них идентичные заголовки, а точнее,

1. если каждое из них имеет одно и то же множество имен атрибутов (следовательно, заметьте, они заведомо должны иметь одну и ту же степень);

2. если соответствующие атрибуты (т.е. атрибуты с теми же самыми именами в двух отношениях) определены на одном и том же домене.

Операции объединения, пересечения и вычитания требуют от операндов совместимости по типу.

Объединением двух совместимых по типу отношений А и В (A UNION B) называется отношение с тем же заголовком, как и в отношениях А и В, и с телом, состоящим из множества всех кортежей, принадлежащих А или В или обоим отношениям.

Пример операции объединения отношений приведен на рис. 4.1 - рис. 4.2.

A		B
CityNo	CityName	RgNo		CityNo	CityName	RgNo
1	Желтые Воды	1		2	Кривой Рог	1
2	Кривой Рог	1		3	Пятихатки	1
3	Пятихатки	1		4	Львов	2

рис. 4.1 Исходные отношения

A UNION B
CityNo	CityName	RgNo
1	Желтые Воды	1
2	Кривой Рог	1
3	Пятихатки	1
4	Львов	2

рис. 4.2 Результат объединения отношений A и B.

4.3.2 Пересечение

Пересечением двух совместимых по типу отношений А и В (A INTERSECT B) называется отношение с тем же заголовком, как и в отношениях А и В, и с телом, состоящим из множества всех кортежей, принадлежащих одновременно обоим отношениям A и B.

Пример операции пересечения отношений приведен на рис. 4.1 и рис. 4.3.

A INTERSECT B
CityNo	CityName	RgNo
2	Кривой Рог	1
3	Пятихатки	1

рис. 4.3 Результат операции пересечения отношений A и B.

4.3.3 Вычитание

Вычитанием двух совместимых по типу отношений А и В (A MINUS B) называется отношение с тем же заголовком, как и в отношениях А и В, и с телом, состоящим из множества всех кортежей, принадлежащих отношению A и не принадлежащих отношению B.

Пример операции вычитания отношений приведен на рис. 4.1 и рис. 4.4.

A MINUS B		B MINUS A
CityNo	CityName	RgNo		CityNo	CityName	RgNo
1	Желтые Воды	1		4	Львов	2

рис. 4.4 Результат операции вычитания отношений A минус B и B минус A.

4.3.4 Произведение

В математике декартово произведение (или для краткости произведение) двух множеств является множеством всех таких упорядоченных пар элементов, что первый элемент в каждой паре берется из первого множества, а второй элемент в каждой паре берется из второго множества. Следовательно, декартово произведение двух отношений, должно быть множеством упорядоченных пар кортежей. Но опять-таки необходимо сохранить свойство замкнутости; иначе говоря, результат должен содержать кортежи, а не упорядоченные пары кортежей.

Декартово произведение двух отношений А и В (A TIMES B), где А и В не имеют общих имен атрибутов, определяется как отношение с заголовком, который представляет собой сцепление двух заголовков исходных отношений А и В, и телом, состоящим из множества всех кортежей t, таких, что t представляет собой сцепление кортежа a, принадлежащего отношению А, и кортежа b, принадлежащего отношению В. Кардинальное число результата равняется произведению кардинальных чисел исходных отношений А и В, а степень равняется сумме их степеней. Пример операции декартова произведения представлена на рис. 4.5

A		B
CityNo	CityName	A_RgNo		B_RgNo	RgName
1	Желтые Воды	1		1	Днепропетровская
2	Кривой Рог	1		2	Львовская
3	Пятихатки	1

A TIMES B
CityNo	CityName	A_RgNo	B_RgNo	RgName
1	Желтые Воды	1	1	Днепропетровская
1	Желтые Воды	1	2	Львовская
2	Кривой Рог	1	1	Днепропетровская
2	Кривой Рог	1	2	Львовская
3	Пятихатки	1	1	Днепропетровская
3	Пятихатки	1	2	Львовская

рис. 4.5 Результат операции декартово произведение отношений A и B.

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

4.4 Свойства основных операций реляционной алгебры

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

Пусть А, В и С - произвольные реляционные выражения (дающие совместимые по типу отношения). Тогда операция объединения:

(A UNION В) UNION С

Эквивалентна операции:

А UNION (В UNION С) (свойство ассоциативности), а .операция объединения:

А UNION B эквивалентна операции:

В UNION A (свойство коммутативности). Аналогично свойства ассоциативности и коммутативности определяются для остальных операций.

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

A UNION В UNION С.

4.5 Специальные реляционные операции

4.5.1 Выборка

Выборка - это сокращенное название -выборки, где обозначает любой скалярный оператор сравнения (=, , >, , ?, <). -выборкой из отношения A по атрибутам Х и Y (в этом порядке)

A WHERE X Y называется отношение, имеющее тот же заголовок, что и отношение А, и тело, содержащее множество всех кортежей отношения А, для которых проверка условия X  Y дает значение истина. Атрибуты X и Y должны быть определены на одном и том же домене, а оператор должен иметь смысл для этого домена.

На рис. 4.6приведен пример операции выборки.

A
CityNo	CityName	RgNo
1	Желтые Воды	1
2	Кривой Рог	1
3	Пятихатки	1
4	Львов	2

A WHERE RgNo = 1
CityNo	CityName	RgNo
1	Желтые Воды	1
2	Кривой Рог	1
3	Пятихатки	1

рис. 4.6 Исходное отношение A и результат операции выборки кортежей из отношения A по условию RGNo = 1.

4.5.2 Проекция

Проекцией отношения А по атрибутам X, Y,..., Z, где каждый из атрибутов принадлежит отношению А

A [ X, Y, …, Z ] называется отношение с заголовком {X, Y,..., Z} и телом, содержащим множество всех кортежей {Х:х, Y:y,..., Z:z}, таких, для которых в отношении А значение атрибута Х равно х, атрибута Y равно y, ..., атрибута Z равно z.

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

A

CityNo	CityName	RgNo
1	Желтые Воды	1
2	Кривой Рог	1
3	Пятихатки	1
4	Львов	2

A [CityName]

CityName
Желтые Воды
Кривой Рог
Пятихатки
Львов

рис. 4.7 Исходное отношение A и результат операции проекции отношения A по атрибуту CityName.

Никакой атрибут не может быть указан в списке атрибутов более одного раза. Синтаксис позволяет опустить список атрибутов совсем (вместе с квадратными скобками). Действие такой операции эквивалентно указанию списка всех атрибутов исходного отношения, т.е. такая операция представляет собой тождественную проекцию. Другими словами, имя отношения является допустимым реляционным выражением. Проекция вида R[ ], т.е. такая, в которой список атрибутов не пропущен, но пустой, тоже допустима. Она представляет собой "нулевую" проекцию.

4.5.3 Естественное соединение

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

Пусть отношения А и В имеют заголовки {Xl, X2, ..., Xm, Y1, Y2, ..., Yn} и {Yl, Y2, ..., Yn, Zl, Z2, ..., Zp} соответственно; т.е. атрибуты Yl, Y2, ..., Yn (и только они) _ общие для двух отношений; Х1, Х2, ... ,Хm - остальные атрибуты отношения A; Zl, Z2, ..., Zp _ остальные атрибуты отношения В. Предположим также, что соответствующие атрибуты (т.е. атрибуты с одинаковыми именами) определены на одном и том же домене. Рассматривать выражения {X1, Х2, ..., Хm}, {Y1, Y2, ..., Yn} и {Zl, Z2, ..., Zp} как три составных атрибута X, Y и Z соответственно. Тогда естественным соединением отношений А и В (A JOIN B) называется отношение с заголовком {X, Y, Z} и телом, содержащим множество всех кортежей {Х:х, Y:y, Z:z}, таких, для которых в отношении А значение атрибута X равно х, а атрибута Y равно у, и в отношении В значение атрибута Y равно у, а атрибута Z равно z.

Пример операции естественного соединения приведен на рис. 4.8.

A		B
CityNo	CityName	RgNo		RgNo	RgName
1	Желтые Воды	1		1	Днепропетровская
2	Кривой Рог	1		2	Львовская
3	Пятихатки	1

A JOIN B
CityNo	CityName	A_RgNo	RgName
1	Желтые Воды	1	Днепропетровская
2	Кривой Рог	1	Днепропетровская
3	Пятихатки	1	Днепропетровская

рис. 4.8 Исходные отношения A и B и результат операции естественного соединения.

Соединение обладает свойствами ассоциативности и коммутативности. Отсюда следует, что выражения:

(A JOIN В) JOIN С и

A JOIN (В JOIN С) могут быть однозначно упрощены к следующему:

A JOIN В JOIN С

Кроме того, выражения:

A JOIN Ви

В JOIN A эквивалентны.

4.5.4 -соединение

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

(A TIMES В) WHERE X Y

-соединение, таким образом, это отношение с тем же заголовком, что и при декартовом произведении отношений A и B, и с телом, содержащим множество кортежей, принадлежащих этому декартову произведению и вычисление условия XY дает значение истина для этого кортежа. Атрибуты Х и У должны быть определены на одном и том же домене, а операция должна иметь смысл для этого домена.

4.5.5 Деление

Пусть отношения А и В имеют заголовки:

{X1, X2,..., Xm, Y1, Y2, ..., Yn} и {Y1, Y2, ..., Yn} соответственно, т.е. атрибуты Y1, Y2,..., Yn -- общие для двух отношений, и отношение A имеет дополнительные атрибуты X1, Х2, ... ,Хm, а отношение В не имеет дополнительных атрибутов. (Отношения А и В представляют соответственно делимое и делитель.) Предположим также, что соответствующие атрибуты (т.е. атрибуты с одинаковыми именами) определены на одном и том же домене. Пусть теперь выражения {X1, Х2, ..., Хm} и {Y1, Y2, ..., Yn} обозначают два составных атрибута Х и Y соответственно. Тогда делением отношений А на В (A DIVIDEBY B) называется отношение с заголовком {X} и телом, содержащим множество всех кортежей {X:x}, таких что существует кортеж {Х:х, Y:y}, который принадлежит отношению A для всех кортежей {Y:y}, принадлежащих отношению В. Нестрого это можно сформулировать так: результат содержит такие X-значения из отношения А, для которых соответствующие Y-значения (из А) включают все Y-значения из отношения В.

Пример операции деления приведен на рис. 4.9. Отношение M является проекцией отношения Marks, а отношение S - проекцией отношения Subjects. Результат операции деления M DIVIDE BY S фактически содержит номера студентов, которые сдавали дисциплины с номерами 1 и 5.

M		S
StNo	SubjNo		SubjNo
1	1		1
1	5		5
2	1
2	5
3	1
3	5
4	1
5	1
M DIVIDE BY S
StNo
1
2
3

рис. 4.9. Пример операции деления.

Восемь операторов Кодда не представляют минимального набора операторов, так как не все из них примитивны, их можно определить в терминах других операторов. Например, естественное соединение - это проекция выборки произведения. Фактически три операции из этого набора, а именно соединение, пересечение и деление, можно определить через остальные пять. Операции выборки, проекции, произведения, объединения и вычитания можно рассматривать как примитивные в том смысле, что ни одна из них не выражается через другие. Поэтому минимальный набор будет состоять из этих пяти примитивных операций. Однако на практике другие три операции (в особенности соединение) настолько часто используются, что имеет смысл обеспечить их непосредственную поддержку, несмотря на то что они не примитивны.

Многие авторы предлагали новые алгебраические операторы после определения Коддом первоначальных восьми. Рассмотрим два таких оператора - EXTEND (расширение) и SUMMARIZE (подведение итогов), которые удачно дополняют основной набор восьми операторов.

4.5.6 Операция расширения

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

EXTEND GROUPS ADD (2002-EnterYear) AS COURCE

GROUPS		Результат операции расширения
GrNo	EnterYear	GrName		GrNo	EnterYear	GrName	Cource
1	1998	А-98-51		1	1998	А-98-51	2
2	1999	Б-99-51		2	1999	Б-99-51	1
3	1998	Б-98-51		3	1998	Б-98-51	2

рис. 4.10 Пример выполнения операции расширения.

4.5.7 Операция подведения итогов

Пусть А1,А2,... ,An - отдельные атрибуты отношения А. Результатом операции подведения итогов

SUMMARIZE A BY (A1, A2, … An) ADD exp AS Z (которая является выражением, а не командой или оператором) будет отношение с заголовком {А1, А2, ..., An, Z} и с телом, содержащим все такие кортежи, которые являются кортежами проекции отношения А по атрибутам Al, A2, ..., An, расширенного значением для нового атрибута Z. Новое значение Z подсчитывается вычислением итогового выражения ехр по всем кортежам отношения А, которые имеют те же самые значения для атрибутов А1, А2, ..., Аn, что и кортеж t. Список атрибутов А1, А2, ..., Аn не должен включать атрибут с именем Z, а выражение ехр не должно ссылаться на атрибут Z. Кардинальное число результата равно кардинальному числу проекции отношения А по атрибутам Al, A2, ..., An, а степень результата равна степени такой проекции плюс единица.

4.5.8 Операторы обновления

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

TARGET := SOURCE где source и target-- реляционные выражения, представляющие совместимые по типу отношения. Вычисленное значение source присваивается отношению target, заменяя его старое значение.

В реляционных системах также существуют операции вставки INSERT, удаления DELETE и модификации UPDATE.

Оператор вставки имеет следующий вид:

INSERT source INTO target где source и target - это реляционные выражения, представляющие совместимые по типу отношения (на практике отношение target является просто именованным отношением). Значение отношения source вычисляется, и все кортежи результата вставляются в отношение target.

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

UPDATE target attribute1:=scalar_expression, attribute2:=scalar_expression, …, attributeN:=scalar_expression

где target - реляционное выражение, а каждый атрибут attribute принадлежит отношению, которое является результатом вычисления указанного выражения. Все кортежи в результирующем отношении обновляются в соответствии с указанными операторами attribute2:=scalar_expression

На практике выражение target часто будет просто ограничивающим условием для некоторого именованного отношения.

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

DELETE target

где target - реляционное выражение; все кортежи в результирующем отношении удаляются.

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

4.5.9 Реляционные сравнения

Реляционное сравнение имеет следующий вид:

Expression expression где expression -это выражения реляционной алгебры, представляющие совместимые по типу отношения, а - один из следующих операторов сравнения:

= (равно)

(не равно)

(подмножество)

< (собственное подмножество)

(надмножество)

> (собственное надмножество).

Литература:

1. Дейт К.Дж. Введение в системы баз данных. -Пер. с англ. -6-е изд. -К. Диалектика, 1998. Стр. 135-171.

ЛЕКЦИЯ 5. Вопросы проектирования БД

• 5.1 Понятие проектирования БД
• 5.2 Функциональные зависимости
• 5.3 Тривиальные и нетривиальные зависимости
• 5.4 Замыкание множества зависимостей и правила вывода Армстронга
• 5.5 Неприводимое множество зависимостей
• 5.6 Нормальные формы - основные понятия
• 5.7 Декомпозиция без потерь и функциональные зависимости
• 5.8 Диаграммы функциональных зависимостей

5.1 Понятие проектирования БД

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

Следует отметить следующие особенности.

1. Следует заметить, что речь здесь пойдет о логическом, а не физическом макете.

2. Физический макет может рассматриваться как отдельная сопутствующая часть. Иначе говоря, для "правильного" составления макета базы данных следует прежде всего создать логический (т.е. реляционный) макет, а затем в виде отдельного шага отобразить этот логический макет на некоторые физические структуры, поддерживаемые СУБД.

3. Физический макет по определению является специфическим для данной СУБД. Логический макет, наоборот, совершенно независим от СУБД, и для его реализации могут быть использованы строгие теоретические принципы.

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

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

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

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

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

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

5.2 Функциональные зависимости

Для демонстрации основных идей данного раздела используется несколько измененная версия отношения Students из учебной БД, которое в дополнение к обычным атрибутам StNo, GrNo, StName, CityNo будет содержать также атрибут RgNo, представляющий город соответствующего поставщика. Во избежание путаницы далее это измененное отношение будет называться SR. В виде таблицы оно представлено на рис. 5.1.

SR
StNo	GrNo	StName	CityNo	RgNo
1	1	Иванов	3	1
2	1	Петров	3	1
3	1	Сидоров	3	1
4	2	Стрельцов	1	1
5	2	Кузнецов	4	2

рис. 5.1 Данные отношения SR.

Следует четко различать:

1. значение этого отношения (т.е. значение переменной отношения) в определенный момент времени;

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

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

Ниже приведено определение концепции функциональной зависимости для второго пункта.

Пусть R является переменной отношения, а X и Y - произвольными подмножествами множества атрибутов отношения R. Тогда Y функционально зависимо от X, что в символическом виде записывается как

XY
(и читается либо как "X функционально определяет Y ", либо как "X стрелка Y "), тогда и только тогда, когда для любого допустимого значения отношения R каждое значение Х связано в точности с одним значением Y.

Иначе говоря, для любого допустимого значения отношения R, когда бы два кортежа отношения R ни совпадали по значению X, они также совпадают и по значению Y. Далее термин "функциональная зависимость" будет использоваться в последнем безотносительном ко времени смысле (за исключением особо оговоренных случаев).

Например, в случае отношения SR функциональная зависимость

{StNo}{GrNo}

выполняется для всех возможных значений SR, поскольку в любой момент времени данному студенту соответствует в точности одна группа; таким образом, любые два кортежа отношения SR в один и тот же момент времени и с одним и тем же номером студента должны соответствовать одной и той же группе. Практически утверждение, что данная функциональная зависимость выполняется "всегда" (т.е. для всех возможных значений SR), является ограничением целостности для отношения SR, поскольку при этом накладываются определенные ограничения на все допустимые значения.

Ниже перечислено несколько безотносительных ко времени функциональных зависимостей для переменной отношения SR

{StNo}{GrNo}

{StNo}{StName}

{StNo}{CityNo}

{StNo}{RgNo}

{StNo}{GrNo, StName}

{StNo}{GrNo, StName, CityNo, RgNo}

{StNo, GrNo} {StName}

и другие.

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

StNoGrNo

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

GrNoCityNo

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

StNo{GrNo, StName, CityNo}

Фактически, если отношение R удовлетворяет функциональной зависимости A  B и A не является потенциальным ключом, то R будет характеризоваться некоторой избыточностью. Например, в случае отношения SR сведения о том, что каждый данный город находится в данной области, будут повторяться много раз (это хорошо видно на рис. 5.1).

На практике важно сократить множество ФЗ до компактных размеров, поскольку, функциональные зависимости являются ограничениями целостности, поэтому при каждом обновлении данных в СУБД все они должны быть проверены.

5.3 Тривиальные и нетривиальные зависимости

Очевидным способом сокращения размера множества ФЗ было бы исключение тривиальных зависимостей, т.е. таких, которые не могут не выполняться. В качестве примера приведем тривиальную ФЗ для отношения SR:

{StNo, GrNo}   {StNo}

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

5.4 Замыкание множества зависимостей и правила вывода Армстронга

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

{StNo}{GrNo, StName}
подразумевает следующие функциональные зависимости:

{StNo}{GrNo}

{StNo}{StName}

Множество всех ФЗ, которые задаются данным множеством функциональных зависимостей S, называется замыканием S и обозначается символом S+.

Поскольку функциональные зависимости являются ограничениями целостности, которые должны быть проверены СУБД, желательно для заданного множества ФЗ S найти такое множество ФЗ которое было бы гораздо меньшего размера, чем множество S, причем каждая ФЗ множества S могла бы быть заменена функциональной зависимостью множества T. Для решения этой задачи следует найти способ вычисления S+ на основе S.

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

Правила вывода Армстронга. Пусть в перечисленных ниже правилах А, В, С и D - произвольные подмножества множества атрибутов заданного отношения R, а символическая запись АВ означает объединение А и В.

1. Рефлексивность: если В является подмножеством А, то АВ.

2. Дополнение: если АВ, то АСВС.

3. Транзитивность: если АВ и ВС, то АС.

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

Из трех описанных выше правил для упрощения задачи практического вычисления замыкания S можно вывести несколько других правил. (Пусть D - это другое произвольное подмножество множества атрибутов R.).

1. Самоопределение: АА.

2. Декомпозиция: если АВС, то АВ и АC.

3. Объединение: если AВ и АС, то АВС.

4. Композиция: если АВ и СD, то ACBD.

5. Если АВ и СD, то А (С - В) BD (где символ "" обозначает объединение множеств, а символ "-" - их разность).Это правило называют также теоремой всеобщего объединения.

Например. Пусть дано некоторое отношение R с атрибутами А, В, С, D, Е, F и следующими ФЗ:

А{ВС}

ВЕ

{CD}{EF}

Далее символами, записанными подряд, например ВС, будем обозначать множество, состоящее из атрибутов В и С, а не объединение В и С.

Этому примеру можно придать более конкретный смысл, а именно: А - номер сотрудника, В - номер отдела, С - номер руководителя (начальника) данного сотрудника, D - номер проекта, возглавляемого данным руководителем (уникальный для каждого отдельно взятого руководителя), Е - название отдела, F - доля времени, уделяемая данным руководителем заданному проекту.

Показать, что зависимость AD  F выполняется для отношения R и таким образом принадлежит замыканию данного множества ФЗ.

1. АВС (дано);

2. АС (из 1 согласно декомпозиции);

3. ADCD (из 2 согласно дополнению);

4. CDEF (дано);

5. ADEF (из 3 и 4 согласно транзитивности);

6. ADF (из 5 согласно декомпозиции).

5.5 Неприводимое множество зависимостей

Пусть S1 и S2 являются двумя множествами ФЗ. Если любая ФЗ, которая является зависимостью множества S1, также является зависимостью множества S2, т.е. если S1+ является подмножеством S2+ то S2 называется покрытием для S1. Это значит, что если накладываемые в СУБД ограничения представлены зависимостями множества S2, то в этой СУБД также наложены ограничения на основе зависимостей множества S1.

Далее, если S2 является покрытием для S1, а S1 - покрытием для S2, т.е. если S1+=S2+ , то S1 и S2 эквивалентны. Ясно, что если S1 и S2 эквивалентны и наложенные в СУБД ограничения представлены зависимостями множества S2, то эти ограничения также могут быть представлены зависимостями множества S1, верно также и обратное утверждение.

Множество ФЗ называется неприводимым тогда и только тогда, когда выполняются перечисленные ниже свойства.

1. Правая часть (зависимая часть) каждой ФЗ множества S содержит только один атрибут (т.е. является одноэлементным множеством).

2. Левая часть (детерминант) каждой ФЗ множества S является неприводимой, т.е. ни один атрибут не может быть опущен из детерминанта без изменения замыкания S+ (без конвертирования множества S в некоторое множество, не эквивалентное множеству S). В таком случае ФЗ является неприводимой слева

3. Ни одна функциональная зависимость в S не может быть опущена из S без изменения замыкания S+ (т.е. без конвертирования множества S в некоторое множество, не эквивалентное множеству S).

Множество зависимостей t, которое неприводимо и эквивалентно некоторому другому множеству зависимостей S, называется неприводимым покрытием множества S. Таким образом, с тем же успехом в системе вместо исходного множества зависимостей S может быть использовано его неприводимое покрытие t. Однако следует отметить, что для заданного множества ФЗ не всегда существует уникальное неприводимое покрытие.

5.6 Нормальные формы - основные понятия

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

Отсюда следует, что каждое нормализованное отношение находится в первой нормальной форме. Иначе говоря, термины "нормализованное" и "1НФ" означают одно и то же. Однако следует отметить, что термин "нормализованное" часто используется для обозначения нормальной формы более высокого уровня, хотя такое обозначение не очень корректно.

рис. 5.2 Нормальные формы отношений.

На рис. 5.2 показано несколько нормальных форм, которые определены к настоящему времени.

Все нормализованные отношения находятся в 1НФ. Некоторые отношения 1НФ находятся также в 2НФ и некоторые отношения 2НФ находятся также в ЗНФ. Мотивом для введения дополнительных определений было то, что вторая нормальная форма "более желательна", чем первая, а третья, в свою очередь, "более желательна", чем вторая. Таким образом, при проектировании базы данных вообще следует использовать отношения не только в первой или во второй, но также и в третьей форме.

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

5.7 Декомпозиция без потерь и функциональные зависимости

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

Рассмотрим отношение Students из учебной базы данных, с атрибутами {StNo, GrNo, StName, CityNo} (рис. 5.3).

Students
StNo	GrNo	StName	CityNo
1	1	Иванов	1
2	1	Петров	3

рис. 5.3 Отношение Students.

Ниже приведены две возможные декомпозиции этого отношения (рис. 5.4).

1. SGN		SC
StNo	GrNo	StName		StNo	CityNo
1	1	Иванов		1	1
2	1	Петров		2	3

2. SGN		GC
StNo	GrNo	StName		GrNo	CityNo
1	1	Иванов		1	1
2	1	Петров		1	3

рис. 5.4 Возможные декомпозиции отношения Students.

В первом случае информация не утрачивается, поскольку отношения SGN и SC все еще содержат информацию о том, что Иванов живет в городе с кодом 1, Петров - 2. Соединение этих отношений позволяет восстановить исходное отношение Students, иначе говоря первая декомпозиция является декомпозицией без потерь.

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

Следует отметить, что процесс, который до сих пор назывался “декомпозицией”, на самом деле называется проецированием, т.е. каждое из показанных выше отношений SGN, SC и GC - в действительности являются проекциями исходного отношения Students. Таким образом оператор декомпозиции в процедуре нормализации фактически является оператором проецирования.

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

Теорема Хеза. Пусть R{A, B, C} является отношением, где A, B, C - атрибуты этого отношения. Если R удовлетворяет зависимости AB, то отношение R равно соединению его проекций {A, B} и {A, C}.

5.8 Диаграммы функциональных зависимостей

Некоторое неприводимое множество зависимостей отношения R можно представить в виде диаграммы функциональных зависимостей (диаграммы ФЗ).

На рис. 5.5 и рис. 5.6 показаны диаграммы ФЗ для некоторых отношений из учебной БД.

рис. 5.5 Диаграмма ФЗ для таблицы Students.

рис. 5.6 Диаграмма ФЗ для таблицы Marks.

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

Литература:

1. Дейт К.Дж. Введение в системы баз данных. -Пер. с англ. -6-е изд. -К. Диалектика, 1998. Стр. 259-276.

ЛЕКЦИЯ 6. Проектирование БД. Нормальные формы отношений

• 6.1 Первая нормальная форма. Возможные недостатки отношения в 1НФ
• 6.2 Вторая нормальная форма. Возможные недостатки отношения во 2НФ
• 6.3 Третья нормальная форма. Возможные недостатки отношения в 3НФ
• 6.4 Нормальная форма Бойса-Кодда

6.1 Первая нормальная форма. Возможные недостатки отношения в 1НФ

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

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

В этом определении всего лишь утверждается, что любое нормализованное отношение находится в 1НФ. Однако отношение, которое находится только в 1 НФ (т.е. не находится ни во второй, ни в третьей нормальной форме) обладает структурой, по некоторым причинам не совсем желательной. Для иллюстрации этого факта допустим, что информация о студентах и оценках содержится не в 2-х отношениях Students и Marks а в одном, назовем его SM.

SM{StNo, CityNo, GrNo, SubjNo, DocNo, Mark}

PRIMARY KEY (StNo, GrNo, SubjNo, DocNo).

Диаграмма функциональных зависимостей этого отношения будет выглядеть как показано на рис. 6.1.

рис. 6.1 Диаграмма функциональных зависимостей отношения SM

Обратите внимание, что диаграммы ФЗ отношения SM “сложнее”, чем диаграммы ФЗ отношений Students и Marks, из которых оно образовано. В диаграммах ФЗ отношений Students и Marks все стрелки начинаются только от первичных ключей, тогда как в диаграмме ФЗ отношения SM появляются дополнительные стрелки. Ниже приведена таблица данных для отношения SM (рис. 6.2).

SM
StNo	StName	GrNo	CityNo	SubjNo	DocNo	Mark
1	Иванов	1	1	1	127	5
1	Иванов	1	1	5	128	4
2	Петров	1	3	1	127	3

рис. 6.2 Данные отношения SM.

Несмотря на то, что отношение SM, как и Students и Marks находится в 1й НФ, оно очевидно обладает избыточностью, поскольку, например, в каждом кортеже для студента Иванова указан его номер “1”, код его группы - “1” и код города, в котором он проживает - “1”. Аналогичная ситуация с другими студентами.

Избыточность в отношении SM приводит к разным аномалиям обновления, получившим такое название по историческим причинам, т.е. к трудностям при выполнении операций обновления типа INSERT (вставка), DELETE (удаление) и UPDATE (обновление). Для начала рассмотрим избыточность типа студент--код города студента, соответствующую функциональной зависимости StNo CityNo, и перечисленные ниже проблемы с операциями обновления.

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

Операция удаления (DELETE). Если удалить единственный кортеж отношения SM для некоторого студента, будет удалена не только информация о соответствующей оценке, но и информация о студенте и городе, в котором он проживает. Например, если в отношении SM удалить кортеж со значением Петров атрибута StName, будет утрачена вся информация об этом студенте.

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

Операция модификации (UPDATE). Фамилия студента и код города, в котором он проживает повторяется в отношении SM множество раз, и это приводит к возникновению проблем при обновлении. Если студент меняет фамилию или переезжает в другой город, то возникает проблема, связанная либо с поиском в отношении SM всех кортежей, в которых присутствует информация об этом студенте, либо с получением несовместимого результата (в одном кортеже городом проживания студента будет один город, а в другом кортеже, городом проживания этого студента, будет другой город).

Для решения проблемы избыточности, которая характерна для отношения SM достаточно заменить его двумя другими:

Students{StNo, GrNo, StName, CityNo}

и

Marks{StNo, SubjNo, DocNo, Mark}

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

Операция вставки (INSERT). Теперь с помощью вставки соответствующего кортежа в отношение Students можно включить информацию о студенте и городе, в котором он проживает, даже если он в настоящий момент не получил не одной оценки.

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

Операция модификации (UPDATE). В переработанной структуре фамилия студента и информация о городе, в котором он проживает, появляется всего один раз, поскольку существует только один кортеж для данного студента в отношении Students (атрибут StNo является первичным ключом для такого отношения). Иначе говоря, избыточность данных StNo-StName-StCity устранена. Благодаря этому теперь можно один раз изменить в соответствующем кортеже отношения Students название города для какого-либо студента.

6.2 Вторая нормальная форма. Возможные недостатки отношения во 2НФ

Определим 2НФ при условии, что существует только один потенциальный ключ, который является первичным ключом.

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

Оба отношения, Students и Marks находятся во второй нормальной форме с первичными ключами StNp и {StNo, SubjNo, DocNo} соответственно, а отношение SM не находится в ней. Всякое отношение, которое находится в 1НФ и не находится в 2НФ, всегда можно свести к эквивалентному набору отношений, находящихся в 2НФ.

Рассмотрим другой пример. Предположим, информация о коде города, названии города и области, в которой этот город расположен находятся в одной таблице CNR{CityNo, CityName, RgNo, RgName} (рис. 6.3).

CNR
CityNo	CityName	RgNo	RgName
1	Желтые Воды	1	Днепропетровская
2	Кривой Рог	1	Днепропетровская
3	Пятихатки	1	Днепропетровская
4	Львов	2	Львовская

рис. 6.3 Данные отношения CNR.

Диаграмма ФЗ отношения CNR выглядит следующим образом - рис. 6.4.

рис. 6.4 Функциональные зависимости в отношении CNR.

Как видно из рис. 6.3, это диаграмма ФЗ “сложнее” диаграмм ФЗ отношений Cities и Regions. Несмотря на то, что отношение CNR находится во 2НФ, оно обладает некоторой избыточностью, связанной с наличием транзитивной ФЗ между атрибутами CityNo и RgName. Транзитивная зависимость приводит к следующим аномалиям обновления.

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

Операция удаления (DELETE). При удалении из отношения CNR последнего кортежа для некоторого города будет удалена не только информация о данном городе, но также информация о том, в какой области этот город находился. Например, при удалении из отношения CNR кортежа для города Львов будет утрачена информация о Львовской области.

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

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

Для решения этих проблем необходимо заменить отношение CNR двумя проекциями:

Cities{CityNo, CityName, RgNo}

Regions{RgNo, RgName}

Переработанная таким образом структура отношений позволит преодолеть все описанные проблемы с операциями обновления.

6.3 Третья нормальная форма. Возможные недостатки отношения в 3НФ

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

Отношения Cities и Regions находятся в третьей нормальной форме. Таким образом вторым этапом нормализации является создание проекций для исключения транзитивных зависимостей.

6.3.1 Сохранение зависимости

В процессе приведения отношений часто возникают ситуации, когда данное отношение может быть подвергнуто операции декомпозиции разными способами. Рассмотрим снова приведенное выше отношение CNR с функциональными зависимостями CityNoCityName, CityNoRgNo, CityNoRgNаме, RgNoRgName и, следовательно, транзитивной зависимостью CityNoRgName (на рис. 6.5 транзитивная зависимость показана пунктирной стрелкой).

рис. 6.5 Функциональные зависимости в отношении CNR

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

Cities{CityNo, CityName, RgNo} и Regions{RgNo, RgName}

Назовем эту декомпозицию просто "декомпозицией №1", имея в виду, что для нее существует альтернативная "декомпозиция №2":

Cities{CityNo, CityName, RgNo} и Regions{CityNo, RgName}

При этом обе проекции Cities одинаковы как для №1, так и для №2. Декомпозиция №2 происходит также без потери информации, а обе ее проекции находятся в ЗНФ. Однако по некоторым причинам декомпозиция №2 менее желательна, чем декомпозиция №1. Например, после выполнения декомпозиции №2 все еще невозможно вставить информацию о том, что некоторая область имеет определенный код, без указания города, который находится в этой области.

Рассмотрим этот пример подробнее. Прежде всего заметим, что зависимости проекций в декомпозиции №1 отмечены сплошными стрелками, тогда как одна, из зависимостей проекций декомпозиции №1 отмечена пунктирной стрелкой. В декомпозиции №1 две проекции независимы друг от друга в следующем смысле: обновления в каждой из проекций могут быть выполнены совершенно независимо друг от друга. (Конечно, за исключением ограничения целостности для Cities и Regions) Если такое обновление допустимо только в контексте данной проекции, т.е. не нарушается уникальность первичного ключа для этой проекции, то соединение этих двух проекций после обновления всегда будет равносильно отношению CNR (т.е. при соединении не будут нарушены ограничения, наложенные на ФЗ в отношении CNR). В декомпозиции №2, наоборот, обновление любой из двух проекций должно тщательно фиксироваться, чтобы гарантировать отсутствие нарушения зависимости RgNoRgName (если два города находятся в одной и той же области, они должны иметь одинаковый код области). Иначе говоря, обе проекции декомпозиции №2 не являются независимыми одна от другой.

Основная проблема заключается в том, что в декомпозиции №2 функциональная зависимость RgNoRgName становится ограничением между отношениями. (Следует отметить, что во многих современных программных продуктах это ограничение должно поддерживаться с помощью процедурной обработки.) В декомпозиции №1, наоборот, транзитивная зависимость SityNoRgName является ограничением между отношениями, которое автоматически выполняется при задействовании двух ограничений внутри отношений: CityNoRgNo и RgNoRgName. Привести в действие эти ограничения достаточно просто за счет соответствующих ограничений, наложенных на уникальность первичных ключей.