ПОЛУЧЕНИЕ РЕЛЯЦИОННЫХОТНОШЕНИЙ ИЗ ДИАРАММ ER – ТИПА

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

Правило 1: Если степень бинарной связи равна 1: 1 и класс принадлежности обеих сущностей является обязательным, то требуется только одно отношение, объединяющее атрибуты двух сущностей. Первичным ключом этого отношения может быть ключ любой из двух сущностей.

Правило 2: Если степень бинарной связи равна 1: 1 и класс принадлежности одной сущности является обязательным, а другой необязательным, то необходимо построение двух отношений. Под каждую сущность необходимо выделить по одному отношению, при этом ключ сущности должен служить первичным ключом для соответствующего отношения. При этом ключ сущности, для которой класс принадлежности является необязательным, добавляется в качестве атрибута в отношение, выделенное для сущности с обязательным классом принадлежности.

Правило 3: Если степень бинарной связи равна 1: 1 и класс принадлежности обеих сущностей является необязательным, то необходимо построение трех отношений: по одному для каждой сущности, ключи которых служат в качестве первичных ключей соответствующих отношений, и одно для связи. Среди своих атрибутов отношение, выделенное для связи, будет иметь ключи сущностей.

При построении отношений для связи 1: М учитывается класс принадлежности М-связанной сущности. Класс принадлежности 1-связанной сущности на конечный результат не влияет.

Правило 4: Если степень бинарной связи 1: М и класс принадлежности М-связанной сущности является обязательным, то достаточным является использование двух отношений, по одному на каждую сущность. При условии, что ключ каждой сущности служит в качестве первичного ключа для соответствующего отношения. Дополнительно ключ 1-связанной сущности должен быть добавлен как атрибут в отношение, отведенной для М-связанной сущности.

Правило 5: Если степень бинарной связи 1: М и класс принадлежности М-связанной сущности является необязательным, то достаточным является использование трех отношений, по одному на каждую сущность, причем ключ каждой сущности служит первичным ключом соответствующего отношения, и одного отношения для связи. Отношение для связи должно иметь среди своих атрибутов ключ каждой сущности.

Правило 6: Если степень бинарной связи равна М: М, то необходимо три отношения: по одному на каждую сущность с первичными ключами от соответствующих сущностей, и одно отношение для связи. Отношение для связи должно иметь среди своих атрибутов ключ каждой сущности.

Процесс проектирования БД

1. Возможность хранения всех необходимых данных.

2. Исключение избыточности.

3. Сведения числа хранимых в БД отношений к минимуму. Решение проблем избыточности, корректировки и обновления данных решается, как правило, разбиением отношения на несколько независимых. Это приводит к общему увеличению числа отношений и соответственно файлов. Это приводит к сложностям пользования и ведения БД.

4. Нормализация отношений для упрощения процедур обновления и удаления данных.

Определение избыточности данных.

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

ТЕМА

Шифр темы	Исполнитель
111	Исп-1
112	Исп-2
113	Исп-1
114	Исп-1

 

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

Шифр темы	Исполнитель
111	Исп-2
112	Исп-1
113	---
114	---

 

То если удалить запись 111 не будет известен исполнитель тем 113 и 114. Таким образом, это пример не избыточности данных, а необходимого неизбыточного дублирования.

Если отношение ТЕМА расширить атрибутом ТЕЛЕФОН

ШИФР ТЕМЫ

ИСПОЛНИТЕЛЬ

ТЕЛЕФОН

 

Мы получим пример избыточного отношения по атрибуту ТЕЛЕФОН. Достаточно хранить один экземпляр телефона для каждого исполнителя. В этом случае для устранения избыточности необходимо получить два отношения.

ТЕМА (ШИФР_ТЕМЫ, ИСПОЛНИТЕЛЬ)

ТЕЛ._ИСПОЛНИТЕЛЯ (ИСПОЛНИТЕЛЬ, ТЕЛЕФОН)

Аномалии вставки, удаления и обновления.

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

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

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

Нормализация реляционных отношений

Функциональная зависимость

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

Логической и методической основой декомпозиции является концепция функциональной зависимости между атрибутами в рассматриваемом отношении.

Определение функциональной зависимости : Если даны два атрибута А и В, то говорят, что В функционально зависит от А, если для каждого значения А существует ровно одно связанное с ним значение В в любой момент времени:

А → В

При этом А и В могут быть не только атомарными, но и составными.

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

Отсутствие функциональной зависимости А В.

 

СТУДУНТ ( НЗК, ФИО, НОМ_ГР )

 НЗК → ФИО

 НЗК  → НОМ_ГР

 

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

