Отношения и функции. Элементы реляционной алгебры

Лабораторная работа №2

Отношения и функции. Элементы реляционной алгебры

Цель работы: Познакомится с понятиями отношений и функций, научится выполнять операции над отношениями.
Теоретические основы

Определение. Упорядоченной парой x, y называется совокупность двух элементов x и y, расположенных в определенном порядке.
Две упорядоченные пары x, y и u, v равны межу собой тогда и только тогда, когда x = u и y = v.
Пример: a, b, 1, 2, x, 4 – упорядоченные пары.
Аналогично можно рассматривать тройки, четверки, n-ки элементов x1, x2, … xn.
Определение. Прямым (или декартовым) произведением двух множеств A и B называется множество упорядоченных пар, таких, что первый элемент каждой пары принадлежит множеству A, а второй – множеству B:
A  B = {a, b: aА и b В}.
В общем случае прямым произведением n множеств А1, А2,… Аn называется множество А1  А2  … Аn, состоящее из упорядоченных наборов элементов a1, a2, …, an длины n, таких, что i- ый ai принадлежит множеству Аi.
Пример: пусть А = {1, 2}, В = {2, 3}, тогда A  B = {1, 2, 1, 3,2, 2,2, 3}.
Определение. Бинарным (или двуместным) отношением R называется подмножество декартова произведения AB, то есть R  AB
Если пара x, y принадлежит R, то это записывается следующим образом: x, y  R или, что то же самое, xR y.
Так как бинарное отношение – множество, то способы задания бинарного отношения такие же, как и способы задания множества (см. разд. 1.1). Бинарное отношение может быть задано перечислением упорядоченных пар или указанием общего свойства упорядоченных пар.
Определение. Областью определения бинарного отношения R называется множество DR = {x: существует y, что xR y}.
Определение. Областью значений бинарного отношения R называется множество ER = {y:существует x, что xRy}.
Определение .Отношение называется обратным к отношению R (обозначается R –1), если R –1 = {x, y:  y, x  R}.
Пример:
R = {1, 2, 2, 3, 3, 4}.
R–1= {2, 1, 3, 2, 4, 3}.
Свойства отношений
Определение. Отношение R называется рефлексивным на множестве X, если для любого x  X выполняется xR x.
Определение. Отношение R называется симметричным на множестве X, если для любых x, y  X из xR y следует yR x.
Очевидно, что R симметрично тогда и только тогда, когда R = R–1.
Определение. Отношение R называется антисимметричным на множестве X, если для любых x, y  X из xRy и yR x следует x = y.
Из определения антисимметричности следует, что всякий раз, когда пара x, y принадлежит одновременно R и R–1, должно выполняться равенство x = y. Другими словами, R  R–1 состоит только из пар вида  x, x .
Определение. Отношение R называется транзитивным на множестве X, если для любых x, y, z  X из xRy и yR z следует xR z.
Определение. Отношение R называется отношением эквивалентности на множестве X, если оно рефлексивно, симметрично и транзитивно на множестве X.
Определение. Пусть R – отношение эквивалентности на множестве X и x  X. Классом эквивалентности, порожденным элементом x, называется подмножество множества X, состоящее из тех элементов y  X, для которых xRy. Класс эквивалентности, порожденный элементом x, обозначается через [x].
Таким образом, [x] = {y X : x R y}.
Классы эквивалентности образуют разбиение множества X, т. е. систему непустых попарно непересекающихся его подмножеств, объединение которых совпадает со всем множеством X.
Определение. Отношение R называется отношением частичного порядка (или просто частичным порядком) на множестве X, если оно рефлексивно, антисимметрично и транзитивно на множестве X. Множество X в этом случае называют частично упорядоченным и указанное отношение часто обозначают символом , если это не приводит к недоразумениям.
Отношение, обратное отношению частичного порядка будет, очевидно, отношением частичного порядка.
Функции. Основные понятия и определения
Определение. Функцией называется любое бинарное отношение, которое не содержит двух пар с равными первыми компонентами и различными вторыми.
Пример:
а) {<1, 2>, <3, 4>, <4, 4>, <5, 6>} – функция.
б) {<x, y>: x, y  R, y = x2} – функция.
в) {<1, 2>, <1, 4>, <4, 4>, <5, 6>} – отношение, но не функция.
Определение. Функции f и g равны, если их область определения – одно и то же множество D, и для любого x  D справедливо равенство f(x) = g(x).
Определение. Функция, реализующая отображение X1  X2 ... Xn Y называется n-местной функцией.
Пример:
Сложение, вычитание, умножение и деление являются двуместными функциями на множестве R действительных чисел, т. е. функциями типа R2  R.
Элементы реляционной алгебры
Так как отношения являются множествами, то все операции над множествами (объединение, пересечение, разность, симметрическая разность) справедливы для отношений.
В реляционной алгебре кроме теоретико-множественных используются и другие операции.
А) Обмен позициями: обозначается (ij)R, при выполнении операции элементы, входящие в кортеж под номерами i и j, меняются местами (операция выполняется над всеми кортежами множества R.
Б) Расширение отношения: обозначается аR, при выполнении операции некоторый элемент а будет записан слева в каждый кортеж множества R.
В) Исключение позиции: обозначается (i, j, …,k)R, при выполнении операции из позиций с номерами i, j, …,k будут удалены элементы. Операция выполняется для каждого кортежа множества R.
Г) Удвоение позиции: обозначается DjR, при выполнении операции элемент, находящийся в j-ой позиции повторно записывается в каждый кортеж множества R справа.




