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

Рис. 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.

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

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

Застрахованные личности
ИНН Место Номер мед. Поликлиника ИНН
личности работы полиса прикрепления страховой
        компании
Код студента Номер семестра Дисциплина - student2.ru Медицинские работники

ИНН Место Стаж Пол Дата рож­
личности работы работы   дения
Рис 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(AbA2,...,An) или R(DbD2,...,Dn).

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

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

Тогда отношение R со схемой R (D\, D2, ...,Dn) есть подмножество 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

Наши рекомендации