Отображение и функции ХНУРЭ, кафедра ПО ЭВМ, Тел. 7021-446, e-mail: belous@kture.Kharkov.ua Лекции 3-4 Н.В. Белоус Факультет компьютерных наук Кафедра. - презентация

1 Отображение и функции ХНУРЭ, кафедра ПО ЭВМ, Тел , Лекции 3-4 Н.В. Белоус Факультет компьютерных наук Кафедра ПО ЭВМ, ХНУРЭ Компьютерная дискретная математика

2 Функциональные отношения Отношение R множеств X и Y (R X Y ) является функциональным, если все его элементы (упорядоченные пары) (x,y) различны по первому элементу: каждому x X либо соответствует только один элемент y Y, такой, что xRy, либо такого элемента y вообще не существует. 2

3 Матрица и граф функционального отношения Матрица функционального отношения, заданного на конечных множествах X и Y, содержит не более одной единицы в каждой строке. Если функциональное отношение задано в виде графа, то из каждой вершины, изображающей первую координату, выходит не более одной дуги. 3 а) функциональное б) функциональное в) не функциональное отношение отношение отношение a1a1 a2a2 a1a1 a2a2 a1a1 b1b1 b2b2 b1b1 b1b1 b2b2

4 Функциональные отношения Пример Пример. A – множество кроликов; B – множество клеток R – отношение размещения кроликов по клеткам – Кролик - Клетка. R – функциональное отношение (каждому кролику может соответствовать только одна клетка). 4

5 Функциональные отношения Продолжение примера Продолжение примера. Обозначим кроликов буквами, а клетки – номерами. A={a,b}, B={1,2,3}. R 1 ={(a,1),(b,3)} R 2 ={(a,1),(b,1)} a b a b a b a b Примеры функциональных отношений Кролик – Клетка R1R1 R2R2

6 Функциональные отношения Продолжение примера. 6 R3R3 Пример нефункционального отношения : R 3 ={(a,1),(a,2),(b,3)}.

7 Область определения и область значений отношения Пусть R – некоторое отношение, R X Y. Областью определения отношения R называется множество D R, состоящее из всех элементов множества X, которые связаны отношением R с элементами множества Y: D R X, D R ={x: у Y,(x,y) R}. Областью значений отношения R называется множество R, состоящее из всех элементов множества Y, которые связаны отношением R с элементами множества X: R Y, R ={y: x X,(x,y) R}. 7

8 Функция или отображение Пусть F функциональное отношение, F X Y. Соответствие x y от первого ко второму элементу каждой пары (x,y) F отношения F называется функцией f или отображением f множества D F в Y и обозначается как f : D F Y 8

9 Область определения и область значений функции Множество D F называется областью определения или задания функции (отображения) f и обозначается как D f ( D F ). Говорят также, что функция f действует из X в Y и определена на подмножестве D f из X. Если D f = X(=D F ), то пишут f: X Y и говорят, что задано отображение X Y. 9

10 Область определения и область значений функции Если множество A X, то через f(A)={y Y: y=f(x), x A} обозначается образ множества A. Множество f(X) Y называется образом или областью значений отображения f и обозначается через f = f(X). Если множество B Y, то множество f –1 (B)={x X: f(x) B} называется прообразом множества B относительно отображения f. 10

11 График функции (отображения) Графиком функции (отображения) f: X Y называется совокупность «двумерных» точек (x,y) вида (x,f(x)) в декартовом произведении X Y. Если F X Y исходное функциональное отношение, порождающее функцию (отображение) f, то F в точности есть график функции f. Не путать понятия «график функции f» и «граф отношения F»: граф с помощью дуг со стрелками описывает действие отображения f на каждом значении аргумента x. 11

12 Типы отображений. Сюръективное отображение Функция f: X Y называется сюръективным отображением, если f = Y. На графе, представляющем сюръективное отображение X Y, из любой вершины x X выходит в точности одна дуга, а в любую вершину, представляющую элемент множества Y, входит не менее одной дуги. 12

13 Типы отображений. Сюръективное отображение 13 Пример сюръективного отображения x1x1 x2x2 x3x3 x4x4 y1y1 y2y2 y3y3 Сюръективное отображение Кролик - Клетка; X =6, Y =4 Пример Пример.

