Концепция независимых проекций, таким образом, обеспечивает критерий выбора одной из нескольких возможных декомпозиции. Декомпозиция с независимыми проекциями в приведенном выше общем смысле предпочтительнее той, в которой проекции зависимы. Риссанен (Rissanen) показал, что проекции R1 и R2 отношения R независимы в упомянутом выше смысле тогда и только тогда, когда:

1. каждая ФЗ в отношении R является логическим следствием функциональных зависимостей в проекциях R1 и R2;

2. общие атрибуты проекций R1 и R2 образуют потенциальный ключ, по крайней мере, для одной из них.

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

6.4 Нормальная форма Бойса-Кодда

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

1. Отношение имеет два (или более) потенциальных ключа.

2. Два потенциальных ключа являются сложными.

3. Они перекрываются (т.е. имеют, по крайней мере, один общий атрибут).

Поэтому оригинальное определение ЗНФ было впоследствии заменено более строгим определением Бойса-Кодда (Boyce/Codd), для которого было принято отдельное название - нормальная форма Бойса-Кодда, НФБК. (На самом деле строгое определение "третьей" нормальной формы, эквивалентное определению нормальной формы Бойса-Кодда, было впервые дано Хезом (Heath) в 1971 году, и этой форме следовало бы дать название "нормальная форма Хеза".)

Замечание. Комбинация условий 1, 2 и 3 не часто встречается на практике, и для отношения без этих условий ЗНФ и НФБК эквивалентны.

Отношение находится в нормальной форме Бойса-Кодда тогда и только тогда, когда каждая нетривиальная и неприводимая слева ФЗ обладает потенциальным ключом в качестве детерминанта.

Менее формальное определение имеет другую формулировку: отношение находится в нормальной форме Бойса-Кодда тогда и только тогда, когда детерминанты являются потенциальными ключами.

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

Примером отношения, которое находится в НФБК может служить отношение Students, в которое добавлен атрибут IdCode - идентификационный код.

Students {StNo, IdCode, GrNo, StName, CityNo}

рис. 6.6 Диаграмма ФЗ расширенного отношения, Students, находящегося в НФБК.

В этом отношении детерминанты являются потенциальными ключами, а все стрелки начинаются с потенциальных ключей. Рассмотрим отношение, не находящееся в НФБК.

Предположим, что информация об идентификационных кодах студентов хранится в отношении Marks. Назовем модифицированное отношение MI {StNo, IdCode, SubjNo, DocNo, Mark} (рис. 6.7).

MI
StNo	IdCode	SubjNo	DocNo	Mark
1	2895764537	1	127	5
1	2895764537	5	128	4
2	3094769520	1	127	3
2	3094769520	5	128	3
3	2984267527	1	127	5

рис. 6.7 Данные отношения MI.

В этом отношении присутствуют 2 потенциальных ключа {StNo, SubjNo, DocNo} и {IdCode, SubjNo, DocNo}. Отношение находится в 3-й НФ, но не находится в НФБК, так как содержит два детерминанта, которые не являются потенциальными ключами этого отношения (StNo и IdCode детерминанты, поскольку они определяют друг друга). Как видно, в отношении MI присутствует доля избыточности, которая имелась и в ранее рассмотренных отношениях (SM и CNR), поэтому оно характеризуется такими же аномалиями обновления. Для решения этой проблемы отношение MI следует разбить на две проекции:

SI {StNo, IdCode} и Marks {StNo, SubjNo, DocNo, Mark}

или другим способом

SI {StNo, IdCode} и Marks {IdCode, SubjNo, DocNo, Mark}

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

Литература:

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

ЛЕКЦИЯ 7. Проектирование БД. Нормальные формы отношений (продолжение)

• 7.1 Многозначные зависимости
• 7.2 Четвертая нормальная форма
• 7.3 Зависимости соединения
• 7.4 Пятая нормальная форма
• 7.5 Итоговая схема процедуры нормализации

7.1 Многозначные зависимости

