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

Инвертированные файлы.

Данные в этих базах представляются в виде таблицы, и далее вводилось инвертирование (индексирование).

Пусть имеется файл о поставщиках некоторых товаров.

Поставщики:

Код	Фамилия	Категория	Сотрудники
А1	Петров		Москва
А2	Иванов		Тула
А3	Орлов		Орёл
А4	Сидоров		Москва

Инвертированная таблица.

Указатели	Город
bA2	Тула
bА1, bA4	Москва
bА3	Орёл

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

Общие особенности до реляционного периода:

1) Все эти СУБД не строились на строгих моделях манипулирования представления.

2) Фактически в этих БД пользователь располагал низкоуровневым интерфейсом.

3) Неоднозначность представления данных.

В 1970 году опубликовал Кодд.

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

Пример: Отношение “Поставщики”.

Код	Фамилия	Категория	Сотрудники
А1	Иванов		Москва
А2	Петров		Москва
А3	Сидоров		Киев
А4	Орлов		Орёл

Столбцы в данной таблице называются атрибутами.

Каждый конкретный поставщик (экземпляр отношения) размещён в строке- кортеже.

Домен - множество допустимых значений атрибута.

Отношение “Товар”.

Код_тов	Наименование	Цена	Сотрудники
В1	Мяч		Тула
В2	Сетка		Орёл
В3	Шайба		Москва

Совпадение атрибутов связывает таблицы. Связи представляются в виде отношения. Пример:между “поставщиками” и “товарами” существует связь “поставляют”.

Код_пост	Код_тов	Количество
А1	В2
А1	В1
А2	В1
А3	В2
А4	В3

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

Например:

Поставщики (Код_пост, ФИО, Категория, Город).

Товар (Код_тов, Наименование, Цена, Город).

Поставка (Код_пост, Код_тов, Количество).

Любое под множество образует подсхему Б.Д..

При проектировании Б.Д. основными целями являются:

- Каждому внешнему представлению соответствует внешняя подсхема, с которой работает программист.

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

Пример неправильно составленной базы данных:

Номер отдела	Сотрудники
	Петров
	Орлов
	Иванов

Пример правильно составленной базы данных:

Номер отдела	Сотрудники
	Петров
	Орлов
	Иванов

- Отсутствие кортежей дубликатов.

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

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

Реляционная модель данных включает три основные части:

1) Структурная. Структура данных единственна для отношения, находящегося в первой нормальной форме.

2) Манипуляционная. Фиксируется два фундаментальных механизма данных, которые называются реляционной алгеброй и реляционным исчислением. На их базе строится язык SQL.

3) Целостносная. Определяется два требования: а) отличие любого кортежа от другого кортежа этого же отношения; б) Требование ссылочной целостности.

Сотрудники (Код_сотр, ФИО, Год_рожд, Код_должн),

Должность (Код_должн, Наименование, Оклад).

В отношении “должность” первичным ключом является “Код_долж”.

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

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

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

Элементы реляционной алгебры.

Пусть D₁, D₂, D₃,..., D_n - совокупность множества доменов необязательно различных.

D₁* D₂* D₃*...* D_n -называется множество упорядоченных кортежей таких, что

, , ,..., . Отношение R на D₁, D₂, D₃,..., D_n называют декартовым подмножеством D₁* D₂* D₃*...* D_n. Число кортежей входящих в отношение называют кардинальным числом, а число доменов называют степенью отношения.

Рассмотрим пять основных операций:

1. Объединение.

Пусть R, S отношения одинаковой арности. Объединением называют отношение той же арности, множество кортежей которого принадлежит либо R или S, либо обоим отношениям.

Пример.

2. Разность.

Пусть R, S отношения одинаковой арности. Разностью называют множество кортежей, принадлежащих R и не принадлежащих S.

Пример.

3. Декартово произведение.

Пусть R отношение k₁ арности, а S отношение k₂ арности. Декартовым произведением называют множество кортежей длины k₁+ k₂ таких, что первый принадлежит R, а последний к S.

Пример.

4. Проекция.

Пример.

Для получения проекции нужно:

а) Вычеркнуть часть столбцов (атрибутов).

б) Переупорядочить оставшиеся столбцы.

в) Если в полученном отношении оказались одинаковые кортежи, исключить повторяющиеся кортежи.

Пусть R есть отношение k арности и пусть i₁, i₂, i₃,..., i_n, где , есть множество различных целых чисел из диапазона от 1 до k.

Есть множество кортежей а₁, а₂, а₃,..., а_n, для каждого из которых существует кортеж b₁, b₂, b₃,..., b_n из отношения R, такой что

5. Селекция.

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

Пример.

Множество кортежей из “Товар”, в которых атрибут Город=“Москва”.

Очень часто используется операция соединения, и её естественные разновидности. Пусть R отношение арности k₁, а S арности k_2. Пусть и .

Операция соединения определяется через селекцию:

Замечание:

Вместо номеров атрибутов можно использовать имена.

Пример.

