Xreferat.com » Рефераты по математике » Свойства бинарных отношений

Свойства бинарных отношений

alt="Свойства бинарных отношений" width="15" height="17" align="BOTTOM" border="0" />есть следующее множество молодых людей: {Вовочка, Петя, Маша, Лена}, причем известны следующие факты:

Вовочка любит Вовочку (эгоист).

Петя любит Машу (взаимно).

Маша любит Петю (взаимно).

Маша любит Машу (себя не забывает).

Лена любит Петю (несчастная любовь).

Информацию о взаимоотношения данных молодых людей можно описать бинарным отношением "любить", заданном на множестве Свойства бинарных отношений. Это отношение можно описать несколькими способами.

Способ 1. Перечисление фактов в виде произвольного текста (как это сделано выше).

Способ 2. В виде графа взаимоотношений:


Свойства бинарных отношений

Рисунок 1 Граф взаимоотношений

Способ 3. При помощи матрицы взаимоотношений:


Таблица 1. Матрица взаимоотношений

Кого

Кто

Вовочка Петя Маша Лена
Вовочка Любит
Петя Любит
Маша Любит Любит
Лена Любит

Способ 4. При помощи таблицы фактов:


Таблица 2 Таблица фактов

Кто любит Кого любят
Вовочка Вовочка
Петя Маша
Маша Петя
Маша Маша
Лена Петя

С точки зрения реляционных баз данных наиболее предпочтительным является четвертый способ, т.к он допускает наиболее удобный способ хранения и манипулирования информацией. Действительно, перечисление фактов как текстовая форма хранения информации уместна для литературного произведения, но с трудом поддается алгоритмической обработке. Изображение в виде графа наглядно, и его удобно использовать как конечную форму представления информации для пользователя, но хранить данные в графическом виде неудобно. Матрица взаимоотношений уже больше соответствует требованиям информационной системы. Матрица удобна в обработке и компактно хранится. Но одно небольшое изменение, например, появился еще Вася и влюбился в несчастную Лену, требует перестройки всей матрицы, а именно, добавления и колонок, и столбцов. Таблица фактов свободна от всех этих недостатков - при добавлении новых действующих лиц просто добавляются новые строки.

Что касается предиката данного отношения, то он имеет следующий вид (дизъюнктивная нормальная форма):

R (x,y) = { (x = "Вовочка" AND y = "Вовочка") OR (x = "Петя" AND y = "Маша") OR (x = "Маша" AND y = "Петя") OR (x = "Маша" AND y = "Маша") OR (x = "Лена" AND y = "Петя") }

Замечание. Приведенное отношение не является ни транзитивным, ни симметричным или антисимметричным, ни рефлексивным, поэтому оно не является ни отношением эквивалентности, ни отношением порядка, ни каким-либо другим разумным отношением.

Замечание. Большая часть мировой литературы существует и имеет смысл лишь постольку, поскольку бинарное отношение "любить" не является отношением эквивалентности. В частности, по этой причине человечество не разбивается на классы эквивалентности взаимно любящих особей. Изучением характеристик данного отношения и соответствующего ему предиката занималось (и продолжает заниматься) большое количество экспертов, таких как Толстой Л.Н., Шекспир В. и др.


2.2 n-арные отношения (отношения степени n)


В математике n-арные отношения рассматриваются относительно редко, в отличие от баз данных, где наиболее важными являются именно отношения, заданные на декартовом произведении более чем двух множеств.

Пример 6. В некотором университете на математическом факультете учатся студенты Иванов, Петров и Сидоров. Лекции им читают преподаватели Пушников, Цыганов и Шарипов, причем известны следующие факты:

Пушников читает лекции по алгебре и базам данных, соответственно, 40 и 80 часов в семестр.

Цыганов читает лекции по геометрии, 50 часов в семестр.

Шарипов читает лекции по алгебре и геометрии, соответственно, 40 и 50 часов в семестр.

Студент Иванов посещает лекции по алгебре у Шарипова и по базам данных у Пушникова.

Студент Петров посещает лекции по алгебре у Пушникова и по геометрии у Цыганова.

Студент Сидоров посещает лекции по геометрии у Цыганова и по базам данных у Пушникова.

Для того чтобы формально описать данную ситуацию (например, в целях разработки информационной системы, учитывающей данные о ходе учебного процесса), введем три множества:

Множество преподавателей Свойства бинарных отношений= {Пушников, Цыганов, Шарипов}.

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

Множество студентов Свойства бинарных отношений= {Иванов, Петров, Сидоров}.

Имеющиеся факты можно разделить на две группы.1 группа (факты 1-3) - факты о преподавателях, 2 группа (факты 4-6) - факты о студентах.