Пусть дано ненормализованное отношение UCTX (т.е. отношение, которое не находится в 1НФ), содержащее информацию о курсах обучения, преподавателях и учебниках. Каждый кортеж такого отношения состоит из названия курса (Course), a также групп имен преподавателей (Teachers) и названий учебников (Texts) - на рис. 7.1 показаны два таких кортежа. Под этим подразумевается, что каждый курс может преподаваться любым преподавателем соответствующей группы с использованием всех указанных учебников. Предположим, что для заданного курса может существовать любое количество соответствующих преподавателей и соответствующих учебников. Более того, допустим, хотя это и не совсем реалистичное допущение, что преподаватели и рекомендуемые учебники совершенно независимы друг от друга. Это значит, что независимо от того, кто преподает данный курс, всегда используется один и тот же набор учебников. Наконец, допустим, что определенный преподаватель или определенный учебник могут быть связан с любым количеством курсов.

UCTX
COURSE	TEACHERS	TEXTS
Физика	проф. Иванов проф. Петров	основы механики оптика
Математика	проф. Иванов	основы механики дискретная математика тригонометрия

рис. 7.1 Ненормализованное отношения UCTX

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

CTX
COURSE	TEACHER	TEXT
Физика	проф. Иванов	основы механики
Физика	проф. Иванов	оптика
Физика	проф. Петров	основы механики
Физика	проф. Петров	оптика
Математика	проф. Иванов	основы механики
Математика	проф. Иванов	дискретная математика
Математика	проф. Иванов	тригонометрия

рис. 7.2 Таблица нормализованного отношения CTX.

В простейшей формулировке нормализованное отношение CTX означает, что кортеж {Course:c, Teacher:t, Техт:x} появляется в данном отношении тогда и только тогда, когда курс c читается преподавателем t с использованием учебника x. Тогда, принимая во внимание допустимость существования для данного отношения всех возможных комбинаций преподавателей вместе с учебниками, можно утверждать, что для отношения CTX верно следующее ограничение: если присутствуют оба кортежа (c,tl,xl) и (c,t2,x2), тогда присутствуют также оба кортежа (c,tl,x2) и (c,t2,xl)

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

Можно заметить, что ситуация может быть исправлена к лучшему, если заменить отношение СТХ его проекциями {Course, Teacher} и {Course, Text}, показанными на рис. 7.3. Обе проекции являются "полностью ключевыми" и находятся в НФБК; более того, отношение СТХ может быть восстановлено с помощью обратного соединения проекций СТ и СХ и потому данная композиция выполняется без потерь. Однако только в 1971 году эти интуитивные идеи были сформулированы Фейгином (Fagin) в строгом теоретическом виде с помощью понятия многозначных зависимостей.

CT		СХ
COURSE	TEACHER		COURSE	TEXT
физика	проф. Иванов		физика	основы механики
физика	проф. Петров		физика	оптика
математика	проф. Иванов		математика	основы механики
			математика	дискретная математика
			математика	тригонометрия

рис. 7.3 Таблицы проекций СТ и СХ

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

Course-->>Teacher

Course-->>Text

Обратите внимание на двойную стрелку, которая в многозначной зависимости A-->>B означает, что "B многозначно зависит от A" или "A многозначно определяет B".

Пусть A, B и C являются произвольными подмножествами множества атрибутов отношения R. Тогда B многозначно зависит от A, что символически выражается записью

А-->>В

тогда и только тогда, когда множество значений B, соответствующее заданной паре (значение A, значение C) отношения R, зависит только от A, но не зависит от C.

Для данного отношения R{A, B, C} многозначная зависимость A-->>B выполняется тогда и только тогда, когда также выполняется многозначная зависимость A -->> C. Таким образом, многозначные зависимости всегда образуют связанные пары и потому их обычно представляют вместе в символическом виде:

А-->>В|С.

Для рассматриваемого примера такая запись будет иметь следующий вид:

Course-->>Teacher|Text

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

Теорема Фейгина (эта теорема является более строгой версией теоремы Хеза). Пусть А, В и С являются множествами атрибутов отношения R{A, В, С}. Отношение R будет равно соединению его проекций {А, В} и {А, С} тогда и только тогда, когда для отношения R выполняется многозначная зависимость А-->>В|С.

7.2 Четвертая нормальная форма

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

7.3 Зависимости соединения

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

