Реляционное исчисление

Формально квантор существования EXISTS определяется как повторение

операции OR (ИЛИ). Другими словами, если r - это отношение с кортежами t1,

t2, … , tm, V - это переменная кортежа, изменяющаяся на данном отношении, и

p(V) - это формула WFF, в которой переменная V используется как свободная

переменная, то формула WFF вида

EXISTS V (p (V))

равносильна следующей формуле WFF.

false OR p (t1) OR … OR p (tm)

В частности, обратите внимание, что если отношение R пустое (т.е.

m=0), то результатом вычисления данного выражения будет значение ложь.

Рассмотрим в качестве примера отношение r, содержащее следующие

кортежи.

(1, 2, 3)

(1, 2, 4)

(1, 3, 4)

Для простоты предположим, что три атрибута, идущие по порядку слева

направо, имеют имена A, B и C соответственно и каждый из этих атрибутов

имеет тип INTEGER. Тогда приведённые ниже выражения будут иметь указанные

значения.

EXISTS V (V.C>1) : true

EXISTS V (V.B>3) : false

EXISTS V (V.A>1 OR V.C = 4) : true

Теперь рассмотрим квантор общности FORALL, для чего вернёмся к

соответствующему примеру из предыдущего раздела.

FORALL PX (PX.COLOR = COLOR (‘Red’) )

Эта формула WFF может быть прочитана следующим образом.

В текущем значении отношения P для всех кортежей (скажем, PX) значение их

атрибута COLOR равно ‘Red’.

Обе ссылки на переменную PX в этом примере связаны.

Подобно тому, как квантор EXISTS был определён как повторение

операции OR, квантор существования FORALL определяется как повторяющаяся

операция AND (И). Другими словами, если обозначения r, V и p(V) имеют тот

же смысл, что и в приведённом выше определении квантора EXISTS, то формула

WFF вида

FORALL V (p (V) )

равносильна следующей формуле WFF.

true AND p (t1) AND … AND p (tm)

В частности, обратите внимание, что если отношение r пустое, то

результатом вычисления данного выражения будет значение истина.

В качестве примера рассмотрим отношение R, содержащее те же

кортежи, что и в предыдущем примере. Тогда приведённые ниже выражения будут

иметь указанные значения.

FORALL V (V.A>1) : false

FORALL V (V.B>1) : true

FORALL V (V.A = 1 and V.C>2) : true

Замечание. Квантор FORALL включён в реляционное исчисление просто

для удобства. Он не является необходимым, так как приведённое ниже

тождество показывает, что любая формула WFF, использующая квантор FORALL,

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

EXISTS.

FORALL V (p) ? NOT EXISTS V (NOT p)

(Проще говоря, выражение «все значения V, удовлетворяющие формуле

p» - это то же самое, что и выражение «нет таких значений V, которые бы не

удовлетворяли формуле p».)

Например, утверждение (истинное)

Для любого целого x существует целое y, такое, что y>x

равносильно утверждению

Не существует целого x, такого, что не существует целого y, такого,

что y>x.

(Иначе говоря, не существует наибольшего целого числа.) Но обычно

легче выразить подобное утверждение в терминах квантора FORALL, чем в

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

словами, на практике гораздо удобнее использовать оба квантора.

2.5. Ещё раз о свободных и связанных переменных.

Предположим, что переменная x изменяется на множестве всех целых

чисел, и рассмотрим следующую формулу WFF.

EXISTS x (x>3)

Связанная переменная x в этой формуле WFF является своего рода

фиктивной переменной. Она служит лишь для связи внутренних параметров

выражения с внешним квантором. В формуле WFF просто утверждается, что

существует целое число (скажем, x), которое больше 3. Следовательно,

значение этой формулы WFF осталось бы полностью неизменным, если бы все

экземпляры x были заменены экземплярами некоторой другой переменной

(скажем, y). Другими словами, формула WFF EXISTS y (y>3) семантически

идентична формуле, приведённой ранее.