14 Типы отображений. Инъективное отображение Функция f: X Y называется инъективным отображением, если из x 1 x 2 следует f(x 1 ) f(x 2 ). На графе, представляющем инъективное отображение X Y из любой вершины x X выходит в точности одна дуга, а в любую вершину, представляющую элемент множества Y, входит не более одной дуги. 14

15 Типы отображений. Инъективное отображение 15 Пример инъективного отображения x1x1 x2x2 x3x3 y1y1 y2y2 y3y3 y4y4 Инъективное отображение Кролик - Клетка; X =6, Y =8 Пример Пример.

16 Типы отображений. Биективное отображение Функция f: X Y называется биективным отображением, если она сюръективна и инъективна. На графе, представляющем биективное отображение X Y конечных множеств, из любой вершины x X выходит в точности одна дуга, а в любую вершину y Y входит одна и только одна дуга. 16

17 Типы отображений. Биективное отображение Биективное отображение f: X Y осуществляет взаимно однозначное отображение между множествами X и Y, поэтому X~Y, X = Y 17 Пример биективного отображения x1x1 x2x2 x3x3 y1y1 y2y2 y3y3 Биективное отображение Кролик - Клетка; X =6, Y =6 Пример Пример.

18 Обратное отображение Если F: X Y биективно, то существует обратное отображение F -1 : Y X, причем D F -1 =Y. 18

19 Реляционная модель данных и реляционная алгебра С математической точки зрения табличное представление данных легко формулируется в терминах теории отношений и поэтому к нему применим аппарат теории множеств. Такая модель данных называется реляционной.Пример: 19 ФамилияИнициалыГруппа АлексеевИ.А.ПО- 01 АндрееваО.П.ПМ-01 БарановН.П.ПМ-01 БыковаН.А.ПО- 01 ВолковВ.В.ПМ- 01

20 Терминология реляционной алгебры Элементы отношения, соответствующие строкам таблицы, называются кортежами. Множества (или области данных, на которых определено отношение), соответствующие столбцам таблицы, называются доменами. Наименования столбцов таблицы называют атрибутами. Схемой отношения является список атрибутов. 20

21 Реляционная модель данных и реляционная алгебра домены: 21 И.А О.П Н.П Н.А В.В. Алексеев Андреева Баранов Быкова Волков ПМ-01 ПО-01

22 Реляционная модель данных и реляционная алгебра атрибуты 22 ФамилияИнициалыГруппа АлексеевИ.А.ПО-01 АндрееваО.П.ПМ-01 БарановН.П.ПМ-01 БыковаН.А.ПО-01 ВолковВ.В.ПМ-01 кортежи

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

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

25 Операции алгебры отношений Пересечение отношений. При выполнении операции пересечения двух отношений ( ) получаем отношение, включающее только те кортежи, которые входят в оба отношения-операнда. 25 Схема выполнения операции

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

27 Операции алгебры отношений Пример Пример. 27 ФамилияИнициалыГруппа АлексеевИ.А.ПО- 01 АндрееваО.П.ПМ-01 БарановН.П.ПМ-01 БыковаН.А.ПО- 01 ВолковВ.В.ПМ- 01 СТУДЕНТ 1 ФамилияИнициалыГруппа АлексеевИ.А.ПО- 01 БыковаН.А.ПО- 01 ДроздовИ.К.ПО-01 ЗайцевО.Н.ПМ-01 КузнецоваЕ.В.ПО- 01 СТУДЕНТ 2 отношений отношений \ отношений Дальше

28 Операции алгебры отношений Продолжение примера Продолжение примера. 28 ФамилияИнициалыГруппа АлексеевИ.А.ПО- 01 БыковаН.А.ПО- 01 СТУДЕНТ 1 СТУДЕНТ 2

29 Операции алгебры отношений Продолжение примера Продолжение примера. 29 ФамилияИнициалыГруппа АлексеевИ.А.ПО- 01 АндрееваО.П.ПМ-01 БарановН.П.ПМ-01 БыковаН.А.ПО- 01 ВолковВ.В.ПМ- 01 ДроздовИ.К.ПО- 01 ЗайцевО.Н.ПМ-01 КузнецоваЕ.В.ПО- 01 ВСЕ СТУДЕНТЫ = СТУДЕНТ 1 СТУДЕНТ 2

