Презентация на тему: ТЕОРИЯ МНОЖЕСТВ ОТНОШЕНИЯ

ТЕОРИЯ МНОЖЕСТВ ОТНОШЕНИЯ
Цель лекции – ознакомиться и овладеть понятиями «отношение», «алгебра отношений», изучить операции над отношениями для применения в задачах компьютерной
ТЕОРИЯ МНОЖЕСТВ ОТНОШЕНИЯ
ТЕОРИЯ МНОЖЕСТВ ОТНОШЕНИЯ
ТЕОРИЯ МНОЖЕСТВ ОТНОШЕНИЯ
ТЕОРИЯ МНОЖЕСТВ ОТНОШЕНИЯ
ТЕОРИЯ МНОЖЕСТВ ОТНОШЕНИЯ
ТЕОРИЯ МНОЖЕСТВ ОТНОШЕНИЯ
ТЕОРИЯ МНОЖЕСТВ ОТНОШЕНИЯ
ТЕОРИЯ МНОЖЕСТВ ОТНОШЕНИЯ
ТЕОРИЯ МНОЖЕСТВ ОТНОШЕНИЯ
ТЕОРИЯ МНОЖЕСТВ ОТНОШЕНИЯ
ТЕОРИЯ МНОЖЕСТВ ОТНОШЕНИЯ
ТЕОРИЯ МНОЖЕСТВ ОТНОШЕНИЯ
ТЕОРИЯ МНОЖЕСТВ ОТНОШЕНИЯ
ТЕОРИЯ МНОЖЕСТВ ОТНОШЕНИЯ
ТЕОРИЯ МНОЖЕСТВ ОТНОШЕНИЯ
ТЕОРИЯ МНОЖЕСТВ ОТНОШЕНИЯ
ТЕОРИЯ МНОЖЕСТВ ОТНОШЕНИЯ
ТЕОРИЯ МНОЖЕСТВ ОТНОШЕНИЯ
ТЕОРИЯ МНОЖЕСТВ ОТНОШЕНИЯ
ТЕОРИЯ МНОЖЕСТВ ОТНОШЕНИЯ
Память с ассоциативным доступом
Память с ассоциативным доступом 1
Память с ассоциативным доступом 2
Память с ассоциативным доступом 3
Выводы
Выводы: схема взаимосвязей между понятиями
ТЕОРИЯ МНОЖЕСТВ ОТНОШЕНИЯ
ТЕОРИЯ МНОЖЕСТВ ОТНОШЕНИЯ
1/30
Средняя оценка: 4.2/5 (всего оценок: 6)
Код скопирован в буфер обмена
Скачать (2360 Кб)
1

Первый слайд презентации: ТЕОРИЯ МНОЖЕСТВ ОТНОШЕНИЯ

ЛЕКЦИЯ 3 Факультет компьютерной инженерии и управления, кафедра АПВТ, ХНУРЭ ДИСКРЕТНАЯ МАТЕМАТИКА

Изображение слайда
2

Слайд 2: Цель лекции – ознакомиться и овладеть понятиями «отношение», «алгебра отношений», изучить операции над отношениями для применения в задачах компьютерной инженерии

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

Изображение слайда
3

Слайд 3

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

Изображение слайда
4

Слайд 4

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

Изображение слайда
5

Слайд 5

Def : n -местным отношением на множестве M называется подмножество декартовой степени множества М: R n  М n Элементы х 1, х 2, …, х n находятся в отношении, если (х 1, х 2, …, х n )  R n n – степень отношения (-арность) R  A 2 – бинарное отношение; R  A 3 – тернарное отношение; R  A n – n -арное отношение Совместимые отношения – отношения одинаковых степеней Определение отношения Множества Декартово произведение A  B, М 1  М 2 … М n Декартова степень М n Отношение R n  М n

Изображение слайда
6

Слайд 6

Операции над отношениями. 1 Для совместимых отношений α  A n, β  В n имеют место следующие операции: Название операции Определение Объединение отношений Пересечение отношений Разность отношений

Изображение слайда
7

Слайд 7

Операции над отношениями. 2 Название операции Определение Дополнение β отношения β до универсального отношения  =А В есть разность  \ β β =  \ β = ( А В )\ β Расширенное декартово произведение α  β ( α и β могут быть несовместимыми ) p – конкатенация кортежа k α с кортежем k β

Изображение слайда
8

Слайд 8

Пример 1 Для совместимых тернарных отношений a,b M 3 a ={(a,b,c), (a,b,d), (b,c,e)} b ={ (a,b,d), (b,d,e), (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) }

Изображение слайда
9

Слайд 9

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

Изображение слайда
10

Слайд 10

Пример 3 Даны отношения a A 2, b A 3 a = { (a,b), (c,d), (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 ) }

Изображение слайда
11

Слайд 11

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

Изображение слайда
12

Слайд 12

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

Изображение слайда
13

Слайд 13

Time Out Преподаватель (П) и студент (С): П: Знаешь? С: Знаю! П: Что знаешь? С: Предмет знаю. П: Какой предмет? С: Который сдаю. П: А какой сдаешь? С: Ну, это Вы придираетесь. Ваш, конечно!

Изображение слайда
14

Слайд 14

Пример специальных операций над отношениями. Постановка задания. 1 Таблица определяет отношение реляционной модели данных : D 1 D 2 D 3 D 4 D 5 b g

Изображение слайда
15

Слайд 15

