Код студента Иностранный язык

Рис. 3.20. Результат нормализации первичного отношения СТУДЕНТ

Необходимо обратить внимание на то, что если бы в исходном от­ношении был еще хотя бы один атрибут, зависимый от атрибутов Ино­странный язык и Код студента, например, атрибут Степень владения языком, то исходное отношение не удовлетворяло бы 2НФ (рис. 3.21).

Код	Ф.И.О.	Номер	Иностранный	Степень владения
студента		группы	язык	языком

Рис. 3.21. Отношение, не удовлетворяющее второй нормальной форме

 

Вторая нормальная форма (2НФ)

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

На рис. 3.22 приведено отношение СЕМЕСТР, не удовлетворяющее 2НФ по следующей причине. Ключ отношения составляют атрибуты код студента и номер семестра, так как комбинация значений именно этих атрибутов уникальна для любого кортежа отношения. Вместе с тем, если атрибуты тип стипендии в семестре и рейтинг в семестре, за­висят от полного ключа, то ф.и.о. и дата рождения являются характери­стиками студента вне зависимости от семестра, т.е. зависят только от части ключа - от атрибута код студента.

Схема отношения СЕМЕСТР Код Ф.И.О. Дата Номер Тип Рейтинг студента   рождения семестра стипендии за семестр

 

 

Кортежи отношения СЕМЕСТР   Гончар А. 29.04.78   стандартная     Гончар А. 29.04.78   стандартная     Гончар А. 29.04.78   не получает   •             Драганов М. 19.01.79   стандартная     Драганов М. 19.01.79   повышенная   •             Акулинин А. 29.04.76   стандартная     Гончар А. 20.01.79   стандартная     Гончар А. 20.01.79   стандартная   •

Рис. 3.22. Отношение, не удовлетворяющее второй нормальной форме

 

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

Приведение отношения к 2НФ (нормализация по 2НФ) заключается в разбиении исходного отношения на два, одно из которых включает атрибуты ключа исходного отношения и атрибуты, зависящие от полно­го ключа, а второе - атрибуты зависящего от части ключа вместе с ат­рибутами этой части. Результат нормализации исходного отношения приведен на рис. 3.23.

СТУДЕНТ Код Ф.И.О. Дата   студента   рождения   СЕМЕСТР     Код Номер Тип стипендии Рейтинг студента студента семестра в семестре в семестре

Рис. 3.23. Результат нормализации отношения приведенного на рис. 3.19

 

Предлагаем читателю самостоятельно нормализовать отношение, приведенное на рис. 3.21.

Третья нормальная форма (ЗНФ)

Отношение удовлетворяет третьей нормальной форме, если оно удовлетворяет 2НФ, и среди его неключевых атрибутов нет зависящих от другого неключевого атрибута (нет атрибутов, транзитивно завися­щих от ключа). На рис. 3.24 приведено отношение, не удовлетворяющее ЗНФ.

Код	Ф.И.О.	Дата	Адрес	Ф.И.О.
студента	студента	рождения	общежития	коменданта общежития
	Гончар Е.	29.04.78	Лыткина,2	Королева И.В.
	Драганов М.	19.01.79	Лыткина,4	Никитина Г.Г.
	Зюкин М.	26.03.79	Лыткина,2	Королева И.В.
	Акулинин А.	29.04.76	Лыткина,4	Никитина Г.Г.
,„

Рис. 3.24. Отношение, не удовлетворяющее третьей нормальной форме

 

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

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

СТУДЕНТ Код Ф.И.О. Дата Адрес студента студента рождения общежития

ОБЩЕЖИТЕ

 

Ф.И.О. коменданта общежития

Рис. 3.25. Результат нормализации отношения рис. 3.24.

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

Адрес общежития

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

В результате нормализации по ЗНФ (нормальная форма) имеем следующее отношение Экзаменационная ведомость (рис. 3.26).

