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

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

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

• 1. Пушников читает лекции по алгебре и базам данных, соответственно, 40 и 80 часов в семестр.
• 2. Цыганов читает лекции по геометрии, 50 часов в семестр.
• 3. Шарипов читает лекции по алгебре и геометрии, соответственно, 40 и 50 часов в семестр.
• 4. Студент Иванов посещает лекции по алгебре у Шарипова и по базам данных у Пушникова.
• 5. Студент Петров посещает лекции по алгебре у Пушникова и по геометрии у Цыганова.
• 6. Студент Сидоров посещает лекции по геометрии у Цыганова и по базам данных у Пушникова.

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

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

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

Для того чтобы отразить факты 1-3 (характеризующие преподавателей и читаемые ими лекции), введем отношение Ri на декартовом произведении А X В X Q , где Q - множество рациональных чисел. А именно, упорядоченная тройка (х, у, п) Є R_r тогда и только тогда, когда преподаватель х читает лекции по предмету у в количестве п часов в семестр. Назовем такое отношение «Читает лекции по...». Множество кортежей, образующих отношение Ri удобно представить в виде таблицы:

Таблица 2.3

Отношение «Читает лекции по...»

Для того чтобы отразить факты 4 6 (характеризующие посещение студентами лекций), введем отношение R2 на декартовом произведении С X В X А . Упорядоченная тройка (z,y,x) Є R₂ тогда и только тогда, когда студент z посещает лекции по предмету у у преподавателя х. Назовем это отношение «Посещать лекции». Его также представим в виде таблицы:

Таблица 2.4

Отношение «Посещать лекции»

Рассмотрим отношение R; подробнее. Оно задано на декартовом произведении ?1— С х В х А. Это произведение, содержащее 3*3*3=27 кортежей, можно назвать «Студенты-Лекции-Преподаватели». Множество Q представляет собой совокупность всех возможных вариантов посещения студентами лекций. Отношение же R? показывает текущее состояние учебного процесса. Очевидно, что отношение Rj является изменяемым во времени отношением.

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

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

• 1. Все используемые множества конечны.
• 2. При добавлении или удалении студентов, предметов, преподавателей просто добавляются или удаляются соответствующие строки в таблице.

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

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

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

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

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

Определение. Пусть отношение R задано на А² некоторого множества Л. Транзитивным замыканием отношения R называется новое отношение R , состоящее из кортежей (х,у) , для которых выполняется:

• либо кортеж (х,у) Є R,

• либо найдется конечная последовательность элементов (z_t,z₂, ???<^zn) ^є А , такая, что все кортежи (х, z_t), (z_t,z₂),(z_n,y) принадлежат отношению R.

Очевидно, что R Є R.

Например, пусть множество А представляет собой следующее множество деталей и конструкций:

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

Таблица 2.5

Отношение R

Транзитивное замыкание R состоит из кортежей:

Таблица 2.6

Транзитивное замыкание отношения R1

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