Проектирование реляционных баз данных: Методические указания по курсу СУБД

Министерство образования Российской Федерации Воронежский государственный университет Факультет прикладной математики и механики Кафедра теоретической и прикладной механики Проектирование реляционных баз данных Методические указания по курсу "СУБД" для студентов 3-4 курсов дневного отделения спец.01.02.04

Составители: доц. А.В.Ковалёв доц. Т.Д. Семыкина ст. преп. А.С.Чеботарёв асс. Ю.Д.Щеглова

Воронеж1999.

3

Введение. Методическое пособие посвящено работе с реляционными базами данных на этапе проектирования задач и создания БД. В настоящее время широкое распространение получила компьютерная обработка статистических данных, задач АСУ, материального и бухгалтерского учета и т.д. При этом все необходимые сведения должны быть организованы определенным образом, который обеспечивает надежность их сохранения, редактирования и использования в процессе эксплуатации. Одним из самых распространенных способов хранения являются реляционные базы данных, что определяется возможностью использования реляционной алгебры. Общепризнанно, что работа с базами данных требует не только научных методов, но и искусства программиста, проектирующего базы данных. При этом необходимо сочетание 3 моментов: 1. База данных должна быть полной, то есть содержать все необходимые для решения поставленной задачи данные, и надежной в пользовании, то есть должна давать правильные ответы на поставленные запросы, должна допускать надежное использование несколькими пользователями (если это потребуется) и т.д. 2. База данных должна быть создана так, чтобы исключить по максимуму ввод неточных данных в базу. С этой целью должна быть составлена справочники, по тем данным, которые имеют постоянные значения на протяжении довольно длительного периода. 3. База данных должна быть составлена с учетом не только особенностей ее заполнения, но и с учетом выходных форм, которые понадобятся как результат решения задачи. Указанные особенности требуют от программиста, проектирующего БД, знание теоретических основ проектирования, полной информированности о работе предприятия (заказчика) по вопросам, касающимся задачи, и, несомненно, опыта работы по проектированию баз. Если опыт приобретается только в процессе работы, то теоретические знания необходимо приобрести до начала работы с БД. Ι. Построение реляционной БД методом декомпозиции. 1. Понятие о реляционных БД. Под базой данных (БД) понимают хранилище структурированных данных, при этом данные должны быть непротиворечивы, минимально избыточны и целостны. Реляционная БД представляет собой совокупность таблиц, содержащих всю информацию, которая должна храниться в БД. Реляционные БД поддерживаются большинством современных СУБД, это связано с удобством их использования в традиционных задачах и на этапе проектирования, на котором возможно использование реляционной алгебры. При этом в терминологии теории реляционных БД таблицам соответствуют отношения, столбцам – атрибуты, строкам – кортежи. При обработке в ЭВМ отношения хранятся в виде файлов, строка или кортеж называются записью, а столбец (атрибут) называется

4