Номер	Номер	Дисциплина	Оцен	Преподаватель
зачетки	семестра		ка
8Г6101		Матанализ		Иванов И.И.
8Г6102		Матанализ		Волков В.В.
8Г6101		Программирование		Петров П.П.
8Г6101		Матанализ		Иванов И.И.
8Г6201		БД иБЗ		Сидоров О.П.
8Г6105		БД иБЗ		Сидоров О.П.
8Г6102		Программирование		Яковлев Д.Ю.

Рис. 3.26. Отношение, удовлетворяющее ЗНФ и не нормализованное по НФБК

 

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

и какую оценку при этом студент получил. Однако необходимо отме­тить, что:

1. Один преподаватель может принимать экзамен только по одной дисциплине;

2. По одной и той же дисциплине могут принимать экзамены раз­личные преподаватели.

В результате можно заметить, что существует ФЗ Преподаватель-> Дисциплина. Если удалить какую-нибудь запись из представленного отношения, например последнюю (где студент с зач. книжкой № 8Г6102 во 2-ом семестре сдал экзамен по Программированию на 4 преподавате­лю Яковлеву Д.Ю.), то будет потеряна информация, что преподаватель Яковлев Д.Ю. принимает экзамен по дисциплине Программирование (это так называемая аномалия удаления). В этом случае есть еще один потенциальный ключ (Номер зачетки, Номер семестра, Преподаватель).

Таким образом, отношение, нормализованное по ЗНФ, может ока­заться нежелательным в структуре БД, так как ЗНФ и как предшест­вующие НФ не учитывают того обстоятельства, что в отношении и может быть несколько потенциальных ключей, которые при этом могут иметь пересечения по составу атрибутов. Этот недостаток устранен в усиленной формулировке требования ЗНФ, данной Р. Бойсом (один из разработчиков SQL) и Э. Коддом (создатель РМД), соответствующая НФ отношения называется нормальной формой Бойса-Кодда (НФБК).

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

В результате нормализации по НФБК исходное отношение деком­позируется на 2 отношения (теорема Хеза): в 1-ом отношении в состав ключа включается детерминант неучтенной выявленной ФЗ (в нашем случае Преподаватель), а зависимая часть этой ФЗ (в нашем случае Дисциплина) из ключа исходного отношения исключается и вместе с детерминантом составляет 2-ое отношение, в котором ключом и стано­вится детерминант ФЗ. Представленное выше отношение в результате нормализации по НФБК декомпозируется на следующие отношения, представленные на рис. 3.27.

Номер	Номер	Преподаватель	Оценка
зачетки	семестра
8Г6101		Иванов И.И.
8Г6102		Волков В.В.
8Г6101		Петров П.П.
8Г6101		Иванов И.И.
8Г6201		Сидоров О.П.
8Г6105		Сидоров О.П.
8Г6102		Яковлев Д.Ю.

 

 

Преподаватель	Дисциплина
Иванов И.И.	Матанализ
Волков В.В.	Матанализ
Петров П.П.	Программирование
Сидоров О.П.	БДиБЗ
Яковлев Д.Ю.	Программирование

Рис. 3.27. Отношение, нормализованное по НФБК

 

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

Четвертая нормальная форма (4НФ)

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

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

Код абитуриента	Факультет	Предмет
	АВТФ	Математика
	АВТФ	Физика
	ИЭФ	Математика
	ИЭФ	Обществознание
	АВТФ	Математика
	АВТФ	Физика
	ИГНД	Математика
	ИГНД	Русский язык

Рис. 3.28. Отношение, удовлетворяющее по НФБК и не нормализованное по 4НФ

 

Все атрибуты этого отношения взаимно независимы и в совокупно­сти составляют единственный первичный ключ. Отношение находится в НФБК.

Однако, при использовании такой структуры может возникнуть 2 нежелательные ситуации. Во-первых, при попытке добавить в это от­ношение новую запись, например (1004, ИЭФ, Математика), мы обяза­ны добавить также и записи (1004, ИЭФ, Обществознание), так как все абитуриенты ИЭФ обязаны иметь один и тот же список сдаваемых предметов. Во-вторых, при попытке удалить запись (1004, ИЭФ, Мате­матика), мы обязаны удалить также и кортеж (1004, ИЭФ, Обществоз­нание) по той же самой причине. Кроме того, если мы удалим кортеж (1003, ИГНД, Математика), а вместе с ним и кортеж (1003, ИГНД, Рус­ский язык), то будет потеряна информация о предметах, которые долж­ны сдаваться на ИГНД. Таким образом, вставка и удаление кортежей не может быть выполнена независимо от других кортежей отношения.

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

Для каждого факультета (для каждого значения из X) каждый по­ступающий на него абитуриент (значение из Y) сдает один и тот же спи­сок предметов (набор значений из Z), и для каждого факультета (для каждого значения из X) каждый сдаваемый на факультете экзамен (зна­чение из Z) сдается одним и тем же списком абитуриентов (набор зна­чений из Y). В отношении "Абитуриент-Факультет-Предмет" имеется многозначная зависимость Факультет->->Абитуриент|Предмет (Х—>—> Y\Z). Эта многозначная зависимость является нетривиальной, так как не существует ФЗ Х—> Y и X->Z. Именно наличие этой зависимости не по­зволяет независимо вставлять и удалять кортежи, кортежи обязаны вставляться и удаляться одновременно целыми наборами.