Теперь рассмотрим другую формулу WFF.

EXISTS x (x>3) AND x3) AND x3) AND y не совсем уместен в контексте

исчисления - более подходящим вариантом был бы параметр . Однако будем использовать именно первый вариант, и в качестве

напоминания приводим следующий синтаксис.

: : = [ WHERE ]

: : =

Напоминаем также, что следующие синтаксические правила теперь

несколько упрощены.

. Во-первых, все ссылки на переменные кортежей в параметре должны быть свободными в пределах значения этого параметра.

. Во-вторых, ссылка на переменную кортежа в предложении WHERE может быть

свободной только в случае, если на эту же переменную (обязательно

свободная) присутствует в соответствующем значении параметра .

Например, следующее выражение является допустимым значением

параметра («Получить номера поставщиков, находящихся

в Лондоне»).

SX.S# WHERE SX.CITY = ‘London’

Здесь ссылка на переменную SX в прототипе кортежа является

свободной. Ссылка на переменную SX в предложении WHERE также является

свободной, поскольку ссылка на ту же переменную (обязательно свободную)

имеется и в значении параметра этого выражения.

Замечание. Далее термин «прототип кортежа» будет употребляться без

скобок.

Приведём другой пример («Получить имена поставщиков детали с

номером ‘P2’»)

SX.SNAME WHERE EXISTS SPX (SPX.S# SX.S# AND

SPX.P#

= P# (‘P2’) )

Здесь все ссылки на переменную SX являются свободными, тогда как

все ссылки на переменную SPX (в предложении WHERE) являются связанными, как

и должно быть, поскольку на них нет ссылок в прототипе кортежа.

Интуитивно понятно, что результатом выполнения операции, заданной

параметром , будет отношение, содержащее все

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

для которых результат вычисления логического выражения, заданного в

предложении WHERE параметром , принимает значение

истина. (Если предложение WHERE опущено, это эквивалентно указанию

выражения WHERE true.) Сделаем некоторые уточнения.

. Прежде всего, прототип кортежа - это список разделённых запятыми

элементов (возможно, заключённый в скобки), каждый элемент которого

является либо ссылкой на атрибут кортежа (который может содержать

предложение AS для введения нового имени атрибута), либо просто именем

переменной кортежа. Тем не менее отметим следующее.

1) В этом контексте имя переменной кортежа чаще всего является

сокращённым обозначением списка разделённых запятыми ссылок на

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

данная переменная кортежа.

2) Ссылка на атрибут кортежа без предложения AS, в принципе, является

сокращённым обозначением ссылки с предложением AS, в которой новое

имя атрибута совпадает со старым.

Следовательно, без потери общности прототип кортежа можно рассматривать

как список, состоящий из разделённых запятыми ссылок на атрибуты в виде

Vi.Ai AS Bj. Обратите внимание, что ссылки Vi- и Aj-е могут повторяться,

тогда как ссылки Bj-е должны быть разными.

. Пусть V1, V2, … ,Vm будут различными переменными кортежей, упоминаемыми в

прототипе кортежа, и пусть эти переменные будут определены на отношениях

r1, r2, … ,rm соответственно. Примем, что r1’, r2’, … ,rm’ - это новые

отношения, полученные после переименования атрибутов в предложении AS, и

пусть r’ - это декартово произведение отношений r1’, r2’, … , rm’.

. Пусть отношение r - это выборка из отношения r’, удовлетворяющая формуле

WFF в предложении WHERE.

Замечание. Здесь предполагается, что на предыдущем шаге были также

переименованы атрибуты, упоминающиеся в предложении WHERE; в противном

случае функция WFF в предложении WHERE может не иметь смысла.

. Конечное значение реляционной операции, заданной параметром , определяется как проекция отношения r по всем заданным

атрибутам Bj.

2.7. Примеры.

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

исчисления кортежей для формулирования запросов.

> Определить имена поставщиков детали с номером ‘P2’

SX

