1 сентября [Лекции]

Связь реляционной модели и модели «сущность-связь». Преобразование ER-модели в реляционную модель

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

 

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

 

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

 

Сформулируем основные принципы (правила) преобразования модели «сущность-связь» в реляционную:

 

1. Каждой сущности ER-модели ставится в соответствие отношение реляционной модели данных (случай категоризации сущностей рассматривается ниже отдельно). При этом необходимо понимать, что имена сущностей и отношений могут быть различны, так как в инфологической модели на имена сущностей не накладываются никакие ограничения, за исключением их уникальности в рамках модели. Одновременно с этим в реляционной модели имена отношений могут быть ограничены требованиями конкретной СУБД. Чаще всего имена отношений являются идентификаторами в некотором специальном базовом языке, ограничены по длине и не могут содержать пробелов и других специальных символов. Например, сущность может называться «Студенты университета», а соответствующее отношение – STUDENTS.

 

2. Каждому атрибуту сущности ставится в соответствие атрибут соответствующего отношения. Переименование атрибутов производится в соответствии с теми же правилами, что и переименование сущностей. Затем каждому атрибуту отношения задается конкретный (допустимый в используемой СУБД) тип данных и обязательность или необязательность данного атрибута (необязательность атрибута означает, что он может принимать специальное значение NULL – пусто).

 

3. Первичный ключ сущности становится первичным ключом (PRIMARY KEY) соответствующего отношения. Все атрибуты, которые входят в первичный ключ сущности, автоматически получают свойство обязательности (NOT NULL – не пусто).

 

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

 

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

 

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

 

7. Разрешение связей «многие-ко-многим». Как уже упоминалось, в реляционной модели поддерживается только один тип связи по множественности – связи «один-ко-многим». Вместе с тем, ER-модель поддерживает и связи «многие-ко-многим» (случай «один-к-одному» не рассматривается, так как он является частным случае связи «один-ко-многим»). Поэтому требуется специальный механизм преобразование связей «многие-ко-многим» при переходе к реляционной модели. В этом случае вводится дополнительное отношение, атрибутами которого являются первичные ключи двух связанных отношений. Данные ключи являются в новом отношении внешними (FOREIGN KEY), образуя вместе уже первичный ключ нового отношения (PRIMARY KEY). Само новое отношение связано с каждым из исходных отношений связью «один-ко-многим».

1 сентября [Лекции]

Нормализация данных и нормальные формы реляционных баз данных

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

 

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

 

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

 

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

 

 

Выделяют три основные нормальные формы.

 

Первая нормальная форма (1НФ) – таблица соответствует первой нормальной форме, если в ней отсутствуют повторяющиеся группы. Повторяющаяся группа – это столбец, в строках (полях) которого может храниться одновременно несколько значений. Такому столбцу соответствует многозначный атрибут модели «сущность-связь». Примером такого атрибута может быть «Номер телефона» в случае, если у человека их несколько (в одном из полей тогда может храниться значение «125-34-56, 8-906-543-24-09»). В этом случае правильным решением будет создание новой таблицы (сущности) для хранения экземпляров значений из повторяющейся группы.

 

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

 

Кафедры

Код института Код кафедры Название Адрес Телефон

 

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

 

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

 

Кафедры

Код кафедры Название Здание Адрес Телефон

 

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

 

Данные нормальные формы не исчерпывают все существующие нормальные формы. Отметим еще несколько важных случаев.

 

Нормальная форма Бойса-Кодда (НФБК) – устраняет некоторые недостатки третьей нормальной формы, принимая во внимание потенциальные ключи, то есть атрибуты или наборы атрибутов, которые могли бы выступать в роли первичного ключа.

 

Четвертая нормальная форма (4НФ) – выявляет многозначные зависимости. Многозначная зависимость – это соответствие одному значению некоторого атрибута A нескольких значений атрибута B и нескольких значений атрибута C, не связанных между собой.

 

Пятая нормальная форма (5НФ) – рассматривает еще более сложные случаи многозначных зависимостей.

 

Доменно-ключевая нормальная форма (ДКНФ) – определяет необходимое и достаточное условие отсутствия ошибок (аномалий). Алгоритм для преобразования таблиц к этой форме в настоящее время неизвестен.

1 сентября [Лекции]

Основные понятия: таблица (отношение), кортеж, домен, первичный ключ. Часть 2.

Действительно, оба отношения R и R1 описывают одну и ту же реальную ситуацию, пусть и по-разному.

 

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

 

