Отношения на множествах

Подмножество RÍ Mⁿ называется n местным отношением на множестве М. Говорят, что а₁,..., а_n находятся в отношении n, если (а₁,...а_n)Î R. Одноместное отношение (свойство, признак) – это просто подмножество М. Наиболее часто встречающиеся и хорошо изученные – бинарные отношения, для них RÍ M². Если а, b находятся в отношении R, то это часто записывают в виде аRb.

Примеры бинарных отношений на множестве людей «быть сыном», «служить в одном полку», «любить», «дружить».

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

Можно определить обратное отношение R^-1. Например, для отношения £ обратным является отношение ³.

Рассмотрим свойства отношений.

Отношение R называется рефлексивным, если для любого аÎ М имеет место аRа. Отношение антирефлексивно, если ни для какого аÎ М не выполняется аRа.

Отношение £ рефлексивно, а отношение «быть сыном» антирефлексивно.

Таким образом, рефлексивность – свойство выполнимости отношения для каждого элемента подмножества R относительно самого себя.

Отношение R симметрично, если из aRb следует bRa (это может быть записано с использованием стрелки следования aRb®bRa). В противном случае отношение R несимметрично, то есть, если aRb истинно, то bRa ложно. Отношение R антисимметрично, если из a_iRa_j и a_jRa_i следует, что a_i=a_j.

Отношение дружбы симметрично. Отношение любви, как правило, несимметрично. Отношение £ антисимметрично, действительно, если а£ b и b£ а, то а=b. Отношение R симметрично тогда и только тогда, когда R=R^-1.

Отношение R транзитивно, если для любых а, b, с из аRb и bRс следует аRс. Это можно записать с использованием знака конъюнкции & (союз «И») и символа ® «следует»:

(аRb)& (bRс)®аRс

Например, отношение «являться начальником» транзитивно. Отношение дружбы нетранзитивно. Для любого отношения R отношение , называемое транзитивным замыканием R, определяется следующим образом: а b, если существует цепочка из n элементов а=а₁, а₂,..., а_n-1, а_n=b, в которой между соседними элементами выполнено R: а₁Ra₂, a₂Ra₃,..., a_n-1Rb.

Транзитивным замыканием отношения «быть сыном» является отношение «быть прямым потомком», являющееся объединением отношений «быть сыном», «быть внуком», «быть правнуком» и т.д.

Отношение называется отношением эквивалентности, если оно рефлексивно, симметрично, транзитивно.

Таково отношение равенства.

Отношение нестрогого порядка рефлексивно, антисимметрично и транзитивно.

Отношение строгого порядка антирефлексивно, антисимметрично и транзитивно.

Отношения £ и ³ для чисел – отношения нестрогого порядка, отношения <, > – отношения строгого порядка.

Пример лексико-графического упорядочения слов в словарях: лесá лето, где á – символ упорядочения.

Отношение доминирования (например, на множестве спортсменов или спортивных команд) обозначается > >. Это отношение антирефлексивно, несимметрично и нетранзитивно.

Отношения (relations) являются основным объектом современных систем управления реляционными базами данных (СУБД), в которых отношения задаются, как правило, на произведении различных множеств. В теории СУБД, в отличие от «академической» записи отношений, принятой в математике используется содержательные записи, например:

< Иван, Мария, цветы, восьмое марта> – четырехместное отношение «Дарить», < Профессор Иванов, студент Петров, отлично> – тернарное отношение «Ставить оценку».

Чаще всего отношения в СУБД задаются таблицами, столбцы которых называют также атрибутами, полями, а строки – кортежами, записями.

Реляционная база данных, то есть база данных, основанных на отношениях, представляет собой совокупность таблиц. Таблица состоит из строк и столбцов. Столбец, то есть поле, задается так называемыми реквизитами: именем, типом (числовой, признаковый и т.д.), длиной, точностью для числовых данных.

Запись, таким образом – это совокупность связанных полей. Таблица – совокупность записей одной структуры. Одно из полей является так называемым первичным ключём, значения которого однозначно указывает на соответствующие ему записи (отношения).