3.4. Способы заданий отношений. Алгебра отношений. Реляционная алгебра

В соответствии с рассмотренным ранее бинарное отношение в множестве V есть подмножество его квадрата А V². Тогда можно дать новое определение графа как совокупности множества V с заданным в нем бинарным отношением А V². Бинарное отношение удобно задать с помощью матрицы смежности, в которой каждый элемент (i, j) взаимно однозначно соответствует элементам множества V². Элемент, принад­лежащий А V², отличается единицей, остальные элементы – нули. Рассмотрим блок-схему ЭВМ фон Неймана (рис.3.18): V= где – устройство ввода; – арифметическое устройство (процессор); с – устройство управления; – запоминающее устройство; – устройство вывода.

Рассмотрим информационный обмел между устройствами v_i и v_j, которые находятся в отношении А, если из устройства v_j поступает информация в устройство v_j. Это отношение может быть задано с мощью матрицы смежности следующим образом [13]:

b c d e

0 1 1 1 0

0 0 1 1 1 b

B = 1 1 0 1 1 c

0 1 1 0 1 d

0 0 1 0 0 e

Граф Д, задаваемый рассмотренным отношениям А, изображен на рис. 3.18.

Рис. 3.18

Рассмотрим еще один способ задания бинарного отношения с помощью фактор-множества. Окрестностью единичного радиуса элемента v_i V называется множество элементов v_j, таких, что (v_i, v_j) V². Множество окрестностей единичное радиуса, взятых для всех элементов множества V при заданном в нем отношении V², называется фактор-множеством V/А множества V по отношению А. Фактор-множество V/А полностью определяет отношение А.

Зададим фактор-множество для рассматриваемого примера в виде двух строк, в первой из которых поместим элементы множества V, во второй – под каждым элементом запишем окрестность единичного радиуса этого элемента. Тогда вторая строка задает фактор-множества V по А:

а ъ с d е

{b, c, d} {c, d, e} {а, Ь, d, ,е} {Ь,с,е} {с}

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

транзитивности и называется отношением упорядоченности и обозначается ≤. Бинарное отношение в множестве V, обладающее свойствами антирефлексивности, антисимметрич-ности и транзитивности, называется отношением строгой упорядоченности и обозначается <. Отношение R в множестве V, обладающее свойствами рефлексивности и транзитивности, называется отношением предпорядка. Задавая те или иные свойства бинарных отношений и используя результаты работ [1, 8, 11, 12], можно прийти к следующей классификационной схеме свойств бинарных отношений (рис. 3.19), из которой следует, что все виды отношений разделяются на классы частичных и линейных (совершенных) отношений порядка. Отношения являются частичными, если элементы не всех пар декартова произведения являются сравнимыми с точки зрения данного отношения; они являются линейными (совершенными), если элементы любой пары декартова произведения V V сравнимы по отношению порядка или равны.

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

Как нетрудно показать, из последнего свойства и свойства антирефлексивности следует транзитивность (для этого достаточно положить v_k = v_j). Таким образом, рассматриваемое отношение есть отношение частичного строгого порядка, обладающее дополнительным качеством квазилейности.

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

Рис. 3.19

С другой стороны, заметим, что антирефлексивное отношение при введении аксиомы полутранзитивности также приобритает свойство транзитивности и становится отношеним частичного строгого порядка, называемым полутразитивным порядком [1.13].

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

Бинарное отношение р называется слаболинейным строгим порядком, если оно антирефлексивно и подчиняется аксиоме:

Данное отношение является полупорядком, в наибольшей степени приближающимся по своим свойствам к свойствам отношения строгого линейного порядка.

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