полем. Число столбцов (полей) называется степенью отношения. Эта величина не изменяется после создания отношения. Тип содержимого и величина поля для реляционных БД тоже строго определена. Текущее число строк (записей) называется мощностью отношения, и она меняется по мере удаления или добавления строк. Атрибут или совокупность атрибутов, позволяющих единственным образом идентифицировать кортеж (запись) называется первичным ключом. 2. Подготовительный этап проектирования Прежде чем приступить к проектированию БД для определенной задачи, необходимо детально обсудить с будущим пользователем (заказчиком) постановку задачи, входные документы, выходные данные, совокупность всех необходимых сведений, которые должны храниться в БД. Особенно внимательно надо изучать имеющуюся документацию по этой проблеме. Это позволяет определить все возможные нюансы, которые могут возникнуть в процессе эксплуатации задачи. Например, в задаче в качестве входного документа фигурирует товарно-транспортная накладная, в которой помимо очевидно необходимых сведений о поставщике и поставках имеется указания на номер вагона. Если не будет предусмотрено в базе хранение этого атрибута, то при возникающих претензиях к транспортникам эту информацию будет трудно установить. Другой пример. В выходных ведомостях присутствует имя поставщика, но под него отведено ограниченное количество знаков, хотя хранящееся в БД имя имеет значительно больший размер. При этом возможно придется вводить дополнительное поле, в котором будет храниться краткое имя поставщика. После определения всех необходимых атрибутов проектировщик должен поставить основные цели. 3. Цели проектирования. Среди множества целей, стоящих перед проектированием, следующие представляются наиболее важными: 1. Возможность хранения всех необходимых данных в БД. 2. Исключение избыточных данных. 3. Сведение числа хранимых в БД отношений к минимуму. 4. Нормализация отношений для упрощения решения проблем, связанных с обновлением и удалением данных. Рассмотрим подробно каждую из этих целей. Необходимость первой очевидна. При достижении второй цели необходимо уметь отделять избыточно дублируемые данные от просто дублируемых. Избыточно дублируемыми являются данные, при удалении которых информация может быть восстановлена из других кортежей отношения. Если же информация оказывается утерянной, то данные не являются избыточными. Например, в базе содержится список проживающих в общежитии с указанием фамилии (Фам), номера комнаты (Кном) и номера телефона в комнате (Тном) В этом примере номера комнат и телефонов дублируемые данные (Рис.1(а)). Но если их убрать в третьей и четвёртой строках, то будет утеряна информация о номерах комнат, в которых проживают Галкин и Дроздов. С другой стороны,

5

если убрать только дублируемые номера телефонов, то эта информация может быть установлена из других кортежей (Рис.1(б)). Таким образом, Тном является избыточно дублируемыми данными. Фам Синицын Воробьев Галкин Дроздов

Кном 2234 2275 2234 2275 (а)

Тном 77-29 77-41 77-29 77-41

Фам Синицын Воробьев Галкин Дроздов

Кном 2234 2275 2234 2275 (б)

Тном 77-29 77-41

Рис.1 Рис.1: (а) – пример дублируемых данных в отношении; (б) – пример отношения после удаления избыточно дублируемых данных. Однако простое удаление избыточных данных из базы может привести к серьёзным проблемам при удалении записи с фамилией Синицин, будет утеряна информация о номере телефона в комнате 2234. Выходом из такой ситуации может оказаться разбиение на две базы (Рис.2). Отношение 1 Фам Кном Синицын 2234 Воробьев 2275 Галкин 2234 Дроздов 2275

Отношение 2 Кном Тном 2234 77-29 2275 77-41

Рис.2 Рис.2. Исключение избыточных данных путем разбиения на два отношения. Цель 3 обусловлена тем, что разбиение одного отношения на два или более меньших отношений желательно с точки зрения исключения определённых проблем, но это неудобно для пользователя. Таким образом, нельзя допускать неограниченный рост числа отношений. Цель 4 на первый взгляд вступает в противоречие с целью 3, но как видно из предыдущего примера необходимость исключать избыточные данные ставит вопрос о нормализации отношений, т.е. о разбиении одного отношения на два или больше отношений согласно специальной процедуре разбиения. Разумное сочетание целей 3 и 4 зависит от опыта и интуиции программиста и позволяет говорить о программировании как об искусстве. 4. Универсальное отношение Проектирование БД начинается с разработки универсального отношения, которое включает все представляющие интерес атрибуты и содержит все данные, необходимые для эксплуатации задачи. Кроме того в этом отношении должны содержаться записи, касающиеся всех типичных, а может быть и исключительных ситуаций, которые могут возникнуть в процессе использования БД.

6

В качестве примера приведем формирование универсального отношения для задачи консультант университета. В процессе изучения всех необходимых для консультанта сведений о студентах были определены следующие атрибуты: Сном: Номер студента. Целое значение, уникальное для каждого студента университета. Сфам: Фамилия студента. Каждый студент имеет только одну фамилию, но возможно, что одну фамилию носят несколько студентов. Кном: Номер комнаты в общежитии городка. Каждый студент живет на территории городка и имеет комнату. В одной комнате может проживать более одного студента. Тном: Номер телефона студента. Каждая комната общежития имеет один телефон и им пользуются все студенты, проживающие в этой комнате. Курс: Номер курса. Это идентификационный номер курса, посещаемого студентом. Консультант будет сохранять данные только о курсах, завершенных студентом. Семестр: Университетский семестр. Представляет собой семестр, в котором данный курс был завершен студентом. Оценка: Оцека за курс. После этого приведем пример таблицы с наиболее типичными записями. КОНСУЛЬТАНТ Сном 3215

