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

Лабораторная работа по предмету «Алгебра»
Информация о работе
  • Тема: Отношения и функции. Элементы реляционной алгебры
  • Количество скачиваний: 12
  • Тип: Лабораторная работа
  • Предмет: Алгебра
  • Количество страниц: 4
  • Язык работы: Русский язык
  • Дата загрузки: 2014-12-16 20:34:47
  • Размер файла: 17.6 кб
Помогла работа? Поделись ссылкой
Ссылка на страницу (выберите нужный вариант)
  • Отношения и функции. Элементы реляционной алгебры [Электронный ресурс]. – URL: https://www.sesiya.ru/laboratornaya-rabota/algebra/1010-otnosheniya-i-funkcii-elementy-relyacionnoy-algebry/ (дата обращения: 16.04.2021).
  • Отношения и функции. Элементы реляционной алгебры // https://www.sesiya.ru/laboratornaya-rabota/algebra/1010-otnosheniya-i-funkcii-elementy-relyacionnoy-algebry/.
Есть ненужная работа?

Добавь её на сайт, помоги студентам и школьникам выполнять работы самостоятельно

добавить работу
Обратиться за помощью в подготовке работы

Заполнение формы не обязывает Вас к заказу

Информация о документе

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

Если Вы являетесь автором текста представленного на данной странице и не хотите чтобы он был размешён на нашем сайте напишите об этом перейдя по ссылке: «Правообладателям»

Можно ли скачать документ с работой

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

Лабораторная работа №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. Краткое резюме о проделанной работе.