Вхождение домена в отношение принято называть атрибутом. При этом атрибуты, принимающие значения из одного домена, называются O-сравнимыми, где O – набор операций сравнения (например, для чисел это <, >, =, <=, >=, <>).

 

Строки отношения называются кортежами. А количество атрибутов в отношении называется его степенью или рангом.

 

Эти понятия позволяют определить схему отношения, описывающую структуру отношения в целом. Схемой отношения R называется перечень атрибутов данного отношения с указанием доменов, к которым они относятся: S_R = ( A1, A2, …, AN ), Ai <= Di.

 

Схемы двух отношений называются эквивалентными, если их степени совпадают и существует такая перестановка имен атрибутов в схемах, что на одинаковых местах будут стоять O-сравнимые атрибуты. Пусть S_R1 = ( A1, A2, …, AN) – схема отношения R1, а S_R2 = ( Bi1, Bi2, …, BiM) – схема R2 после упорядочивания. Тогда R1 ~ R2, если 1) N = M, 2) Aj, Bij <= Dj.

 

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

 

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

 

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

 

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

 

Код преподавателя	Фамилия	Имя	Отчество
Пк1	Петров	Семен	Федорович
Пк2	Иванов	Константин	Александрович

 

 

Номер студенческого билета	Фамилия	Имя	Отчество	Факультет	Код преподавателя
Сб001	Теребов	Петр	Павлович	IT	Пк2
Сб002	Тишин	Сергей	Сергеевич	IT	Пк1
Сб003	Курилова	Вера	Ивановна	IT	Пк1
Сб005	Фурсова	Ника	Федоровна	IT	Пк2
Сб005	Теремков	Иван	Максимович	IT	Пк1

 

Необходимо отметить, что в отличие от, например, модели «сущность-связь», реляционная модель обеспечивает только один тип связей по множественности – связи типа «один-ко-многим».

1 сентября [Лекции]

12 правил Кодда

Вскоре после появления теории Кодда идея реляционных баз данных стала популярна среди разработчиков СУБД. Однако, сделать реляционную СУБД оказалось непросто. Сложилась ситуация, когда после некоторых усовершенствований одни фирмы стали называть свои разработки реляционными (иногда просто добавляя '/R' к имени своей СУБД), а другие – вообще отказываться от создания реляционных СУБД в силу сложности задачи.

Для того чтобы внести ясность в оценку разработок одних фирм и помочь другим сформулировать цель, к которой стремиться, создатель реляционной теории Э. Кодд в конце 70-х годов прошлого века опубликовал свои 12 правил соответствия произвольной СУБД реляционной модели, дополнив основные понятия реляционных баз данных определениями, важными для практики. Формально правил было сформулировано 13, но основное правило обычно упоминается без номера или под номером 0, так что в историю вошли «12 правил Кодда».

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

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

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

3. Правило наличия значения (missing information). В полностью реляционной СУБД должны иметься специальные индикаторы (отличные от пустой символьной строки или строки из одних пробелов и отличные от нуля или какого-то другого числового значения) для выражения (на логическом уровне, систематично и независимо от типа данных) того факта, что значение отсутствует по меньшей мере по двум различным причинам: его действительно нет либо оно неприменимо к данной позиции. СУБД должна не только отражать этот факт, но и распространять на такие индикаторы свои функции манипулирования данными не зависимо от типа данных.

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

5. Правило полноты языка работы с данными. Сколько бы много в СУБД ни поддерживалось языков и режимов работы с данными, должен иметься по крайней мере один язык, выразимый в виде командных строк в некотором удобном синтаксисе, который бы позволял формулировать:

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

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

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

8. Правило физической независимости. Диалоговые операторы и прикладные программы на логическом уровне не должны страдать от каких-либо изменений во внутренних методах хранения данных или в методах доступа к СУБД.

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

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

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

12. Правило ненарушения реляционного языка. Если в реляционной СУБД имеется язык низкого уровня (для работы с отдельными строками), он не должен позволять нарушать или «обходить» правила, сформулированные на языке высокого уровня (множественном) и занесенные в системный каталог.

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

12 мая [Лекции]

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

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


Для его понимания требуется напомнить основные понятия алгебры множеств. Алгеброй называется множество с некоторым набором операций, замкнутое относительно этих операций. Это означает, что результат применения любой из операций к элементам множества снова является элементом исходного множества. Полным декартовым произведением множеств D1, D2, …, DN называется набор всевозможных сочетаний из N элементов d1, d2, …, dN, каждый из которых берется из соответствующего множества (di <- DI). Если множество Di содержит Mi элементов, то полное декартово произведение будет содержать M1 * M2 * … MN элементов.