Сфам Беляев

Кном 52412

Тном 217

3462

Русин

63220

118

3567

Клюквин

51306

108

4756

Ягодкин

51306

108

Курс Мтн1 Лал1 Мтн2 Дфг2 Мтн2 Дфг3 Лал1 Трм2 Мтн1 Дфг3 Мтн1

Семестр 01 01 02 02 02 03 01 02 01 03 01

Оценка Хор Удв Хор Хор Отл Отл Отл Хор Хор Отл Хор

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

7

представляющие все типичные ситуации (и, желательно, предусмотреть исключительные случаи), возникающие в данной задаче. КОНСУЛЬТАНТ Сном 3215 3215 3215 3215 4362 4362 4362 3567 3567 3567 4756

Сфам Беляев Беляев Беляев Беляев Русин Русин Русин Клюквин Клюквин Клюквин Ягодкин

Кном 52412 52412 52412 52412 63220 63220 63220 51306 51306 51306 51306

Тном 217 217 217 217 118 118 118 108 108 108 108

Курс Мтн1 Лал1 Мтн2 Дфг2 Мтн2 Дфг3 Лал1 Трм2 Мтн1 Дфг3 Мтн1

Семестр 01 01 02 02 02 03 01 02 01 03 01

Оценка Хор Удв Хор Хор Отл Отл Отл Хор Хор Отл Хор

Рис.4 Универсальное отношение для базы «Консультант» После составления универсального отношения необходимо протестировать его на стандартные запросы пользователя БД. При этом могут быть выявлены наиболее типичные проблемы, возникающие при использовании единственного отношения. В качестве наиболее типичных можно отметить. Проблема вставки. Пусть студент сдал очередной курс, и при этом в базу заносится новая запись, в которой помимо новых данных должны повторяться уже имеющиеся в базе данные относительно студента. Это представляет для программиста определенные проблемы по обеспечению однозначности и непротиворечивости заполнения БД. С другой стороны, новые записи могут создать проблемы при получении ответа на некоторые запросы. Например, в базу консультант будет внесена запись о вновь поступившем студенте, не успевшем сдать ни одного курса. При подсчете средний балл для студентов, занесенных в базу, будет понижен из-за этой записи. Проблема обновления. Наличие избыточно дублируемых данных в универсальном отношении приводит к ситуации, когда исправляются данные в одних кортежах, а в других могут остаться неисправленными. В этом случае программист должен затратить дополнительные усилия на то, чтобы при исправлении дублируемых данных отслеживались все кортежи с этими данными. Например, в базе «Консультант» при изменении номера телефона в одной из комнат приходится отслеживать все записи, в которых встречается этот номер комнаты. Если отношение содержит большое количество записей, их поиск требует достаточно много времени. Проблема удаления. Если отношение имеет нескольких пользователей, и один из них удаляет ненужную ему информацию, то вместе с этим могут быть потеряны и

8

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

A —> B Математическая форма записи

Диаграмма или графическая форма записи

Рис.5 ФЗ не могут быть доказаны путем простого просмотра отдельного экземпляра отношения и нахождения двух атрибутов, имеющих те же значения в более чем одном кортеже. Это может служить ключом к тому, в каком направлении следует вести поиск ФЗ, но не доказательством. ФЗ необходимо получить исходя из базовых свойств самих атрибутов. Пример.(Рис.6 Различные способы представления ФЗ, существующих между атрибутами отношения КОНСУЛЬНАНТ)

Сном —> Сфам Сном —> Кном Кном —> Тном Сном —> Тном Сном, Курс, Семестр —> Оценка Рис.6(а)

9

Рис.6(б) Диаграмма ФЗ может указать на наличие проблем в соответствующем отношении и необходимость его разбиения. Критерием окончания декомпозиции может служить соответствие его нормальной форме Бойса-Кодда. 6. Нормальная форма Бойса-Кодда. Введем необходимые понятия. 1. Возможный ключ. Возможный ключ представляет собой атрибут или набор атрибутов, который может быть использован для данного отношения в качестве первичного ключа. Первичный ключ всегда является возможным ключом; однако не исключено наличие других возможных ключей, которые могли бы быть, но не были использованы в качестве первичного ключа. 2. Детерминант. Если А→В есть ФЗ и В не зависит функционально от любого подмножества А, то говорят, что А представляет собой детерминант В. Одним из самых первых, но и одним из самых важных результатов в области реляционных БД стало доказанное Коддом утверждение о том, что большинство потенциальных аномалий в БД будет устранено в случае должной декомпозиции каждого отношения в нормальную форму Бойса – Кодда (НФБК). Эта форма определяется следующим образом: отношение находится в НФБК, если и только если каждый детерминант отношения является возможным ключом. Хотя существуют нормальные формы более высокого уровня, которые накладывают даже более сильные ограничения на разрабатываемые отношения, на практике большинство проектировщиков стараются получить отношения в НФБК. 7. Основные этапы приведения базы данных к НФБК. 1. Разработка универсального отношения для БД. 2. Определение всех ФЗ между атрибутами отношения. 3. Определение того, находится ли отношение в НФБК. Если да, проектирование завершается; если нет, отношение должно быть разложено на два отношения.

10

4. Повторение шагов 2 и 3 для каждого нового отношения, полученного в результате декомпозиции. Проектирование завершается, когда все отношения будут находиться в НФБК. Декомпозиция отношения, не приведенного в НФБК, на два отношения, осуществляется с помощью ФЗ следующим образом: Пусть отношение R(А,В,С,D,E,…) не приведено к НФБК. Определяется ФЗ, например C→D, про которую известно, что она является причиной того, что отношение R не находится в НФБК. (С является детерминантом, но не является возможным ключом.) Создаются два новых отношения: R1(А,В,С,E,…) и R2(С,D), где зависимостная часть ФЗ была выделена из R и опущена при формировании отношения R1, и ФЗ была использована полностью при формировании отношения R2. Теперь необходимо проверить, находятся ли в НФБК отношения R1 и R2. Про отношение R2(С,D) говорят, что оно является проекцией отношения R. Этот тип декомпозиции называется декомпозицией без потерь при естественном соединении. Пример.(Рис.7 Пример отношения R1 и R2)

Рис.7 При декомпозиции все время возникает вопрос, какую очередную ФЗ выбрать для проекции. Простым правилом выбора ФЗ для проекции может служить поиск «цепочки ФЗ» вида

11

A→B→C с последующим использованием для проекции крайней правой зависимости. Например, в схеме (3.2) существует цепочка ФЗ Сном →Кном →Тном, которая может быть заменена на два отношения R1(Кном, Тном) и R2(Сном, Кном). Однако, не все схемы ФЗ сводятся к цепочке. Например, на схеме (3.3) ФЗ Сном→Сфам и Сном→Кном не являются цепочкой. Но в этом случае очевиден способ разбиения на 2 отношения, которые будут находиться в НФБК. Особым случаем является набор ФЗ, при котором возможный ключ отношения содержит совокупность детерминантов ФЗ (Рис.8).