Для того чтобы отразить факты 1-3 (характеризующие преподавателей и читаемые ими лекции), введем отношение Свойства бинарных отношенийна декартовом произведении Свойства бинарных отношений, где Свойства бинарных отношений - множество рациональных чисел. А именно, упорядоченная тройка Свойства бинарных отношенийтогда и только тогда, когда преподаватель Свойства бинарных отношенийчитает лекции по предмету Свойства бинарных отношенийв количестве Свойства бинарных отношенийчасов в семестр. Назовем такое отношение "Читает лекции по…". Множество кортежей, образующих отношение Свойства бинарных отношенийудобно представить в виде таблицы:


Таблица 3 Отношение "Читает лекции по…"

A (Преподаватель) B (Предмет) Q (Количество часов)
Пушников Алгебра 40
Пушников Базы данных 80
Цыганов Геометрия 50
Шарипов Алгебра 40
Шарипов Геометрия 50

Для того чтобы отразить факты 4-6 (характеризующие посещение студентами лекций), введем отношение Свойства бинарных отношенийна декартовом произведении Свойства бинарных отношений. Упорядоченная тройка Свойства бинарных отношенийтогда и только тогда, когда студент Свойства бинарных отношенийпосещает лекции по предмету Свойства бинарных отношенийу преподавателя Свойства бинарных отношений. Назовем это отношение "Посещать лекции". Его также представим в виде таблицы:


Таблица 4 Отношение "Посещать лекции"

C (студент) B (предмет) A (Преподаватель)
Иванов Алгебра Шарипов
Иванов Базы данных Пушников
Петров Алгебра Пушников
Петров Геометрия Цыганов
Сидоров Геометрия Цыганов
Сидоров Базы данных Пушников

Рассмотрим отношение Свойства бинарных отношенийподробнее. Оно задано на декартовом произведении Свойства бинарных отношений. Это произведение, содержащее 3*3*3=27 кортежей, можно назвать "Студенты-Лекции-Преподаватели". Множество Свойства бинарных отношенийпредставляет собой совокупность всех возможных вариантов посещения студентами лекций. Отношение же Свойства бинарных отношенийпоказывает текущее состояние учебного процесса. Очевидно, что отношение Свойства бинарных отношенийявляется изменяемым во времени отношением.

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

Удобство использования табличной формы для задания отношения определяется в данном случае следующими факторами:

Все используемые множества конечны.

При добавлении или удалении студентов, предметов, преподавателей просто добавляются или удаляются соответствующие строки в таблице.

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

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

Замечание. В таблицу "Посещать лекции" нельзя добавить кортеж (Иванов, Геометрия, Пушников). Действительно, из таблицы "Читает лекции по…", представляющей отношение Свойства бинарных отношений, следует, что Пушников не читает предмет "Геометрия". Оказалось, что таблицы связаны друг с другом, и существенным образом! Это пример семантического ограничения - такое ограничение является следствием нашей трактовки данных, хранящихся в отношении (следствием понимания смысла данных).

3. Транзитивное замыкание отношений


Введем понятие транзитивного замыкания, связанное с бинарными отношениями, которое понадобится в дальнейшем.

Определение 11. Пусть отношение Свойства бинарных отношенийзадано на декартовом квадрате Свойства бинарных отношенийнекоторого множества Свойства бинарных отношений. Транзитивным замыканием отношения Свойства бинарных отношенийназывается новое отношение Свойства бинарных отношений, состоящее из кортежей Свойства бинарных отношений, для которых выполняется:

либо кортеж Свойства бинарных отношений,

либо найдется конечная последовательность элементов Свойства бинарных отношений, такая, что все кортежи Свойства бинарных отношенийпринадлежат отношению Свойства бинарных отношений.

Очевидно, что Свойства бинарных отношений.

Пример 7. Пусть множество Свойства бинарных отношенийпредставляет собой следующее множество деталей и конструкций:

Свойства бинарных отношений= {Болт, Гайка, Двигатель, Автомобиль, Колесо, Ось}

причем некоторые из деталей и конструкций могут использоваться при сборке других конструкций. Взаимосвязь деталей описывается отношением Свойства бинарных отношений ("непосредственно используется в") и состоит из следующих кортежей:


Таблица 5 Отношение R

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

Транзитивное замыкание Свойства бинарных отношенийсостоит из кортежей (добавленные кортежи помечены серым цветом):

Таблица 6 Транзитивное замыкание отношения R

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

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

Выводы


Множество - это неопределяемое понятие, представляющее некоторую совокупность данных. Элементы множества можно отличать друг от друга, а также определять, принадлежит ли данный элемент данному множеству. Над множествами можно выполнять операции объединения, пересечения, разности и дополнения.

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

Отношение - это подмножество декартового произведения множеств. Отношения состоят из однотипных кортежей. Каждое отношение имеет предикат отношения и каждый n-местный предикат задает n-арное отношение.

Отношение является математическим аналогом понятия "таблица".

Отношения обладают степенью и мощностью. Степень отношения - это количество элементов в каждом кортеже отношения (аналог количества столбцов в таблице). Мощность отношения - это мощность множества кортежей отношения (аналог количества строк в таблице).

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

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: