Код студента Номер семестра Дисциплина

Рис. 3.7. Простая сетевая структура (варианты 3.6 б и г)

Пример на рис. 3.7 хотя и является лишь фрагментом в модели ор­ганизации учебного процесса в вузе, тем не менее, иллюстрирует наи­более важные особенности сетевой структуры: более одного старшего и циклы. Пример составлен на основе примера на рис. 3.5, поэтому в уже известных элементах опущены имена не ключевых данных. Элемент ИТОГОВАЯ АТТЕСТАЦИЯ отличается от элемента АТТЕСТАЦИЯ только в том случае, если дисциплина читается несколько семестров, а элемент ДИСЦИПЛИНА содержит характеристики дисциплины, еди­ные для всех студентов, ее изучающих.

К сетевым следует отнести также связи многие к многим (М:М) и связь один к одному (1:1)

Связь М:М - это когда каждому элементу одной структуры можно поставить в соответствие несколько элементов другой, но и наоборот каждому элементу второй структуры можно поставить в соответствии несколько экземпляров первой (рис 3.8 и 3.9).

ДИСЦЕ	[ПЛИНА
Код	Дисциплина	Рейтинг студента
студента		по дисциплине

I СЕМЕСТР

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

Рис 3.8 Связь типа М:М (вариант 1)

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

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

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

t

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

Код	Кафедра	Должность	Стаж рабо­
преподавателя			ты

Рис 3.9 Связь типа М:М (вариант2)

Связь 1:1 - это когда каждому элементу одной структуры можно поставить в соответствие только один (или ни одного) экземпляр дру­гой, но и наоборот каждому элементу второй структуры можно поста­вить в соответствии только один экземпляров первой (рис 3.10).

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

СТУДЕНТ2 Код Место рож­ Дата рож­ Пол студента дения дения студента

Рис 3.10 Пример связи типа 1:1

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

Пример, иллюстрирующий возможность нескольких связей между парой линейных структур (вариант 3.6 а), а также типы связей 1:1 и М:М, представлен на рис. 3.11.

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

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

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

Застрахованные личности ИНН Место Номер мед. Поликлиника ИНН личности работы полиса прикрепления страховой         компании

Медицинские работники

ИНН	Место	Стаж	Пол	Дата рож­
личности	работы	работы		дения

Рис 3.11. Несколько связей между парой линейных структур (связи 1:1, М:М) - ва­риант 3.6 а)

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

Работники ( ^

ИНН	Место	Стаж	Пол	Дата ро­
личности	работы	работы		ждения

Рис 3.12. Связь типа петля вариант 3.6. д)

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

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

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

Следует заметить, что в полном объеме сетевая структура не под­держивается ни одной реально действующей СУБД. Она была опреде­лена группой CODASYL [3] как универсальная структура, позволяющая реализовать информационную модель практически любой ПрО. Это на­правление отражало интересы проектировщиков БД и прикладных про­граммистов, с которых во многом снимались проблемы отслеживания связей между записями различных файлов. Однако в 80-ые гг. в связи с широким распространением ПК преобладающее развитие получило второе направление, которое использует реляционную модель данных, описание которой представлено ниже.

Контрольные вопросы и задания к разделам 3.1, 3.2, 3.3, 3.4

1) Что такое структура данных?

2) Что такое логическая и физическая структуры данных?

3) Назовите основные требования, которым должна удовлетворять:

- линейная структура данных;

- иерархическая структура данных;

- сетевая структура данных.

4) Назовите и поясните существо типовых связей между парой ли­нейных структур.

3.5. Реляционная модель данных

3.5.1. История применения реляционной модели данных

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

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

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

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

3.5.2. Основные понятия реляционной модели данных

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

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

Формализованное определение основных понятий реляционной модели данных базируется на теории множеств.

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

Пусть дана совокупность множеств каждое из кото­

рых () представляет собой множество возможных значений /-го атри­бута (^) отношения R. Множества D могут пересекаться и даже совпа­дать, т.е. различные атрибуты могут быть определены на пересекаю­щихся или даже на одном и том же домене. Например, атрибуты дата приема на работу и дата увольнения.

Схемой отношения R называется конечное множество имен атри­бутов {4>^A2>->^An}_f причем каждому атрибуту ставится в соответст- А- —> D-

вие домен ^{1 1}' Схема отношения R записывается в виде R(A_bA₂,...,A_n) или R(D_bD₂,...,D_n).

Пусть множество D есть декартово произведение доменов схемы

D={L\*D*,...*D_n}.

Тогда отношение R со схемой R (D\, D₂, ...,D_n) есть подмножество Z),

По существу, отношение соответствует рассмотренной нами ли­нейной структуре с соблюдением всех присущих ей требований (один и тот же порядок следования атрибутов, один и тот же размер и тип зна­чений одного атрибута во всех кортежах отношений). Дополнительные, присущие реляционной модели требования - обязательное наличие в отношении ключа и удовлетворение нормальным формам. Так, приве­денные на рис. 3.1 и 3.2 линейные структуры СТУДЕНТ и СЕМЕСТР в реляционной модели данных будут отношениями, а данные - № за­четной книжки, Ф.И.О., Пол, Цата рождения и Номер семестра, Оценка, Рейтинг по дисциплине - атрибутами отношений с ключами, отмеченными жирным шрифтом на рис. 3.13.

Схема отношения СТУДЕНТ № зачетной Ф.И.О. Номер группы Пол Дата книжки       рождения

Схема отношения СЕМЕСТР № зачетной Номер Тип Рейтинг книжки семестра стипендии за семестр

Рис. 3.13. Схемы простых отношений

В реляционной модели обязательно устанавливается и имеет опре­деляющее значение понятие функциональной зависимости одного ат­рибута X от другого Y в отношении R, означающее, что если известно значение первого атрибута (<детерминанта) X, то значение второго ат­рибута {зависимой части) Y определено и имеет единственное значение. Формальное определение функциональной зависимости: X—>Y. Напри­мер, если в отношении Студент известен № зачетной книжк, то для любого кортежа отношения Студент однозначно определены значения его атрибутов ФИО, Номер группы, Пол, Цата рождения, т.е. № зачет­ной книжки ->{ФИО, Номер группы, Пол, Цата рождения), аналогич­но для отношения Семестр:

№ зачетной книжки, Номер семестра ->{Тип стипендии, Рейтинг за семестр}

3.5.3. Ключ отношения

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

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

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

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

Рассмотрим понятие ключа более пристально для отношений, при­веденных ранее на рис. 3.13.

Драганов М. получает дополнительное образование и имеет, в свя­зи с этим, две зачетной книжки. Есть два различных студента с одина­ковой фамилией Гончар А. (например, Анна и Алексей), поэтому Ф.И.О. не является ключом. Ключом является атрибут № зачетной книжки, так как для конкретного значения этого атрибута значения ос­тальных атрибутов имеют единственное значение (рис. 3.14).

Схема отношения СТУДЕНТ № зач. книжки Ф.И.О. Номер группы Пол Дата рождения Кортежи отношения СТУДЕНТ Гончар А. Ж 29.04.78 Драганов М. М 19.01.79 Зюкин М. м 26.03.79 •         Акулинин А. м 29.04.76 Драганов М. м 19.01.79

Рис.3.14. Ключ состоит из одного атрибута

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

Рассмотрим вариант, когда вместо № зачетной книжки возьмем атрибут ИНН студента (личности) (рис. 3.15). Тогда для одного значе­ния ИНН студента может быть два различных кортежа для студентов обучающихся параллельно на нескольких специальностях (студент Дра- ганов М.).

ИНН студента	Ф.И.О.	Номер группы	Пол	Дата рождения
	Гончар Е.		Ж	29.04.78
	Драганов М.		М	19.01.79
	Зюкин М.		м	26.03.79
••
	Акулинин А.		м	29.04.76
	Драганов М.		м	19.01.79

Рис 3.15. Изменение ключевого атрибута

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

Другой, более простой пример отношения, ключ которого состоит из двух атрибутов № зачетной книжки и Номер семестра, приведен на рис. 3.16.

Схема отношения СЕМЕСТР № зачетной Номер Тип Рейтинг книжки семестра стипендии за семестр

Кортежи отношения СЕМЕСТР стандартная стандартная не получает •       стандартная повышенная •       стандартная стандартная стандартная •

Рис. 3.16. Отношение, ключ которого состоит из двух атрибутов

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

3.5.4. Нормализация отношений

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

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

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

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

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

Первая нормальная форма (1НФ)

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

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

СТУДЕНТ Код   Место рождения Иностран­ студента ФИО Республика Область Город (село) ный язык

Рис. 3.17. Отношение не удовлетворяющее 1НФ по наличию составного атрибута

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

Более значительная специфика связана с атрибутом с множествен­ными значениями.

Соблюдая требования одного размера атрибута во всех кортежах, мы должны бы были представить исходное отношение либо в виде рис. 3.18, либо в виде рис. 3.19.

Код	Ф.И.О.	№ груп­	Иностранный язык
студента		пы
	Гончар А.		немецкий, английский
	Драганов М		немецкий, шведский, польский
	Зюкин М.		латынь
• • •
	Акулин А.		не владеет

Рис. 3.18. Размещение множества значений в одном атрибуте

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

Код	Ф.И.О.	Номер	Иностранный
студента		группы	язык
	Гончар А.		немецкий
	Гончар А.		английский
	Драганов М.		немецкий
	Драганов М.		шведский
	Драганов М.		польский
	Зюкин М.		латынь
• • •
	Акулинин А.		не владеет

Рис. 3.19. Организация хранения атрибутов с множественными значениями в виде типичной для реляционной модели однородной структуры

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

Реляционная модель требует нормализации (приведения к 1НФ) путем разбиения исходного отношения на два следующим образом: из исходного отношения СТУДЕНТ исключается атрибут с множествен­ным значением и получается новое отношение СТУДЕНТ 1, а исклю­ченный атрибут вместе с ключом исходного отношения образуют новое отношение СТУДЕНТ2 (рис. 3.20), причем оба атрибута являются клю­чевыми.

СТУДЕНТ1

Код студента Ф.И.О. Дата рождения

СТУДЕНТ2