R(A, B, C) Рис.8 В этом случае разбиение должно проводится таким образом, чтобы не была утеряна ни одна ФЗ. В приведенной схеме (рис.3.9) можно создать 2 отношения R1(А, В) и R2(С, В), но его надо проверить на случай соединения двух итоговых отношений. Если в этом случае возникают проблемы, то может быть придется ограничиться одним отношением R(А, В, С), которые, строго говоря, не находятся в НФБК. Перед тем как использовать набор ФЗ при проектировании, особое внимание необходимо обратить на выявление избыточных ФЗ. Зависимость, не заключающая в себе такой информации, которая не могла бы быть получена на основе других зависимостей из числа использованных при проектировании БД, называется избыточной ФЗ. Поскольку избыточная ФЗ не содержит уникальной информации, она может быть удалена из набора ФЗ без отрицательного воздействия на результаты. Избыточные ФЗ удаляются на начальном этапе проектирования до применения алгоритма декомпозиции. Одним из простейших путей появления в наборе ФЗ избыточных зависимостей является генерация ФЗ с помощью концепции транзитивной зависимости. Транзитивная зависимость определяется следующим образом. Если А → В и В → С, то А → С – транзитивная зависимость. Два момента следует подчеркнуть. Во-первых, транзитивная зависимость А→С, приведенная в определении выше, является вполне корректной зависимостью. С ней не связано ничего сомнительного. Во-вторых, если А→В, В→С и А→С входят в набор ФЗ, следовательно А→С является избыточной и ее использование в процессе проектирования не требуется. Действительно, транзитивная зависимость А→С причинит больше вреда, чем пользы при проектировании, и ее следует исключить из набора перед началом проектирования. 8. Минимальное покрытие. Набор неизбыточных ФЗ, полученный путем удаления всех избыточных ФЗ из исходного набора, называется минимальным покрытием. К сожалению, минимальное покрытие не всегда является уникальным, поскольку порядок, в

12

котором осуществляется процедура удаления избыточных ФЗ, может оказать влияние на полученное минимальное покрытие. В заключение следует подчеркнуть один важный момент, связанный с удалением избыточных ФЗ из исходного набора: избыточные ФЗ следует удалять по одной, каждый раз заново анализируя новый набор на предмет присутствия в нем избыточных ФЗ. Эта процедура завершается, как только не останется ни одной избыточной ФЗ, оставшийся набор является минимальным покрытием. 9. Обобщенный алгоритм декомпозиции. 1. Построение универсального отношения для БД. 2. Определение всех ФЗ, существующих между атрибутами универсального отношения. 3. Удаление всех избыточных ФЗ из исходного набора ФЗ с целью получения минимального покрытия. Эта процедура проводится путем поочередного удаления избыточных ФЗ с последующей проверкой получаемого на каждом шаге набора ФЗ на наличие хотя бы одной избыточной ФЗ. 4. Использование ФЗ из минимального покрытия для декомпозиции универсального отношения в набор НФБК-отношений. Далее должен быть применен алгоритм декомпозиции в разделе «Основные этапы приведения БД к НФБК» 5. Если может быть получено более чем одно минимальное покрытие, осуществляется сравнение результатов, полученных на основе различных минимальных покрытий, с целью определения варианта, лучше других отвечающего требованиям предприятия. При использовании алгоритма декомпозиции (шаг 4) следует помнить о нежелательности проекции, порождаемой ФЗ, у которой зависимостная часть является детерминантом другой ФЗ; также повышенное внимание требуется в тех случаях, когда зависимостная часть ФЗ зависит более чем от одного детерминанта. В любом из этих случаев может быть утеряна ФЗ из БД. Если в процессе декомпозиции достигнуто состояние, в котором проецирование, невлекущее за собой потерь ФЗ, становится невозможным, проектировщик должен будет сделать выбор из двух альтернатив: (1) выбор оставшихся ФЗ и создание одного отношения для каждых детерминанта и набора зависящих от него атрибутов; (2) изменение порядка ранее проведенных декомпозиций, ведь алгоритм проектирования не ведет к единственному решению. После завершения разработки НФБК-отношений, рассматриваемых уже в качестве окончательного проекта, полученный набор необходимо проконтролировать на предмет наличия невыявленных проблем. 1. Составляются списки ФЗ для каждого отношения. Эти списки проверяются по двум направлениям: во-первых, одна и та же ФЗ не должна появляться более чем в одном отношении; и во-вторых, набор ФЗ, полученный в результате проектирования, должен в точности совпадать с набором, присутствующим в минимальном покрытии, полученном перед началом проектирования. В противном случае, необходимо показать возможность получения итогового набора ФЗ из

13

