2008 г.

Базы данных. Вводный курс

Сергей Кузнецов

Лекция 5. Базисные средства манипулирования реляционными данными: алгебра A Дейта и Дарвена

5.1. Введение

В этой лекции мы обсудим новый «минимальный» вариант алгебры, предложенный несколько лет тому назад Дейтом и Дарвеном [1.5]. Как уже отмечалось в предыдущей лекции, возможно, новая алгебра не очень практична, но зато красива и элегантна.

Обсуждавшаяся в предыдущей лекции алгебра Кодда в большей степени базируется на теории множеств. Базовыми операциями являются переименование атрибутов, объединение, пересечение, взятие разности, декартово произведение, проекция и ограничение. Операция соединения общего вида, хотя и включается в алгебру, является вторичной и явно представляется через другие операции. Фундаментальная же в реляционном подходе операция естественного соединения выражается через соединение общего вида и в алгебру не включается. В терминах алгебры Кодда проще всего определяются алгебраические черты языка SQL, в частности общая семантика оператора SELECT.

Базисом предложенной Крисом Дейтом и Хью Дарвеном Алгебры A являются операции реляционного отрицания (дополнения), реляционной конъюнкции (или дизъюнкции) и проекции (удаления атрибута). Реляционные аналоги логических операций определяются в терминах отношений на основе обычных теоретико-множественных операций и позволяют выражать напрямую операции пересечения, декартова произведения, естественного соединения, объединения отношений и т. д. Путем комбинирования базовых операций выражаются операции переименования атрибутов, соединения общего вида, взятия разности отношений. Алгебра A позволяет лучше осознать логические основы реляционной модели, хотя, безусловно, является в меньшей степени ориентированной на практическое применение, чем алгебра Кодда¹⁶⁾. Даже сами авторы Алгебры A, Дейт и Дарвен, в своем учебном языке Tutorial D [1.5] используют не Алгебру A напрямую, а некоторое ее надмножество, в большей степени напоминающее алгебру Кодда.

5.2. Базовые операции Алгебры A

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

Пусть r – отношение, A – имя атрибута отношения r, T – имя соответствующего типа (т. е. типа или домена атрибута A), v – значение типа T. Тогда:

заголовком Hr отношения r называется множество атрибутов, т.е. упорядоченных пар вида <A, T>. По определению никакие два атрибута в этом множестве не могут содержать одно и то же имя атрибута A;
кортеж tr, соответствующий заголовку Hr, – это множество упорядоченных триплетов вида <A, T, v>, по одному такому триплету для каждого атрибута в Hr;
тело Br отношения r – это множество кортежей tr. Заметим, что (в общем случае) могут существовать такие кортежи tr, которые соответствуют Hr, но не входят в Br.

Заметим, что заголовок – это множество (упорядоченных пар вида <A, T>), тело – это множество (кортежей tr), и кортеж – это множество (упорядоченных триплетов вида <A, T, v>). Элемент заголовка – это атрибут (т. е. упорядоченная пара вида <A,T>); элемент тела – это кортеж; элемент кортежа – это упорядоченный триплет вида <A, T, v>. Любое подмножество заголовка – это заголовок, любое подмножество тела – это тело, и любое подмножество кортежа – это кортеж.

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

Во всех формальных спецификациях exists обозначает квантор существования; exists tr означает «существует такой tr, что». Символ «» означает принадлежность одного множества другому; trBr означает, что элемент tr принадлежит множеству Br. Выражение trBr означает, что элемент tr не принадлежит множеству Br. Операции minus и union являются традиционными теоретико-множественными операциями взятия разности и объединения множеств.

Поскольку некоторые базовые операции Алгебры A имеют названия обычных логических операций, чтобы избежать путаницы, имена реляционных операций берутся в угловые скобки: <NOT>, <AND>, <OR> и т. д. В исходный базовый набор операций входят операции реляционного дополнения <NOT>, удаления атрибута <REMOVE>, переименования атрибута <RENAME>, реляционной конъюнкции <AND> и реляционной дизъюнкции <OR>.

5.2.1. Операция реляционного дополнения

Пусть s обозначает результат операции <NOT> r. Тогда:

Hs = Hr (заголовок результата совпадает с заголовком операнда);
Bs = {ts : exists tr (tr Br and ts = tr) } (в тело результата входят все кортежи, соответствующие заголовку и не входящие в тело операнда).

Операция <NOT> производит дополнение s заданного отношения r. Заголовком s является заголовок r. Тело s включает все кортежи, соответствующие этому заголовку и не входящие в тело r.

Видимо, следует пояснить, почему реляционный аналог операции логического отрицания называется здесь операцией реляционного дополнения. Во-первых, термин «дополнение» полностью соответствует сути операции <NOT>: тело результата операции <NOT> r является дополнением Br до полного множества кортежей, соответствующих Hr. Во-вторых, это не противоречит природе булевской операции NOT: у булевского типа имеются всего два значения – true и false, и NOT true = false, а NOT false = true. (Кстати, обратите внимание, что операцию NOT в трехзначной логике (см. лекцию 1) уже нельзя считать операцией дополнения.)

