Соединение

( supplier

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

В примере на рис. 4 показаны два отношения R и S, являющиеся соединяемыми без потери информации, а на рис. 5 показано соединение R с S. Бинарное отношение R является соединимым с бинарным отношением S, если существует такое тернарное отношение U, что Π12(U) = R и Π23(U) = S. Любое такое тернарное отношение называется соединением R с S. Если R, S – бинарные отношения, такие что Π2(R) = Π1(S), то R является соединимым с S. Одним из соединений, которое всегда в таком случае существует, является естественное соединение, определяемое как

R*S = {(a, b, c):R(a, b) A S(b, c)},

где R(a, b) принимает значение true, если (a, b) входит в R, и аналогично для S(b, c). Из этого определения немедленно следует, что

Π12(R*S) = R

Π23(R*S) = S.

Заметим, что соединение, показанное на рис. 5, является естественным соединением R с S с рис. 4. Однако оно не является единственным соединением R с S. На рис. 6 показано еще одно возможное соединение отношений с рис. 4.

Рис. 4. Два соединимых отношения

R*S	( supplier	part	project )
	1	1	1
	1	1	2
	2	1	1
	2	1	2
	2	2	1

Рис. 5. Естественное соединение R с S (с рис. 4)

R*S	( supplier	part	project )
	1	1	2
	2	1	1
	2	2	1

Рис. 6. Еще одно соединение R с S (с рис. 4)

При обследовании этих отношений обнаруживается некоторый элемент (элемент 1) домена part (домена, по которому производится соединение), обладающий тем свойством, что он встречается более одного раза и в R, и в S. И именно этот элемент приводит к множественности соединений. Такой элемент домена соединения называется точкой неоднозначности по отношению к соединению R с S.

Если либо Π21(R), либо S является функцией, то при соединении R с S не может возникнуть никакой точки неоднозначности. В этом случае единственным соединением R с S является естественное соединение. Заметим, что повторяющееся уточнение "R с S" является необходимым, поскольку S могло бы быть соединимым с R (как и R с S), и это соединение потребовало бы совершенно отдельного рассмотрения. На рис. 4 ни одно из отношений R, Π21(R), S, Π21(S) не является функцией.

Неоднозначность при соединении R с S иногда можно разрешить при помощи других отношений. Предположим, что имеется или может быть выведено из других источников, независимых от R и S, отношение T на доменах project и supplier со следующими свойствами:

Π1(T) = Π2(S);

Π2(T) = Π1(R);

T(j, s) →
p(R(s, p) ∧ S(p, j));

R(s, p) →
j(S(p, j) ∧ T(j, s));

S(p, j) →
s(T(j, s) ∧ R(s, p)).

Тогда мы можем построить трехстороннее соединение отношений R, S, T, т.е. тернарное отношение U, такое что

Π12(U) = R;

Π23(U) = S;

Π31(U) = T.

Такое соединение мы будем называть циклическим 3-соединением, чтобы отличать его от линейного 3-соединения, которое является кватернарным отношением V, таким что

Π12(V) = R;

Π23(V) = S;

Π34(V) = T.

Хотя может существовать более одного циклического 3-соединения (см., например, рис. 7 и 8), условия, при которых это может случиться, включают намного более строгие ограничения, чем те, которые допускают множественность 2-соединений. Более точно, R, S, T должны содержать точки неоднозначности по отношению к соединению R с S (скажем, точку x), S с T (скажем, y) и T с R (скажем, z). Кроме того, точка y должна быть связана с точкой x в S, точка z с точкой y – в T, и точка x с точкой z – в R. Заметим, что на рис. 7 этим свойством обладают точки

x = a; y = d; z = 2.

R	( s	p )	S	( p	j )	T	( j	s )
	1	a		a	d		d	1
	2	a		a	e		d	2
	2	b		b	d		e	2
				b	e

<

Рис. 7. Бинарные отношения с несколькими циклическими 3-соединениями

U	( s	p	j )	U'	( s	p	j )
	1	a	d		1	a	d
	2	a	e		2	a	d
	2	b	d		2	a	e
	2	b	e		2	b	d
					2	b	e

Рис. 8. Два циклических 3-соединения отношений с рис. 7

Естественное линейное 3- соединение трех бинарных отношений R, S, T определяется следующим образом:

R*S*T = {(a, b, c, d):R(a, b) ∧ S(b, c) ∧ T(c, d)}.

Скобки в левой части не требуются, поскольку естественное 2-соединение (*) ассоциативно. Для получения циклического варианта естественного 3-соединения мы вводим операцию γ, которая производит отношение степени n-1 из отношения степени n путем связывания его крайних точек. Более точно, если R является n-арным отношением, то

γ(R) = ((al, a2, . . . , an-l):R(al, a2, . . . , an-l, an) ∧ al = an).

Тогда естественное циклическое 3-соединение отношений R, S, T можно представить выражением

γ(R*S*T).

Очевидным образом понятия линейного и циклического 3-соединений и из естественных вариантов расширяются на случай соединения n бинарных отношений (где n ≥ 3). Однако стоит сказать несколько слов по поводу соединения отношений, которые необязательно являются бинарными. Рассмотрим случай, в котором отношения R (степени r) и S (степени s) соединяются по p своим доменам (p < r, p < s). Для простоты предположим, что эти p доменов являются последними p из r доменов R и первыми p из s доменов S. Если бы это было не так, мы всегда могли бы добиться этого, применив соответствующие перестановки. Теперь образуем декартово произведение первых r-p доменов R и назовем полученное множество новым доменом A. Аналогично, возьмем декартово произведение последних p доменов R и назовем его доменом B. Возьмем декартово произведение последних s-p доменов S и назовем его C.

Теперь мы можем трактовать R как бинарное отношение на доменах A, B. Аналогично, мы можем трактовать S как бинарное отношение на доменах B, C.В такой трактовке к отношениям непосредственно применимы понятия линейного и циклического 3-соединения. Аналогичный подход можно применить для определения линейного и циклического n-соединения n отношений произвольных степеней.

Содержание раздела