минимального покрытия с помощью правил вывода. Если хотя бы одна из этих проверок окажется недостоверной, следует проанализировать процесс проектирования для выявления ошибок и/или рассмотреть другие варианты проектирования. 2. Осуществляется проверка на присутствие избыточных отношений. Отношение является избыточным, если (а) все атрибуты в избыточном отношении могут быть найдены в одном другом отношении проектного набора; (б) все атрибуты в избыточном отношении могут быть найдены в отношении, которое может быть получено из других отношений предложенного проектного набора с помощью серии операций объединения этих отношений. Если устанавливается избыточность отношения, его следует исключить из проектного набора. Для примера, иллюстрирующего первый тип избыточности, полагаем, что набор проектных отношений имеет вид: R1(A,B) R2(B,C,Y,Z) R3(A,B,K) Отношение R1 является избыточным, так как все его атрибуты присутствуют в отношении R3. Для иллюстрации избыточности второго типа положим, что предлагаемый проектный набор имеет вид: R1(A,C,X) R3(D,K,F) R5(D,E,G,H) R7(A,B,D) R8(A,B,E,G) Отношение R8 является избыточным, так как применение операции объединения R5 и R7 (общим атрибутом является D) дает в результате отношение R9(A,B,D,E,G,H), которое содержит все атрибуты, присутствующие в R8. 3. Рассмотрение отношений с практической точки зрения. Изучается характер использования отношений в конструируемой БД и определяется, будут ли они поддерживать те типы запросов и операций обновления, которые предполагается использовать. Глава II. ER-метод проектирования БД. 1. Основные понятия. Этот метод меньше связан с реляционным типом БД. Название его определяется аббревиатурой словосочетания ESSENCE (сущность) – RELATION (связь). При проектировании ЕR-метода выделяются объекты, явления, для которых необходимо создать БД, и определяется характер связи между ними. Приведем пример. Пусть требуется создать БД, предназначенную для хранения информации о преподавателях кафедры и о курсах, которые они читают. Очевидно, в этом случае фигурирует 2 сущности преподаватель и курс.

14

Связь – читает. Эта связь может быть наглядно представлена в виде диаграммы ER-экземпляров (Рис.9(а)) или диаграммы ER-типа (Рис.9(б))

Рис.9(а)

Рис.9(б) В методе ЕR не существует четкого определения терминов, используемых в нем, поэтому приведем несколько интуитивные определения. СУЩНОСТЬ. Сущность определяется как некоторый объект, представляющий интерес для организации. Этот объект должен иметь экземпляры, отличающиеся друг от друга и допускающие однозначную идентификацию. Единственный определяющий признак, который может помочь в нахождении сущностей, состоит в том, что сущность – это, как правило, существительное. Примерами сущностей могут служить машины, банковские счета, колледжи, служащие и контракты. На Рис.9(а) и Рис.9(б) сущностями являются преподаватель и курс, в то время как отдельные экземпляры каждой сущности идентифицируются с помощью НП и НК соответственно. СВЯЗЬ. Связь представляет собой соединение между двумя или более сущностями. При поиске связей в основном следует полагаться на то обстоятельство, что связь обычно выражается глаголом. Типичными примерами связей между двумя сущностями являются: служащие РАБОТАЮТ – В отделах, студенты ИЗУЧАЮТ учебные предметы, рабочие ОБСЛУЖИВАЮТ механизмы. Тесно связано с предыдущими третье важное понятие – атрибут. АТРИБУТ. Атрибут есть свойство сущности. Например, атрибутами, могущими быть свойствами сущности преподаватель, являются: фамилия, звание, должность. Определения сущности, связи и атрибута не отличаются особой конкретностью, однако являются приемлемыми для использования в тех целях, на которые они рассчитаны.

15

Атрибут, или набор атрибутов, используемый для идентификации экземпляра сущности, называется ключом сущности. Каждый экземпляр связи однозначно определяется набором ключей сущностей, соединяемых этой связью. Таким образом, НП, НК является одним ключом связи. На диаграммах ЕR-типа, подобных показанной на Рис.9(б), сущности представляются в виде прямоугольников, а связи – в виде ромбов. Ниже каждой сущности размещается атрибут, или набор атрибутов, являющийся ключом сущности для данной сущности. Значения цифры «1» на диаграмме (см. Рис.9(б)) и маленьких сплошных кружков будут обсуждены в следующем разделе. В большинстве случаев для определения набора отношений проектируемой БД используются диаграммы ЕR-типа, а не диаграммы экземпляров. Важной характеристикой связи между двумя (и более) сущностями является степень связи. 2. Использование диаграмм ЕR-типа для построения БД В качестве первого шага рассмотрим проектирование отношений в случае бинарной связи между сущностями. Бинарной называется связь, установленная между двумя сущностями. Необходимо отметить, что это может быть простейшим элементом в ЕRдиаграмме. Например, пусть для сущностей S1, S2, S3, S4 можно построить следующую диаграмму: (Рис.10)