На рисунке представлен пример конкретного набора данных, соответствующих некоторому моменту времени. Однако, если данное отношение удовлетворяет некоторому не зависящему от времени ограничению, то 3-декомпозируемость отношения TSG может быть более фундаментальным и не зависящим от времени свойством, т.е. свойством, которое удовлетворяется для всех допустимых значений данного отношения. Для того чтобы понять, каким должно быть такое отношение, прежде всего отметим, что утверждение "отношение TSG равно соединению трех проекций TS, SG и TG" эквивалентно следующему утверждению:

Если пара (t1,s1) находится в отношении TS и пара (s1,g1) находится в отношении SG и пара (t1,g1) находится в отношении TG то тройка (t1,s1,g1) находится в отношении TSG.

TSG
TEACHER	SUBJECT	GROUP
Иванов	Математика	А-98-51
Иванов	Физика	Б-00-51
Петров	Математика	А-99-51
Петров	Физика	А-98-51

TS			SG			TG
TEACHER	SUBJECT		SUBJECT	GROUP		TEACHER	GROUP
Иванов	Физика		Математика	А-99-51		Иванов	А-98-51
Иванов	Математика		Математика	А-98-51		Иванов	Б-00-51
Петров	Физика		Физика	А-98-51		Петров	А-99-51
Петров	Математика		Физика	Б-00-51		Петров	А-98-51
	Соединение по Subject
	TEACHER	SUBJECT	GROUP
	Иванов	Физика	А-98-51
	Иванов	Физика	Б-00-51
	Иванов	Математика	А-99-51
	Иванов	Математика	А-98-51
	Петров	Физика	А-98-51
	Петров	Физика	Б-00-51
	Петров	Математика	А-99-51
	Петров	Математика	А-98-51
		Соединение по комбинации Teacher и Group
			Исходное TSG

рис. 7.4 Отношение TSG является соединением трех бинарных проекций.

Исходя из этих заключений можно сказать, что пара (t1,s1) присутствует в отношении TS тогда и только тогда, когда тройка (t1, s1, g2) присутствует в отношении TSG для некоторого значения g2. Тогда приведенное выше утверждение можно переписать в виде ограничения, накладываемого на отношение SPJ:

Если (t1,s1,g2), (t2,s1,g1), (t1,s2,g1) находятся в отношении TSG то (t1,s1,g1) также находится в отношении TSG.

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

Циклическое ограничение с практической точки зрения обозначает, что, например, если:

1. Петров преподает математику;

2. математика преподается в А-98-51;

3. Петров преподает в А-98-51

то:

4. Петров преподает математику в А-98-51.

Обратите внимание, что из взятых вместе условий (1), (2) и (3) не следует (4).

Пусть R является отношением, а А, В,..., Z-- произвольными подмножествами множества атрибутов отношения R. Отношение R удовлетворяет зависимости соединения

* (A, B, ..., Z)

тогда и только тогда, когда оно равносильно соединению своих проекций с подмножествами атрибутов А, В, ..., Z.

Отсюда ясно, что отношение TSG с зависимостью соединения *(TS, SG, TG) может быть 3-декомпозируемым. Однако следует ли выполнять такую декомпозицию? По всей видимости, да, так как отношение TSG характеризуется многочисленными аномалиями обновления, которые можно устранить с помощью 3-декомпозиции. Пример был приведен при определении циклического ограничения, из-за наличия которого, в отношении TSG должен присутствовать следующий кортеж (рис. 7.5)

TEACHER	SUBJECT	GROUP
Петров	Математика	А-98-51

рис. 7.5 Дополнительный кортеж.

Также теорема Фейгина может быть сформулирована следующим образом: отношение R{A, В, С} удовлетворяет зависимости соединения *(АВ, АС) тогда и только тогда, когда оно удовлетворяет многозначной зависимости А -->> В | С.

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

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

7.4 Пятая нормальная форма

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

Отношение TSG не находится в 5НФ. Оно удовлетворяет некоторой зависимости соединения, а именно ЗД-ограничению, которое, конечно, не подразумевается его единственным потенциальным ключом. Наоборот, после 3-декомпозиции проекции TS, SG и GT находятся в 5НФ, поскольку для них вовсе нет зависимостей соединения.

7.4.1 Зависимости соединения, подразумеваемой потенциальными ключами

Рассмотрим простой пример, в котором дано отношение с данными студентов Students с потенциальным ключом StNo. Такое отношение удовлетворяет нескольким зависимостям соединения, например зависимости

