§ 8. Отношения (обобщение). Алгебраические

СИСТЕМЫ

Рассмотренные бинарные отношения являются составной частью множества отношений .

Подмножество называется n – арным отношением на множестве М.

Запись Mⁿ означает декартово произведение n равных множеств М, т.е.

Элементы находятся в отношении R , если кортеж

Степень декартового произведения равных множеств М определяет арность отношения.

Отношение называется бинарным отношением ; называют тернарным отношением .

Два отношения и , имеющие одну и ту же степень, называются совместимыми.

Операции над отношениями

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

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

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

4. Расширенным декартовым произведением двух отношений является множество всех кортежей таких, что - конкатенация кортежа и кортежа .

Конкатенация кортежей является кортеж

Пример. Даны совместимые отношения :

Определить объединение, пересечение, разность этих отношений.

□ 1. .

2. .

3. . ■

Пример. Пусть заданы множества М₁ = {a,b},

= ; М₂ = {a,c},

= .

□ Выберем отношения и следующим образом : . Тогда дополнением отношения является следующее отношение: = . ■

Пример. Даны отношения , . Определить расширенное декартово произведение этих отношений.

□ Расширенное декартово произведение будет иметь вид:

. ■

Алгебраические системы

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

Частными случаями алгебраической системы являются: решетка, модель, алгебра отношений, реляционная алгебра.

Моделью называется совокупность множества М с заданными в нем отношениями :

,

где множество М – носитель модели, S – сигнатура модели, представляющая собой множество отношений различной арности.

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

Реляционная алгебра – это алгебра отношений с дополнительными операциями над отношениями : выбора, проекции, соединения.

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

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

Пример. Рассмотрим 5-арное отношение R₅ :

R₅ = ,

или

D₁ D₂ D₃ D₄ D₅

.

□ Данная таблица определяет отношение реляционной модели данных. Отношение R₅ является подмножеством декартова произведения доменов

.

Элементами домена D_i служат значения атрибутов. Порядок столбцов в таблице фиксирован, строки в общем случае могут располагаться произвольно.

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

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

Для определения проекций отношений множество в реляционной алгебре разбивается на два подмножества в случае бинарного отношения и на n подмножеств в случае n – арного отношения:

Ø , ;

Ø,

Проекцией Пр (R₂ / A) бинарного отношения R₂ , R₂ , на А называется множество элементов Пр ( R₂ / A )= .

Проекцией Пр ( R_n / ) n – арного отношения

на называется множество кортежей , где , каждый из которых является частью элемента n – арного отношения R_n .

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

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

Пусть требуется определить результаты выполнения операций :

- выбора по домену D₃ по значению c₂ ;

- проекции по домену D₅ ;

- проекции по доменам D₂ , D₅ ;

- соединения по домену D₁ для двух таблиц: первые четыре кортежа R₅ и вторые четыре кортежа R₅ .

Результаты операций будут следующие :

;

;

;

.

Если отношение R₅ описывает “экзамены”, то значениями атрибутов домена D₁ (a_i , i= ) могут быть шифры студенческих групп; значениями атрибутов домена D₂ (b_i , i= ) – названия дисциплин; домена

D₃ (c_i , i= ) – фамилии экзаменаторов; домена D₄ ( f_i , i= ) – даты экзаменов; домена D₅ (g_i , i=1,2 ) – номера аудиторий.

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

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

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