РХ.Р# WHERE PX.WEIGHT > OR EXISTS SPX I

WEIGHT ( 16.0 ) SPX.PI = PX.PI AND SPX.SI = SI ( S2

7.4. Сравнительный анализ реляционного исчисления и реляционной алгебры

в начале этой главы утверждалось, что реляционная алгебра и реляционное исчисление в своей основе эквивалентны. Обсудим это утверждение более подробно. Вначале Кодд в [6.1] показал, что алгебра по крайней мере мощнее исчисления. Он сделал это, придумав алгоритм, называемый алгоритмом редукции Кодда, с помощью которого любое выражение исчисления можно преобразовать в семантически эквивалентное выражение алгебры. Мы не станем приводить здесь этот алгоритм полностью, а ограничимся довольно сложным примером, иллюстрирующим в общих чертах, как он функционирует.

Рис. 7.1. База данных поставщиков, деталей и проектов (значения для примера)

В действителыюсти алгорипш, представленный в [6.1], содержит небольшую ошибку [7.2]. Более того, определенная в этой статье версия реляционного исчисления не включала аналога оператора объединения, следовательно, исчисление Кодда значительно менее мощное, чем его алгебра. Как бы там ни было, утверждение о том, что алгебра и исчисление, включающее аналог операции объединения, эквивалентны, является истиной, что доказано многими авторами [6.12].

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

Рассмотрим теперь следующий запрос: Получить имена поставщиков и названия городов, в которых находятся поставщики деталей по крайней мере для одного проекта в Афинах (Athens), поставляющих по крайней мере 50 штук каждой детали . Выражение реляционного исчисления для этого запроса следующее.

( SX.SNAME, SX.CITY ) WHERE EXISTS JX FORALL PX EXISTS SPJX

( JX.CITY = Athens AND JX.Jf = SPJX.J# AND PX.PI = SPJX.PI AND SX.SI = SPJX.SI AND SPJX.QTY > QTY { 50 ) )

Здесь SX, PX, JX и SPJX - переменные кортежей, получающие свои значения из переменных-отношений S, Р, J и SPJ соответственно. Теперь покажем, как можно вычислить это выражение, чтобы достичь требуемого результата.

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

SX РХ JX

SPJX

Все кортежи отношения S 5 кортежей

Все кортежи отношения Р 6 кортежей

Кортежи отношения J, в которых CITY = Athens 2 кортежа

Кортежи отношения SPJ, в которых CITY > 50 24 кортежа

Этап 2. Строим декартово произведение диапазонов, выбранных на первом этапе. Вот результат.

(И т.д.) Bee произведение содержит 5*6*2*24 = 1 440 кортежей.

Замечание. Для экономии места здесь это отношение полностью не приводится. Мы также не переименовывали атрибуты (хотя это следовало бы сделать во избежание двусмысленности), а просто расположили их в таком порядке, чтобы было видно, какой атрибут SI относится, например, к отношению S, а какой - к отношению SPJ. Это также сделано для сокращения изложения.

Этап 3. Осуществляем выборку из построенного на этапе 2 произведения в соответствии с частью условие соединения фразы WHERE. В нащем примере эта часть выглядит следующим образом.

JX.Jf = SPJX.Jf AND PX.PI = SPJX.PI AND SX.SI =SPJX.Sl

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

(Это отношение, конечно, представляет собой эквивалент результата операции соединения.)

Этап 4. Применяем кванторы в порядке справа налево следующим образом.

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

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

Замечание. Под делением здесь подразумевается оригинальная операция деления Кодда (см. аннотацию к [6.3]).

В нашем примере имеем следующие кванторы. EXISTS JX FORALL PX EXISTS SPJX Значит, выполняются следующие операции.

1. (EXISTS SPJX) Проецируем, исключая атрибуты переменной-отношения SPJ (SPJ.SI, SPJ.PI, SPJ. Л и SPJ.QTY). В результате получаем следующее.