* ( (StNo, GrNo, StName), (StNo, CityNo) ).

Это значит, что отношение Students равносильно соединению его проекций с атрибутами {StNo, GrNo, StName} и {StNo, CityNo}, а потому может быть подвергнуто декомпозиции без потерь на указанные проекции. (Заметьте, что его не следует, а можно подвергнуть декомпозиции.) Существование этой зависимости соединения следует (или подразумевается) из того, что StNo является потенциальным ключом (в действительности это следует из теоремы Хеза).

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

7.5 Итоговая схема процедуры нормализации

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

Из приведенных выше правил можно выделить некоторые особенности.

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

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

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

Литература:

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

ЛЕКЦИЯ 8. Проектирование БД методом сущность-связь. ER-диаграммы

• 8.1 Возникновение семантического моделирования
• 8.2 Основные понятия метода
• 8.3 Диаграммы ER-экземпляров и ER-типа
• 8.4 Правила формирования отношений
• 8.5 Методология IDEF1 (самостоятельное изучение)

8.1 Возникновение семантического моделирования

Широкое распространение реляционных СУБД и их использование в самых разнообразных приложениях показывает, что реляционная модель данных достаточна для моделирования предметных областей. Однако проектирование реляционной базы данных в терминах отношений на основе механизма нормализации часто представляет собой очень сложный и неудобный для проектировщика процесс. Потребности проектировщиков баз данных в более удобных и мощных средствах моделирования предметной области вызвали к жизни направление семантических моделей данных. В этой лекции рассматривается одна из популярных семантических моделей данных - модель "сущность-связь".

Метод сущность-связь называют также методом "ER-диаграмм": во-первых, ER -аббревиатура от слов Essence (сущность) и Relation (связь), во-вторых, метод основан на использовании диаграмм, называемых соответственно диаграммами ER-экземпляров и диаграммами ER-типа.

8.2 Основные понятия метода

Основными понятиями метода сущность-связь являются следующие:

1. сущность - представляет собой объект, информация о котором хранится в БД. Экземпляры сущности отличаются друг от друга и однозначно идентифицируются. Названиями сущностей являются, как правило, существительные, например: ПРЕПОДАВАТЕЛЬ, ДИСЦИПЛИНА, ГРУППА.

2. Атрибут сущности - представляет собой свойство сущности. Это понятие аналогично понятию атрибута в отношении. Так, атрибутами сущности ПРЕПОДАВАТЕЛЬ может быть его Фамилия, Должность, Стаж (преподавательский) и т. д.

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

4. Связь между сущностями. Связь двух или более сущностей - предполагает зависимость между атрибутами этих сущностей. Название связи обычно представляется глаголом. Примерами связей между сущностями являются следующие- ПРЕПОДАВАТЕЛЬ ВДЕТ ДИСЦИПЛИНУ (Иванов ВЕДЕТ "Организацию БД и знаний"), ПРЕПОДАВАТЕЛЬ ПРЕПОДАЕТ В ГРУППЕ (Иванов ПРЕПОДАЕТ В 256 группе);

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

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

7. Диаграммы ER-экземпляров;

8. Диаграммы ER-типа.

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

8.3 Диаграммы ER-экземпляров и ER-типа

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

1. диаграммы ER-экзрмпляров,

2. диаграммы ER-типа, или ER-диаграммы.

На рисунке рис. 8.1 приведена диаграмма ER-экземпляров для сущностей ПРЕПОДАВАТЕЛЬ и ДИСЦИПЛИНА со связью ВЕДЕТ.

рис. 8.1 Диаграмма ER-экземпляров.

Диаграмма ER-экземпляров показывает, какую конкретно дисциплину (СУБД, C++ и т.д.) ведет каждый из преподавателей. На рис. 8.2 представлена диаграмма ER-типа, соответствующая рассмотренной диаграмме ER-экземпляров.

рис. 8.2 Диаграмма ER-типа.

На начальном этапе проектирования БД выделяются атрибуты, составляющие ключи сущностей.

На основе анализа диаграмм ER-типа формируются отношения проектируемой БД. При этом учитывается степень связи сущностей и класс их принадлежности, которые, в свою очередь, определяются на основе анализа диаграмм ER-экземпляров соответствующих сущностей.

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