Чтобы привести пример использования операции <NOT>, предположим, что в состав домена ДОПУСТИМЫЕ_НОМЕРА_ПРОЕКТОВ, на котором определен атрибут ПРО_НОМ отношения НОМЕРА_ПРОЕКТОВ с рис. 5.1 слева, входит всего пять значений {1, 2, 3, 4, 5}. Тогда результат операции <NOT> НОМЕРА_ПРОЕКТОВ будет таким, как показано на рис. 5.1 справа.

5.2.2. Операция удаления атрибута

Пусть s обозначает результат операции r <REMOVE> A. Для обеспечения возможности выполнения операции требуется, чтобы существовал некоторый тип (или домен) T такой, что <A, T> Hr (т. е. в состав заголовка отношения r должен входить атрибут A). Тогда:

Рис. 5.1. Результат операции <NOT> НОМЕРА_ПРОЕКТОВ

Hs = Hr minus {<A, T>}, т. е. заголовок результата получается из заголовка операнда изъятием атрибута A;
Bs = {ts : exists tr exists v (tr Br and v T and <A,T,v> tr and ts = tr minus {<A,T,v>})}, т. е. в тело результата входят все кортежи операнда, из которых удалено значение атрибута A.

Операция <REMOVE> производит отношение s, формируемое путем удаления указанного атрибута A из заданного отношения r. Операция эквивалентна взятию проекции r на все атрибуты, кроме A. Заголовок s получается теоретико-множественным вычитанием из заголовка r множества из одного элемента {<A, T>}. Тело s состоит из таких кортежей, которые соответствуют заголовку s, причем каждый из них является подмножеством некоторого кортежа тела отношения r.

Примером операции REMOVE (конечно же, очень похожим на пример использования операции PROJECT из предыдущей лекции) является СЛУЖАЩИЕ REMOVE ПРО_НОМ (получить данные о служащих, участвующих в проектах). Результат этой операции над отношением СЛУЖАЩИЕ, тело которого приведено в верхней части рис. 5.2, показан на рис. 5.2 внизу.

Рис. 5.2. Результат операции СЛУЖАЩИЕ REMOVE ПРО_НОМ

5.2.3. Операция переименования

Пусть s обозначает результат операции r <RENAME> (A, B). Для обеспечения возможности выполнения операции требуется, чтобы существовал некоторый тип T, такой, что <A, T> Hr, и чтобы не существовал такой тип T, что <B, T> Hr. (Другими словами, в схеме отношения r должен присутствовать атрибут A и не должен присутствовать атрибут B.) Тогда:

Hs = (Hr minus {<A, T>}) union {<B, T>}, т. е. в схеме результата B заменяет A;
Bs = {ts : exists tr exists v (tr Br and v T and <A, T, v> tr and ts = (tr minus {<A, T, v>}) union {<B, T, v>})}, т. е. в кортежах тела результата имя значений атрибута A меняется на B.

Операция <RENAME> производит отношение s, которое отличается от заданного отношения r только именем одного его атрибута, которое изменяется с A на B. Заголовок s такой же, как заголовок r, за исключением того, что пара <B, T> заменяет пару <A, T>. Тело s включает все кортежи тела r, но в каждом из этих кортежей триплет <B, T, v> заменяет триплет <A, T, v>.

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

5.2.4. Операция реляционной конъюнкции

Пусть s обозначает результат операции r₁ <AND> r₂. Для обеспечения возможности выполнения операции требуется, чтобы если <A, T1>Hr₁ и <A, T2>Hr₂, то T1=T2. (Другими словами, если в двух отношениях-операндах имеются одноименные атрибуты, то они должны быть определены на одном и том же типе (домене).) Тогда:

Hs = Hr₁ union Hr₂, т. е. заголовок результата получается путем объединения заголовков отношений-операндов, как в операциях TIMES и JOIN из предыдущей лекции;
Bs = { ts : exists tr₁ exists tr₂ ((tr₁Br₁ and tr₂Br₂) and ts = tr₁ union tr₂)}; обратите внимание на то, что кортеж результата определяется как объединение кортежей операндов; поэтому:
- если схемы отношений-операндов имеют непустое пересечение, то операция <AND> работает как естественное соединение;
- если пересечение схем операндов пусто, то <AND> работает как расширенное декартово произведение;
- если схемы отношений полностью совпадают, то результатом операции является пересечение двух отношений-операндов.

Операция <AND> является реляционной конъюнкцией, в некоторых случаях выдающей в результате отношение rs, ранее называвшееся естественным соединением двух заданных отношений r₁ и r₂. Заголовок rs является объединением заголовков r₁ и r₂. Тело s включает каждый кортеж, соответствующий заголовку s и являющийся надмножеством некоторого кортежа из тела r₁ и некоторого кортежа из тела r₂.

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

