ТЕОРИЯ МНОЖЕСТВ ОТНОШЕНИЯ

– д.т.н., проф. Хаханов В.И.
ДИСКРЕТНАЯ МАТЕМАТИКА

изучить операции над отношениями для применения в задачах компьютерной инженерии
Содержание:

Понятие n-местного отношения.
Совместимость отношений
Операции над отношениями
Реляционная алгебра
Дополнительные операции над отношениями
Пример применения отношений при составлении реляционной базы данных

Тема: Отношения

9-12 с.
Лавров И.А., Максимова Л.Л. Задачи по теории множеств,

математической логике и теории алгоритмов. М.: Наука. Главная редакция физико-математической литературы, 1984. 8-12 с.
Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М.: Энергия, 1980. 12-21 с.
Богомолов А.М., Сперанский Д.В. Аналитические методы в задачах контроля и анализа дискретных устройств. Саратов: Изд-во Саратовского ун-та, 1986. 240с.
Новиков Ф.А. Дискретная математика для программистов. С.-П., 2001. С. 4-24.
Хаханов В.І., Хаханова І.В., Кулак Е.М., Чумаченко С.В. Методичні вказівки до практичних занять з курсу “Дискретна математика”. Харків, ХНУРЕ. 2001. 21-23 с.

декартово (прямое) произведение множеств
Ключевые слова:
отношение,
степень отношения,
совместимость

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

множества М:
RnМn
Элементы х1, х2, …, хn находятся в отношении,

если (х1, х2, …, хn)Rn
n – степень отношения (-арность)
RA2 – бинарное отношение;
RA3 – тернарное отношение;
RAn – n-арное отношение
Совместимые отношения – отношения одинаковых степеней

Определение отношения

операции:

(c,d,e)}
операции объединения, пересечения и разности определяются так:

ab ={(a,b,c), (a,b,d), (b,c,e),

(b,d,e), (c,d,e)};
ab ={ (a,b,d) };
a\b ={(a,b,c), (b,c,e) }

(c,a), (c,c) }
Пусть универсальное  и бинарное b отношения задаются

следующим образом:
 =AB={ (a,a), (a,c), (b,a), (b,c) }
b={ (a,c), (c,a) }  B2
Дополнение отношения b есть:
b= \b=(AB)\b={ (a,a), (b,a), (b,c) }

Пример 2

(a,e) },
b={(a,b,c), (b,d,e)}
Расширенное декартово произведение
отношений a и b определяется

как
ab = { (a,b,a,b,c), (a,b,b,d,e), (c,d,a,b,c), (c,d,b,d,e), (a,e,a,b,c), (a,e,b,d,e) }

модель (множество с заданным отношением) широко применяются при формализации реальных

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

Алгебра отношений. 1

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

проекцию,
соединение
В соответствии с потребностями практики вводятся и другие операции:
обмен позициями;
удвоение позиций;
свертка, композиция.

знаешь?
С: Предмет знаю.
П: Какой предмет?
С: Который сдаю.
П: А какой сдаешь?
С:

Ну, это Вы придираетесь.
Ваш, конечно!

отношение реляционной модели данных:
D1
D2
D3
D4
D5
b
g

D3 по значению атрибута c2 ;
a2 – проекция по домену

D5 ;
a3 – проекция по доменам D2, D5 ;
a4 – соединение по домену D1 по условию «равно» для двух таблиц b (первые четыре кортежа R5) и g (вторые четыре кортежа R5).

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

по домену D3 по значению c2 :
D1
D2
D3
D4
D5
b
g

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

отношениями. Выбор. 2

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

по одному домену определяет совокупность элементов и не является отношением:
a2 – проекция по домену D5:
a2={g1,g2}

Пример специальных операций над отношениями. Проекция. 1

D1

D2

D3

D4

D5

b

g

2 и более в зависимости от количества столбцов, по которым

ведется проецирование:

a3 – проекция по доменам D2, D5:

Пример специальных операций над отношениями. Проекция. 2

D1

D2

D3

D4

D5

b

g

универсального бинарного отношения R2AB на множество А называется совокупность элементов

Pr(R2/A)={ai | (ai,bi)R2}

Def: проекцией Pr(Rn/Ai1,Ai2,…,Aim) универсального n-арного отношения Rn Ai1Ai2…Ain на множества Ai1,Ai2,…,Aim называется совокупность кортежей (ai1,ai2,…,aim), где aijAij, каждый из которых является частью n-арного вектора из отношения Rn:
Pr(Rn/Ai1,Ai2,…,Aim)={(ai1,ai2,…,aim)| aij Aij , j=1,2,…,m}

по домену D1 по условию «равно» для двух таблиц b

(первые четыре кортежа R5) и g (вторые четыре кортежа R5):

позволяет построить одну таблицу, каждая строка которой образуется соединением двух

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

Пример специальных операций над отношениями. Соединение. 2

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

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

подмножество декартова произведения двух множеств;
в) подмножество декартова произведения любого конечного
количества

множеств;
г) подмножество декартовой степени множества;
д) результат объединения данных множеств;
е) результат пересечения данных множеств.

2. Отношения являются совместимыми:
а) всегда;
б) если они имеют разные степени;
в) если они имеют одинаковые степени;
г) если они бинарные.
3. Операция выбора представляет собой построение:
а) «горизонтального» подмножества отношения;
б) «вертикального» подмножества отношения;
в) «диагонального» подмножества отношения;
г) «бинарного» подмножества отношения;

в) «диагонального»
подмножества отношения.
5. Операция проекции по двум доменам представляет

собой построение:
а) «горизонтального» подмножества отношения;
б) «вертикального» подмножества отношения;
в) «диагонального» подмножества отношения;
г) бинарного подмножества отношения.

6. Операция проекции по одному домену представляет собой построение:
а) «горизонтального» подмножества отношения;
б) «вертикального» подмножества отношения;
в) «диагонального» подмножества отношения;
г) бинарного подмножества отношения;
д) некоторого отношения степени n;
е) множества элементов, не являющегося отношением.