8.3.1 Связи типа 1:1 и необязательный класс принадлежности

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

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

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

8.3.2 Связи типа 1:1 и обязательный класс принадлежности

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

рис. 8.3 Диаграмма ER-экземпляров для связи 1:1 и обязательным КП обеих сущностей.

рис. 8.4 Диаграмма ER-типа для связи 1:1 и обязательным КП обеих сущностей.

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

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

Диаграммы ER-типа графически изображаются следующим образом:

1. обязательное участие в связи экземпляров сущности отмечается блоком с точкой внутри, смежным с блоком этой сущности (рис. 8.4).

2. необязательное участие экземпляров сущности в связи - дополнительный блок к блоку сущности не пристраивается, а точка размещается на линии связи (рис. 8.2).

3. символы на линии связи указывают на степень связи.

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

На практике степень связи и класс принадлежности сущностей при проектировании БД определяется спецификой предметной области. Рассмотрим примеры вариантов со степенью связи 1:М или М:1.

Связь типа 1:М - каждый преподаватель может вести несколько дисциплин, но каждая дисциплина ведется одним преподавателем,

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

Примеры с типом связи 1:М или М:1 могут иметь ряд вариантов, отличающихся классом принадлежности одной или обеих сущностей. Обозначим обязательный класс принадлежности символом "О", а необязательный - символом "Н", тогда варианты для связи типа 1:М условно можно представить как: О-О, О-Н, Н-О, Н-Н. Для связи типа М:1 также имеются 4 аналогичных варианта.

8.3.3 Связи типа 1:М вариант Н-О

Каждый преподаватель может вести несколько дисциплин ИЛИ ни одной, но каждая дисциплина ведется одним преподавателем (рис. 8.5, рис. 8.6).

рис. 8.5 Диаграмма ER-экземпляров для связи типа 1:М варианта Н-О

рис. 8.6. Диаграмма ER-типа для связи типа 1:М варианта Н-О

По аналогии легко составить диаграммы и для остальных вариантов.

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

8.3.4 Связи типа М:М и вариант класса принадлежности О-Н

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

рис. 8.7 Диаграмма ER-экземпляров для связи типа М:М и вариант класса принадлежности О-Н.

рис. 8.8 Диаграмма ER-типов для связи типа М : М и варианта О-Н.

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

Процесс проектирования базы данных является итерационным - допускающим возврат к предыдущим этапам для пересмотра ранее принятых решений и включает следующие этапы:

1. выделение сущностей и связей между ними;

2. построение диаграмм er-типа с учетом всех сущностей и их связей;

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

4. добавление не ключевых атрибутов в отношения;

5. приведение предварительных отношений к нормальной форме Бойса-Кодда, например, с помощью метода нормальных форм;

6. пересмотр er-диаграмм в следующих случаях;

6.1. некоторые отношения не приводятся к нормальной форме Бойса-Кодда;

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

После преобразования ER-диаграмм осуществляется повторное выполнение предыдущих этапов проектирования (возврат к этапу 1).

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

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

8.4 Правила формирования отношений

Правила формирования отношений основываются на учете следующего:

степени связи между сущностями (1:1, 1:М, М:1, М:М);

класса принадлежности экземпляров сущностей (обязательный и необязательный).

Рассмотрим формулировки шести правил формирования отношений на основе диаграмм ER-типа.

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

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

На рис. 8.9 приведены диаграмма ER-типа и отношение, сформированное по правилу 8.4.1 на ее основе.

рис. 8.9 Диаграмма и отношения для правила 8.4.1

На рис. 8.9 используются следующие обозначения:

Cl, C2 - сущности 1 и 2;

Kl, K2 - ключи первой и второй сущности соответственно;

Rl - отношение 1, сформированное на основе первой и второй сущностей;

Kl, K2,... означает, что ключом сформированного отношения может быть либо К1, либо К2.

8.4.2 Степень связи 1:1, класс принадлежности одной сущности обязательный, а второй - необязательный

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

На рис. 8.10 приведены диаграмма ER-типа и отношения, сформированные по правилу 8.4.2 на ее основе.

рис. 8.10 Диаграмма и отношения для правила 8.4.2

8.4.3 Степень связи 1:1, класс принадлежности обеих сущностей - необязательный

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

рис. 8.11 Диаграмма и отношения для правила 8.4.3

На рис. 8.11 приведены диаграмма ER-типа и отношения, сформированные по правилу 8.4.3 на ее основе.

Сформулируем аналогичные два правила для вариантов, степень связи между сущностями которых 1:М. Если две сущности С1 и С2 связаны как 1:М, сущность С1 будем называть односвязной (1-связной), а сущность С2-многосвязной (М-связной). Определяющим фактором при формировании отношений, связанных этим видом связи, является класс принадлежности М-связной сущности. Так, если класс принадлежности М-связной сущности обязательный, то в результате применения правила получим два отношения, если необязательный - три отношения. Класс принадлежности односвязной сущности не влияет на результат.

8.4.4 Степень связи между сущностями 1:М (или М:1), класс принадлежности М-связной сущности обязательный

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

На рис. 8.12 приведены диаграмма ER-типа и отношения, сформированные по правилу 8.4.4.

рис. 8.12 Диаграмма и отношения для правила 8.4.4.

8.4.5 Степень связи 1:М (М:1)и класс принадлежности М-связной сущности - необязательный

Если степень связи 1:М (М:1)и класс принадлежности М-связной сущности является необязательным, то необходимо формирование трех отношений (рис. 8.13).

рис. 8.13 Диаграмма и отношение для правила 8.4.5

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

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

8.4.6 Степень связи М:М, независимо от класса принадлежности сущностей

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

На рис. 8.14 приведены диаграмма ER-типа и отношения, сформированные по правилу 8.4.6. В конспекте показан вариант с классом принадлежности сущностей Н-Н, хотя, согласно правилу 8.4.6, он может быть произвольным.

рис. 8.14. Диаграмма и отношения для правила 8.4.6.

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

8.5 Методология IDEF1 (самостоятельное изучение)

Метод IDEF1, разработанный Т. Рэмей (T. Ramey), также основан на подходе П. Чена и позволяет построить модель данных, эквивалентную реляционной модели в третьей нормальной форме. В настоящее время на основе совершенствования методологии IDEF1 создана ее новая версия - методология IDEF1X. IDEF1X разработана с учетом таких требований, как простота изучения и возможность автоматизации. IDEF1X-диаграммы используются рядом распространенных CASE-средств (таких, как, ERwin, Design/IDEF).

Сущность в методологии IDEF1X является независимой от идентификаторов или просто независимой, если каждый экземпляр сущности может быть однозначно идентифицирован без определения его отношений с другими сущностями (рис. 8.15). Сущность называется зависимой от идентификаторов или просто зависимой, если однозначная идентификация экземпляра сущности зависит от его отношения к другой сущности (рис. 8.16).

рис. 8.15. Независимые от идентификатора сущности.

рис. 8.16. Зависимые от идентификатора сущности.

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

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

5. каждый экземпляр сущности-родителя может иметь ноль, один или более связанных с ним экземпляров сущности-потомка;

6. каждый экземпляр сущности-родителя должен иметь не менее одного связанного с ним экземпляра сущности-потомка;

7. каждый экземпляр сущности-родителя должен иметь не более одного связанного с ним экземпляра сущности-потомка;

8. каждый экземпляр сущности-родителя связан с некоторым фиксированным числом экземпляров сущности-потомка.

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

Связь изображается линией, проводимой между сущностью-родителем и сущностью-потомком с точкой на конце линии у сущности-потомка. Мощность связи обозначается как показано на рис. 8.17 (мощность по умолчанию - N).

рис. 8.17. Мощность связи.

Идентифицирующая связь между сущностью-родителем и сущностью-потомком изображается сплошной линией (рис. 8.18). Сущность-потомок в идентифицирующей связи является зависимой от идентификатора сущностью. Сущность-родитель в идентифицирующей связи может быть как независимой, так и зависимой от идентификатора сущностью (это определяется ее связями с другими сущностями).

рис. 8.18. Идентифицирующая связь.

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

рис. 8.19. Неидентифицирующая связь.

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

рис. 8.20. Атрибуты и первичные ключи.

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

рис. 8.21. Примеры внешних ключей.

Литература:

1. Базы данных: Учебник для высших учебных заведений /Под ред. проф. А.Д. Хомоненко. -Спб.: КОРОНА принт, 2000. -416с. Стр. 147-161.