Пусть R (A1, A2, …, AN) - схема отношения, X и Y – подмножества (A1, A2, …, AN). Говорят, что Х функционально определяет Y (X→ Y), если в любом отношении R, являющемся текущим значением R, не может содержаться два кортежа, компоненты которых совпадают по всем атрибутам, принадлежащим множеству Х, но не совпадают по одному или более атрибутам принадлежащим множеству Y.

 

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

 

УСПЕВ ( НЗК, ФИО, ДИСЦ., ОЦЕНКА, ДАТА )

НЗК+ДИСЦ. полностью определяет атрибут ОЦЕНКА.

 

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

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

Наличие тех или иных зависимостей в схеме отношения определяет степень ее нормализации.

Существует 4 нормальные формы и еще одна дополнительная нормальная форма Бойса-Кодда.

 

Определение 1 НФ: Отношение находится в 1 НФ если каждый его элемент имеет и всегда будет иметь атомарное строение.

В этом случае реляционное отношение представлено в виде множества неповторяющихся кортежей.

Эта форма является достаточной для работы языков запросов СУБД.

 

Определение 2 НФ: Отношение задано во 2НФ, если оно является отношением в 1 НФ и каждый атрибут не являющийся первичным атрибутом в этом отношении, полностью зависит от любого возможного ключа этого отношения.

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

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

Если ключи составные, отношение заданное в 1НФ может не быть отношением во 2НФ.

ПОСТАВКА (НОМЕР_ИЗДЕЛИЯ, НОМЕР_ПОСТАВЩИКА, ИМЯ_ПОСТАВЩИКА, СВЕДЕНИЯ_О_ ПОСТАВЩИКЕ, ЦЕНА)

НОМЕР_ИЗДЕЛИЯ, НОМЕР_ПОСТАВЩИКА → ЦЕНА

НОМЕР_ПОСТАВЩИКА    →    ИМЯ_ПОСТАВЩИКА     

                                             СВЕДЕНИЯ_О_ ПОСТАВЩИКЕ

 

ПОСТАВКА (НОМЕР_ИЗДЕЛИЯ, НОМЕР_ПОСТАВЩИКА, ЦЕНА)

ПОСТАВЩИК(НОМЕР_ПОСТАВЩИКА, ИМЯ_ПОСТАВЩИКА, СВЕДЕНИЯ_О_ ПОСТАВЩИКЕ)

 

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

 

Определение 3 НФ: Отношение задано в 3 НФ, если оно задано во 2 НФ и каждый атрибут из отношения, не являющийся первичным, нетранзитивно зависит от каждого возможного ключа.

Пусть А, В, С – атрибута реляционного отношения. Если С зависит от В, а В – от А, то С зависит от А. Если при этом обратное соответствие неоднозначно (т.е. А не зависит от В или В не зависит от С), то говорят, что С транзитивно зависит от А.

 

А

 

В

 

С

Преобразование в 3НФ состоит в разбиении исходного отношения на два:

А                                                 В

 

В                                                  С

 

Определение 4 НФ: Схема реляционного отношения задана в 4 НФ, если при существовании многозначной зависимости

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

СЛУЖАЩИЙ

СЛУЖАЩИЙ	ИН.ЯЗЫК	ДОЛЖНОСТЬ	ГОД
Иванов	Английский	инженер	1996
Иванов	Немецкий	инженер	1996
Иванов	Немецкий	Ст.инженер	1998
Иванов	Английский	Ст.инженер	1998
Сидоров	Французский	Вед.инженер	1998
Сидоров	Французский	Руководитель	1999
Сидоров	Испанский	Вед.инженер	1999
Сидоров	Испанский	Руководитель	1999

 СЛУЖАЩИЙ           ИН.ЯЗЫК

  СЛУЖАЩИЙ          ДОЛЖНОСТЬ

Для устранения избыточности выполняет разбиение

 

ЯЗЫК

СЛУЖАЩИЙ	ИН.ЯЗЫК
Сидоров	Французский
Сидоров	Испанский
Иванов	Английский
Иванов	Немецкий

ДОЛЖНОСТЬ

СЛУЖАЩИЙ	ДОЛЖНОСТЬ	ГОД
Сидоров	Вед.инженер	1998
Сидоров	Руководитель	1999
Иванов	Инженер	1996
Иванов	Ст.инженер	1998

 

      Алгоритм декомпозиции

Предлагаемый алгоритм целесообразно использовать, если в БД учитывается порядка 20-30 атрибутов.