Определить результаты выполнения следующих операций : a 1 – выбор по домену D 3 по значению атрибута c 2 ; a 2 – проекция по домену D 5 ; a 3 – проекция по доменам D 2, D 5 ; a 4 – соединение по домену D 1 по условию «равно» для двух таблиц b ( первые четыре кортежа R 5 ) и g ( вторые четыре кортежа R 5 ). Пример специальных операций над отношениями. Постановка задания. 2

Изображение слайда
16

Слайд 16

Пример специальных операций над отношениями. Выбор. 1 a 1 – выбор по домену D 3 по значению c 2 : D 1 D 2 D 3 D 4 D 5 b g

Изображение слайда
17

Слайд 17

Def: операция выбора представляет собой процедуру построения «горизонтального» подмножества отношения, т.е. подмножества кортежей, обладающих заданным свойством Пример специальных операций над отношениями. Выбор. 2

Изображение слайда
18

Слайд 18

Def: операция проекции определяет построение «вертикального» подмножества отношения или множества кортежей, получаемого выбором одних и исключением других доменов Проекция по одному домену определяет совокупность элементов и не является отношением: a 2 – проекция по домену D 5 : a 2 = {g 1,g 2 } Пример специальных операций над отношениями. Проекция. 1 D 1 D 2 D 3 D 4 D 5 b g

Изображение слайда
19

Слайд 19

Проекция по двум и более доменам является отношением степени 2 и более в зависимости от количества столбцов, по которым ведется проецирование: a 3 – проекция по доменам D 2, D 5 : Пример специальных операций над отношениями. Проекция. 2 D 1 D 2 D 3 D 4 D 5 b g

Изображение слайда
20

Слайд 20

Пример специальных операций над отношениями. Проекция. 3 Def: проекцией Pr(R 2 /A) универсального бинарного отношения R 2 AB на множество А называется совокупность элементов Pr(R 2 /A) = {a i | (a i,b i ) R 2 } Def: проекцией Pr(R n /A i 1,A i 2,…,A i m ) универсального n -арного отношения R n  A i 1  A i 2  …  A i n на множества A i 1,A i 2,…,A i m называется совокупность кортежей ( a i 1,a i 2,…,a i m ), где a i j A i j, каждый из которых является частью n - арного вектора из отношения R n : Pr(R n /A i 1,A i 2,…,A i m ) = {(a i 1,a i 2,…,a i m )| a i j A i j, j=1,2,…,m}

Изображение слайда
21

Слайд 21

Пример специальных операций над отношениями. Соединение. 1 a 4 – соединение по домену D 1 по условию «равно» для двух таблиц b (первые четыре кортежа R 5 ) и g (вторые четыре кортежа R 5 ): D 1 D 2 D 3 D 4 D 5 b g

Изображение слайда
22

Слайд 22

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

Изображение слайда
23

Слайд 23: Память с ассоциативным доступом

Память с ассоциативным доступом В ассоциативной памяти поиск информации выполняется исходя из некоторого признака данных, а не по их расположению – адресу или номеру в очереди.. Ячейка ассоциативной памяти содержит два поля: поле признака, называемого тэгом или образом (pattern) и поле данных. При выборке входные данные одновременно сравниваться со всеми полями признака во всех ячейках памяти. При сравнении может быть использовано все слово или набор указанных разрядов входного слова. Разновидностью ассоциативной памяти является CAM (Content Addressable Memory). При обращении в данной памяти на выход поступает адрес ячейки, содержимое которой соответствует признаку поиска. Если значение с выхода CAM подать на вход RAM будет построено полное ассоциативное ЗУ.

Изображение слайда
24

Слайд 24: Память с ассоциативным доступом 1

Изображение слайда
25

Слайд 25: Память с ассоциативным доступом 2

Ассоциативная память используется для кэшированмя данных. Для модификации логических адресов в системах с виртуальной организацией памяти, при аппаратной интерпретации алгоритмов поиска данных: в телекомуникациях, сетях, Ethernet и иных протокольных приложениях. Для выбора реализации CAM для конкретного преложения необходимо оценить следующие параметры: • Word Size (width) • Number of Words (depth) • Match or Compare time (read) • Significance of Write Speed • Clock Frequency • Masks and Outputs Постоянная ассоциативная память(доступна только операция чтения) представляет собой дешифратор, построенный на переключательных таблицах(рис). Каждый LUT представляет собой 4-вх компаратор

Изображение слайда
26

Слайд 26: Память с ассоциативным доступом 3

В первом случае память имеет малое время анализа данных, но требует большое время для записи в память. Второй вариант позволяет легко создавать память большого объема, но при этом память требует достаточно больших временных затрат на поиск информации. Ассоциативную память можно реализовать используя: 1) встроенные сдвиговые регистры SRL16E или SRLC16; 2) распределенную память; 3) выделеные блоки памяти Block SelectRAM+

Изображение слайда
27

Слайд 27: Выводы

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

Изображение слайда
28

Слайд 28: Выводы: схема взаимосвязей между понятиями

Множества Декартово произведение A  B, A 1  A 2 …  A n Декартова степень A n Операции, законы Соответствия G  A  B Отношения R n  A n A k = < N k, S k > Классификация соответствий Свойства + = + = Операции, законы + A r = < N r, S r > =

Изображение слайда
29

Слайд 29

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

Изображение слайда
30

Последний слайд презентации: ТЕОРИЯ МНОЖЕСТВ ОТНОШЕНИЯ

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

Изображение слайда