Рис.10 Из этой диаграммы устанавливаются 3 бинарных связи. После того, как в проектируемой базе данных определены сущности и связи, необходимо определить набор предварительных отношений, предполагаемые первичные ключи для каждого отношения и набор атрибутов в каждом из них. Каждое отношение проверяется на соответствие его НФБК, для чего для каждого отношения определяются межатрибутные ФЗ. Если полученные в итоге отношения не находятся в НФБК, или если некоторым атрибутам не находится логически обоснованных мест в предварительных отношениях, то в этих случаях необходимо пересмотреть ERдиаграммы на предмет устранения возникших затруднений.

16

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

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

17

диаграмм ER-типа можно получить, опираясь на класс принадлежности и степень отношения как на определяющие факторы. Первоначально рассматривается возможность использования одного отношения. Оказывается, что существенная роль в этом случае принадлежит классу принадлежности. Например, рассмотрим ситуацию, когда в отношениях S1(кл1, S1атр1, S1атр2) и S2(кл2, S2атр1, S2атр2) степень связи 1:1 и класс принадлежности обеих сущностей обязательный. В этом случае отношение S(кл1, S1атр1, S1атр2, кл2, S2атр1) будет находится в НФБК. Так как степень связи здесь 1:1 и класс принадлежности является обязательным как для сущности S1, так и для сущности S2, гарантируется однократное появление каждого значения кл1 и каждого значения кл2 в любом экземпляре отношения. Это значит, что отношение никогда не будет содержать ни пустой информации, ни повторяющихся групп избыточных данных. Ключ сущности S1 был избран в качестве первичного ключа для отношения, но также может быть использован ключ сущности S2. Итак, можно сформулировать первое правило генерации отношений. ПРАВИЛО 1. Если степень бинарной связи равна 1:1 и класс принадлежности обеих сущностей является обязательным, то требуется только одно отношение. Первичным ключом этого отношения может быть ключ любой из двух сущностей. Если степень связи равна 1:1 и класс принадлежности одной сущности является обязательным, а другой – необязательным, то одного отношения недостаточно. Так как будут пробелы на месте атрибутов тех экземпляров, которые не участвуют в связях. Способ исключения пробелов состоит в использовании вместо одного отношения двух. Каждое отношение будет содержать информацию, касающуюся одной сущности. Кроме того, ключ сущности, класс принадлежности которой является необязательным, необходимо поместить в качестве атрибута в отношение, содержащее информацию о сущности, класс принадлежности которой является обязательным. ПРАВИЛО 2. Если степень бинарной связи равна 1:1 и класс принадлежности одной сущности является обязательным, а другой – необязательным, то необходимо построение двух отношений. Под каждую сущность необходимо выделение одного отношения, при этом ключ сущности должен служить первичным ключом для соответствующего отношения. Кроме того, ключ сущности, для которого класс принадлежности является необязательным, добавляется в качестве атрибута в отношение, выделенное для сущности с обязательным классом принадлежности. Воспользовавшись этим правилом можно получить следующие отношения S2(кл2, S2атр1, кл1) S1(кл1, S1атр1, S1атр2) В этом случае, когда степень бинарной связи равна 1:1 и класс принадлежности ни одной из сущностей не является обязательным, одного

18

