1.6. Выразимые, именованные и хранимые отношения

С банком данных связаны два набора отношений: множество именованных и множество выразимых отношений. Множество именованных отношений - набор тех отношений, которые сообщество пользователей может идентифицировать посредством простых имен (или идентификаторов). Отношение R входит во множество именованных отношений после его объявления пользователем, обладающим соответствующими правами; оно выходит из этого множества, когда этот пользователь отменяет объявление R.

Множество выразимых отношений - набор всех отношений, которые могут быть описаны выражениями языка данных. Такие выражения состоят из простых имен отношений из множества именованных отношений, имен поколений, ролей и доменов, логических связок, кванторов исчисления предикатов⁶⁾ и некоторых символов константных отношений, таких как >, =. Множество именованных отношений является подмножеством множества выразимых отношений, как правило, очень малым подмножеством.

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

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

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

2. Избыточность и согласованность

2.1. Операции над отношениями.

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

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

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

2.1.1. Перестановка. Бинарное отношение представляется в виде массива с двумя столбцами. В результате перестановки этих столбцов получается обратное отношение. В общем случае, при перестановке столбцов n-арного отношения про результирующее отношение говорят, что оно является перестановкой заданного отношения. Существует, например, 4! = 24 перестановок отношения поставка, приведенного на рис.1, с учетом тождественной перестановки, которая оставляет порядок столбцов неизменным.

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

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

Оператор селекции p используется для получения любой требуемой перестановки, проекции или комбинации этих операций. Так, если L - список из k значений⁷⁾ L = i₁,i₂,...,i_k и R - n-арное отношение (n>=k), то p_L (R) есть k-арное отношение, j-тый столбец которого есть i_j-тый столбец R (j=1,2,...,k) и в котором удалены дубликаты результирующих строк. Рассмотрим отношение поставка на рис.1. Перестановка проекции этого отношения приведена на рис.4. Заметьте, что в этом частном случае проекция имеет меньше n-кортежей, чем исходное отношение.

P31(поставка)	(проект	поставщик)
	5	1
	5	2
	1	4
	7	2

Рисунок 4. Перестановка проекции отношения c рис.1

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

В примере на рис.5 показаны два отношения R, S, которые могут быть соединены без потери информации, а на рис.6 представлен результат соединения R и S. Бинарное отношение R соединимо с бинарным отношением S, если существует тернарное отношение U такое, что p₁₂(U)=R и p₂₃(U)=S. Любое такое тернарное отношение называется соединением R и S. Если R, S являются бинарными отношениями, такими, что p₂(R) = p₂(S), то R соединимо с S. Одно из соединений, которое всегда существует в таком случае, это естественное соединение, определяемое так:

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

где R(a,b) имеет значение истина, если (a,b) является элементом R, и S(b,c) - аналогично. Очевидно, что

p₁₂(R*S) = R

и

p₂₃(R*S) = S.

Заметим, что соединение, показанное на рис.6, является естественным соединением отношений R и S, представленных на рис.5. Другое соединение показано на рис.7.

R	(поставщик	деталь)	S(деталь	проект)
	1	1	1	1
	2	1	1	2
	2	2	2	1

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

R*S	(поставщик	деталь	проект)
	1	1	1
	1	1	2
	2	1	1
	2	1	2
	2	2	1

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

U	(поставщик	деталь	проект)
	1	1	2
	2	1	1
	2	2	1

Рисунок 7. Другое соединение R и S (рис.5)

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

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

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

