Главная » SQL, Базы данных » СРАВНИТЕЛЬНЫЙ АНАЛИЗ РЕЛЯЦИОННОГО ИСЧИСЛЕНИЯ И РЕЛЯЦИОННОЙ АЛГЕБРЫ

0

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

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

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

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

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

{ SX.SNAME, SX.CITY } WHERE EXISTS JX FORALL PX EXISTS SPJX ( JX.CITY = ‘Athens’

AND JX.J# = SPJX.J#

AND PX.P# = SPJX.P#

AND SX.S# = SPJX.S#

AND SPJX.QTY > QTY (

50 ) )

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

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

SX. Все кортежи отношения s — 5 кортежей.

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

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

.

■     SPJX. Кортежи отношения SPJ, в которых QTY ≥ QTY (50) — 24 кортежа.

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

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

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

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

JX.J# = SPJX.J# AND PX.P# = SPJX.P# AND SX.S# = SPJX.S#

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

(Это отношение представляет собой наглядный пример соединения по эквивалентности.)

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

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

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

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

деления

Кодда (см. аннотацию к [7.4]).

В нашем примере имеем следующие кванторы.

EXISTS JX FORALL PX EXISTS SPJX

Таким образом, затем выполняются следующие операции.

■     EXISTS SPJX. Исключение с помощью операции проекции атрибутов перемен ной отношения SPJ (SPJ.S#, SPJ.P#, SPJ. J# и SPJ.QTY). В результате получа ем следующее,

■     FORALL PX. Деление полученного результата на отношение Р. В результате имеем следующее.

■     EXISTS JX. Исключение с помощью операции проекции атрибутов отношения J (J. J#, J. JNAME и J. CITY). В результате получаем следующее.

Этап 5. Получение проекции результата этапа 4 в соответствии со спецификациями в кортеже-прототипе. В нашем примере кортеж-прототип имеет следующий вид.

(SX.SNAME,   SX.CITY)

Значит, конечный результат вычислений будет таков.

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

Этим мы завершаем обсуждение данного примера. Конечно, можно намного  улучшить используемый алгоритм (см. главу 18, в частности, аннотацию к [18.4]). И хотя многие подробности в пояснениях были опущены, этот пример вполне адекватно отражает общую идею работы алгоритма редукции.

Кстати, теперь можно объяснить одну (не единственную) из причин того,  почему Кодд определил ровно восемь алгебраических операторов. Эти восемь операторов образуют удобный целевой язык, который может служить средством  возможной реализации реляционного исчисления. Другими словами, для заданного языка, построенного на основе реляционного исчисления (подобно языку QUEL), один из возможных подходов к реализации заключается в том, что организуется получение запроса в том виде, в каком он предоставлен пользователем. По существу, он будет являться просто выражением реляционного исчисления, к которому затем можно будет применить определенный алгоритм редукции,  чтобы  получить эквивалентное алгебраическое выражение. Это алгебраическое  выражение, разумеется, будет включать набор алгебраических операций, которые, безусловно, будут реализуемыми по определению. (Следующий этап  состоит в оптимизации полученного алгебраического выражения, о чем речь пойдет в главе 18.)

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

Прежде всего, отметим, что некоторый язык принято называть реляционно полным,

если он по своим возможностям, по крайней мере, не уступает реляционному исчислению. Иначе говоря, для этого необходимо, чтобы любое отношение, которое можно определить с помощью реляционного исчисления, можно было определить и с помощью некоторого  выражения  рассматриваемого  языка  [7.1].  (В  главе  7  отмечалось,  что "реляционно полный" означает "не уступающий по возможностям реляционной алгебре", а не исчислению, но, как читатель вскоре убедится, это одно и то же. По сути, из самого существования алгоритма редукции Кодда немедленно следует, что  реляционная

алгебра обладает реляционной полнотой.)

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

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

Далее, поскольку алгебра обладает реляционной полнотой, для доказательства того,

что некоторый язык L также обладает реляционной полнотой, достаточно показать, что в языке L есть аналоги всех восьми алгебраических операций (на самом деле достаточно

показать, что в нем есть аналоги пяти примитивных операций) и что операнды любой операции  языка  L  могут  быть  представлены  произвольными  выражениями  языка  L (соответствующего типа). Язык SQL — это пример языка, реляционную полноту которого можно доказать описанным способом (упр. 8.9). Язык QUEL — еще один пример подобного языка. В действительности на практике часто проще показать то, что в языке

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

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

Вычислительная полнота — это один из факторов, побудивших ввести в  реляционную алгебру операции EXTEND И SUMMARIZE (обсуждавшиеся в главе 7). В следующем разделе описано, как можно расширить реляционное исчисление, чтобы обеспечить в нем наличие аналогов этих операций.

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

[8.13]. Отсюда следует, что реляционная алгебра и реляционное исчисление логически

эквивалентны.

Источник: Дейт К. Дж., Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — 1328 с.: ил. — Парал. тит. англ.

По теме:

  • Комментарии