На рис. 3.19 сплошными линиями со стрелками показаны пути формирования более сложных свойств отношений посредством комбинации более простых. Так, например, объединением свойства симметричности и рефлексивности приводит к толерантности, рефлексивности и транзитивности – к частичному квазипорядку, транзитивности и антирефлексивности – к частичному строгому порядку, линейности и частичного квазипорядка – линейному квазипорядку и т.д. Штриховыми линиями со стрелками показаны пути развития свойств отношений за счет их соответствующего усиления. Характерными в этом отношении является движение от ацикличности к антитранзитивности и от ацикличности к линейному строгому порядку по двум путям, первый из которых связан с постепенным переходом от квазилинейности к линейности (через интервальный порядок, полупорядок и слаболинейный порядок), а второй – с постепенным переходом от полилинейности к линейности (через полилинейный, лесной и древесный порядки).

Для бинарных отношений справедлив принцип двойственности. Отношение, обратное отношению упорядоченности, также является отношением упорядоченности. Часто принцип двойственности формулируют следующим образом: если теорема справедлива для частично упорядоченных множеств, то справедлива и двойственная ей теорема. Аналагично бинарному отношению определим n-арное отношение Т. Под n-арным отношением Т в множестве М понимается подмножество Т его n-й степени Если элементы то говорят, элементы находятся в отношении Т. Любое n-арное отношение может быть задано в виде списка, элементами которого являются последовательности (кортежи), определяемые этим отношением.

С имметричным называется n-арное отношение Т в множестве М, такое, что если то любая последователь­ность получен-ная из пере­становкой элементов, также находится в отношении Т: В дальнейшем n-арное отношение, обладающее свойством симметричности, будем называть S-отношением, или словесным отношением. Элементы множества М, в котором определено S-отношение, будем на­зывать буквами, а подмножества, определяемые S-отношением, - сло­вами и обозначать греческой буквой с нижним индексом. Задавать S-отношение можно более удобными способами: матрицей инцидентности и модельным графом (мографом). Матрицей инцидентности на­зывается матрица, каждому столбцу которой взаимно однозначно соот­ветствует буква, строке – слово, определяемое S-тношением, и

0 в противном случае.

1 при

Например, S-отношение в множестве onpeделяющие слова с помощью матрицы инцидентности можно задать следующим образом [13]:

u o p c ы

0 0 1 1 1 0

0 1 0 1 1 0

B = 0 0 0 1 1 1

1 0 1 0 1 0

Для задания S-отношения с помощью модельного графа каждой букве множества М ставят в соответствие вершину графа и каждой вершине приписывают идентификаторы слов, в которые эта буква входит. Про­цесс сопоставления каждой букве множества идентификаторов слов, в которые эта буква входит, будем называть моделизацией графа G. В результате моделизации графа G каждой вершине взаимно однозначно соответствует буква, взвешенная множеством идентификаторов слов, в которые она входит; при этом две вершины смежны, если им соответст­вует хотя бы один общий идентификатор. Полученную таким образом на графе функцию, областью определения которой являются вершины графа, а областью значений – множества идентификаторов слов, будем назы­вать модельным графом (мографом) и обозначать G^м =(( V, W), E), Здесь W-монжество идентификаторов слов. На рис. З.20 задано З-отношение с помощью модального графа в множестве М= определяемое словами Однозначно задать S-отношение с помощью графа можно, если в качества носителя графа (множество вершин) взять не только множество букв, но и множество идентификаторов слов. Такое задание S-отношение осуществляется двудольным графом. Двудольный граф, задающий З-отношение в множестве изображен на рис. 3.21. Уточним теперь введенное ранее понятие модели. Моделью называется совокупность множества М с заданными в нем отношениями:

где множество М – носитель модели, а заданные отношения образуют сигнатуру модели

Рис. 3.20 Рис. 3.21

Степень носителя определяет арность отношения. Два отношения и имеющие одну и ту же степень, называются совместными по объединению или просто совместимыми.

Очевидно, что n-местную операцию ƒ_n (m₁, m₂,…, m_n) = m_n+1 можно рассматривать как (n+1)-арное отношение R_n+1, Совокупность множества с заданными в нем операциями и отношениями, следуя А. И. Мальцеву, будем называть алгебраической системой [3]. Частным случаем алгебраической системы являются алгебра отношений и ее расширение – реляционная алгебра. Рассмотрим алгебру отношений, носитель который – множество отношений, а сигнатура – операции объединений, пересечения, разности и расширенного декартова произведения отношений.

