Парадигма развития науки (стр. 33 )

Отношения бывают двуместные (или бинарные), трехместные (или тернарные) и вообще п-местные или n-арные, где п — произ­вольное число. Термин «бинарное (двуместное) отношение» говорит о том, что для его представления используется упорядоченная пара элементов.

Формально бинарное отношение (обозначим его R) между двумя множествами M1 и М2 может быть определено как под­множество прямого произведения M1×M2:

R (М1, М2) = {<х, у>| xM1, y M2}.

Другими словами, бинарное отношение R представляет собой множество упорядоченных пар <х, у>. Если xM1, y M2, и дан­ная упорядоченная пара находится в отношении R, то это записы­вается в виде xRy.

п-местным отношением на множествах M1×M2×…×Мп, назы­вается подмножество декартового произведения M1×M2×…×Мп:

R ( M1,M2,…,Мп) = {< х1, х2,...,хп>| x1M1, x2 М2,..., xпMп}.

Множества M1,M2,...,Mп называют областями определения (доменами), т. е. домены — множества, из которых черпаются кон­кретные значения элементов кортежа, п-местное отношение

R(M1,M2,…,Мп) удобно представлять в виде таблицы, где каждая i-я строка есть кортеж <хi1, хi2,...,хiп>, а каждый столбец соответ­ствует одному и тому же компоненту декартова произведения, т. е. в нем могут появляться только элементы из соответствующей об­ласти определения (соответствующего домена).

Очень важное требование к отношениям заключается в том, что каждая строка (кортеж) рассматривается как элемент множества R, а в множествах дубликаты не имеют смысла, т. е., на­пример, множества {1, 2, 3} и {3, 2, 3, 1, 2} считаются эквивалент­ными. Поэтому если в результате операций над отношениями по­являются одинаковые строки, то в результирующем отношении должна остаться только одна из них.

Можно отметить, что n-местное отношение может быть исполь­зовано для представления набора объектов. Рассмотрим отноше­ние, названное ТЕЛЕВИЗОР (табл. 22.1).

Таблица 22.1

Каждая строка в табл. 22.1 выполняет роль описания отдельно­го объекта, а в данном случае атрибуты объекта интерпретируются столбцами отношений. Множество допустимых значений ат­рибута интерпретируется соответствующим доменом. Поэтому столбцы отношений называют также атрибутами и присваивают им имена. В этом случае можно говорить об отображении имен атри­бутов в значения, принадлежащие соответствующим доменам. В общем случае при разработке структуры хранения данных ис­пользуют различные виды таблиц.

Важную роль в процессе обработки данных играет упорядочен­ность строк таблиц. Иногда к таблице подсоединяют дополнитель­ный «внешний» столбец, содержащий последовательность целых чисел от 1 до п, который отражает упорядоченность строк табли­цы. При этом пользователь не имеет доступа к этому столбцу. Та­кая таблица называется последовательной таблицей. В ней каж­дой текущей строчке можно поставить в соответствие предыду­щую строку и последующую.

Упорядочение таблицы может быть произведено и по значени­ям одного из столбцов, соответствующему арбитру. В этом случае она называется упорядоченной.

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

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

Список имен атрибутов отношения называется схемой отношения. Если отношение называется R и его схема имеет атрибуты с именами А1, A2,...,An, то схема отношений будет

R ( А1, A2,...,An).

Для табл. 22.1 схема отношения будет иметь вид: ТЕЛЕВИЗОР (наименование, индекс, диаметр кинескопа, цена).

Можно заметить, что существует аналогия между отношением и файлом, между кортежем и логической записью, между схемой отношения и форматом записи.

Графы. В математике хорошо разработано теоретическое на­правление, позволяющее выражать отношения между объекта­ми в виде специальных рисунков — графов. Граф представляет со­бой набор некоторых точек на плоскости X, которые называют вершинами, и множество отрезков U, соединяющих все или неко­торые вершины. Отрезки U называют дугами или ребрами графа. Например, на рис. 22.3 изображен граф, состоящий из пяти вершин Х={х|х=а, b, с, d, е} и трех ребер U={u|u= (a,b), (a,d), (c,e)}.

Математически граф G можно определить как пару множеств X и U: G(X, U).

Форма представления отношения R в виде графа, заданного на множестве М×М, позволяет элементы множеств М выбрать в качестве вершин, а в качестве дуг изобразить упорядоченные пары элементов

< xi, хj >M×М характеризующие само отношение R. Так как дуга изображается стрелкой, то началу стрелки ставится в соответствие первый элемент кортежа < xi, хj >, а окончанию стрелки — второй.

Рис. 22.3. Пример графа Рис. 22.4. Эквивалентные графы

Так, графу (22.3) можно поставить в соот­ветствие некоторое отношение (<а, b>, <a, d>, <c, е>), заданное на прямом произведении множества М на себя, где М={а, b, с, d, e). Таким образом, при отображении с помощью графов некоторого отношения R между объектами вершины графа будут представ­лять объекты, а дуги — отношения между объектами.

Поскольку граф представляет собой абстрактное геометриче­ское отображение связей между объектами, дуги не обязательно должны быть прямыми, а вершины на плоскости могут быть рас­положены произвольно (рис. 22.4).

В практических задачах типична ситуация, когда связи между объектами являются симметричными, т. е. отношение R выполня­ется как между объектами < xi, хj >, так и между < хj, xi >. В этом случае вместо двух дуг, соединяющих объекты (рис. 22.5, а), мож­но нарисовать одну дугу (рис. 22.5, б).

Рис. 22.5. Неориентированный граф

Когда все дуги в графе изображаются двойной стрелкой, стрелки можно не рисовать (рис. 22.5, в).

Дуги в этом случае называют ребрами, а сам граф — неориен­тированным графом. Граф, в котором задана ориентация дуг, на­зывается соответственно ориентированным графом или орграфом.

Некоторые свойства графов. Иногда удобно представлять графы в виде не­которых матриц, в частности смежности и инциденций.

Две вершины хi и хj являются смежными, если они различны и существует дуга, идущая из хi в хj. Дуга называется инцидентной вершине х, если она заходит в эту вершину или исходит из нее.

Обозначим через х1, х2,..., хi,..., хj,..., xn вершины графа, а через и1,.....,иk,.....,иl его дуги.

Введем числа:

Квадратная матрица ||rij|| порядка n×n называется матрицей смежности графы.

Для построения матрицы инциденций введем числа sil.

Матрица S = ||sil|| порядка n×k называется матрицей инциденций для дуг графа.

Подграфом GA графа G(X, U) называется граф, в который входит лишь часть вершин графа G, образующих множество Аx Х вместе с дугами, соеди­няющими эти вершины.

Путем в графе G называется такая последовательность дуг

μ=(и1,.....,иk), в которой конец каждой предыдущей дуги совпадает с началом следующей.

Контур — это замкнутый путь μ= (и1,.....,иk), у которого начальная вер­шина xi совпадает с конечной xk. Контур единичной длины, образованный дугой вида (xi, xi) называется петлей.