Реферат: Реляционное исчисление

Содержание.

1. Введение.

2. Исчисление кортежей.

2.1. Синтаксис.

2.2. Переменныекортежей.

2.3. Свободные исвязанные переменные кортежей.

2.4. Кванторы.

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

2.6.Реляционные операции.

2.7. Примеры

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

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

4.1. Примеры

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

5.1. Примеры

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

6.1. Примеры

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

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

1.Введение.

Часть реляционноймодели, которая связана с операторами манипулирования данными, основывается наиспользовании реляционной алгебры. Однако с тем же основанием можно сказать,что она построена на базе реляционного исчисления. Другими словами,реляционная алгебра и реляционное исчисление представляют собой дваальтернативных подхода. Принципиальное различие между ними следующее.Реляционная алгебра в явном виде представляет набор операций (соединение,объединение, проекция и т.д.), которые можно использовать, чтобы сообщитьсистеме, как в базе данных из определённых отношений построить некотороетребуемое отношение, а реляционное исчисление просто представляет системуобозначений для определения требуемого отношения в терминах данныхотношений.

Например, рассмотримтри отношения:

Ø S-поставщики, каждый поставщик имеетуникальный номер (S#); имя (SNAME);значение рейтинга или статуса (STATUS); месторасположения (CITY). Предполагается, что каждыйпоставщик находится только в одном городе.

Ø P-детали, у каждого вида детали естьуникальный номер (P#); название детали (PNAME); цвет (COLOR); вес (WEIGHT); город, где хранится этот вид деталей (CITY). Каждый отдельный вид детали имеет только один цвет ихранится на складе только в одном городе.

Ø SP-поставки, служит для организациилогической связи двух других отношений. Например, первая строка отношения SP связывает поставщика с номером ‘S1’из отношения S с соответствующей деталью, имеющей номер‘P1’ в отношении P, т.е.представляет факт поставки деталей типа ‘P1’поставщиком с номером ‘S1’ (а также указываетколичество деталей-300 штук). Таким образом, каждая поставка характеризуетсяномером поставщика (S#), номером детали (P#) и количеством (QTY).Предполагается, что в одно и то же время может быть не более одной поставки для одного поставщика и одной детали.

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# QTY S1 P1 300 S1 P2 200 S1 P3 400 S1 P4 200 S1 P5 100 S1 P6 100 S2 P1 300 S2 P2 400 S3 P2 200 S4 P2 200 S4 P4 300 S4 P5 400 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

Рассмотрим запрос«Выбрать номера поставщиков и названия городов, в которых находятся поставщикидетали с номером ‘P2’». Алгебраическая версия этогозапроса выглядит приблизительно так:

— Сначала выполнить соединение отношения поставщиков S и отношения поставок SP по атрибутуS#.

— Далее выбрать из результата этого соединения кортежи с номеромдетали ‘P2’.

— И, наконец, выполнить для результата этой выборки операциюпроекции по атрибутам S# и CITY.

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

— Получить атрибуты S# и CITYдля таких поставщиков, для которых в отношении SPсуществует запись о поставке с тем же значением атрибута P#,равным ‘P2’.

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

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

Подчеркнём, однако, чтоупомянутые отличия существуют только внешне. На самом деле реляционнаяалгебра и реляционное исчисление логически эквивалентны. Каждому выражениюв алгебре соответствует эквивалентное выражение в исчислении, и точно таккаждому выражению в исчислении соответствует эквивалентное выражение в алгебре.Это означает, что между ними существует взаимнооднозначное соответствие, аразличия связаны лишь с разными стилями выражения; исчисление ближе кестественному языку, а алгебра - к языку программирования; Но повторим ещераз, эти различия только кажущиеся, а не реальные. В частности, ни один изподходов нельзя назвать « болеенепроцедурным « по сравнению с другим.

Реляционное исчислениеосновано на разделе математической логики, который называется исчислением предикатов.Идея использования исчисления предикатов в качестве основы языка баз данныхвпервые была высказана в статье Кунса (Kuhns).Понятие реляционного исчисления, т.е. специального применения исчисления предикатов,в реляционных базах данных, впервые было предложено Коддом в 1972, а позже Коддпредставил язык, основанный непосредственно на реляционном исчислении иназванный « подъязык данных ALPHA». Сам язык ALPHA никогда не был реализован, однако язык QUEL, который действительно был реализован и некотороевремя серьезно конкурировал с языком SQL, оченьпоходил на язык ALPHA, оказавший заметное влияние напостроение языка QUEL .

Основным средствомреляционного исчисления является понятие переменной кортежа (такженазываемойпеременной области значений). Коротко говоря, переменнаякортежа – это переменная, «изменяющаяся на» некотором заданном отношении, т.е.переменная, допустимыми значениями которой являются кортежи заданногоотношения. Другими словами, если переменная кортежа V изменяется в пределах отношения r, то в любойзаданный момент переменная V представляет некоторыйкортеж t отношения r. Например, запрос «Получить номера поставщиковиз числа тех, которые находятся в Лондоне» может быть выражен на языке QUEL так:

RANGE OF SX IS S;

RETRIEVE(SX.S#) WHERE SX.CITY = “London”;

Переменной кортежа здесьявляется переменная SX, которая изменяется на отношении,представляющем собой текущее значение переменной – отношения S(оператор RANGE – оператор определения этойпеременной). Оператор RETRIEVE означаетследующее: «Для каждого возможного значения переменной SX выбирать компонент S# этого значения тогда и толькотогда, когда его компонент CITY имеет значение ‘London’».

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

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

В статье Лакруа (Lacroix) и Пиротте (Pirotte)предлагается альтернативная версия исчисления, называемая исчислением доменов,в которой переменные кортежа изменяются на доменах, т.е. являются переменными,изменяемыми на доменах, а не на отношениях. В литературе предлагается множество языков исчисления доменов. Наиболее известный из них – пожалуй, Query-By-Example,или QBE (в действительности онявляется смешанным, так как в языке QBE присутствуют и элементы исчисления кортежей). Существует несколько коммерческихреализаций этого языка.

2.Исчисление кортежей.

Сначала введем дляреляционного исчисления конкретный синтаксис, взяв за образец (хотя умышленноне совсем точно) версию исчисления языка Titorial D, а затем перейдём к обсуждениюсемантики. В следующих ниже подразделах обсуждаются синтаксис и семантика.

2.1.Синтаксис.

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

Начнем с повторениясинтаксиса параметра <реляционное выражение>. < реляционноевыражение>

::= RELATION {<списоквыражений кортежей>}

| < имя переменной-отношения>

| < реляционная операция>

| < реляционное выражение>

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

<определениепеременной кортежа>

::= RANGEVAR <имя переменной кортежа >

RANGES OVER<список реляционных выражений >;

Параметр <имя переменной кортежа> может использоваться как <выражение кортежа>, однако,лишь в определенном контексте, а именно:

— перед точкой и последующим уточнением в параметре < ссылка наатрибут кортежа >;

— сразу после квантора в параметре < логическое выражение с квантором>;

— как операнд в параметре < логическое выражение >;

— как параметр < прототип кортежа > или как (операнд)подпараметр < выражение> в параметре < прототип кортежа >.

< ссылка на атрибут кортежа >

::= <имя переменной кортежа>.<ссылка на атрибут>[ AS <имя атрибута>]

Параметр <ссылка наатрибут кортежа > может использоваться как параметр < выражение>, нотолько в определенном контексте, а именно:

— как операнд параметра <логическое выражение >;

— как параметр <прототип кортежа > или как (операнд) подпараметр <выражение> в параметре <прототип кортежа>.

< логическоевыражение >

::= … все обычные возможности вместе с:

| < логическое выражение с квантором>

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

— Параметр < логическое выражение> расположен непосредственнопосле параметра < реляционная операция> (т.е. параметр < логическоевыражение > следует сразу за ключевым словом WHERE.).

— Ссылка (обязательно свободная) именно на эту переменную кортежанепосредственно присутствуют в значении параметра <прототип кортежа>,непосредственно содержащегося в том же выражении <реляционная операция>(т.е.параметр <прототип кортежа> располагается непосредственно перед ключевымсловом WHERE).

Замечание потерминологии. В контексте реляционного исчисления (в версии исчислениядоменов или исчисления кортежей) логические выражения часто называют правильнопостроенными формулами (well-formed formulas – WFF,что произносится как « вэфф»). Далее мы также будем часто пользоваться этойтерминологией.

< логическоевыражение с квантором>

::= EXISTS < имя переменной кортежа >(<логическое выражение >)

| FORALL <имя переменной кортежа > (<логическое выражение >)

< реляционнаяоперация >

:: = < прототип кортежа > [ WHERE < логическоевыражение >]

В реляционной алгебре параметр < реляционная операция > представлял собой одну из формпараметра <реляционное выражение>, однако здесь он определяется иначе.Другие формы параметра < реляционное выражение > (в основном, именапеременных – отношений и обращение к операторам выбора) допустимы, как и ранее.

< прототипкортежа >

::= < выражение кортежа>

Все ссылки на переменныекортежа, помещенные непосредственно в значение параметра <прототип кортежа>,должны быть свободными в пределах данного параметра < прототип кортежа>.

Замечание.Прототип кортежа – термин удачный, но не стандартный.

2.2. Переменныекортежей.

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

RANGEVARSX RANGES OVER S;

RANGEVARSY RANGES OVER S;

RANGEVAR SPX RANGES OVER SP;

RANGEVAR SPY RANGES OVER SP;

RANGEVAR PX RANGES OVER P;

RANGEVAR SU RANGES OVER

(SX WHERE SX.CITY=’London’)

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

SPX.P# SPX = P# (‘P1’) ) );

Переменная кортежа SU из последнего примера определена на объединении множествакортежей поставщиков детали с номером ‘P1’. Обратитевнимание, что в определении переменной кортежа SUиспользуются переменные кортежей SX и SPX.Также обратите внимание на то, что в подобных определениях переменных,построенных на объединении отношений, объединяемые отношения, безусловно,должны быть совместимы по типу.

Замечание. Переменные кортежей не являются переменными в обычномсмысле (как в языках программирования); они являются переменными в логическомсмысле.

2.3. Свободные и связанные переменныекортежей.

Каждая ссылка напеременную кортежа (в некотором контексте, в частности в формуле WFF) является или свободной, или связанной.Сначала поясним это утверждение в чисто синтаксических терминах, а затемперейдем к обсуждению его смысла.

Пусть V– переменная кортежа. Тогда имеем следующее.

— Ссылки на переменную V в формулах WFF типа NOT p свободны или связаны в пределах этой формулы в зависимостиот того, свободны ли они в формуле p.Ссылки напеременную V в формулах WFFтипа (p AND q) и (p OR q) свободны или связаны в зависимости от того, свободны лиони в формулах p и q.

— Ссылки на переменную V, которые свободныв формуле WFF p,связаны в формулах WFF типа EXISTS V(p) и FORALL V(p). Другие ссылки на переменные кортежей в формуле p будут свободны или связаны в формулах WFFтипа EXISTS V(p) и FORALL V(p) в соответствии с тем, свободныли они в формуле p.

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

— Единственная ссылка на переменную V взначении параметра <имя переменной кортежа> является свободной в пределахэтого параметра <имя переменной кортежа>.

— Единственная ссылка на переменную V взначении параметра <ссылка на атрибут кортежа> V.A является свободной в пределах этого параметра <ссылка наатрибут кортежа>.

— Если ссылка на переменную V являетсясвободной в некотором выражении exp, то эта ссылка будеттакже свободной в любом выражении exp’, непосредственносодержащем выражение exp как подвыражение, если тольков выражении exp’ не вводится квантор, связывающийпеременную V.

Приведём несколько примеровформул WFF, содержащих переменные

кортежей.

— Простые сравнения

SX.S# = S# (‘S1’)

SX.S# = SPX.S#

SPX.P# ≠ PX.P#

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

— Логические выражения из простых сравнений

PX.WEIGHT <WEIGHT (15.5) OR PX.CITY = ‘Rome’

NOT (SX.CITY = ‘London’)

SX.S# = SPX.S#AND SPX.P# ≠ PX.P#

PX.COLOR = COLOR(‘Red’) OR PX.CITY = ‘London’

Здесь также все ссылки напеременные SX,PX и SPX являются свободными.

— Формулы WFF с кванторами

EXISTS SPX(SPX.S# = SX.S# AND SPX.P# = P# (‘P2’) )

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

В этих примерах ссылки напеременные SPX и PX являютсясвязанными, а ссылка на переменную SX являетсясвободной. Подробнее данные примеры объясняются ниже.

2.4. Кванторы.

Существуют два квантора: EXISTS и FORALL. Квантор EXISTS являетсяквантором существования, а FORALL─ кванторомвсеобщности. По сути, если выражение p ─ формула WFF, в которой переменная V свободна,то выражения

EXISTS V (p)

FORALL V (p)

также являются допустимымиформулами WFF, но переменная Vв них обеих будет связанной. Первая формула означает следующее: «Существуетпо крайней мере одно значение переменной V, такое,что вычисление формулы p даёт для него значение истина».Вторая формула означает следующее: «Для всех значений переменной V вычисление формулы p даёт значение истина».Предположим, например, что переменная V изменяется намножестве «Члены сената США в 1999 году», и предположим также, что выражение p ─ следующая формула WFF: «V ─ женщина» (разумеется, здесь не пытаемсяиспользовать формальный синтаксис). Тогда выражение EXISTS V(p) будетдопустимой формулой WFF, имеющей значение истина(true); выражение FORALL V(p) такжебудет допустимой формулой WFF, но вычисление егозначения будет давать значение ложь (false).

Теперь рассмотрим кванторсуществования EXISTS более внимательно. Ещё разобратимся к примеру из предыдущего раздела.

EXISTS SPX (SPX.S# = SX.S# AND SPX.P# = P# (‘P2’))

Из приведённых ранеерассуждений следует, что эта формула WFF может бытьпрочитана следующим образом.

В текущем значении отношения SPсуществует кортеж (скажем, SPX), такой, длякоторого значение атрибута S# в этом кортежеравно значению атрибута SX.S# (какое бы оно ни было), а значение атрибута P# в кортеже SPX равно ‘P2’.

Каждая ссылка напеременную SPX в этом примере является связанной.Единственная ссылка на переменную SX свободна.

Формально кванторсуществования EXISTS определяется как повторениеоперации OR (ИЛИ). Другими словами, если r ─ это отношение с кортежами t1,t2, …, tm, V─ это переменная кортежа, изменяющаяся на данном отношении, и p(V) ─ это формула WFF, в которой переменная Vиспользуется как свободная переменная, то формула WFFвида

EXISTS V (p (V))

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

falseOR 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, для чего вернёмся к соответствующемупримеру из предыдущего раздела.

FORALLPX (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, содержащее те же кортежи, что ив предыдущем примере. Тогда приведённые ниже выражения будут иметь указанныезначения.

FORALLV (V.A>1) : false

FORALLV (V.B>1) : true

FORALLV (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.

EXISTSx (x>3) AND x<0

Здесь имеется три ссылкина переменную x, обозначающие две различныепеременные. Первые две ссылки связаны и могли быть заменены ссылкой надругую переменную y без изменения общего смыслаформулы. Третья ссылка на переменную x не может бытьбезболезненно изменена. Таким образом, из двух приведённых ниже формул WFF первая эквивалентна рассмотренной формуле, а вторая─ нет.

EXISTSy (y>3) AND x<0

EXISTSy (y>3) AND y<0

Кроме того, обратите внимание, что окончательное значение первоначальнойформулы WFF не может быть определено, если неизвестно значениесвободной переменной x. В отличие от неё формула WFF, в которой все ссылки на переменные являются связанными,всегда однозначно имеет значение либо истина, либо ложь.

Дополнительная терминология. Формула WFF,в которой все переменные связаны, называется закрытой формулой WFF (фактически она являетсявысказыванием). Открытаяформула WFF ─ это формула, которая неявляется закрытой, т.е. такая формула, которая содержит по крайней мере однуссылку на свободную переменную.

2.6. Реляционныеоперации.

Параметр <реляционнаяоперация> не совсем уместен в контексте исчисления ─ более подходящимвариантом был бы параметр <реляционное определение>. Однако будемиспользовать именно первый вариант, и в качестве напоминания приводим следующийсинтаксис.

<реляционнаяоперация>

:: = <прототип кортежа> [ WHERE <логическоевыражение> ]

<прототипкортежа>

:: = <выражениекортежа>

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

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

— Во-вторых, ссылка на переменную кортежа в предложении WHERE может быть свободной только в случае, если на эту жепеременную (обязательно свободная) присутствует в соответствующем значениипараметра <прототип кортежа>.

Например, следующеевыражение является допустимым значением параметра <реляционная операция>(«Получить номера поставщиков, находящихся в Лондоне»).

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

Здесь ссылка напеременную SX в прототипе кортежа является свободной.Ссылка на переменную SX в предложении WHEREтакже является свободной, поскольку ссылка на ту же переменную (обязательносвободную) имеется и в значении параметра <прототип кортежа> этоговыражения.

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

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

SX.SNAMEWHERE EXISTS SPX (SPX.S# SX.S# AND

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

Здесь все ссылки напеременную SX являются свободными, тогда как все ссылкина переменную SPX (в предложении WHERE)являются связанными, как и должно быть, поскольку на них нет ссылок в прототипекортежа.

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

— Прежде всего, прототип кортежа ─ это список разделённыхзапятыми элементов (возможно, заключённый в скобки), каждый элемент которогоявляется либо ссылкой на атрибут кортежа (который может содержать предложение AS для введения нового имени атрибута), либо просто именемпеременной кортежа. Тем не менее отметим следующее.

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

б) Ссылкана атрибут кортежа без предложения 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’

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 WHERECOLOR = 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 Display Rome J3 OCR Athens J4 Console Athens 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.Строим декартово произведение диапазонов, выбранных на первом этапе. Вотрезультат.

S# SN

STA

TUS

CITY P# PN CO-LOR WEIGHT CITY J# JN CITY S# P# J# QTY S1 Sm 20 Lon P1 Nt Red 12.0 Lon J3 OR Ath S1 P1 J1 200 S2 Sm 20 Lon P1 Nt Red 12.0 Lon J3 OR Ath S1 P1 J4 700 .. .. .. … .. .. … … … .. .. … .. .. .. …

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

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

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

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

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

S# SN

STA

TUS

CI-TY P# PN CO-LOR WEIGHT CITY J# JN CI-TY S# P# J# QTY S1 Sm 20 Lon P1 Nt Red 12.0 Lon J4 Cn Ath S1 P1 J4 700 S2 Jo 10 Par P3 Sc Blue 17.0 Rom J3 OR Ath S2 P3 J3 200 S2 Jo 10 Par P3 Sc Blue 17.0 Rom J4 Cn Ath S2 P3 J4 200 S4 Cl 20 Lon P6 Cg Red 19.0 Lon J3 OR Ath S4 P6 J3 300 S5 Ad 30 Ath P2 Bt Green 17.0 Par J4 Cn Ath S5 P2 J4 100 S5 Ad 30 Ath P1 Nt Red 12.0 Lon J4 Cn Ath S5 P1 J4 100 S5 Ad 30 Ath P3 Sc Blue 17.0 Rom J4 Cn Ath S5 P3 J4 200 S5 Ad 30 Ath P4 Sc Red 14.0 Lon J4 Cn Ath S5 P4 J4 800 S5 Ad 30 Ath P5 Cm Blue 12.0 Par J4 Cn Ath S5 P5 J4 400 S5 Ad 30 Ath P6 Cg Red 19.0 Lon J4 Cn Ath S5 P6 J4 500

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

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

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

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

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

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

EXISTS JX FORALLPX EXISTS SPJX

Значит, выполняются следующиеоперации.

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

SPJ.P#, SPJ.J# иSPJ.QTY). В результате получаемследующее.

S# SN

STA

TUS

CI-TY P# PN CO-LOR WEIGHT CITY J# JN CI-TY S1 Sm 20 Lon P1 Nt Red 12.0 Lon J4 Cn Ath S2 Jo 10 Par P3 Sc Blue 17.0 Rom J3 OR Ath S2 Jo 10 Par P3 Sc Blue 17.0 Rom J4 Cn Ath S4 Cl 20 Lon P6 Cg Red 19.0 Lon J3 OR Ath S5 Ad 30 Ath P2 Bt Green 17.0 Par J4 Cn Ath S5 Ad 30 Ath P1 Nt Red 12.0 Lon J4 Cn Ath S5 Ad 30 Ath P3 Sc Blue 17.0 Rom J4 Cn Ath S5 Ad 30 Ath P4 Sc Red 14.0 Lon J4 Cn Ath S5 Ad 30 Ath P5 Cm Blue 12.0 Par J4 Cn Ath S5 Ad 30 Ath P6 Cg Red 19.0 Lon J4 Cn Ath

2.(FORALL PX) Делим полученный результат на отношение P.В результате имеем следующее.

S# SN STATUS CITY J# JNAME CITY 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 (SPXWHERE SPX.P# = PX.P#, QTY) AS TOTQTY)

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

SUM (SPX, QTY) ASGRANDTOTAL)

Ø Определить номера и вес в граммах всех типов деталей, вескоторых превышает 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 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 ASSB) WHERE EXISTS CITYZ

(S (S#: SX, CITY: CITYZ) AND

S (S#: SY, CITY: CITYZ) AND

SX < SY)

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

NAMEX WHEREEXISTS SX EXISTS PX

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

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

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

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

NAMEX WHEREEXISTS 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 USINGCITY;

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г.