Операции над отношениями.
Поскольку отношения являются множествами, к ним применимы все обычные теоретико-множественные операции. Однако результат может не быть отношением; например, объединение бинарного и тернарного отношений не является отношением.
Операции, обсуждаемые ниже, предназначены специально для отношений. Они вводятся по причине их ключевой роли при получении отношений из других отношений. Основное областью применения этих операций являются информационные системы без логического вывода (т.е. системы, которые не обеспечивают механизм логического вывода), хотя применимость операций не обязательно исчезает при добавлении таких механизмов.
Большинство пользователей не должно быть напрямую связано с этими операциями. Однако проектировщикам информационных систем и людям, занимающимся управлением банком данных, следует знать их в совершенстве.
2.1.1. Перестановка. Бинарное отношение представляется в виде массива с двумя столбцами. В результате перестановки этих столбцов получается обратное отношение. В общем случае, при перестановке столбцов n-арного отношения про результирующее отношение говорят, что оно является перестановкой заданного отношения. Существует, например, 4! = 24 перестановок отношения поставка, приведенного на рис. 1, с учетом тождественной перестановки, которая оставляет порядок столбцов неизменным.
Поскольку пользовательская реляционная модель состоит из набора связей (отношений с неупорядоченными доменами), перестановка не является существенной для такой модели, рассматриваемой отдельно. Она, тем не менее, существенна при рассмотрении хранимых представлений этой модели. В системе, обеспечивающей симметричное использование отношений, множество запросов, на которые может быть получен ответ с использованием хранимого отношения, совпадает с аналогично получаемым множеством для любой перестановки этого отношения. Хотя одновременное хранение отношения и некоторой его перестановки не является логически необходимым, соображения производительности могут сделать это целесообразным.
2.1.2. Проекция. Предположим, что мы выбрали некоторые столбцы отношения (отбросив остальные) и затем удалили из полученного массива все дубликаты строк. Полученный в результате массив представляет отношение, про которое говорят, что оно является проекцией данного отношения.
Оператор селекции π используется для получения любой требуемой перестановки, проекции или комбинации этих операций. Так, если L – список из k значений
L = i1, i2,...,ik, и R – n-арное отношение (n≥k), то πL
(R) есть k-арное отношение, j-тый столбец которого есть ij-тый столбец R (i=1,2,...,k) и в котором удалены дубликаты результирующих строк. Рассмотрим отношение поставка на рис.1. Перестановка проекции этого отношения приведена на рис.4. Заметьте, что в этом частном случае проекция имеет меньше n-кортежей, чем исходное отношение.
| π31(поставка) | (проект | поставщик) |
| 5 | 1 | |
| 5 | 2 | |
| 1 | 4 | |
| 7 | 2 |
2.1.3. Соединение. Предположим, что нам даны два бинарных отношения, имеющих некоторый общий домен. При каких условиях мы можем скомбинировать эти отношения для построения тернарного отношения, сохраняющего всю информацию из данных отношений?
В примере на рис.5 показаны два отношения R и S, которые могут быть соединены без потери информации, а на рис.6 представлен результат соединения 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) ∧ S(b,c)},
где R(a,b) имеет значение истина, если (a,b) является элементом R, и S(b,c) – аналогично. Очевидно, что
π12(R*S) = R
и
π23(R*S) = S.
Заметим, что соединение, показанное на рис.6, является естественным соединением отношений R и S, представленных на рис.5. Другое соединение показано на рис.7.
| R | (поставщик | деталь) | S(деталь | проект) |
| 1 | 1 | 1 | 1 | |
| 2 | 1 | 1 | 2 | |
| 2 | 2 | 2 | 1 |
| R*S | (поставщик | деталь | проект) |
| 1 | 1 | 1 | |
| 1 | 1 | 2 | |
| 2 | 1 | 1 | |
| 2 | 1 | 2 | |
| 2 | 2 | 1 |
| U | (поставщик | деталь | проект) |
| 1 | 1 | 2 | |
| 2 | 1 | 1 | |
| 2 | 2 | 1 |
При обследовании этих отношений обнаруживается элемент (элемент 1) домена деталь (домена, по которому производится соединение), обладающий тем свойством, что он имеет более одного вхождения и в R, и в S. Этот элемент увеличивает количество возможных соединений. Такой элемент домена соединения называется точкой неоднозначности относительно соединения R и S.
Если π21(R) или S являются функциями,
то при соединении R с S не может возникнуть точка неоднозначности. В этом случае естественное соединение является единственным соединением R с S. Заметьте, что повторяющееся уточнение "R с S" является необходимым, поскольку S может быть соединимым с R (как и R с S), и это соединение должно быть предметом полностью отдельного рассмотрения. На рис.5 ни одно из отношений R, π21(R), S, π21(S) не является функцией.
Неоднозначность в соединении R и S может быть иногда разрешена при помощи других отношений. Предположим, что нам даны или мы можем построить на доменах проект и поставщик из источников, не зависимых от R и S, отношение T со следующими свойствами:
- π1(T) = π2(S)
- π1(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, то есть тернарное отношение такое, что
π12(U)=R, π23(U)=S, π31(U)=T
Такое соединение мы будем называть циклическим 3-соединением, чтобы отличать его от линейного 3-соединения, которое представляло бы собой 4-арное отношение V такое, что
π12(V)=R, π23(V)=S, π34(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 |
| 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 |
Естественное линейное соединение трех бинарных отношений R, S, T определяется так:
R*S*T = { (a,b,c,d) : R(a,b) ∧ S(b,c) ∧ T(c,d) },
где скобки в левой части равенства не нужны, т.к. естественное 2-соединение (*) ассоциативно. Для получения циклического аналога мы введем оператор ν, выдающий в качестве результата отношение степени n-1 из отношения степени n, связывая вместе его концы. Если R есть n-арное отношение (n≥2), то связывание R определяется уравнением
ν(R) = { (a1, a2, ....,an-1) : R(a1, a2, ...., an-1, an) ∧ a1=an}
Теперь мы можем представить естественное циклическое 3-соединение R, S, T
выражением
ν(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 = π13
(U). Таким образом, два отношения являются композиционными в том и только в том случае, когда они являются соединяемыми. Однако, существование более чем одного соединения R и S не влечет за собой существования более чем одной композиции R и S.
Для естественного соединения R и S существует естественная композиция,
определяемая как
R · S = π13 (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 |
| T | (проект | поставщик) |
| 1 | 2 | |
| 2 | 1 |
| 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 |
Расширение понятия композиции на пары необязательно бинарных отношений (возможно, с разными степенями) следует тому же подходу, что и расширение понятия попарного соединения таких отношений.
Недостаточное понимание понятия композиции привело некоторых разработчиков систем к ситуации, которую можно назвать ловушкой связей. Эта ловушка может быть проиллюстрирована на следующем примере. Предположим, что описание каждого поставщика связано указателями с описаниями каждой из деталей, поставляемых этим поставщиком, и, аналогичным образом, описание каждой детали связано с описаниями каждого проекта, использующего эту деталь. Напрашивающийся вывод, являющийся, вообще говоря, ошибочным, заключается в том, что если проследовать по всем путям от данного поставщика через детали, поставляемые им к проектам, в которых используются эти детали, то можно получить правильное множество всех проектов, в которых участвует этот поставщик. Такое заключение верно только в очень частном случае, когда искомое отношение между проектами и поставщиками является, по существу, естественным соединением двух других отношений – и конечно, мы должны добавить фразу "в любой момент времени", т.к.
обычно это свойство подразумевает существование требований, относящихся к технике путей доступа.
2.1.5. Ограничение. Подмножество отношения является отношением. Один из способов воздействия отношения S на отношение R для получения подмножества R заключается в применении операции ограничения отношения R по отношению S. Эта операция является обобщением ограничения функции на подмножество ее области определения и определяется следующим образом.
Пусть L, M – списки индексных значений одинаковой длины такие, что L = i1, i2,..., ik, M = j1, j2, ..., jk, где k≤ степень R и k≤ степень S. Тогда L,M-ограничение R по S, обозначаемое как RL|MS, есть максимальное подмножество R' множества R, такое, что
πL(R') = πM
(S).
Эта операция определена только в том случае, если применима операция равенства между элементами πih( R), с одной стороны и pjh(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 |
Теперь мы готовы рассмотреть различные применения этих операций над отношениями.