Задание к работе

Сформировать декартово произведение множеств АВ (A задаётся не более чем m случайными неповторяющимися цифрами, В задаётся не более, чем n случайными неповторяющимися цифрами), составить бинарное отношение R, выполнить над R указанные операции (независимые друг от друга).
Вариант выбирается по последней цифре зачётной книжки. Если стоит «0», то выбирается 10 вариант.
Варианты заданий
1 вариант 2 вариант 3 вариант 4 вариант 5 вариант
m 6 7 5 7 6
n 6 5 7 6 8
Отношение R Больше на 2 или на 3 Меньше на 1 или на 2 больше или равно Делится без остатка Не делится нацело
Операции над R 1.Обратное отношение.
2. Удвоение 1-ой позиции.
1.Обмен позициями.
2. Удвоение 2-ой позиции.
1.Обратное отношение.
2. Исключение 1-ой позиции.
1.Исключение 2-ой позиции.
2. Удвоение 1-ой позиции 1.Расширение отношения на случайный элемент
2. Удвоение 1-ой позиции
6 вариант 7 вариант 8 вариант 9 вариант 10 вариант
m 5 6 6 7 6
n 6 7 5 7 7
Отношение R Больше на 3 или на 4 Меньше на 3 или на 4 больше или равно Делится без остатка Не делится нацело
Операции над R 1.Обратное отношение.
2. Удвоение 1-ой позиции.
1.Обмен позициями.
2. Удвоение 2-ой позиции.
1.Обратное отношение.
2. Исключение 1-ой позиции.
1.Исключение 2-ой позиции.
2. Удвоение 1-ой позиции 1.Расширение отношения на случайный элемент
2. Удвоение 1-ой позиции


Контрольные вопросы

1. Укажите способы задания бинарного отношения.
2. Для какого отношения  всегда выполняется условие  = –1?
3. Укажите способы задания функций.
4. Проверьте, какие свойства выполняются для следующих отношений:
а) отношение "жить в одном городе";
б) отношение "жить дальше на 20 км";
в) отношение "быть старше".
Содержание отчета
1. Постановка задачи.
2. Листинг программы.
3. Результат работы программы.
4. Ответы на контрольные вопросы.
5. Краткое резюме о проделанной работе.