Объединением двух совместимых отношений и является множество всех кортежей, каждый из которых принадлежит хотя бы одному из этих отношений. Объединением отношений и является

Рассмотренные отношения являются совместимыми, так как их сте­пени равны:

Пересечением R двух совместимых отношений и является множество всех кортежей, принадлежащих как отношению так и отношению Пересечением отношению и является =

Разностью двух совместимых отношений и является множество всех кортежей, принадлежащих отношению и не принадлежащих отношению . Так, например,

Расширенным декартовым произведением двух отношений и является множество всех кортежей таких, что - конкатенация кортежа и кортежа (конкатенация кортежей и , – кортеж

Например, для рассмотренных отношений и расширенное декартово произведение

Понятия модели и алгебры отношений находят широкое применение при формализации реальных объектов. Рассмотрим, как используется алгебра отношений при создании информационного обеспечения – разработке реляционной базы данных [13] .

Основой построения реляционной базы данных является двумерная таблица, каждый столбец которой соответствует домену (или атрибуту), строка – кортежу значений атрибутов, находящихся в отношении R. Рассмотрим 5-арное отношение R₅ (экзамены) (табл. 3.2) специальности автоматизированные системы управления (АСУ) в Кишиневском политехническом институте (часть расписания). Эта таблица определяет отношение реляционной модели данных. Отношение R₅ является подмножеством декартова произведения в котором сомножитель является доменом Д_і. Элементами домена Д_і служат значения ат­рибутов. Домен Д₁ (группа) содержит значения АСУ-891 .АСУ-881, АСУ-882, АСУ-871:

Д₁ = {АСУ-891, АСУ-881, АСУ-882, АСУ-871}.

Аналогично имеем домены:

Д₂ (дисциплина):

Д₂ = {математика, физика, программирование, математические модели информационных процессов, информационная технология}.

Таблица 3.2

R5	Д1	Д2	Д3	Д4	Д5
1.	АСУ-891	Математика	Проф. Иванов	03.01	Ауд. 3-501
2.	АСУ-881	Физика	Проф. Петров	03.01	Ауд. 3-502
3.	АСУ-882	Программирование	Доцент Ильин	03.01	Ауд. 3-505
4.	АСУ-871	Математические модели информационных процессов	Проф. Федоров	06.01	Ауд. 3-504
5.	АСУ-891	Физика	Проф. Петров	09.01	Ауд. 3-504
6.	АСУ-881	Программирование	Доцент Ильин	09.01	Ауд. 3-501
7.	АСУ-882	Математика	Проф. Иванов	10.01	Ауд. 3-502
8.	АСУ-871	Программирование	Проф. Петров	10.01	Ауд. 3-505

Д₃ (экзаменатор):

Д₃= {проф. Иванов, проф. Петров, доцент Ильин, проф. Федоров}.

Д₄ (дата проведения экзамена):

Д₄= {03.01, 06.01, 09,01, 10.01}.

Д₅ (ауд.):

Д₅= {ауд. 3-501, ауд. 3-502, ауд. 3-504, ауд. 3-505}.

Порядок столбцов в таблице фиксирован, строки в общем случае могут располагаться произвольно. Цифры первого столбца 1,2, ..., 8 идентифицируют элементы отношения R₅.

Для преобразования отношений определим реляционную алгебру [13]. Носитель реляционной алгебры представляет собой множество отношений; сигнатура кроме введенных операций (объединения, пересечения, разности расширенного декартова произведения отношений) включает специальные операции над отношениями: выбор, проекцию и соединение. Операция выбора представляет собой процедуру построения горизонтального подмножества отношения, т.е. подмножества кортежей, обладающих заданным свойством. С помощью операции выбора построим отношение (экзамены, проходящие в ауд.3-501). Результатом операции являются строки, в которых домен Д₅ представлен значением ауд.3-501; это 1-я и 6-я строки. (табл.3.3).

Для определения проекции отношений множество в реляционной алгебре разбивается на два подмножества в случае бинарного отношении.

Таблица 3.3

	Д1	Д2	Д3	Д4	Д5
1	АСУ-891	Математика	Проф. Иванов	03.01	Ауд. 3-501
6	АСУ-881	Программирование	Доцент Ильин	09.01	Ауд. 3-501

и на n подмножеств – в случае n -арного отношения:

Проекцией П_р (R₂/А) бинарного отношения на А называется множество элементов . Проекцией П_р n-арного отношения на называется множество кортежей где каждый из которых является частью элемента n-арного отношения R_n. Проекция определяет построение вертикального подмножества отношения, т.е. множества подмножеств кор­тежей, получаемого выбором одних и исключением других доменов. Проекция П_р (R₅/Д₂, Д₃) порождает множество пар, каждая из которых определяет дисциплину и экзаменатора (табл.3.4). Одинаковые строки объединяются в одну. Операция соединения по двум таблицам, имеющим общий домен, позволяет построить одну таблицу, каждая строка кото­рой образует соединение двух строк исходных таблиц.

Из заданных таблиц берут строки, содержащие одно и то же значение из общего домена; общему домену сопоставляют один столбец. Для примера рассмотрим табл. 3.5 и 3.6.

Таблица 3.4

R2	Д2	Д3
	Математика Физика Программирование Математические модели информационных процессов Информационная технология	Проф. Иванов Проф. Петров Доцент Ильин Проф. Федоров Проф. Федоров

Таблица 3.5

R5	Д1	Д2	Д3	Д4	Д5
	АСУ-891 АСУ-881 АСУ-882 АСУ-871	Математика Физика Программирование Математические модели информационных процессов	Проф. Иванов Проф. Петров Доцент Ильин Проф. Федоров	03.01 03.01 03.01 06.01	Ауд. 3-501 Ауд. 3-502 Ауд. 3-505 Ауд. 3-504

Таблица 3.6

R5	Д1	Д2	Д3	Д4	Д5
	АСУ-891 АСУ-881 АСУ-882 АСУ-871	Физика Программирование Математика Информационная технология	Проф. Петров Доцент Ильин Проф. Иванов Проф. Федоров	09.01 09.01 10.01 10.01	Ауд. 3-504 Ауд. 3-501 Ауд. 3-502 Ауд. 3-505

Таблица 3.7

Rg	Д1	Д2	Д3	Д4	Д5	Д/2	Д/3	Д/4	Д/5
	АСУ-891	Матема-тика	Проф. Иванов	03.01	Ауд. 3-501	Мате-матика	Проф. Иванов	03.01	Ауд. 3-501
	АСУ-881	Физика	Проф. Петров	03.01	Ауд. 3-502	Физика	Проф. Петров	03.01	Ауд. 3-502
	АСУ-882	Програ-ммиро вание	Доцент Ильин	03.01	Ауд. 3-505	Програ-ммиро-вание	Доцент Ильин	03.01	Ауд. 3-505
	АСУ-871	Математические модели информационных процессов	Проф. Федоров	06.01	Ауд. 3-504	Математические модели информационных процессов	Проф. Федоров	06.01	Ауд. 3-504
	АСУ-891	Матема-тика	Проф. Иванов	03.01	Ауд. 3-501	Математика	Проф. Иванов	03.01	Ауд. 3-501

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

Операцию соединения можно определить и по другим условиям (>, ≥, ≠, ‹, ≤, и т.д. ). При этом запрос в реляционной базе данных будет выполнен тем быстрее, чем меньше операций над отношениями он содержит. Поэтому к исходным рассматриваемым множествам отношений применяется стратегия преобразования, построенная на основе алгебраических законов и приводящая к минимальному выражению множеств отношений [8,13].

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