(1) p₁(T) = p₂(S) (2) p₁(T) = p₁(R) (3) T(j,s) (r) $ p(R(s,p) L S(p,j) (4) R(s,p) (r) $ j(S(p,j) L T(j,s) (5) S(p,j) (r) $ s(T(j,s) L R(s,p)

В этом случае мы можем построить соединение трех отношений R, S, T, то есть тернарное отношение такое, что

p₁₂(U)=R, p₂₃(U)=S, p₃₁(U)=T

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

p₁₂(V)=R, p₂₃(V)=S, p₃₄(V)=T.

Поскольку возможно существование более чем одного циклического 3-соединения (см., например, рис.8,9), обстоятельства, при которых это может происходить, накладывают гораздо более сильные ограничения, чем условия множественности 2-соединений. Более точно, отношения R, S, T должны содержать точки неоднозначности соединений R и S (скажем, точка x), S и T (скажем, y) и T и R ( скажем, z) и, более того, y должно соответствовать x в S, z соответствовать y в T и x соответствовать z в R. Заметьте, что на рис.8 точки 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	e 2

Рисунок 8. Бинарные отношения с несколькими циклическими 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

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

Естественное линейное соединение трех бинарных отношений R, S, T определяется так:

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

где скобки в левой части равенства не нужны, т.к. естественное 2-соединение (*) ассоциативно. Для получения циклического аналога мы введем оператор g, выдающий в качестве результата отношение степени n-1 из отношения степени n, связывая вместе его концы. Таким образом, если R есть n-арное отношение (n>=2), то связывание R определяется уравнением

g(R) = { (a₁, a₂, ....,a_n-1) : R(a₁, a₂, ...., a_n-1, a_n) L a₁=a_n}

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

g(R*S*T).

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

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

2.1.4. Композиция. Читатель, возможно, знаком с понятием композиции применительно к функциям. Мы обсудим обобщение этого понятия и применим его вначале к бинарным отношениям. Наши определения композиции и композиционности основаны непосредственно на определениях соединения и соединимости, приведенных выше.

Предположим, что нам даны два отношения R и S. T является композицией R и S, если существует соединение U отношений R и S такое, что T = p₁₃ (U). Таким образом, два отношения являются композиционными в том и только в том случае, когда они являются соединяемыми. Однако, существование более чем одного соединения R и S не влечет за собой существования более чем одной композиции R и S.

Для естественного соединения R и S существует естественная композиция,⁹⁾ определяемая как

R · S = p₁₃ (R*S) .

Естественная композиция отношений R и S, приведенных на рис. 5, показана на рис.10, другая композиция приведена на рис.11 (получена из соединения, представленного на рис.7).

В случае существования двух или более соединений, количество различных композиций может варьироваться от 1 до общего количества различных соединений. Ha рис.12 представлен пример двух отношений, имеющих несколько соединений и всего одну композицию. Заметьте, что точка неоднозначности c теряется при композиции R и S, т.к. однозначное соответствие устанавливается через точки a,b,d,e.

R.S	(проект	поставщик)
	1	1
	1	2
	2	1
	2	2

Рисунок 10. Естественная композиция отношений R и S (показанных на рис.5)

T	(проект	поставщик)
	1	2
	2	1

Рисунок 11. Другая комрозиция отношений R и S (показанных на рис.5)

R	(поставщик	деталь)	S	(деталь	проект)
	1	a		a	g
	1	b		b	f
	1	c		c	f
	2	c		c	g
	2	d		d	g
	2	e		e	f

Рисунок 12. Много соединений, только одна композиция

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

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

2.1.5. Ограничение. Подмножество отношения является отношением. Один из способов воздействия отношения S на отношение R для получения подмножества R заключается в применении операции ограничения отношения R по отношению S. Эта операция является обобщением ограничения функции на подмножество ее области определения и определяется следующим образом.

Пусть L,M - списки индексных значений одинаковой длины такие, что L=i₁,i₂,...,i_k, M=j₁,j₂, ...,j_k, где k<= степень R и k<= степень S. Тогда L,M ограничение R по S, обозначаемое как R_L|_MS, есть максимальное подмножество R" множества R, такое, что

p_L(R") = p_M (S).

Эта операция определена только в том случае, если применима операция равенства между элементами p_ih(R), с одной стороны и p_jh(S), с другой, для всех h=1,2,...k.

Три отношения R,S,R", приведенные на рис.13, удовлетворяют уравнению R"=R_(2,3)|_(1,2)S.

R ( s р j )	S( р j )	R"( s р j )
1 a A	a A	1 a A
2 a A	c B	2 a A
2 a B	b B	2 b B
2 b A
2 b B

Рисунок 13. Пример сужения

Теперь мы готовы рассмотреть различные применения этих операций над отношениями.