60

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

Деление

Пусть два отношение R1 и R2 имеют заголовки, соответственно {X, Y} и {Y}, где X, Y атрибуты (возможно составные). Атрибут (группа атрибутов) Y – общие для обоих отношений. Отношение R1 имеет, кроме того, дополнительные атрибуты X, а отношение R2 не имеет никаких дополнительных атрибутов. Полагаем, что атрибуты с одинаковыми именами Y обоих отношений определены на одинаковых доменах.

Тогда операцией деления отношения R1 на отношение R2, обозначаемой R1 DIVIDE BY R2, где R1 – делимое, а R2 – делитель, называется отношение с заголовком {X} и телом, содержащим множество всех кортежей {<X:x>} таких, что существует набор кортежей {<X:x>, <Y:y>}, принадлежащий отношению R1, для всех кортежей {<Y:y>}, принадлежащих отношению R2.

Несколько менее строго это можно сформулировать так: результирующее отношение содержит такие значения атрибутов Х отношения R1, для которых соответствующие значения атрибута Y из R1 включают все значения атрибута Y из отношения R2.

Пример 1

61

Пример 2

Пусть даны два отношения: ОТНОШЕНИЕ_1 и ОТНОШЕНИЕ_2.

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

63

2) T2:= T1 WHERE КОД_ДИСЦИПЛ = ‘Д2’

T2

3) T3:= T2[ИМЯ]

T3

ИМЯ

Иванов

Зайцева

Здесь символ “:=” означает оператор присваивания, обозначения Ti используются в качестве имен, временных отношений, являющихся промежуточными результатами вычислений.

Пример 2

Запрос: «Получить имена и города студентов, сдавших информатику».

(((ДИСЦИПЛИНЫ WHERE НАИМЕНОВАНИЕ=‘Информатика’) JOIN УСПЕВАЕМОСТЬ)[КОД_СТУД] JOIN Студенты)[ИМЯ, ГОРОД]

Другой вариант этого запроса

(((ДИСЦИПЛИНЫ WHERE НАИМЕНОВАНИЕ=‘Информатика’)[КОД_СТУД] JOIN УСПЕВАЕМОСТЬ) JOIN СТУДЕНТЫ) [ИМЯ, ГОРОД]

В результате обоих вариантов будут получены одинаковые отношения, содержащие два атрибута ИМЯ и ГОРОД.

ИМЯ ГОРОД

Иванов Орел Сидоров Москва Зайцева Липецк

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

Пример 3

Запрос: «Получить имена студентов, которые не сдавали дисциплину Д6».

((СТУДЕНТЫ[КОД_СТУД] MINUS (УСПЕВАЕМОСТЬ

WHERE КОД_ДИСЦИПЛ = ‘Д6’) [КОД_СТУД]) JOIN Студенты)[ИМЯ]

Это выражение эквивалентно последовательному выполнению действий

64

T1:= СТУДЕНТЫ[КОД_СТУД];

T2:= УСПЕВАЕМОСТЬ WHERE КОД_ДИСЦИПЛ = ‘Д6’; T3:= T2[КОД_СТУД];

T4:= T1 MINUS T2;

T5:= T4 JOIN Студенты;

T6:= T5[ИМЯ]

Отношение T6 содержит искомый результат.

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

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

Например, выражение из примера 1

((СТУДЕНТЫ JOIN УСПЕВАЕМОСТЬ) WHERE КОД_ДИСЦИПЛ = ‘Д2’) [ИМЯ]

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

((УСПЕВАЕМОСТЬ WHERE КОД_ДИСЦИПЛ = ‘Д2’) JOIN СТУДЕНТЫ)[ИМЯ].

Можно обратить внимание, что второе выражение возможно более рационально с точки зрения времени, затрачиваемого на выполнения запроса. Действительно, в нем вначале из отношения УСПЕВАЕМОСТЬ отбираются кортежи, удовлетворяющие заданному условию, благодаря чему уменьшается число кортежей, участвующих в операции соединения с отношением

СТУДЕНТЫ.

Этот пример говорит о том, что реляционная алгебра предоставляет возможность использования тождественных преобразований алгебраических выражений для оптимизации выполнения запросов, например с точки зрения длительности их выполнения. «Хорошая» СУБД должна иметь в своем составе средства, осуществляющие такую оптимизацию и обеспечивающие в идеале независимость времени выполнения запросов от формы его представления пользователем.