Сибилев В.Д. Модели и проектирование баз данных

Подождите немного. Документ загружается.

кортежей операнда. Имеет смысл ввести такие агрегатные функции,

которые выполняют вычисления, часто встречающиеся при

подведении итогов:

COUNT

число значений атрибута;

SUM сумма значений атрибута;

AVG

среднее арифметическое значений атрибута;

MAX максимальное значение атрибута;

MIN

минимальное значение атрибута.

Пример:

SUMMARIZE SPJ BY (S#, P#) SUM(Qt) AS Tot_Qt;

Это выражение производит отношение со схемой {S#, P#,

Tot_Qt}. Тело отношения для каждой пары значений {S#, P#},

встретившейся в SPJ хотя бы один раз, будет содержать ровно один

кортеж с соответствующими значениями номера поставщика, номера

детали и суммарного объема поставок этой детали этим поставщиком

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

детали.

2.5.6 Операторы обновления данных. Для обновления данных

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

значений атрибутов в существующих кортежах базовых отношений.

Они не входят в состав операций РА. Мы приводим здесь синтаксис

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

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

обновления данных.

Оператор вставки кортежей. Синтаксис для оператора

вставки кортежей определим так:

INSERT источник INTO приемник;

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

производящие отношения, совместимые по объединению.

Все кортежи источника вставляются в приемник.

Пример:

Пусть в схеме нашей БД определено отношение TEMP со

схемой {P#, TOTAL}. Оператор

INSERT ((SUMMARIZE SPJ BY (P#) SUM (Qt) AS TOTAL)

WHERE TOTAL > 10000) INTO TEMP;

вставит в отношение TEMP все кортежи отношения, произведенного

операцией SUMMARIZE.

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

этого оператора следующий:

UPDATE приемник список-присваиваний;

список-присваиваний ::= атрибут := скалярное-выражение |

список-присваиваний, атрибут := скалярное-выражение

Здесь приемник – любое реляционное выражение. Каждый

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

Все кортежи приемника обновляются в соответствии с

указанным списком присваиваний.

Пример:

UPDATE (S WHERE Ci = ‘Яя’) St := St10;

Будут обновлены значения атрибута St во всех кортежах

отношения S, удовлетворяющих условию Ci = ‘Яя’.

Оператор удаления кортежей. Оператор удаления кортежей

имеет вид:

DELETE приемник;

Здесь приемник – любое реляционное выражение.

Удаляются все кортежи целевого отношения, произведенного

приемником.

Пример:

DELETE (S WHERE Ci = ‘Яя’);

Будут удалены все кортежи отношения S, содержащие сведения

о поставщиках, размещенных в Яе.

Реляционные выражения, встречающиеся в операторах INSERT,

UPDATE, DELETE, определяют область действия этих операторов.

Как правило, эти выражения оказываются либо именами базовых

отношений, либо подмножествами кортежей этих отношений. Однако,

в принципе, они могут определять какую угодно часть БД.

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

множеств кортежей. Даже когда обновляется один кортеж, на самом

деле обновляется множество, состоящее из одного элемента. Иногда

обновление одноэлементного множества невозможно.

Например, в нашей БД может существовать ограничение

целостности: «Все поставщики из Яи имеют одинаковые статусы».

Тогда операция

UPDATE (S WHERE S# = ’S1’) St := 50;

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

S1 размещается в Яе и есть еще поставщики из Яи. Такая операция

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

UPDATE (S WHERE Ci = ‘Яя’) St := 50;

обновляющую все кортежи, соответствующие поставщикам из Яи,

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

целостности.

2.5.7 Резюме. РА замкнута относительно множества отношений.

Всякое выражение РА производит отношение, следовательно,

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

Выражения РА имеют процедурную интерпретацию.

Подмножество данных, представленное выражением РА (запрос),

может быть вычислено в соответствии с определениями элементарных

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

скобок.

РА есть средство записи выражений. Выражения РА могут

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

данных и других целей.

Все реляционные операции манипулируют данными на уровне

множеств кортежей.

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

2.6.1 Алгебра и исчисление. Реляционное исчисление (РИ), как

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

реляционными данными.

РА и РИ эквивалентны в том смысле, что для любого

допустимого выражения РА можно построить формулу РИ,

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

возникает вопрос: зачем включать в РМД и алгебру, и исчисление?

Ответ кроется в разном уровне процедурности этих механизмов.

РА представляет в явном виде набор операций, которые можно

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

реляционной алгебры имеют процедурную интерпретацию. Они

сообщают системе, как из базовых отношений построить требуемое

производное отношение. Оно может быть вычислено в соответствии с

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

старшинства и возможных скобок.

В отличие от РА, РИ есть просто система обозначений для

определения производного отношения в терминах других отношений.

Для формул РИ процедурной интерпретации нет. Они декларативны.

Формула просто определяет условия, которым должны удовлетворять

кортежи результирующего отношения, – требуемые данные

Например, запрос: «Получить имена поставщиков,

поставляющих деталь Р2» в терминах алгебры имеет вид:

(( SPJ JOIN S) WHERE P# = ‘P2’)[Sn];

и описывает следующую процедуру:

 построить естественное соединение SPJ и J по атрибуту S#;

 выбрать из результата кортежи, в которых P# = ‘P2’;

 выполнить проекцию результата на атрибут Sn.

Однако можно и не указывать, какие соединения, проекции и

селекции строить. Можно сформулировать на некотором формальном

языке фразу следующего содержания:

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

которых в SPJ существуют кортежи с тем же значением атрибута

S# и со значением атрибута P# = ‘P2’.»

Подобной фразой можно точно указать системе характеристики

интересующего нас отношения. Пусть она сама решает, какие

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

Формальный язык для точной записи подобных высказываний

называется реляционным исчислением. Его основой является

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

терминах исчисления. Однако, на самом деле это не всегда так.

исчисление предикатов первого порядка.

Современная РМД располагает двумя вариантами реляционных

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

переменных являются отношения (РИ с переменными-кортежами), а в

другом – домены (РИ с переменными на доменах). Оба РИ, как и РА,

обладают свойством замкнутости относительно множества отношений.

То есть формулы РИ определяются над отношениями и

интерпретируются как отношения. Это дает возможность строить

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

реляционной БД.

2.6.2 РИ с переменными-кортежами. Основным понятием

этого варианта РИ является понятие переменной-кортежа.

 Пусть R – некоторое отношение. Величина t,

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

переменной-кортежем, определенной на R.

На интуитивном уровне переменная-кортеж это

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

одна строка – текущее значение переменной.

Синтаксис исчисления. Для записи выражения РИ кортежей

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

целевого отношения и сформулировать условия, которым должны

удовлетворять кортежи его тела.

область-определения ::= RANGE OF переменная IS

список-элементов-области;

выражение ::= (список-целевых-элементов) [WHERE ппф] ;

целевой-элемент ::= переменная |

переменная.атрибут [AS атрибут];

ппф ::= условие | NOT ппф | условие AND ппф |

условие OR ппф |IF условие THEN ппф |

EXISTS переменная (ппф) |

FOR ALL переменная (ппф) | (ппф);

условие ::= (ппф) | сравнение;

сравнение ::= символ  символ;

символ ::= переменная.атрибут | константа;

 :: = < | > | =;

Здесь отношение, переменная, атрибут - идентификаторы;

список – список элементов, разделенных запятыми, ппф – правильно

построенная формула исчисления. Квадратные скобки показывают, что

заключенные в них компоненты могут быть опущены.

Область определения. Переменная-кортеж t определяется

фразой:

RANGE OF t IS X

, X

, …, X

;

где t– имя переменной-кортежа;

– имя отношения или выражение исчисления кортежей.

Все X

должны быть совместимы по объединению. Переменная

t принимает значение на объединении X

 X

…  X

Обычно список элементов области определения – это одно

отношение. Например, предложение

RANGE OF SX IS S;

указывает область определения переменной SX – отношение S.

Вот более сложный случай.

RANGE OF SPJX IS SPJ;

RANGE OF SY IS (SX) WHERE SX.Ci = ‘Яя’,

(SX) WHERE

EXISTS SPJX (SPJX.S# = SX.S#

AND SPJX.P# = ‘P1’);

Переменная SY принимает значения на множестве кортежей

отношения S, относящихся к поставщикам, расположенным в Яе или

поставляющим деталь Р1.

Список целевых элементов. Каждый целевой элемент – это или

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

t.A [ AS X ],

где t – имя переменной-кортежа;

А – имя атрибута сопоставляемого отношения;

Х – новое имя атрибута А, используемое в ссылках на атрибут

переменной-кортежа t.

Сопоставляемое отношение – это область определения

переменной t, то есть, отношение являющееся объединением

элементов-области.

В вышеприведенном примере сопоставляемое отношение есть

объединение отношений

(SX) WHERE SX. Ci = ‘Яя’;

(SX) WHERE EXISTS SPJX

(SPJX. S# = SX. S# AND SPJX. P# = ‘P1’);

Примеры целевых списков:

SX.S#, SX.Sn;

SX.Ci AS SCity;

SX.S#, SX.Ci AS SCity, PX.P#, PX.Ci AS Pcity;

Список целевых элементов не имеет смысла вне выражения

исчисления.

Целевой список определяет схему целевого отношения. Имена

атрибутов (и, соответственно, домены) наследуются от схемы

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

конструкцией «AS атрибут».

Правильно построенные формулы (ППФ). Как видно из

определения, ППФ – это предикат первого порядка.

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

SX.S# = SPJX.S#;

SX.S# = ‘S1’;

SX.S# = SPJX.S# AND SPJX.P# = ‘P1’;

NOT (SX.Ci = ‘Яя’);

IF SX.Ci = ‘Яя’ THEN SPJX.S# = ‘S1’;

Последний предикат – пример намеренно бессмысленного, но

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

Правильно построенная формула может содержать кванторы

EXISTS (существует) и FORALL (для всякого).

Выражение EXISTS SX (SX.Ci = ‘Яя’) может быть прочитано

так: «Существует в области определения переменной SX кортеж со

значением атрибута Ci равным ‘Яя’». Предикат принимает

значение .T., если в текущем значении отношения S есть хотя бы один

кортеж со значением Ci = ‘Яя’.

Вообще говоря, если R – некоторое отношение, t – переменная,

определенная на R, t

, t

, …, t

– значения t (кортежи R), a f(t) – ППФ,

то формула EXISTS t (f(t)) равносильна бескванторной формуле .F.

OR f(t

) OR f(t

) OR … OR f(t

Выражение FORALL SX (SX. Ci = ‘Яя’) может быть прочитано

так: «В каждом кортеже отношения S значение атрибута Ci равно

‘Яя’».

В предыдущих обозначениях формула FORALL t (f(t))

равносильна бескванторной формуле .Т. AND f(t

) AND f(t

) AND …

AND f(t

). Очевидно, FORALL t (f(t)) равносильно NOT EXISTS t (NOT

(f(t)).

Переменная t, входящая в ППФ, называется связанной или

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

Примеры:

f(t) – переменная t свободная;

f(t, q) – переменные t и q свободные;

EXISTS t (f(t, q)) – переменная t связанная, q – свободная;

FORALL t (f(t)) AND g(t) - первое вхождение t – связанное,

второе – свободное.

В последней формуле одним и тем же символом t обозначены

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

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

меняя смысла высказывания и значения предиката. Переменная

служит здесь лишь для связи внутренних параметров предиката f( ) с

внешним квантором. Второе вхождение переменной t имеет

совершенно иной смысл. Здесь g(t) принимает то или иное значение в

зависимости от значения переменной t. Заменить t на x, например,

здесь нельзя, поскольку х и t могут принимать различные значения.

 Связанная переменная подобна локальной переменной

в языках программирования.

Формула, в которой все переменные связаны, называется

закрытой. Например, FORALL x (EXISTS y (f(x, y))) – закрытая

формула. Формула, содержащая по крайней мере одну свободную

переменную, называется открытой.

Примеры запросов. Здесь приведены формулы РИ кортежей,

эквивалентные выражениям РА из примеров п. 2.5.4. Номера формул

соответствуют номерам запросов.

1) RANGE OF JX IS J;

JX;

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

SX, PX, JX, SPJX определены на отношениях S, P, J, SPJ,

соответственно. Если понадобится определить на отношении более

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

например, SY, SZ… Ненужные скобки будем опускать.

2) (JX.J#, JX.Jn) WHERE Ci = ‘Томск’;

3) SPJX.S# WHERE J# = ‘J1’;

4) SPJX.S# WHERE J# = ‘J1’ AND P# = ‘P1’;

5) JX.Jn WHERE EXISTS SPJX

(SPJX.S# = ‘S1’ AND SPJX.J# = JX.J#);

6) PX.Co WHERE EXISTS SPJX

(SPJX.S# = ‘S1’ AND SPJX.P# = PX.P#);

7) SPJX.S# WHERE J# = ‘J1’ AND EXISTS SPJY

(SPJY.S# = SPJX.S# AND J# = ‘J2’);

8) SPJX.S# WHERE SPJX.J# = ‘J1’ AND EXISTS PX

(PX.P# = SPJX.P# AND PX.Co = ‘красный’);

9) SPJX.P# WHERE FORALL JX

(IF JX.Ci = ‘Томск’ THEN EXISTS SPJY

(SPJY.J# = JX.J# AND SPJY.P# = SPJX.P#));

Другая формулировка этого запроса, не использующая квантора

всеобщности:

SPJX.P# WHERE NOT EXISTS JX

(JX.Ci = ‘Томск’ AND NOT EXISTS SPJY

(SPJY.J# = JX.J# AND SPJY.P# = SPJX.P#));

10) SPJX.S# WHERE EXISTS PX

(PX.Co = ‘красный’ AND PX.P# = SPJX.P#) AND

EXISTS JX (JX.J# = SPJX.J# AND

(JX.Ci = ‘Томск’ OR JX.Ci = ‘Яя’));

11) JX.J# WHERE EXISTS SPJX EXISTS SX

(JX.J# = SPJX.J# AND SX.S# =SPJX.S# AND

NOT (JX.Ci = SX.Ci) );

12) JX.J# WHERE NOT EXISTS SPJX EXISTS PX

(SPJX.P# = PX.P# AND PX.Ci = ‘Томск’ AND

PX.Co = ‘красный’ AND SPJX.J# = JX.J#);

13) SX.Sn WHERE EXISTS SPJX

(SPJX.P# = ‘P2’ AND SPJX.S# = SX.S#);

14) SX.Sn WHERE FORALL PX (EXISTS SPJX

(PX.P# = SPJX.P# AND SPJX.S# = SX.S#));

2.6.3 Реляционное исчисление с переменными на доменах. В

этом варианте РИ используются скалярные переменные,

принимающие значения на доменах.

Условие принадлежности. Основное отличие синтаксиса РИ

доменов от определенного в п. 2.6.2 состоит в том, что здесь используется

специальная синтаксическая конструкция – условие принадлежности:

отношение (пара, пара, …),

пара ::= атрибут : символ,

символ ::= переменная | литерал.

Здесь отношение и переменная – идентификаторы.

 Условие принадлежности принимает значение

«истина», если и только если в отношении существует кортеж, в

котором указанные атрибуты принимают указанные значения.

Примеры.

Условие S(S# : ‘S1’) примет значение .T., если и только если в

текущем значении отношения S существует кортеж со значением

атрибута S#, равным S1.

Условие SPJ(S# : SX, P# : PX) принимает значение .T., если и

только если в SPJ есть кортеж, в котором значения S# и P#

совпадают с текущими значениями переменных SX и PX,

определенных на доменах S# и P#.

Примеры запросов. Здесь приведены формулы РИ доменов,

эквивалентные выражениям РА из некоторых примеров п. 2.5.4.

Номера формул соответствуют номерам запросов.

1) RANGE OF JX IS J#;

RANGE OF JnX IS Jn;

RANGE OF CiX IS Ci;

(JX, JnX, CiX) WHERE J(J# : JX, Jn : JnX, Ci : CiX);

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