Например, пусть множество D1 содержит фамилии D1 = { Иванов, Петров, Сидоров }, множество D2 содержит наименования предметов D2 = { Базы данных, Информатика, Программирование }, а множество D3 – оценки D3 = { 2, 3, 4, 5 }. Тогда полное декартово произведение этих множеств будет содержать 3 * 3 * 4 = 36 элементов:


D1 x D2 x D3 = { <Иванов, Базы данных, 2>, <Иванов, Базы данных, 3>, <Иванов, Базы данных, 4>, <Иванов, Базы данных, 5>, <Иванов, Информатика, 2>, <Иванов, Информатика, 3>, <Иванов, Информатика, 4>, <Иванов, Информатика, 5>, <Иванов, Программирование, 2>, <Иванов, Программирование, 3>, <Иванов, Программирование, 4>, <Иванов, Программирование, 5>, <Петров, Базы данных, 2>, < Петров, Базы данных, 3>, < Петров, Базы данных, 4>, < Петров, Базы данных, 5>, < Петров, Информатика, 2>, < Петров, Информатика, 3>, < Петров, Информатика, 4>, < Петров, Информатика, 5>, < Петров, Программирование, 2>, < Петров, Программирование, 3>, < Петров, Программирование, 4>, < Петров, Программирование, 5>, <Сидоров, Базы данных, 2>, < Сидоров, Базы данных, 3>, < Сидоров, Базы данных, 4>, < Сидоров, Базы данных, 5>, < Сидоров, Информатика, 2>, < Сидоров, Информатика, 3>, < Сидоров, Информатика, 4>, < Сидоров, Информатика, 5>, < Сидоров, Программирование, 2>, < Сидоров, Программирование, 3>, < Сидоров, Программирование, 4>, < Сидоров, Программирование, 5> }. Элементы этого множества описывают все возможные варианты исходов ситуации, которая может быть определена словами «студент получил за предмет следующую оценку».


В заключение отметим важное свойство полного декартового произведения: все элементы полного декартового произведения различны. Это означает, что в нем не найдется двух одинаковых n-ок, так как иначе исходные множества необходимо содержали бы одинаковые элементы, что невозможно.


Вернемся теперь к понятию отношение. N-кратным отношением R называется подмножество декартова произведения D1 x D2 x … x DN множеств D1, D2, …, DN (N >= 1), причем множества необязательно различны. Сами множества D1, D2, …, DN называются доменами.


В то время как полное декартово произведение описывает все возможные исходы некоторого события, отношение R моделирует определенную реальную ситуацию и может содержать любое количество элементов. Рассмотрим в качестве примера отношение R = { <Иванов, Базы данных, 5>, <Иванов, Информатика, 4>, <Иванов, Программирование, 5>, < Петров, Базы данных, 4>, < Петров, Информатика, 3>, <Петров, Программирование, 4>, < Сидоров, Информатика, 4>, <Сидоров, Программирование, 3> }. Данное отношение моделирует ситуацию «результаты сдачи экзаменов студентами» (Сидоров не сдавал экзамен по Базам данных).


Любое отношение R, впрочем, как и полное декартово произведение, легко может быть изображено графически в виде таблицы, столбцам которой соответствуют вхождения доменов в отношение, а строкам – наборы n значений, взятых из доменов, которые расположены в определенном порядке соответственно заголовку таблицы:

 

R
Фамилия	Предмет	Оценка
Иванов	Базы данных	5
Иванов	Информатика	4
Иванов	Программирование	5
Петров	Базы данных	4
Петров	Информатика	3
Петров	Программирование	4
Сидоров	Информатика	4
Сидоров	Программирование	3

 

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

 

1. в таблице нет двух одинаковых строк (как и в отношении нет двух одинаковых кортежей);

2. столбцы таблицы соответствуют атрибутам отношения;

3. каждый атрибут отношения (таблицы) имеет уникальное имя;

4. порядок строк в таблице произвольный (как и кортежей в отношении);

5. порядок столбцов в таблице также может быть произвольным (от перестановки столбцов отношение не меняется).

 

Согласно этим свойства, отношение R1, изображенное ниже, равно (одинаково с точки зрения реляционной модели) отношению R:

 

R1
Предмет	Фамилия	Оценка
Информатика	Петров	3
Базы данных	Иванов	5
Программирование	Иванов	5
Информатика	Сидоров	4
Информатика	Иванов	4
Программирование	Сидоров	3
Базы данных	Петров	4
Программирование	Петров	4