WHERE EXISTS SPX (SPX.S# = SX.S# AND

SPX.P# = P# (‘P2’) )

Обратите внимание на использование имени переменной кортежа в

прототипе кортежа. Этот пример является сокращённой записью следующего

выражения.

(SX.S#, SX.NAME, SX.STATUS, SX.CITY)

WHERE EXISTS SPX (SPX.S# = SX.S# AND

SPX.P# = P# (‘P2’) )

Этот же пример решённый средствами реляционной алгебры выглядит так

( (SP JOIN S) WHERE P# =’P2’) {SNAME}

> Определить имена поставщиков по крайней мере одной красной детали

SX.SNAME

WHERE EXISTS SPX (SX.S# = SPX.S# AND

EXISTS PX (PX.P# = SPX.P# AND

PX.COLOR =

COLOR (‘Red’) ) )

Этот же пример решённый средствами реляционной алгебры выглядит так

( ( ( P WHERE COLOR = COLOR (‘Red’) )

JOIN SP) {S#} JOIN S) {SNAME}

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

алгебры.

В начале утверждалось, что реляционная алгебра и реляционное

исчисление в своей основе эквивалентны. Осудим это утверждение более

подробно. Вначале Кодд показал, что алгебра по крайней мере мощнее

исчисления. Он сделал это, придумав алгоритм, называемый алгоритмом

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

преобразовать в семантически эквивалентное выражение алгебры. Мы не станем

приводить здесь этот алгоритм полностью, а ограничимся довольно сложным

примером, иллюстрирующим в общих чертах, как он функционирует.

|S# |SNAME |STATUS |CITY |

|S1 |Smith |20 |London |

|S2 |Jones |10 |Paris |

|S3 |Black |30 |Paris |

|S4 |Clark |20 |London |

|S5 |Adams |30 |Athens |

|S#|P# |J#|QTY |

|S1|P1 |J1|200 |

|S1|P1 |J4|700 |

|S2|P3 |J1|400 |

|S2|P3 |J2|200 |

|S2|P3 |J3|200 |

|S2|P3 |J4|500 |

|S2|P3 |J5|600 |

|S2|P3 |J6|400 |

|S2|P3 |J7|800 |

|S2|P5 |J2|100 |

|S3|P3 |J1|200 |

|S3|P4 |J2|500 |

|S4|P6 |J3|300 |

|S4|P6 |J7|300 |

|S5|P2 |J2|200 |

|S5|P2 |J4|100 |

|S5|P5 |J5|500 |

|S5|P5 |J7|100 |

|S5|P6 |J2|200 |

|S5|P1 |J4|100 |

|S5|P3 |J4|200 |

|S5|P4 |J4|800 |

|S5|P5 |J4|400 |

|S5|P6 |J4|500 |

|P#|PNAME |COLOR |WEIGHT |CITY |

|P1|Nut |Red |12.0 |London|

|P2|Bolt |Green |17.0 |Paris |

|P3|Screw |Blue |17.0 |Rome |

|P4|Screw |Red |14.0 |London|

|P5|Cam |Blue |12.0 |Paris |

|P6|Cog |Red |19.0 |London|

|J#|JNAME |CITY |

|J1|Sorter|Paris |

|J2|Displa|Rome |

| |y | |

|J3|OCR |Athens|

|J4|Consol|Athens|

| |e | |

|J5|RAID |London|

|J6|EDS |Oslo |

|J7|Tape |London|

S-детали, P- поставщики, J- проекты, SPJ- поставки.

Рассмотрим теперь следующий запрос: «Получить имена поставщиков и

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

для одного проекта в Афинах, поставляющих по крайней мере 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. Для каждой переменной кортежа выбираем её область значений

(т.е. набор всех значений для переменной), если это возможно. Выражение

«выбираем, если возможно» подразумевает, что существует условие выборки,

встроенное в фразу WHERE, которую можно использовать, чтобы сразу исключить

из рассмотрения некоторые кортежи. В нашем случае выбираются следующие

наборы кортежей.

SX : Все кортежи отношения S

5 кортежей

PX : Все кортежи отношения P

6 кортежей

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

2 кортежа

SPJX : Кортежи отношения SPJ, в которых CITY ? 50

24 кортежа

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

первом этапе. Вот результат.

|S5 |Adams |30 |Athens |J4 |Console |Athens |

(Теперь у нас есть место, чтобы показать отношение полностью, без

сокращений.)

1.(EXISTS JX) Проецируем, исключая атрибуты отношения J (J.J#, J.NAME и

J.CITY). В результате получаем следующее.

|S# |SN |STATUS |CITY |

|S5 |Adams |30 |Athens |

Этап 5. Проецируем результат этапа 4 в соответствии со спецификациями

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

(SX.SNAME, SX.CITY)

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

|SNAME |CITY |

|Adams |Athens |

Из сказанного выше следует, что начальное выражение исчисления

семантически эквивалентно определённому вложенному алгебраическому

выражению, и, если быть более точным, это проекция от проекции результата

деления проекции выборки из произведения четырёх выборок (!).

И хотя многие подробности в пояснениях были упущены, этот пример

вполне адекватно отражает общую идею работы алгоритма редукции.

Теперь моно объяснить одну из причин (и не только одну)

определения Коддом ровно восьми алгебраических операторов. Эти восемь

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

реализации реляционного исчисления. Другими словами, для заданного языка,

построенного на основе реляционного исчисления (подобно языку QUEL), один

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

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

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

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

получить эквивалентное алгебраическое выражение. Это алгебраическое

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

по определению реализуемы по самой своей природе.

Также следует отметить, что восемь алгебраических операторов Кодда

являются мерой оценки выразительной силы любого языка баз данных.

Некоторый язык принято называть реляционно полным, если он по

своим возможностям по крайней мере не уступает реляционному исчислению.

Иначе говоря, любое отношение, которое можно определить с помощью

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

рассматриваемого языка. («Реляционно полный» значит «не уступающий по

возможностям реляционной алгебре», а не исчислению, но это одно и то же,

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

Кодда немедленно следует, что реляционная алгебра обладает реляционной

полнотой.)

Реляционную полноту можно как основную меру выразительной силы

языков баз данных в самом общем случае. В частности, так как реляционное

исчисление и реляционная алгебра обладают реляционной полнотой, они могут

служить основой для проектирования не уступающих им по выразительности

языков без необходимости выполнять пересортировку для организации циклов.

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

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

использования прикладными программистами.

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

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

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

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

аналоги пяти примитивных операций) и что операндами любой операции языка L

могут быть любые выражения этого языка. Язык SQL - это пример языка,

реляционную полноту которого можно доказать указанным способом. Язык QUEL -

ещё один пример подобного языка. В действительности на практике часто проще

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

то, что в нём существуют эквиваленты выражений реляционного исчисления.

Именно поэтому реляционная полнота обычно определяется в терминах

алгебраических выражений, а не в терминах выражений реляционного

исчисления.

При этом важно понимать, что реляционная полнота необязательно

влечёт за собой полноту какого-либо другого рода. Например, желательно,

чтобы язык также обеспечивал «вычислительную полноту», т.е. позволял

вычислять результаты всех вычислимых функций. Заметим, что согласно нашему

определению исчисление не обладает полнотой такого рода, хотя на практике

подобная полнота для языка баз данных весьма желательна. Вычислительная

полнота - это один из факторов, побудивших ввести в реляционную алгебру

операции EXTEND и SUMMARIZE. В следующем разделе описано, как можно

расширить реляционное исчисление, чтобы обеспечить в нём наличие аналогов

этих операций.

Вернёмся к вопросу эквивалентности алгебры и исчисления. Мы на

примере показали, что любое выражение исчисления можно преобразовать в его

некоторый алгебраический эквивалент, а значит, алгебра по крайней мере не

уступает по своей мощности исчислению. Можно показать обратное: каждое

выражение реляционной алгебры можно преобразовать в эквивалентное выражение

реляционного исчисления, а значит, исчисление по крайней мере не уступает

по своей мощности реляционной алгебре. Отсюда следует, что реляционная

алгебра и реляционное исчисление эквивалентны.

4. Вычислительные возможности.

Несмотря на то что ранее об этом не упоминалось, в определённом

нами реляционном исчислении уже есть аналоги алгебраических операторов

EXTEND и SUMMARIZE, и вот почему.

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

подпараметры .

. В параметре сравниваемыми элементами могут быть

произвольные подпараметры .

. Первым или единственным аргументом в параметре

является подпараметр .

4.1. Примеры.

> Для каждой детали выбрать номер и общий объём поставки в штуках

(PX.P#, SUM (SPX WHERE SPX.P# = PX.P#, QTY) AS TOTQTY)

> Определить общее количество поставляемых деталей

SUM (SPX, QTY) AS GRANDTOTAL)

> Определить номера и вес в граммах всех типов деталей, вес которых

превышает 10000г

(PX.P#, PX.WEIGHT * 454 AS GMWT)

WHERE PX.WEIGHT * 454 > WEIGHT

(10000)

Обратите внимание, что спецификация AS GMWT в прототипе кортежа даёт имя

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

использования в предложении WHERE и выражение PX.WEIGHT * 454 должно быть

указано в двух местах.

5. Исчисление доменов.

Как указывалось в «Введении», реляционное исчисление,

ориентированное на домены (или исчисление доменов), отличается от

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

переменные доменов, т.е. переменные, принимающие свои значения в пределах

домена, а не отношения. С практической точки зрения большинство очевидных

различий между версиями исчисления доменов и исчисления кортежей основано

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

условие принадлежности можно записать так.

R (пара, пара, …)

Здесь R- имя отношения, а каждый параметр пара имеет вид A: v, где

A - атрибут отношения R, а v - имя переменной домена или литерал. Проверка

условия даёт значение истина тогда и только тогда, когда в текущем значении

отношения R существует кортеж, имеющий указанные значения для указанных

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

SP (S# : S# (‘S1’), P# : P# (‘P1’) )

Он будет иметь значение истина тогда и только тогда, когда в

отношении SP будет существовать кортеж со значением атрибута S#, равным

‘S1’, и значением атрибута P#, равным ‘P1’. Аналогично условие

принадлежности

SP (S# : SX, P# : PX)

принимает значение истина тогда и только тогда, когда в отношении SP

существует кортеж со значением атрибута S#, эквивалентным текущему значению

переменной домена PX (опять же, какому бы ни было).

Далее будем подразумевать существования следующих переменных

доменов.

Домен

Переменная домена

S#

SX, SY, …

P#

PX, PY, …

NAME

NAMEX, NAMEY, …

COLOR

COLORX, COLORY, …

WEIGHT

WEIGHTX, WEIGHTY, …

QTY

QTYX, QTYY, …

CHAR

CITYX, CITYY, …

INTEGER

STATUSX, STATUSY, …

Ниже приведено несколько примеров выражений исчисления доменов.

SX

SX WHERE S (S# : SX)

SX WHERE S (S# : SX, CITY : ‘London’)

(SX, CITYX) WHERE S (S# : SX, CITY : ‘London’)

AND SP (S# : SX, P# : P# (‘P2’) )

(SX,PX) WHERE S (S# : SX, CITY : CITYX)

AND P (P# : PX, CITY : CITYY)

AND CITYX ? CITYY

Если говорить нестрого, первое выражение означает множество всех

номеров поставщиков, второе - множество всех номеров поставщиков из

Лондона. Следующее выражение - это выраженный в терминах исчисления доменов

запрос «Определить номера поставщиков и названия городов, в которых

находятся поставщики детали с номером ‘P2’» (вспомните, что в этом запросе,

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

существования). И последнее выражение - это представленный в терминах

исчисления доменов запрос «Найти все такие пары номеров поставщиков и

номеров деталей, для которых поставщик и деталь находятся в одном городе».

5.1. Примеры.

> Найти все такие пары номеров поставщиков, в которых два поставщика

находятся в одном городе

(SX AS SA, SY AS SB) WHERE EXISTS CITYZ

(S (S# : SX, CITY :

CITYZ) AND

S (S# : SY, CITY :

CITYZ) AND

SX < SY)

> Определить имена поставщиков по крайней мере одной красной детали

NAMEX WHERE EXISTS SX EXISTS PX

(S (S# : SX, SNAME : NAMEX)

AND SP (S# : SX, P# : PX)

AND P (P# : PX, COLOR : COLOR (‘Red’) ) )

> Выбрать имена поставщиков всех типов деталей

NAMEX WHERE EXISTS SX (S (S# : SX, SNAME : NAMEX)

AND FORALL PX (IF P (P# : PX)

THEN SP

(S# : SX, P# : PX)

END IF)

6. Средства языка SQL.

Как уже говорилось в разделе «Сравнительный анализ реляционного

исчисления и реляционной алгебры», в основу реляционного языка могут быть

положены как реляционная алгебра, так и реляционное исчисление. Что же

положено в основу языка SQL? Ответом будет №частично и то, и другое, а

частично ни то, ни другое…». Когда язык SQL только разрабатывался,

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

реляционного исчисления. Действительно, именно этим мотивировалось введение

в язык конструкции IN . Однако со временем выяснилось, что язык

SQL нуждается в определённых средствах как реляционной алгебры, так и

исчисления, поэтому он был расширен для включения этих функций. На

сегодняшний день ситуация складывается таким образом, что язык SQL в чём-то

похож на реляционную алгебру, в чём-то на реляционное исчисление, а в чем-

то отличается от них обоих.

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

которые потенциально могут иметь очень высокую степень сложности.

6.1.

Примеры.

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

SELECT P.P#, P.WEIGHT * 454 AS GMWT

FROM P;

Спецификация AS GMWT вводит соответствующее имя результирующего столбца.

Таким образом, два столбца результирующей таблицы будут называться P# и

GMWT. Если бы спецификация AS GMWT была опущена, то соответствующий

столбец был бы фактически безымянным. Отметим, что хотя в подобных случаях

правила языка SQL в действительности не требуют от пользователя указания

имени результирующего столбца.

> Выбрать информацию обо всех парах поставщиков и деталей, находящихся в

одном городе

В языке SQL существует несколько способов формулирования этого запроса.

Приведем три самых простых.

1. SELECT S.*, P.P#, P.NAME, P.COLOR, P.WEIGHT

FROM S, P

WHERE S.CITY =P.CITY;

2. S JOIN P USING CITY;

3. S NATURAL JOIN P;

Результатом в каждом случае будет естественное соединение таблиц S и P (по

атрибуту города CITY).

Первая формулировка заслуживает более подробного обсуждения. Именно одна

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

языка SQL (явная операция JOIN была добавлена в стандарт SQL/92).

Концептуально можно рассматривать реализацию этой версии запроса следующим

образом.

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

произведение S TIMES P. (Строго говоря, перед вычислением

произведения следовало бы позаботится о переименовании столбцов. Для

простоты мы этого не делаем.)

. Во-вторых, после выполнения предложения WHERE мы получаем выборку из

этого произведения, в которой два значения атрибута CITY в каждой

строке равны (иначе говоря, выполнено соединение таблиц поставщиков

и деталей по эквивалентности их атрибутов городов).

. В-третьих, после выполнения предложения SELECT мы получаем проекцию

выборки по столбцам, указанным в предложении SELECT. Конечным

результатом будет естественное соединение указанных таблиц.

Следовательно, предложение FROM в языке SQL соответствует декартову

произведению, предложение WHERE - операции выборки, а совместное

применение предложений SELECT-FROM-WHERE - проекции выборки произведения.

7. Заключение.

Мы рассмотрели реляционное исчисление, альтернативное реляционной

алгебре.

Внешне два подхода очень отличаются: исчисление имеет описательный

характер, тогда как характер алгебры - предписывающий, но на более низком

уровне они представляют собой одно и то же, поскольку любые выражения

исчисления могут быть преобразованы в семантически эквивалентные выражения

алгебры и наоборот.

Реляционное исчисление существует в двух версиях: исчисление

кортежей и исчисление доменов. Основное различие между ними состоит в том,

что переменные исчисления кортежей изменяются на отношениях, а переменные

исчисления доменов изменяются на доменах.

Выражение исчисления кортежей состоит из прототипа кортежа и

необязательного предложения WHERE, содержащего логическое выражение или

формулу WFF («правильно построенную формулу»). Подобная формула WFF может

включать кванторы (EXISTS и FORALL), свободные и связанные ссылки на

переменные, логические (булевы) операторы (AND, OR, NOTи др.) и т.д. Каждая

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

упомянута в прототипе кортежа.

Замечание. Здесь этот вопрос явно не затрагивался, но выражения

реляционного исчисления предназначены, по существу, для тех же целей, что и

выражения реляционной алгебры.

На примере было показано[1], как алгоритм редукции Кодда может

использоваться для преобразования произвольного выражения реляционного

исчисления в эквивалентное выражение реляционной алгебры, таким образом

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

Вновь обратившись к вопросу реляционной полноты, мы кратко обсудили, каким

образом можно доказать, что некоторый язык L является полным в этом смысле.

Кроме того, здесь обсуждалось, как можно расширить исчисление

кортежей с целью поддержки определённых вычислительных возможностей

(аналогичные возможности в реляционной алгебре обеспечиваются операциями

EXTEND и SUMMARIZE). Затем нам было представлено краткое введение в

исчисление доменов и отмечено (правда, без попытки доказать это), что оно

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

исчисление доменов и реляционная алгебра эквивалентны.

И наконец, нашему вниманию был представлен обзор соответствующих

средств языка SQL. Язык SQL является своеобразной смесью реляционной

алгебры и исчисления (кортежей

). Например, в нём есть прямая поддержка таких операций реляционной

алгебры, как соединение и объединение, но одновременно с этим используются

переменные кортежей и квантор существования из реляционного исчисления. SQL

– запрос представляет собой табличное выражение. Обычно такая конструкция

содержит единственное выражение выборки, однако поддерживаются и различные

типы явных выражений операций соединения (JOIN), причём выражения

соединения и выборки могут комбинироваться произвольным образом с помощью

операторов UNION, INTERSECT и EXCEPT. Также упоминалось о возможности

использования предложения ORDER BY для определения упорядоченности строк в

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

(любого вида).

В частности, были описаны следующие компоненты выражений выборки.

. Базовое предложение SELECT, в том числе использование ключевого слова

DISTINCT, скалярных выражений, введение имён результирующих столбцов и

использование предложения SELECT *

. Предложение FROM, включая использование переменных кортежей

. Предложение WHERE, включая использование оператора EXISTS

. Предложение GROUP BY и HAVING, включая использование обобщающих функций

COUNT, SUM, AVG, MAX и MIN

. Использование подзапросов в предложениях SELECT, FROM и WHERE

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

(т.е. схема формального определения) для выражений выборки.

8. Список литературы.

1) «Введение в системы баз данных» К.Дж.Дейт, издательство «Питер», СПб

2002г.

2) «Базы данных: модели, разработка, реализация» учебник под редакцией

Т.Карповой, издательство «Питер», СПб 2001г.

3) «Системы баз данных» Г.Гаремо-Малино, Москва 2003г.

8. Список литературы.

4) «Введение в системы баз данных» К.Дж.Дейт, издательство «Питер», СПб

2002г.

5) «Базы данных: модели, разработка, реализация» учебник под редакцией

Т.Карповой, издательство «Питер», СПб 2001г.

6) «Системы баз данных» Г.Гаремо-Малино, Москва 2003г.

-----------------------

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

Страницы: 1, 2