отношения недостаточно. При использовании только одного отношения возможны два пути возникновения пробелов. Также недостаточным является использование двух отношений, так как возникают проблемы в связи с внесением ключа одной сущности в отношение, выделенное под другую сущность. Единственное решение заключается в выделении трех отношений: по одному для каждой сущности и одного для связи. Теперь можно сформулировать третье правило генерации отношений. ПРАВИЛО 3. Если степень бинарной связи равна 1:1 и класс принадлежности ни одной сущности не является обязательным, то необходимо использовать три отношения: по одному для каждой сущности, ключи которых служат в качестве первичных в соответствующих отношениях, и одного для связи. Среди своих атрибутов отношение, выделяемое связи, будет иметь по одному ключу сущности от каждой сущности. 2.2 Предварительные отношения для бинарных связей степени 1:N Для случая бинарных связей степени 1:1 устанавливаются три отдельных правила генерации соответствующего набора предварительных отношений. Для случая бинарных связей степени 1:n требуется только два правила. Фактором, определяющим выбор и использование одного из этих двух правил, является класс принадлежности n-связной сущности; класс принадлежности 1-связной сущности не влияет на конечный результат в обоих случаях. Рассмотрим пример связи, изображенной на диаграмме (Рис.12)

Рис.12 Согласно диаграмме каждый экземпляр сущности S1 может участвовать в связи только один раз, а экземпляры сущности S2 участвует в связи не менее одного раза. Следовательно, в отношении, посвященном связи S1 и S2, будут появляться пустые поля, где класс принадлежности сущности не обязательный, а в полях отведенных для атрибута n-связной сущности будут повторы. Причем, повторы будут существовать и в том случае, если класс принадлежности nсвязной сущности обязателен. Решить все эти проблемы, вне зависимости от класса принадлежности 1связной сущности, можно согласно следующему правилу. ПРАВИЛО 4. Если степень бинарной связи равна 1:n и класс принадлежности n-связной сущности является обязательным, то достаточным является использование двух отношений, по одному на каждую сущность, при условии, что ключ сущности каждой сущности служит в качестве первичного ключа для соответствующего отношения. Дополнительно ключ 1-связной

19

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

Рис.13 В связи с этим возникает несколько проблем: пробелы в полях, отведенных тем экземплярам сущности, которые не участвуют в связи; повторяются поля в тех случаях, когда экземпляры S2 участвуют в связи более одного раза. Последняя проблема остается и в том случае, когда класс принадлежности односвязной сущности обязателен. Если в этом случае применить правило 4 и сформировать 2 отношения, то не исчезнут пробелы в тех полях, которые отведены под ключ S2, т.е. у этой сущности необязательный класс принадлежности. Решить все эти проблемы вне зависимости от класса принадлежности 1связной сущности можно, следуя этому правилу. ПРАВИЛО 5. Если степень бинарной связи равна 1:n и класс принадлежности n-связной сущности является необязательным, то необходимо формирование трех отношений: по одному для каждой сущности, причем ключ каждой сущности служит первичным ключом соответствующего отношения, и одного отношения для связи. Связь должна иметь среди своих атрибутов ключ сущности от каждой сущности. 2.3. Предварительные отношения для бинарных связей степени M:N Если степень бинарной связи равна m:n, то для хранения данных требуются три отношения вне зависимости от класса принадлежности как первой, так и второй сущностей. При использовании одного или двух отношений неизбежно возникновение пробелов и/или повторяющихся групп данных в экземплярах этих отношений; какая из двух проблем возникает при использовании двух отношений зависит от классов принадлежности двух сущностей. Предлагается следующее правило генерации предварительных отношений для случая степени m:n. ПРАВИЛО 6. Если степень бинарной связи равна m:n, то для хранения данных необходимо три отношения: по одному для каждой сущности, причем ключ каждой сущности используется в качестве первичного ключа соответствующего отношения, и одного отношения для связи. Последнее отношение должно иметь в числе своих атрибутов ключ сущности каждой сущности.

20

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

Литература Джексон Г. Проектирование реляционных баз данных для использования с микроЭВМ. – М: Мир, 1991. – 252 с. Горев А., Ахаян Р., Макашарипов С. Эффективная работа с СУБД. – СПб: ПИТЕР, 1997. – 700 с. Каратыгин С., Тихонов А., Долголаптев В. Базы данных: Простейшие средства обработки информации. Электронные таблицы. Система управления базами данных: В 2 т. – М.: АВF, 1995. – Т.1. – С.1 – 411. Райли, Дэвид Д. Абстракция и структуры данных: Вводный курс. – М: Мир, 1993. – 750 с.

Редактор Кузнецова З.Е.