30 Операции алгебры отношений Продолжение примера Продолжение примера. 30 ФамилияИнициалыГруппа АндрееваО.П.ПМ-01 БарановН.П.ПМ-01 ВолковВ.В.ПМ-01 СТУДЕНТ 1 \ СТУДЕНТ 2

31 Операции алгебры отношений Прямое произведение отношений. При выполнении прямого произведения ( ) двух отношений получаем отношение, множество кортежей которого является декартовым произведением множеств кортежей первого и второго операндов. 31 Схема выполнения операции прямого произведения отношений

32 Операции алгебры отношений Пример Пример. Рассмотрим отношения КУРС и СТУДЕНТ 1 32 Уч. годКурс КУРС СТУДЕНТ 1 КУРС= КУРС СТУДЕНТ 1 ФамилияИнициалыГруппа АлексеевИ.А.ПО- 01 АндрееваО.П.ПМ-01 БарановН.П.ПМ-01 БыковаН.А.ПО- 01 ВолковВ.В.ПМ- 01 СТУДЕНТ 1

33 Операции алгебры отношений 33 ФамилияИнициалыГруппаУч. годКурс АлексеевИ.А.ПО АлексеевИ.А.ПО АндрееваО.П.ПМ АндрееваО.П.ПМ БарановН.П.ПМ БарановН.П.ПМ БыковаН.А.ПО БыковаН.А.ПО ВолковВ.В.ПМ ВолковВ.В.ПМ КУРС СТУДЕНТ 1 На предыдущий

34 Операции алгебры отношений Ограничение отношения. Результатом ограничения ( ) отношения по некоторому атрибуту или атрибутам является отношение, включающее кортежи отношения- операнда, которые удовлетворяют этому условию. 34

35 Операции алгебры отношений Пример Пример. Выполним ограничение отношения ВСЕ СТУДЕНТЫ по атрибуту Группа=ПО-01. Назовем результат – СТУДЕНТ ПО ФамилияИнициалыГруппа АлексеевИ.А.ПО- 01 БыковаН.А.ПО- 01 ДроздовИ.К.ПО- 01 КузнецоваЕ.В.ПО- 01 СТУДЕНТЫ ПО-01 На предыдущий

36 Операции алгебры отношений Проекция отношения. При выполнении проекции отношения ( ) на заданный набор его атрибутов отношение-результат получается путем удаления из отношения-операнда атрибутов, не указанных в заданном наборе. 36 Схема выполнения операции проекции отношения

37 Операции алгебры отношений Пример Пример. Выполним проекцию отношения КУРС СТУДЕНТ 1 по атрибутам Группа, Уч. год, Курс 37 ГруппаУч. годКурс ПО ПО ПМ ПМ Группа, Уч. год, Курс (КУРС СТУДЕНТ 1) КУРС СТУДЕНТ 1

38 Операции алгебры отношений Естественное соединение отношений. При естественном соединении двух отношений ( >< ) образуется результирующее отношение, кортежи которого являются соединением кортежей первого и второго отношений, если значение общих атрибутов совпадает. 38 Схема выполнения операции естественного соединения отношений

39 Операции алгебры отношений Пример Пример. Рассмотрим отношение НОМЕР 39 ФамилияИнициалыЗачетка NСтуд N АлексеевИ.А АндрееваО.П БарановН.П БыковаН.А ВолковВ.В ДроздовИ.К ЗайцевО.Н КузнецовЕ.В НОМЕР На предыдущий

40 Операции алгебры отношений Продолжение примера Продолжение примера. 40 ФамилияИнициалыГруппаЗачетка NСтуд N АлексеевИ.А.ПО БыковаН.А.ПО ДроздовИ.К.ПО КузнецовЕ.В.ПО СТУДЕНТ ПО-01 >< НОМЕР СТУДЕНТ ПО-01НОМЕР

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

42 Операции алгебры отношений Пример Пример. Произведем деление отношения НОМЕР на отношение ФАМИЛИЯ СТ ПО Зачетка NСтуд N НОМЕР ФАМИЛИЯ СТ ПО 01 НОМЕР ФАМИЛИЯ СТ ПО 01