3.1. Операции

J K

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

Объединение

Предположим, что HR1 HR2 (а значит, n p), т. е. предполагается, что отношения R1 и R2 имеют одинаковое количество атрибутов, совпадающих с точностью до их перестановки.

def

Определение 1. Объединением отношений R1 и R2 называется отношение R R1 Y R2 HR; BR , где

def

HR HR1 HR2 ;

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

Пересечение

Опять же предположим, что HR1 HR2 (а значит, n p), т. е. отношения R1 и R2 имеют одинаковое количество атрибутов, совпадающих с точностью до их перестановки.

def

Определение 2. Пересечением отношений R1 и R2 называется отношение R R1 X R2 HR; BR , где

def

HR HR1 HR2 ;

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

Разность

Вновь предполагаем, что HR1 HR2 (а значит, n p), т. е. отношения R1 и R2 имеют одинаковое количество атрибутов, совпадающих с точностью до их перестановки.

15

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

Декартово произведение

А здесь мы не накладываем никакие условия на отношения R1 и R2, описанные в начале параграфа. Введем дополнительное определение:

Определение 4. Два отношения R1 и R2 называются совместимыми по операции произведения, если они не имеют одинаковых атрибутов в своих заголовках, т. е. HR1 X HR2 .

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

Определение 5. Декартовым произведением (или просто произведением) совместимых по произ-

def

ведению отношений R1 и R2 называется отношение R R1 R2 HR; BR , где

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

Замечание. Произведение можно определить и для отношений, имеющих одинаковые атрибуты (т. е. совпадают имя и домен), т. е. для отношений R1 и R2, у которых HR1 X HR2 . Для этого используется оператор RENAME, который переименовывает подаваемый атрибут для получения атрибута с уникальным именем (например, если имя отношения есть Rname, а имя атрибута этого отношения есть Aname, то можно переименовать этот атрибут в Rname.Aname). И перед тем, как получить результирующее отношении одинаковые атрибуты отношений-операндов переименовываются, т. е. отношения становятся совместимыми по произведению, а значит, для них будет справедливо изложенное определение декартова произведения.

Декартово произведение редко используется в силу его некоторой неосмысленности на практике:

•кардинальность результата велика (равна произведению кардинальностей отношенийоперандов),

•результат не более информативен, чем взятые в совокупности операнды,

чаще используются его вариации — операции соединения.

Сокращение (выборка, ограничение, селекция)

16

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

Проекция

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

Соединения

Можно выделить несколько видов соединений:

•-соединение,

•эквисоединение,

•естественное соединение,

•левые, правые и полные внешние соединения.

Пусть P tă; ď; ą; ě; ; u — некоторая операция сравнения. Пусть задана предикатная фор-

является отношение, содержащее в заголовке атрибуты обоих отношений, и с кортежами, являющимися конкатенациями (объединениями) тех кортежей T1 первого отношения-операнда с кортежами T2

второго отношения-операнда, для которых выполняется (истинно) условие T1:AR1 T2:AR2 .

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

17

Замечание. Нетрудно видеть, что -соединение отношений является «подмножество» декартова произведения этих отношений. А именно -соединение можно выразить через выборку и декартово произведение так:

R1 'F R2 F pR1 R2q :

Частным случаем -соединения, который чаще всего используется, является соединение по эквивалентности:

Определение 9. Соединением по эквивалентности (по равенству, эквисоединением) отноше-

ний R1 и R2 по атрибутам R1:AR1 и R2:AR2 называется -соединение этих отношений по условию

R1:AR1 R2:AR2 .

Эквисоединение обычно происходит по ключевым полям — первичный ключ в одном отношении и внешний ключ во втором отношении.

Существует еще тоже нередко используемое естественное соединение, для вычисления которого надо знать только отношения-операнды и ничего больше (остальное вычисляется самой операцией). Пусть A — множество общих атрибутов отношений R1 и R2 (т. е. имеют одинаковые имена и домены, а также имеют одинаковый смысл, A Ď HR1 и A Ď HR2 ), все остальные атрибуты различны.

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

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

Пусть опять же имеется некоторый оператор сравнения P tă; ď; ą; ě; ; u и задана предикатная формула F F pAR1 ; AR2 q R1:AR1 R2:AR2 .

Определение 11. Левым внешним -соединением отношений R1 и R2 по условию F называется от-

def

ношение R R1 'F R2 HR; BR , где

HR HR1'F R2 ;

!

BR BR1'F R2 Y T1 Y pAR12 ; DR12 ; !q Y : : : Y pARp2 ; DRp2 ; !q

T1 P BR1 ^ @T2 P BR2 qF pT1:AR1 ; T2:AR2 qy FALSE( :

Замечание. Левое внешнее -соединение отношений R1 и R2 отличается от -соединения лишь тем, что дополнительно добавляются кортежи, образованные кортежами отношения R1, части которых не входят в обычное -соединение, к которым добавляются атрибуты отношения R2 с неопределенными значениями !.

1 Заметим, что можно написать и pHR1 zAq Y pHR2 zAq Y A HR1 Y HR2 , но в этой упрощенной записи надо понимать, что атрибуты из множества A должны быть в HR только по одному экземпляру.

2 В реализациях неопределенные значения ! обычно обозначаются как NULL.

18