Модуль 1. Математические основы баз данных и знаний

Лекция 2 Начала отношений 1. Определение отношения 2. Бинарные отношения 3. Способы задания отношений

1. Отношения Подмножество R декартового произведения множеств A 1 x A 2 x…x A n называется отношением степени n (n-арным отношением). Мощность множества кортежей, входящих в отношение R называют мощностью отношения R

1. Отношения Ключевые моменты: все элементы отношения есть однотипные кортежи отношение включает в себя не все возможные кортежи - имеется критерий (предикат отношения ), позволяющий определить, какие кортежи входят в отношение, а какие - нет

1. Отношения Кортеж (а 1,а 2,…,а n ) принадлежит отношению R тогда и только тогда, когда предикат этого отношения P(a 1,a 2,…a n ) принимает значение "истина". Удобно обозначать и отношение и его предикат как R и R(x 1,x 2,…,x n )

2. Бинарные отношения (отношения степени 2) Примеры отношений: Отношение эквивалентности Отношения порядка Функциональное отношение

2. Бинарные отношения (отношения степени 2) Отношения эквивалентности: Отношение R на множестве А 2 есть отношение эквивалентности, если: 1. (х,х) R для всех х А (рефлексивность) 2. Если (х,у) R, то (у,х) R ( симметричность) 3. Если (х,у) R и (у,z) R то (х,z) R (транзитивность)

2. Бинарные отношения (отношения степени 2) Отношения эквивалентности: Аналоги обозначения отношения эквивалентности 1. х х для всех х А (рефлексивность) 2. Если х у то у х ( симметричность) 3. Если х у и у z то х z (транзитивность)

2. Бинарные отношения (отношения степени 2) Отношения эквивалентности: При задании отношения эквивалентности на множестве А, оно разбивается на взаимно непересекающиеся подмножества, состоящие из эквивалентных друг другу элементов (классы эквивалентности)

2. Бинарные отношения (отношения степени 2) Отношения эквивалентности (пример): На множестве целых чисел Z задано отношение «равенство по модулю n» - два числа равны по модулю n, если равны их остатки при делении на n. предикат отношения

2. Бинарные отношения (отношения степени 2) Классы эквивалентности: [0] = {0, n, 2n, } [1] = {1, n+1, 2n+1, } [n-1] = {n-1, n+n-1, 2n+n-1, }

2. Бинарные отношения (отношения степени 2) Отношения порядка: Отношение R на множестве А 2 есть отношение порядка, если: 1. (х,х) R для всех х А (рефлексивность) 2. Если (х,у) R и (у,х) R то х=у (антисимметричность) 3. Если (х,у) R и (у,z) R то (х,z) R (транзитивность)

2. Бинарные отношения (отношения степени 2) Отношения порядка (аналог обозначения): Отношение R на множестве А 2 есть отношение порядка, если: 1. х х для всех х А (рефлексивность) 2. Если х у и у х то х=у (антисимметричность) 3. Если х у и у z то х z (транзитивность)

2. Бинарные отношения (отношения степени 2) Функциональное отношение: Отношение R на декартовом произведении множеств А 1 х А 2 есть функциональное отношение, если: (х,у) R и (х,z) R то у = z (однозначность функции)

3. Способы задания отношений бинарное отношение «любить» на множестве А 2 Пусть множество есть следующее множество молодых людей: {Вовочка, Петя, Маша, Лена}, причем известны следующие факты: Способ 1 – перечисление фактов Вовочка любит Вовочку (эгоист). Петя любит Машу (взаимно). Маша любит Петю (взаимно). Маша любит Машу (себя не забывает). Лена любит Петю (несчастная любовь).

3. Способы задания отношений бинарное отношение «любить» на множестве А 2 Способ 2 – граф

3. Способы задания отношений бинарное отношение «любить» на множестве А 2 Способ 3 – матрица взаимоотношений Кого Кто ВовочкаПетяМаша Лена ВовочкаЛюбит Петя Любит Маша Любит Лена Любит

3. Способы задания отношений бинарное отношение «любить» на множестве А 2 Способ 4 – таблица фактов Кто любитКого любят Вовочка ПетяМаша Петя Маша ЛенаПетя

3. Способы задания отношений бинарное отношение «любить» на множестве А 2 Предикат отношения R(x,y) = {(x = "Вовочка" AND y = "Вовочка") OR (x = "Петя" AND y = "Маша") OR (x = "Маша" AND y = "Петя") OR (x = "Маша" AND y = "Маша") OR (x = "Лена" AND y = "Петя")}

3. Способы задания отношений n-арные отношения В университете учатся студенты Иванов, Петров и Сидоров. Лекции им читают преподаватели Пушников, Цыганов и Шарипов, причем известны следующие факты: Пушников читает лекции по алгебре и базам данных, соответственно, 40 и 80 часов в семестр. Цыганов читает лекции по геометрии, 50 часов в семестр. Шарипов читает лекции по алгебре и геометрии, соответственно, 40 и 50 часов в семестр. Студент Иванов посещает лекции по алгебре у Шарипова и по базам данных у Пушникова. Студент Петров посещает лекции по алгебре у Пушникова и по геометрии у Цыганова. Студент Сидоров посещает лекции по геометрии у Цыганова и по базам данных у Пушникова.

введем три множества: Множество преподавателей А = {Пушников, Цыганов, Шарипов}. Множество предметов В = {Алгебра, Геометрия, Базы данных}. Множество студентов С = {Иванов, Петров, Сидоров}.

Группы фактов: 1 группа (факты 1-3) - факты о преподавателях 2 группа (факты 4-6) - факты о студентах

Отношение R 1 – «Читает лекции по…» упорядоченная тройка (x,y,n) R 1 тогда и только тогда, когда преподаватель x читает лекции по предмету y в количестве n часов в семестр A (Преподаватель) B (Предмет) Q (Количество часов) ПушниковАлгебра40 ПушниковБазы данных 80 ЦыгановГеометрия50 ШариповАлгебра40 ШариповГеометрия50

Отношение R 2 – «Посещать лекции …» упорядоченная тройка (z,y,x) R 2 тогда и только тогда, когда студент z посещает лекции по предмету y у преподавателя х C (студент)B (предмет)A (Преподаватель) ИвановАлгебраШарипов ИвановБазы д-ныхПушников ПетровАлгебраПушников ПетровГеометрияЦыганов СидоровГеометрияЦыганов СидоровБазы д-ныхПушников

3. Способы задания отношений транзитивное замыкание отношений Пусть отношение R задано на декартовом квадрате A 2 некоторого множества. Транзитивным замыканием отношения называется новое отношение состоящее из кортежей, для которых выполняется: либо кортеж (х,у) R, либо найдется конечная последовательность элементов, такая, что все кортежи принадлежат отношению R.

3. Способы задания отношений транзитивное замыкание отношений Пусть множество A представляет собой следующее множество деталей и конструкций: A = {Болт, Гайка, Двигатель, Автомобиль, Колесо, Ось} отношение R ("непосредственно используется в")

3. Способы задания отношений транзитивное замыкание отношений Отношение R: КонструкцияГде используется БолтДвигатель БолтКолесо ГайкаДвигатель ГайкаКолесо ДвигательАвтомобиль КолесоАвтомобиль ОсьКолесо

3. Способы задания отношений транзитивное замыкание отношений КонструкцияГде используется БолтДвигатель БолтКолесо ГайкаДвигатель ГайкаКолесо ДвигательАвтомобиль КолесоАвтомобиль ОсьКолесо БолтАвтомобиль ГайкаАвтомобиль ОсьАвтомобиль