Содержание.
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 так:
RANGEOF SXIS S;
RETRIEVE (SX.S#) WHERE SX.CITY = “London”;
Переменной кортежа здесь являетсяпеременная SX, котораяизменяется на отношении, представляющем собой текущее значение переменной –отношения S (оператор RANGE – оператор определения этой переменной). Оператор RETRIEVE означает следующее:«Для каждого возможного значения переменной SX выбирать компонент S# этого значения тогда и только тогда, когда егокомпонент CITY имеет значение ‘London’».
В связи с тем, что реляционное исчисление основано на переменных кортежа,его первоначальную версию (для отличия от исчисления доменов, речь о котором пойдет ниже) называют также исчислением кортежей.
Замечание. Дляудобства примем следующее соглашение: далее в этой книге термины исчисление иреляционное исчисление, приведенные безуточнения «кортежей» или «доменов», будут означать именноисчисление кортежей (там, где это играеткакую-то роль).
В статье Лакруа (Lacroix) и Пиротте (Pirotte) предлагаетсяальтернативная версия исчисления, называемая исчислением доменов,в которой переменные кортежа изменяются на доменах, т.е. являются переменными,изменяемыми на доменах, а не на отношениях. В литературе предлагается множество языков исчисления доменов. Наиболееизвестный из них – пожалуй, Query-By-Example, или QBE(в действительности он являетсясмешанным, так как в языке QBE присутствуют и элементы исчисления кортежей).Существует несколько коммерческих реализаций этого языка.
2.Исчислениекортежей.
Сначалавведем для реляционного исчисления конкретный синтаксис, взяв за образец (хотяумышленно не совсем точно) версию исчисления языка TitorialD, а затем перейдём к обсуждению семантики. В следующих ниже подразделах обсуждаются синтаксис исемантика.
2.1.Синтаксис.
Замечание. Многие из приведенных здесьсинтаксических правил не будут поняты вам до тех пор, пока вы не изучите семантический материал, следующий далее.Однако мы все же решили собрать все правила вместе для удобства ссылок.
Начнем с повторения синтаксиса параметра.
:: = RELATION{}
|
|
|
Иными словами, синтаксис параметра остаетсяпрежним, однако из наиболее важных егоподпараметров, , теперь будет иметьсовершенно иное определение.
:: = RANGEVAR
RANGESOVER ;
Параметр может использоватьсякак , однако,лишь в определенном контексте, а именно:
§ и последующим уточнением впараметре ;
§
§ ;
§ .
:: = .[ AS]
Параметр может использоваться как параметр , но только в определенном контексте, а именно:
§
§ параметр или как (операнд)подпараметр в параметре .
:: = … все обычные возможности вместе с:
|
Ссылкина переменные кортежей в значениипараметра могут быть свободными в пределах этого параметра тогда и только тогда, когдавыполнено два следующих условия.
§ расположен непосредственнопосле параметра (т.е. параметр следуетсразу за ключевым словом WHERE.).
§ содержащегося в том же выражении (т.е. параметр располагается непосредственно перед ключевым словом WHERE).
Замечаниепо терминологии. В контексте реляционного исчисления (в версии исчисления доменов или исчисления кортежей)логические выражения часто называют правильно построенными формулами (well-formedformulas– WFF, что произноситсякак « вэфф»). Далее мы также будем часто пользоваться этой терминологией.
:: = EXISTS ()
| FORALL ()
:: = [ WHERE ]
Вреляционной алгебре параметр представлял собой одну из форм параметра , однако здесь он определяетсяиначе. Другие формы параметра (в основном, имена переменных – отношений иобращение к операторам выбора) допустимы, как и ранее.
:: =
Все ссылки на переменные кортежа,помещенные непосредственно в значение параметра ,должны быть свободными в пределах данного параметра .
Замечание. Прототип кортежа – терминудачный, но не стандартный.
2.2. Переменные кортежей.
Приведём несколько примеров определенияпеременных кортежей (выраженных в контексте базы данных поставщиков и деталей).
RANGEVAR SX RANGES OVER S;
RANGEVAR SY RANGES OVER S;
RANGEVAR SPX RANGESOVER SP;
RANGEVAR SPY RANGESOVER SP;
RANGEVAR PX RANGES OVER P;
RANGEVAR SU RANGES OVER
(SX WHERESX.CITY=’London’)
(SX WHERE EXISTSSPX (SPX.S# = SX.S# AND
SPX.P# SPX = P# (‘P1’) ) );
Переменная кортежа SU из последнего примера определена наобъединении множества кортежей поставщиков детали с номером ‘P1’. Обратите внимание, что вопределении переменной кортежа SUиспользуются переменные кортежей SX и SPX.Также обратите внимание на то, что в подобных определениях переменных,построенных на объединении отношений, объединяемые отношения, безусловно,должны быть совместимы по типу.
Замечание. Переменные кортежей не являются переменными в обычномсмысле (как в языках программирования); они являются переменными в логическом смысле.
2.3.Свободные и связанные переменные кортежей.
Каждая ссылка на переменную кортежа (внекотором контексте, в частности в формуле WFF) является или свободной,или связанной. Сначала поясним этоутверждение в чисто синтаксических терминах, а затем перейдем к обсуждению егосмысла.
Пусть V – переменная кортежа. Тогда имеем следующее.
§ V вформулах WFF типа NOTp свободны или связаны в пределах этой формулы в зависимости оттого, свободны ли они в формуле p.Ссылкина переменную V вформулах WFF типа (pANDq) и (pORq) свободны или связаны взависимости от того, свободны ли они в формулах p и q.
§ V,которые свободны в формуле WFFp,связаны в формулах WFFтипа EXISTSV(p) и FORALLV(p). Другие ссылки на переменные кортежейв формуле p будутсвободны или связаны в формулах WFFтипа EXISTSV(p) и FORALLV(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 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 ─ женщина»(разумеется, здесь не пытаемся использовать формальный синтаксис). Тогдавыражение EXISTSV(p) будет допустимой формулой WFF, имеющей значение истина (true); выражение FORALLV(p) также будет допустимой формулой WFF, но вычисление егозначения будет давать значение ложь (false).
Теперь рассмотрим квантор существования EXISTS более внимательно. Ещёраз обратимся к примеру из предыдущего раздела.
EXISTSSPX (SPX.S# = SX.S# ANDSPX.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вида
EXISTSV (p (V))
равносильна следующей формуле WFF.
false OR p (t1) OR … OR p ™
В частности, обратите внимание, что еслиотношение R пустое(т.е. m=0), торезультатом вычисления данного выражения будет значение ложь.
Рассмотрим в качестве примера отношениеr, содержащее следующиекортежи.
(1, 2, 3)
(1, 2, 4)
(1, 3, 4)
Для простоты предположим, что триатрибута, идущие по порядку слева направо, имеют имена A, B и Cсоответственно и каждый из этих атрибутов имеет тип INTEGER. Тогда приведённыениже выражения будут иметь указанные значения.
EXISTSV (V.C>1) : true
EXISTS V (V.B>3) : false
EXISTSV (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 вида
FORALLV (p (V) )
равносильна следующей формуле WFF.
trueAND p (t1) AND … ANDp ™
В частности, обратите внимание, чтоесли отношение rпустое, то результатом вычисления данного выражения будет значение истина.
В качестве примера рассмотрим отношениеR, содержащее те жекортежи, что и в предыдущем примере. Тогда приведённые ниже выражения будутиметь указанные значения.
FORALLV (V.A>1) : false
FORALL V (V.B>1) : true
FORALLV (V.A = 1 and V.C>2) :true
Замечание.Квантор FORALL включёнв реляционное исчисление просто для удобства. Он не является необходимым, таккак приведённое ниже тождество показывает, что любая формула WFF, использующая квантор FORALL, всегда может бытьзаменена эквивалентной формулой WFF,использующей квантор EXISTS.
FORALL V (p) ≡ NOTEXISTS V (NOT p)
(Проще говоря, выражение «все значения V, удовлетворяющие формуле p» ─ это то же самое,что и выражение «нет таких значений V, которые бы не удовлетворяли формуле p».)
Например, утверждение (истинное)
Длялюбого целого x существует целое y, такое, что y>x
равносильно утверждению
Несуществует целого x, такого, что не существует целого y, такого, что y>x.
(Иначе говоря, не существует наибольшего целого числа.) Но обычно легче выразитьподобное утверждение в терминах квантора FORALL, чем в терминах квантора EXISTS, с использованием двойногоотрицания. Другими словами, на практике гораздо удобнее использовать обаквантора.
2.5.Ещё раз о свободных и связанных переменных.
Предположим, что переменная xизменяетсяна множестве всех целых чисел, и рассмотрим следующую формулу WFF.
EXISTSx (x>3)
Связанная переменная x в этой формуле WFFявляется своего рода фиктивнойпеременной. Она служит лишь для связи внутренних параметров выражения с внешнимквантором. В формуле WFFпросто утверждается, что существует целое число (скажем, x), которое больше 3. Следовательно, значение этой формулы WFF осталось бы полностью неизменным, если бы все экземпляры x были заменены экземплярами некоторой другой переменной (скажем,y). Другими словами, формула WFFEXISTSy (y>3) семантически идентична формуле,приведённой ранее.
Теперь рассмотрим другую формулу WFF.
EXISTS x (x>3) AND x
Здесь имеется три ссылки на переменную x, обозначающие две различные переменные. Первые две ссылки связаны имогли быть заменены ссылкой на другую переменную y без изменения общего смысла формулы.Третья ссылка на переменную xне может быть безболезненно изменена. Таким образом, из двух приведённых нижеформул WFF перваяэквивалентна рассмотренной формуле, а вторая ─ нет.
EXISTS y (y>3) AND x
EXISTS y (y>3) AND y
Кроме того, обратите внимание,что окончательное значение первоначальной формулы 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)являются связанными, как и должно быть, поскольку на них нет ссылок в прототипекортежа.
Интуитивно понятно, что результатомвыполнения операции, заданной параметром , будетотношение, содержащее все возможные значения кортежей, определяемых параметром, для которых результат вычисления ло