2. Сергей Кузнецов, “Основы современных баз данных”. Центр Информационных Технологий, http://www.citforum.ru/database/osbd/contents.shtml

ЛЕКЦИЯ 9. Язык SQL

• 9.1 История создания и развития SQL
• 9.2 Основные понятия SQL
• 9.3 Запросы на чтение данных. Оператор SELECT
• 9.4 Многотабличные запросы на чтение (объединения).

9.1 История создания и развития SQL

Язык для взаимодействия с БД SQL появился в середине 70-х и был разработан в рамках проекта экспериментальной реляционной СУБД System R. Исходное название языка SEQUEL (Structered English Query Language) только частично отражает суть этого языка. Конечно, язык был ориентирован главным образом на удобную и понятную пользователям формулировку запросов к реляционной БД, но на самом деле уже являлся полным языком БД, содержащим помимо операторов формулирования запросов и манипулирования БД средства определения и манипулирования схемой БД; определения ограничений целостности и триггеров; представлений БД; возможности определения структур физического уровня, поддерживающих эффективное выполнение запросов; авторизации доступа к отношениям и их полям; точек сохранения транзакции и откатов. Таким образом, SQL стал достаточно мощным языком для взаимодействия с СУБД. На сегодняшний день SQL является единственным стандартным языком запросов. Язык SQL обладает следующими достоинствами:

1. независимость от конкретных СУБД. Если при создании БД не использовались нестандартные возможности языка SQL предоставляемые некоторой СУБД, то такую БД можно без изменений перенести на СУБД другого производителя. К сожалению большинство БД используют особенности СУБД, на которой работают, что затрудняет их перенос на другую СУБД без изменений;

2. реляционная основа. Реляционная модель имеет солидный теоретический фундамент. Язык SQL основан на реляционной модели и является единственным языком для реляционных БД;

3. SQL обладает высокоуровневой структурой, напоминающей английский язык.

4. SQL позволяет создавать различные представления данных для различных пользователей;

5. SQL является полноценным языком для работы с БД;

6. стандарты языка SQL. Официальный стандарт языка SQL опубликован ANSI и ISO в 1989 году и значительно расширен в 1992 году.

9.2 Основные понятия SQL

9.2.1 Операторы

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

рис. 9.1 Структура оператора SQL.

Каждый оператор SQL начинается с глагола, т.е. ключевого слова, описывающего действие, выполняемое оператором. Типичными глаголами являются SELECT (выбрать), CREATE (создать), INSERT (добавить), DELETE (удалить), COMMIT(завершить). После глагола идет одно или несколько предложений. Предложение описывает данные, с которыми работает оператор, или содержит уточняющую информацию о действии, выполняемом оператором. Каждое предложение также начинается с ключевого слова, такого как WHERE (где), FROM (откуда), INTO (куда) и HAVING (имеющий). Одни предложения в операторе являются обязательным, а другие - нет. Конкретная структура и содержимое предложения могут изменяться. Многие предложения содержат имена таблиц или столбцов; некоторые из них могут содержать дополнительные ключевые слова, константы и выражения.

В стандарте ANSI/ISO определены ключевые слова, которые применяются в качестве глаголов и в предложениях операторов. В соответствии со стандартом, эти ключевые слова нельзя использовать для именования объектов базы данных, таких как таблицы, столбцы и пользователи

9.2.2 Имена.

У каждого объекта в базе данных есть уникальное имя. Имена используются в операторах SQL и указывают, над каким объектом базы данных оператор должен выполнить действие. В стандарте ANSI/ISO определено, что имена имеются у таблиц, столбцов и пользователей. Во многих реализациях SQL поддерживаются также дополнительные именованные объекты, такие как хранимые процедуры, именованные отношения "первичный ключ - внешний ключ" и формы для ввода данных.

В соответствии со стандартом ANSI/ISO, в SQL имена должны содержать от 1 до 18 символов, начинаться с буквы и не содержать пробелы или специальные символы пунктуации. В стандарте SQL2 максимальное число символов в имени увеличено до 128.

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

Admin.Students

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

Students.StName

9.2.3 Типы данных в SQL