Выбираются кортежи, в которых значение В меньше D.

Естественное соединение.

Предполагают, что имеются одноимённые атрибуты, и соединение выполняют по одноимённым атрибутам (по их значениям). При этом одноимённые атрибуты не дублируются.

Пример.

Соединение производится по атрибутам В и С,

На основе реляционной алгебры строится язык манипулирования данными - реляционное исчисление, которое разделяется на а) Исчисление на доменах, б) Исчисление на кортежах.

Единственная структура- это таблица.

Проектирование систем баз данных.

1) Строят концептуальную модель предметной области, максимально отражающую её.

2) Строят схему БД.

3) Должна быть обеспечена возможность хранения всех необходимых данных в БД, исключая избыточность дублирования.

4) Необходимо свести к минимуму число хранимых отношений. Для этого нормализуют отношения для предотвращения аномалий при вставке, удалении, обновлении.

Устранение избыточности.

Пусть имеется некоторое отношение:

Служащий	Начальник	Рабочий тел
Иванов	Котлов	22-22-22
Петров	Орлов	22-45-23
Сидоров	Соколов	22-34-30
Орлов	Котлов	22-22-22

В отношении имеется избыточное дублирование значения атрибута “Рабочий тел” у Котлова.

Пусть преподаватель консультирует студентов, которые проживают в общежитии.

Консультант:

Номер	Имя	Комната	Тел	Предмет	Семестр	Оценка
	Петров			Математика
	Петров			Базы данных
	Петров			Физика
	Петров			Математика
	Иванов			Математика
	Иванов			Алгебра
	Иванов			Физика
	Смирнов			Базы данных
	Смирнов			Английский
	Смирнов			Сети
	Алексеев			Немецкий

В представленном отношении нет атомарности атрибутов.

Аномалия вставки.

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

Аномалия обновления.

Если у Петрова изменился номер комнаты, то нужно изменять четыре кортежа.

Аномалия удаления.

Преподаватель узнаёт, что Алексеев закончил изучение немецкого языка и удаляет его из списка, пропадает информация о комнате и телефоне или оставить Алексеева в списке, но без предмета, что очень неудобно.

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

Определим, что такое функциональная зависимость.

Пусть а и b атрибуты БД.

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

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

На первом этапе выписываются все функциональные зависимости для этого отношения:

Номер Имя

Номер Комната

Номер Телефон

Телефон Комната

Комната Телефон

Номер, Предмет, Семестр Оценка

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

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

(Номер, Имя, Должность, Оклад, Кафедра, Предмет, Часы, Сл. Телефон)

Первичный ключ может быть составным:

(Номер, Предмет, Имя, Должность, Оклад, Кафедра, Часы, Сл. Телефон)

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

НомерДолжностьОклад – транзитивная зависимость.

Выполним декомпозицию.

Преподаватель_предмет (Номер, Предмет, Часы)

Преподаватель (Номер, Имя, Должность, Кафедра)

Кафедра (Кафедра, Сл. Телефон)

Должность (Должность, Оклад)

Все четыре отношения в третьей нормальной форме.

Существуют более сильные требования. В ряде ситуаций 3-я нормальная форма не помогает, тогда применяют третью нормальную форму Бойса-Кодда.

Определения:

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

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

Пример. Отношение “Консультант”.

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

Детерминанты: Имя, Комната, Тел, Оценка.

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

Сведение к НФБК устраняет большинство аномалий при проектировании БД.

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

1. Разрабатывается отношение в 1 НФ.

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

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

4. Для полученных отношений повторяют шаги 2 и 3.

Пусть имеется отношение R(А, В, С, D, E,...). Пусть имеет место функциональная зависимость

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

То есть функциональная зависимость выделяется в отдельное отношение.

Такая декомпозиция происходит без потерь при естественном соединении.

Пример. Пусть существуют

Появились два лишних кортежа.

Декомпозиция отношения консультант:

Номер, Предмет, СеместрОценка

Номер Имя

Номер Комната

Номер Телефон

Телефон Комната

Комната Телефон

Консультант (Номер, Имя, Комната, Тел, Предмет, Семестр, Оценка)

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

Применим это к отношению “Консультант”.

R₁ ( Номер, Предмет, Семестр, Имя, Комната, Оценка )

R₂ ( Комната, Телефон )

R₃ ( Номер, Предмет, Семестр, Оценка )

R₄ ( Номер, Имя, Комната ).

Таким образом, окончательно получаем:

R₂ ( Комната, Телефон )

R₃ ( Номер, Предмет, Семестр, Оценка )

R₄ ( Номер, Имя, Комната ).

R₂: R₄:

Номер	Имя	Комната
	Петров
	Иванов
	Смирнов
	Алексеев

Комната	Тел

R₃:

Номер	Предмет	Семестр	Оценка
	Математика
	Базы данных
	Физика
	Математика
	Математика
	Алгебра
	Физика
	Базы данных
	Английский
	Сети
	Немецкий

Существенно сократилось число кортежей.

Дата добавления: 2014-01-20