Так как в основу алгоритма полагается удовлетворение НФБК, то еще остается 3 нормальная форма, которая налагает еще более жесткие ограничения.

1. Разработка универсального отношения для БД.

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

СЛУЖАЩИЙ

ШИФР	ФАМИЛИЯ	ОБРАЗ-Е	ОТДЕЛ	ДОЛЖН.
0341	Иванов	высшее	31	Инженер
0341	Иванов	высшее	31	Ст. инж-р
0341	Иванов	высшее	31	Вед. Инж-р

Атрибуты ОТДЕЛ и ДОЛЖН. представляют повторяющуюся группу.

Такая корректно заполненная таблица представляет собой универсальное реляционное отношение.

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

3. Определение того, что находится ли отношение в НФБК. Если «ДА» проектирование завершается, если «НЕТ», отношение должно быть разложено на два отношения.

      Декомпозиция выполняется следующим образом:

Пусть отношение R (A, B, C, D, E…) не приведено к нормальной форма Бойса- Кодда.

Определяется функциональная зависимость C → D, про которую известно, что она является причиной того, что отношение не находится в НФБК. С является детерминантом, но не является возможным ключом.  Создаются два новых отношения.

R1 ( A, B, C, E…)

R2 ( C, D )

Отношение R2 называется проекцией отношения R.

Этот метод декомпозиции называется декомпозицией без потерь.

 

УСПЕВАЕМОСТЬ ( НЗК, ФИО, НОМЕР_КОМН.,     НОМЕР_ТЕЛ., ДИСЦ., СЕМЕСТР, ОЦЕНКА)

 

Возможные ключи:

НЗК+ДИСЦ.+СЕМЕСТР

Детерминанты:

НЗК+ДИСЦ.+СЕМЕСТР → ОЦЕНКА

НЗК                                   → ФИО

                                                   НОМЕР_КОМН.

 НОМЕР_КОМН.           →       НОМЕР_ТЕЛ.  

 

УСПЕВАЕМОСТЬ ( НЗК, ДИСЦ., СЕМЕСТР, ОЦЕНКА)

СТУДЕНТ ( НЗК, ФИО, НОМЕР_КОМН.)

ОБЩЕЖИТИЕ ( НОМЕР_КОМН., НОМЕР_ТЕЛ)

 

4. Повторение шагов 2 и 3 для каждого нового отношения, полученного в результате декомпозиции.

 

 УСПЕВАЕМОСТЬ ( НЗК, ДИСЦ., СЕМЕСТР, ОЦЕНКА)

 Возможные ключи:

НЗК +ДИСЦ.+СЕМЕСТР

 Детерминанты:

НЗК +ДИСЦ.+СЕМЕСТР → ОЦЕНКА

Список возможных ключей совпал с списком детерминант,       

следовательно реляционное отношение находится в

НФБК.

 

СТУДЕНТ ( НЗК, ФИО, НОМЕР_КОМН.)

 Возможные ключи:

НЗК

 Детерминанты:

НЗК                                    →    ФИО

                                                          НОМЕР_КОМН.

   Список возможных ключей совпал с списком детерминант,       

следовательно реляционное отношение находится в

НФБК.

 

ОБЩЕЖИТИЕ (НОМЕР_КОМН., НОМЕР_ТЕЛ)

Возможные ключи:

НОМЕР_КОМН.

Детерминанты:

НОМЕР_КОМН.            →      НОМЕР_ТЕЛ.

Список возможных ключей совпал с списком детерминант,       

следовательно реляционное отношение находится в НФБК.

В этом примере можно найти иллюстрацию нормализации реляционного отношения по 2 НФ. Здесь наблюдается транзитивная зависимость

НЗК →     НОМЕР_КОМН.   → НОМЕР_ТЕЛ.

 

ОСНОВЫ РЕЛЯЦИОННОЙ АЛГЕБРЫ

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

Математически отношение определяется следующим образом:

Пусть даны N множеств D1, D2, …, DN, тогда R есть отношение над этими множествами, если R есть множество упорядоченных n-кортежей вида < d₁, d₂, …, d_N> , где d₁ – элемент из D1, d₂ – элемент из D2, d_N – элемент из DN. D1, D2, DN называются доменами отношения R.

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

объединения отношений;

пересечения отношений;

взятия разности отношений;

взятия декартова произведения отношений.

Специальные реляционные операции включают:

ограничение отношения;

проекцию отношения;

соединение отношений;

деление отношений.

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

⇐ Предыдущая234567891011Следующая ⇒

Поделиться: