Реляционная Алгебра

к.э.н., доцент Д.Г. Корнеев
2009 год

«Базы данных»
Лекция № 2

качестве операндов и возвращают отношение в качестве
результата.

Первая версия

этой алгебры была определена Коддом.
Эта "оригинальная" алгебра включала восемь операций, которые
подразделялись на описанные ниже две группы с четырьмя операциями каждая.

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

Специальные реляционные операции, такие как сокращение (известное также под названием выборки), проекция, соединение и деление.

элементов, принадлежащих либо к одному из них, либо к обоим

заданным множествам.
Поскольку любое отношение представляет собой (или, скорее, содержит) множество (а именно множество кортежей), оно, безусловно, позволяет формировать объединение двух таких множеств; результатом является множество, состоящее из всех кортежей, присутствующих либо в одном, либо в обоих из заданных отношений.
Например, объединение множества кортежей поставщиков, которые в настоящее время присутствуют в S, и множества кортежей деталей, присутствующих в настоящее время в
отношении Р, безусловно, представляет собой множество.

S# }

Поставки P { P#, PNAME, COLOR,
WEIGHT, CITY } PRIMARY

KEY
{ P# }

SP { S#, P#, QTY }
PRIMARY KEY { S#, P# }
FOREIGN KEY { S# } REFERENCES S
FOREIGN KEY { P# } REFERENCES P

он не является отношением; отношения не могут содержать смесь кортежей

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

таким: если даны отношения А и В одного и того

же типа, то объединение этих отношений А UNION В является отношением того же типа с телом, которое состоит из всех кортежей t, при-
сутствующих в А или В или в обоих отношениях.

показанный на рис. (оба они получены из текущего значения отношения

поставщиков S;
В «А» приведены данные о поставщиках из Лондона, а в «В» — данные о поставщиках, которые поставляют деталь Р1). В таком случае в объединение A UNION В (см. рис. а) входят поставщики, которые либо находятся в Лондоне, либо поставляют деталь Р1, либо соответствуют обоим этим условиям.
Обратите внимание на то, что в результате содержатся три кортежа, а не четыре; по определению отношения никогда не содержат дубликаты кортежей (поэтому, неформально выражаясь, из результатов операции объединения "устраняются дубликаты").

той же причине, для реляционной операции пересечения требуется, чтобы ее

операнды принадлежали к одному и тому же типу.
Если даны отношения А и В одного и того же типа, то пересечением этих отношений А INTERSECT В является отношение того же типа с телом, состоящим из всех кортежей t,
таких, что t присутствует одновременно в А и В.

В показаны на рис. Тогда пересечение A INTERSECT В (рис.

б) включает всех поставщиков, которые находятся в Лондоне и поставляют деталь Р1.

реляционной операции разности требуется, чтобы ее операнды принадлежали к одному

и тому же типу.
Если даны отношения А и В одного и того же типа, то разностью этих отношений А MINUS В (в указанном порядке), является отношение того же типа с телом, состоящим из всех кортежей t, таких, что t присутствует в А, но не в В.

В показаны на рис.
Тогда результат операции разности A MINUS

В (рис. в) включает поставщиков, которые находятся в Лондоне и не поставляют деталь Р1;
Результат операции разности В MINUS A (рис. г) включает поставщиков, которые поставляют деталь Р1 и не находятся в Лондоне.
Обратите внимание на то, что оператор MINUS характеризуется направленностью (некоммутативностью), так же, как вычитание в обычной арифметике (например, "5 - 2" и "2 - 5" не являются одним и тем же).

является множество всех таких упорядоченных пар, что в каждой паре

первый элемент берется из первого множества, а второй — из второго множества.
Поэтому декартово произведение двух отношений, неформально выражаясь, представляет собой множество упорядоченных пар кортежей. Но мы снова должны сохранить свойство замкнутости;
Иными словами, необходимо, чтобы результат содержал кортежи как таковые, а не упорядоченные пары кортежей.

расширенная форма этой операции, в которой каждая упорядоченная пара кортежей

заменяется одним кортежем, являющимся объединением двух рассматриваемых кортежей.
Это означает, что если даны следующие кортежи:
{ Al, A2, . . . , Am}
и
{ B1, B2, ..., Bn }
то теоретико-множественное объединение этих двух кортежей представляет собой приведенный ниже единственный кортеж:
{ Al, A2, ..., Am, Bl, B2, ..., Bn}

В отношений А и В,
не имеющих общих атрибутов,

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

отношения, т.е. подмножество кортежей заданного отношения, для которых удовлетворяется некоторое

указанное условие.

имеет атрибуты Х,

Y, . . ., Z (и, возможно, другие атрибуты). В таком случае проекция отношения А по атрибутам X, Y, . . . , Z, которая определяется с помощью следующего выражения:
А { X, Y, . . . , Z }
является отношением, соответствующим описанным ниже требованиям:

Его заголовок формируется из заголовка отношения а путем удаления всех атрибутов, не указанных в множестве { X, Y, . . . , Z }.
Тело состоит из всех кортежей { х , у, . . . , z}, таких что в отношении А присутствует кортеж со значением х атрибута X, у атрибута Y... и z атрибута Z.

имеют следующие атрибуты.
X 1 , Х 2 , . .

. , X m , Y 1 , Y 2 , . . . , Yn (A)
Yl , Y2, . . . , Yn, Z l , Z 2 , . . . , Zp (B)
Это означает, что два рассматриваемых отношения имеют общее множество атрибу-
тов Y, состоящее из атрибутов Yl, Y2 , . . . , Yn (и только из этих атрибутов),
Другие атрибуты отношения А образуют множество Х, состоящее из атрибутов X1, Х2, Xm,
Другие атрибуты отношения В образуют множество Z, состоящее из атрибутов Z1, Z2, . . , Zp.

. , Xm },{ Yl, Y2, . . . ,

Yn } и { Zl, Z2,. . ., Zp } могут рассматриваться, соответствен-но, как три составных атрибута X, Y и Z.
В таком случае (естественное) соединение A и B выражается следующим образом.
A JOIN B
Оно представляет собой отношение с заголовком {X, Y, Z} и телом, состоящим из всех таких кортежей {Xх, Yу, Zz}, что любой из этих кортежей присутствует и в отношении A, со значением х атрибута X и значением у атрибута Y, и в отношении B, со значением у атрибута Y и значением z атрибута Z.

имеют следующие атрибуты:
XI, Х2, . . . ,Хm (А); Yl,

Y2, ..., Yn (В)
Здесь ни один из атрибутов Хi (i = 1, 2, . . ., m) не имеет одинакового имени с любым из атрибутов Yj (j = 1, 2, . . ., n).
Пусть отношение С имеет следующие атрибуты:
X I , Х 2 , . . . , Xm, Y l , Y 2 , . . . , Yn (С)
ЭТО означает, что C имеет заголовок, представляющий собой (теоретико-множественное) объединение заголовков А и В. Будем рассматривать множества {XI, Х2, ..., Хm}
{ Yl, Y2, . . ., Yn }, соответственно, как составные атрибуты X и Y. В таком случае операция деления A на B по C (где а — делимое, B — делитель, а C — посредник) может быть
представлена с помощью следующего выражения.
A DIVIDEBY B PER C

состоящим из всех кортежей { X х }, присутствующих в

А, причем таких, что кортеж { Х х, Y у } присутствует в С для всех кортежей { Y у }, присутствующих в В.

Иными словами, данный результат состоит из тех значений х, присутствующих в А, для которых соответствующие значения у в С включают все значения у из В.

В каждом случае делимое (DEND) представляет собой проекцию текущего значения

отношения S по атрибуту S#; посредник (MED) в каждом случае является проекцией текущего значения отношения SP по атрибутам S# и Р#; а три делителя (DOR) являются такими, как указано на этом рисунке.