Для разрешения этой аномалии, избавления многозначной зависи­мости, исходное отношение необходимо декомпозировать следующим образом (теорема Фейджина): если имеется набор непересекающихся атрибутов (X,Y,Z) отношения R и существует многозначная зависимость X->->Y\Z, то декомпозиция отношения R выполняется на проекции R} =R[X, Y] и R₂=R[X,ZJ.

Определение 4НФ: Отношение находится в 4НФ тогда и только тогда, когда отношение находится в НФБК и не содержит нетривиаль­ных многозначных зависимостей.

Приведенное отношение "Абитуриент-Факультет-Предмет" нахо­дится в НФБК, но не в 4 НФ. Для того чтобы отношение было нормали­зовано по 4НФ, необходимо убрать из него многозначную зависимость, для чего декомпозируем исходное отношение на следующие отноше­ния, представленные на рис. 3.29.

В полученных отношениях устранены аномалии вставки и удале­ния, характерные для отношения "Абитуриенты-Факультеты- Предметы". Заметим, что полученные отношения остались полностью ключевыми, и в них по-прежнему нет ФЗ.

Факультет	Код абитуриента
АВТФ
ИЭФ
АВТФ
ИГНД
j
Факультет	Предмет
АВТФ	Математика
АВТФ	Физика
ИЭФ	Математика
ИЭФ	Обществознание
ИГНД	Математика
ИГНД	Русский язык

Рис. 3.29. Отношение, нормализованное по 4НФ

 

Отношения с нетривиальными многозначными зависимостями воз­никают, как правило, в результате естественного соединения двух от­ношений по общему атрибуту. Фактически это приводит к попытке хра­нить в одном отношении информацию о двух независимых, разных сущностях. В качестве еще одного примера можно привести ситуацию, когда в одном отношении храниться информация о том, что студент изучает несколько дисциплин и посещает несколько спортивных сек­ций, что приводит к возникновению нетривиальной многозначной зави­симости Студент->->Дисциплина|СпортСекции.

Пятая нормальная форма (5НФ)

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

Рассмотрим следующий пример (рис. 3.30).

Преподаватель	Дисциплина	Группа
Иванов И.И.	Программирование
Петров П.П.	Матанализ
Петров П.П.	Матанализ
Сидоров О.П.	ИС
Сидоров О.П.	БД	8МЯ61
Яковлев Д.Ю.	Матанализ	8МЯ61

Рис. 3.30. Отношение, не нормализованное по 5НФ

 

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

Представленное отношение находится в 4НФ. Однако при уволь­нении преподавателя необходимо удалить все записи, в которых указа­но, по каким дисциплинам и у каких групп он читал лекции.

Если отношение «Х-Y-Z» спроецировать на составные парные ат­рибуты {Х-Y}, {Y-Z}, {X-Z}, то соединение этих проекций дает исходное отношение. Это означает, что в рассматриваемом отношении существо­вала зависимость соединения. В результате отношение будет нахо­диться в 5НФ.

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

Применим нормализацию по 5НФ для рассматриваемого примера. Разбиваем отношение «Преподаватель-Дисциплина-Группа» на 3 про­екции {Преподаватель-Дисциплина} (ПД), {Дисциплина-Группа} (ДГ), {Преподаватель-Группа} (ПГ) (рис. 3.31):

ПД_____________________________

Преподаватель	Дисциплина
Иванов И.И.	Программирование
Петров П.П.	Матанализ
Сидоров О.П.	ИС
Сидоров О.П.	БД
Яковлев Д.Ю.	Матанализ

 

ДГ

Дисциплина	Группа
Программирование
Матанализ
Матанализ
ИС
БД	8МЯ61
Матанализ	8МЯ61

 

 

ПГ Преподаватель Группа Иванов И.И.   Петров П.П.   Петров П.П.   Сидоров О.П.   Сидоров О.П. 8МЯ61 Яковлев Д.Ю. 8МЯ61

 

Рис. 3.31. Проекции исходного отношения для нормализации по 5НФ

Получим попарные соединения полученных 3 приведенных выше проекций, которые будут иметь вид (рис. 3.32):

пд-пг
Преподаватель	Дисциплина	Группа
Иванов И.И.	Программирование
Петров П.П.	Матанализ
Петров П.П.	Матанализ
Сидоров О.П.	ИС
Сидоров О.П.	ис	8МЯ61
Сидоров О.П.	БД	8МЯ61
Сидоров О.П.	БД
Яковлев Д.Ю.	Матанализ	8МЯ61
пд-дг
Преподаватель	Дисциплина	Группа
Иванов И.И.	Программирование
Петров П.П.	Матанализ
Петров П.П.	Матанализ
Петров П.П.	Матанализ	8МЯ61
Сидоров О.П.	ИС
Сидоров О.П.	БД	8МЯ61
Яковлев Д.Ю.	Матанализ
Яковлев Д.Ю.	Матанализ
Яковлев Д.Ю.	Матанализ	8МЯ61
ДГ-ПГ
Преподаватель	Дисциплина	Группа
Иванов И.И.	Программирование
Петров П.П.	Программирование
Иванов И.И.	Матанализ
Петров П.П.	Матанализ
Петров П.П.	Матанализ
Сидоров О.П.	Матанализ
Петров П.П.	ИС
Сидоров О.П.	ИС
Сидоров О.П.	БД	8МЯ61
Яковлев Д.Ю.	БД	8МЯ61
Сидоров О.П.	Матанализ	8МЯ61
Яковлев Д.Ю.	Матанализ	8МЯ61

 

Рис. 3.32. Отношения, полученные в результате соединения проекций исходного от­ношения

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

5НФ является последней из известных НФ. Условия ее получения довольны нетривиальны и поэтому она почти не используется на прак­тике. Кроме того, она имеет определенные недостатки: в полученных отношениях на основе проекций исходного отношения содержатся кор­тежи с ложной информацией (которой нет в исходном отношении), так как были эти отношения были получены в результате соединения про­екций. Поэтому для правильной интерпретации необходимо рассматри­вать совместно все проекции основного отношения. На практике проек­тирования БД ограничиваются нормализацией по ЗНФ или НФБК.

3.5.5. Операции реляционной алгебры

Общие положения

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

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

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

Восемь основных операций над отношениями реализуются в реля­ционной модели данных:

• пять традиционных операций над множествами - объединение, пересечение, разность, декартово произведение, деление;

• три специальные реляционные операции - проекции, выбора (селекции) и соединения.

Учитывая, что операции объединения, пересечения и разности

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

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

Объединением двух совместимых по объединению отношений R1 и R2 является отношение R3, содержащее множество всех кор­тежей, принадлежащих или R1, или R2, или обоим вместе.

Другой вариант завершения этого определения «..., принадлежа­щих R1 и тех кортежей R2, которые не принадлежат R/».

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

Естественно, что R3 также совместимо по объединению с R1 и R2.

Ниже приведем пример (рис. 3.33).

ПРЕПОДАВАТЕЛЬ

Личный номер преподавателя	Ф.И.О. преподавателя	Дата ро­ждения	Пол	Адрес
НАУЧНЫЙ РАБОТНИК
Личный номер работника	Ф.И.О. научного работника	Дата ро­ждения	Пол	Адрес
СОТРУДНИК
Личный номер сотрудника	Ф.И.О. сотрудника	Дата рождения	Пол	Адрес

Рис. 3.33. Отношения, совместимые по объединению

 

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

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

Пересечением двух совместимых по объединению отношений R1 и R2 является отношение R3, содержащее кортежи, принадле­жащие как R1, так и R2.

Рассмотрим пример (рис. 3.34). Пусть имеем отношения СТУДЕНТ, содержащее сведения о всех студентах института, и ЖИЛЕЦ, содержащее сведения о всех проживающих в общежитии.

СТУДЕНТ Ф.И.О. студента Серия и номер паспорта Пол Дата рождения Семейное положение ЖИЛЕЦ Ф.И.О. жильца Серия и номер паспорта Пол Дата рождения Семейное положение

Рис. 3.34. Отношения для пересечения

 

В результате выполнения операции пересечения получаем отноше­ние СТУДЕНТО, содержащее сведения о студентах, проживающих в общежитии (рис. 3.35).

СТУДЕНТО Ф.И.О. Серия и номер Пол Дата Семейное студента паспорта   рождения положение

Рис. 3.35. Отношение, полученное в результате пересечения исходных отношений

 

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

На примере, приведенном ранее на рис. 3.34, в результате вычита­ния отношения СТУДЕНТ из отношения ЖИЛЕЦ получаем отноше­ние НЕСТУДЕНТ, содержащее сведения о всех проживающих в обще­житии, но не являющихся студентами (рис. 3.36).

А в результате вычитания отношения ЖИЛЕЦ из отношения СТУДЕНТ, получаем отношение СТУДЕНТН, содержащее сведения о студентах, не проживающих в общежитии.

НЕСТУДЕНТ Ф.И.О. Серия и номер Пол Дата Семейное студента паспорта   рождения положение

 

Рис. 3.36. Отношение, полученное в результате разности исходных отношений

Здесь также с помощью одной операции выполняются важные для управленцев информационные запросы.

Декартовым произведением отношения А со схемой (Ai, А2,..., А_п) и отношения В со схемой {В\, В2,...,В_т) является отношение С, со схемой (А\, А2,...,А_п, В\,В2,--.,В_т равной объеди­нению схем отношений Л и В, кортежи которого получены путем конкатенации (присоединения) каждого кортежа отношения В с каждым кортежем отношения А.

ПРИМЕР. Пусть имеем отношение АВТ, содержащее список участников команды факультета Автоматики и вычислительной тех­ники по шахматам и отношение РАЦ, содержащее аналогичный список команды Российско-американского центра. Тогда декартовым произведением АВТ х РАЦ будет отношение ВСТРЕЧИ, содержащее список пар участников, которые должны играть друг с другом (рис.3.37).

АВТ РАЦ

Ф.И.О.	Разряд	Дата ро­		Ф.И.О.	Разряд	Дата ро­
игрока		ждения		игрока		ждения
АВТ				РАЦ

ВСТРЕЧИ

 

 

Ф.И.О.	Разряд	Дата рожде­	Ф.И.О.	Разряд	Дата рож­
игрока	игрока	ния	игрока	игрока	дения
АВТ	АВТ	игрока АВТ	РАЦ	РАЦ	игрока РАЦ

Рис. 3.37. Пример декартово произведения

 

Операция деления одного отношения (делимого) на другое от­ношение (делитель) может быть выполнена, если все множество атрибутов делителя является подмножеством атрибутов делимо­го.

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

В него включаются только те кортежи, декартово произведе­ние которых с делителем содержится в делимом (является под­множеством делимого).

Ф.И.О.	Иностр. язык	Степень владения языком
ДЕЛИМОЕ
Ф.И.О.	Иностр. язык	Степень владения языком
Иванов	английский	свободно
Сидоров	английский	свободно
Сидоров	японский	разговорный
Сидоров	турецкий	со словарем
Кузнецова	английский	со словарем
Кузнецова	турецкий	свободно
Иванова	немецкий	разговорный
Иванова	турецкий	свободно
Иванова	английский	со словарем

ДЕЛИМОЕ

ЧАСТНОЕ (результат) Ф.И.О. Кузнецова Иванова

Рис. 3.38. Пример деления отношения

 

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

Второй вариант определения «... нового отношения, множество атрибутов которого является подмножеством атрибутов исходно­го отношения».

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

ДЕЛИТЕЛЬ Иностр. язык Степень владения языком ДЕЛИТЕЛЬ Иностр. язык Степень владения языком английский со словарем турецкий свободно

На примере отношения СТУДЕНТ выполняем операцию проекции по атрибуту номер группы, получаем отношение группа, представ­
ляющую собой список всех групп, в которых учатся студенты (рис.3.39).

СТУДЕНТ Код Ф.И.О. Номер Дата студента студента группы Рождения

 

ГРУППА

_____ Номер группы

Рис 3.39. Пример проекции отношения

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

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

Ограничения могут быть заданы в виде логического выражения, элементами которого являются простейшие условия типа «Имя атри­бута - знак сравнения - значение атрибута» (в общем случаев «Вы­ражение - знак сравнения - выражение»), которые могут соединяться булевыми операторами И (AND), ИЛИ (OR), иметь знак отрицания (NOT), а также использовать круглые скобки для изменения старшин­ства выполнения булевых операций по правилам математической логи­ки.

Знаки сравнения >, <, =, >=, <=.

Например, для отношения СТУДЕНТ (рис. 3.40) требуется ото­брать кортежи, относящиеся к первому году учебы, причем для студен­тов, не получающих стипендию, но имеющих достаточно высокий рей­тинг - от 800 до 900 баллов.

Условие отбора (номерсеместра = 1 ИЛИ номерсеместра = 2) И тип стипендии в семестре = не получает И (рейтинг за семестр > 800 И р ейтинг за семестр < 900).

СТУДЕНТ Код Ф.И.О. Номер Тип стипендии Рейтинг

 

студента

студента

семестра

в семестре

за семестр

Рис. 3.40. Отношение для селекции

 

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

Соединением отношения А по атрибуту X с отношением В по атрибуту Y называется множество всех кортежей, являющихся конкатенацией таких кортежей а е А и кортежей b е В, для кото­рых выполняется условие X * Y (под * понимается одна из операций сравнения =, <, >, >=, <=). X и Y должны быть определены на одном и том же домене.

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

Например, если для расчета суммарного рейтинга студентов (рей­тинг группы равен сумме рейтингов студентов за семестры) необходима информация из двух отношений:

СТУДЕНТ Код Ф.И.О. Номер Дата студента   группы рождения

 

 

СЕМЕСТР Код Номер Тип Рейтинг студента семестра стипендии за семестр

 

 

в результате операции соединения получим отношение (рис. 3.41). Код Ф.И.О. Номер Дата Код Номер Тип Рейтинг студ- студ-та группы рожде студ семе­ сти­ за се­ та     ния та стра пен­дии местр

Рис. 3.41. Пример соединения отношений

 

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

Чаще всего операция соединения используется вместе с операциями проекции и селекции (или предшествует им). В приведенном примере не имеет смысла иметь два атрибута Код студента.

Тот факт, что при соединении часто нарушается требование нор­мальности по 2НФ, не существенен, так как соединение реализуется временно, на период обработки связываемых отношений. (Денормали- зация)

3.5.6. Языки обработки реляционных БД

В качестве языка обработки реляционных БД рассмотрим язык структурированных запросов SQL.

История SQL

В начале 1970-х годов после появления в июне 1970 г. работы Э.Кодда «Реляционная модель данных для больших совместно исполь­зуемых банков данных» корпорация IBM была разработана эксперимен­тальная реляционная СУБД IBM System R, для которой был создан спе­циальный язык SEQUEL, позволявший относительно просто управлять данными в этой СУБД [5]. Целью разработки было создание простого непроцедурного языка, которым мог воспользоваться любой пользова­тель, даже не имеющий навыков программирования. Собственно разра­боткой языка запросов занимались Дональд Чэмбэрлин (Donald D. Chamberlin) и Рэй Бойс (Ray Воусе). Пэт Селинджер (Pat Selinger) зани­малась разработкой стоимостного оптимизатора (cost-based optimizer), Рэймонд Лори (Raymond Lorie) занимался компилятором запросов.

Первоначальное название языка было SEQUEL - акроним «Structured English Query Language» - «английский язык структуриро­ванных запросов» и произносится как «сиквэл». Позже по юридическим соображениям^[1] язык SEQUEL был переименован в SQL - аббревиатура «Structured Query Language» - «язык структурированных запросов», и официальное произношение названия стало побуквенным «эс-кью-эль» (однако многие англоговорящие разработчики БД до сих пор использу­ют первое произношение названия языка) [6]. В 1979 г. корпорация Relational Software (впоследствии ставшей Oracle) представила коммер­ческую реализацию SQL для СУБД Oracle V2 для машин VAX. Корпо­рация Oracle отобрала у IBM права на SQL и сейчас является собствен­ником всех выпускаемых на рынок SQL продуктов.

Стандарты SQL

После появления этого языка стал появляться ряд конкурирующих программ SQL на рынке, необходимо было иметь какой-то стандарт языка, к которому они должны быть приведены и следовать. В 1986 г. первый официальный стандарт языка SQL-86 был принят ANSI (American National Standards Institute - Американский национальный институт стандартов), который был одобрен ISO (International Organization for Standardization - Международной организацией по стандартизации) в 1987 г. и несколько уточнён в 1989 г. Дальнейшее развитие языка поставщиками СУБД потребовало принятия в 1992 г. нового расширенного стандарта SQL-92 (SQL2), был определен базовый уровень (Entry level) соответствия реализации этому стандарту. Сле­дующим стандартом стал SQL: 1999 (SQL3), в котором добавлена под­держка регулярных выражений, рекурсивных запросов, поддержка триггеров, базовые процедурные расширения, нескалярные типы дан­ных и некоторые объектно-ориентированные возможности. В настоящее время действует принятый в 2003 г. стандарт SQL:2003, в котором вве­дены расширения для работы с XML-данными, оконные функции (при­меняемые для работы с OLAP-БД), генераторы последовательностей и основанные на них типы данных. Позднее были внесены некоторые мо­дификации в этот стандарт: функциональность работы с XML-данными значительно расширена, появилась возможность совместно использо­вать в запросах SQL и XQuery - в результате появился стандарт SQL:2006. В стандарте SQL:2008 улучшены возможности оконных функций, устранены некоторые неоднозначности стандарта SQL:2003[7].

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