В стандарте ANSI/ISO определены типы данных, которые можно использовать для представления информации в реляционной базе данных. Типы данных, имеющиеся в стандарте SQL1, составляют лишь минимальный набор и поддерживаются во всех коммерческих СУБД. В табл. 9.1 перечислены типы данных, определенные в стандартах SQL1 и SQL2.

табл. 9.1 Типы данных в SQL.

Тип данных	Описание
CHAR (длина)	Строки символов постоянной длины
CHARACTER (длина)
VARCHAR(длина)	Строки символов переменной длины*
CHAR VARYING(длина)
CHARACTER VARYING (длина)
NСНАР(длина)	Строки локализованных символов постоянной длины*
NATIONAL CHAR(длина)
NATIONAL CHARACTER(длина)
NCHAR VARYING(длина)	Строки локализованных символов переменной длины*
NATIONAL CHAR VARYING(длина)
NATIONAL CHARACTER VARYING(длина)
INTEGER	Целые числа
INT
SMALLINT	Маленькие целые числа
BIT(длина)	Строки битов постоянной длины*
BIT VARYNG(длина)	Строки битов переменной длины*
NUMERIC(точность, степень)	Масштабируемые целые (десятичные) числа
DECIMAL(точность, степень)
DEC(точность, степень)
FLOAT(точность)	Числа с плавающей запятой
REAL	Числа с плавающей запятой низкой точности
DOUBLE PRECISION	Числа с плавающей запятой высокой точности
DATE	Календарная дата*
TIME(точность)	Время
TIME STAMP(точность)	Дата и время*
INTERVAL	Временной интервал*

В SQL1 используются следующие типы данных:

1. Строки символов постоянной длины. В столбцах, имеющих этот тип данных, обычно хранятся имена людей и компаний, адреса, описания и т д.

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

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

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

В большинстве коммерческих СУБД помимо типов данных, определенных в стандарте SQL1, имеется множество дополнительных типов данных, большинство из которых вошло в стандарт SQL2. Ниже перечислены наиболее важные из них:

1. Строки символов переменной длины. Почти во всех СУБД поддерживается тип данных VARCHAR, позволяющий хранить строки символов, длина которых изменяется в некотором диапазоне В стандарте SQL1 были определены строки постоянной длины, которые справа дополняются пробелами.

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

3. Дата и время. Поддержка значений даты/времени также широко распространена в различных СУБД, хотя способы ее реализации довольно сильно отличаются друг от друга. Как правило, над значениями этого типа данных можно выполнять различные операции. В стандарт SQL2 входит определение типов данных DATE, TIME, TIMESTAMP и INTERVAL, включая поддержку часовых поясов и возможность указания точности, представления времени (например, десятые или сотые доли секунды).

4. Булевы данные. Некоторые СУБД явным образом поддерживают логические значения (TRUE или FALSE).

9.2.4 Константы

В стандарте ANSI/ISO определен формат числовых и строковых констант, или литералов, которые представляют конкретные значения данных. Этот формат используется в большинстве реализации SQL.

Числовые константы. Целые и десятичные константы (известные также под названием точных числовых литералов) в операторах SQL представляются в виде обычных. десятичных чисел с необязательным знаком плюс (+) или минус (-) перед ними:

21 -3752000,00 +497500,8778

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

1.5Е3 -3.14159Е1 2.5Е-7 0.783926Е21

Символ Е читается как "умножить на десять в степени", так что первая константа представляет число "1,5 умножить на десять в степени 3", или 1500.

Строковые константы. В соответствии со стандартом ANSI/ISO, строковые константы в SQL должны быть заключены в одинарные кавычки, как показано в следующих примерах:

Jones, John J.' 'New York' 'Western'

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

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

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

В стандарт SQL2 вошли наиболее полезные символьные константы из различных реализации SQL, в частности константы CURRENT_DATE, CURRENT_TIME, CURRENT_TIMESTAMP, а также USER, SESSION_USER и SYSTEM_USER (обратите внимание на знак подчеркивания!).

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

SELECT CITY, TARGET, SALES, (SALES/TARGET) * 100

FROM OFFICES

В соответствии со стандартом ANSI/ISO, в выражениях можно использовать четыре арифметические операции: сложение (X + Y), вычитание (X - Y), умножение (X * Y) и деление (X / Y). Для формирования сложных выражений можно использовать скобки.

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