Рис. 5.3. Примерные отношения для иллюстрации операции <AND>

На рис. 5.4(a) у отношений СЛУЖАЩИЕ и ПРОЕКТЫ имеется общий атрибут ПРО_НОМ. Поэтому операция <AND> работает как операция естественного соединения. На рис. 5.4(b) пересечение заголовков отношений СЛУЖАЩИЕ_В_ПРОЕКТЕ_1 и ПРОЕКТЫ пусто, и поэтому в результате реляционной конъюнкции производится расширенное декартово произведение этих отношений. Наконец, на рис. 5.4(c) схемы отношений СЛУЖАЩИЕ_В_ПРОЕКТЕ_1 и СЛУЖАЩИЕ_В_ПРОЕКТЕ_2 совпадают, и телом операции <AND> является пересечение тел отношений-операндов.

Рис. 5.4. Иллюстрации операции реляционной конъюнкции

5.2.5. Операция реляционной дизъюнкции

Пусть s обозначает результат операции r₁ <OR> r₂. Для обеспечения возможности выполнения операции требуется, чтобы если <A, T1>Hr₁ и <A, T2>Hr₂, то должно быть T1 = T2 (одноименные атрибуты должны быть определены на одном и том же типе). Тогда:

Hs = Hr₁ union Hr₂ (из схемы результата удаляются атрибуты-дубликаты);
Bs = { ts : exists tr₁ exists tr₂ ((tr₁Br₁ or tr₂Br₂) and ts = tr₁ union tr₂)}; очевидно, что при этом:
- если у операндов нет общих атрибутов, то в тело результирующего отношения входят все такие кортежи ts, которые являются объединением кортежей tr₁ и tr₂, соответствующих заголовкам отношений-операндов, и хотя бы один из этих кортежей принадлежит телу одного из операндов;
- если у операндов имеются общие атрибуты, то в тело результирующего отношения входят все такие кортежи ts, которые являются объединением кортежей tr₁ и tr₂, соответствующих заголовкам отношений-операндов, если хотя бы один из этих кортежей принадлежит телу одного из операндов, и значения общих атрибутов tr₁ и tr₂ совпадают;
- если же схемы отношений-операндов совпадают, то тело отношения-результата является объединением тел операндов.

Операция <OR> является реляционной дизъюнкцией и обобщением того, что ранее называлось объединением. Заголовок s есть объединение заголовков r₁ и r₂. Тело s состоит из всех кортежей, соответствующих заголовку s и являющихся надмножеством либо некоторого кортежа из тела r₁, либо некоторого кортежа из тела r₂.

Предположим, у нас имеются отношения ПРОЕКТЫ_1 {ПРОЕКТ_НАЗВ, ПРОЕКТ_РУК} и НОМЕРА_ПРОЕКТОВ {ПРО_НОМ} (рис. 5.5). Предположим также, что домен атрибута ПРОЕКТ_НАЗВ включает значения ПРОЕКТ_1, ПРОЕКТ_2, ПРОЕКТ_3, домен атрибута ПРОЕКТ_РУК ограничен значениями Иванов, Иваненко, а доменом атрибута ПРО_НОМ является множество {1, 2, 3}. Результат операции ПРОЕКТЫ <OR> НОМЕРА_ПРОЕКТОВ показан на рис. 5.5.

Как показано на рис. 5.5, операция <OR> при наличии операндов с несовпадающими схемами производит результат, гораздо более мощный, чем результат операции взятия расширенного декартова произведения из лекции 4, и еще менее осмысленный с практической точки зрения.

Для иллюстрации операции <OR> над операндами, схемы которых имеют непустое пересечение, воспользуемся отношением ПРОЕКТЫ_2 {ПРО_НОМ, ПРОЕКТ_РУК} (рис. 5.6) и унарным отношением НОМЕРА_ПРОЕКТОВ, схема и тело которого показаны на рис. 5.5. Будем предполагать, что множества значений доменов атрибутов такие же, как в предыдущем примере. Результат операции ПРОЕКТЫ_2 <OR> НОМЕРА_ПРОЕКТОВ показан на рис. 5.6.

Как уже отмечалось, при совпадении схем отношений-операндов результатом выполнения над ними операции <OR> является объединение отношений. Это непосредственно следует из спецификации операции. Если этот факт кажется неочевидным, еще раз внимательно посмотрите на спецификацию. Иллюстрирующий пример мы приводить не будем.

Рис. 5.5. Результат операции <OR> над операндами без общих атрибутов

Рис. 5.6. Результат операции <OR> над операндами, схемы которых частично пересекаются

16 Нельзя не упомянуть еще и о том, что «алгебра» Кодда в действительности не является алгеброй отношений в математическом смысле, поскольку ее операции применимы не ко всем отношениям. В отличие от этого Алгебра A – это «настоящая» алгебра, в которой отсутствуют какие-либо ограничения на операнды операций.

Назад Содержание Вперёд