Алгебра А

Материал из Википедии — свободной энциклопедии

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

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

[править] Обозначения и вводные замечания

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

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

[править] Операции

[править] Операция реляционного дополнения

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

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

[править] Операция удаления атрибута

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

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

[править] Операция переименования

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

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

[править] Операция реляционной конъюнкции

Пусть s обозначает результат операции r1 <AND> r2. Для обеспечения возможности выполнения операции требуется, чтобы если <A, T1> $\in$ Hr1 и <A, T2> $\in$ Hr2, то T1 = T2. (Другими словами, если в двух отношениях-операндах имеются одноименные атрибуты, то они должны быть определены на одном и том же типе (домене).)
Тогда:
Заголовок результата получается путем объединения заголовков отношений-операндов, как в операциях TIMES и JOIN в алгебре Кодда;
Кортеж результата определяется как объединение кортежей операндов; поэтому:
если схемы отношений-операндов имеют непустое пересечение, то операция <AND> работает как естественное соединение;
если пересечение схем операндов пусто, то <AND> работает как расширенное декартово произведение;
если схемы отношений полностью совпадают, то результатом операции является пересечение двух отношений-операндов.
Операция <AND> является реляционной конъюнкцией, в некоторых случаях выдающей в результате отношение s, ранее называвшееся естественным соединением двух заданных отношений r1 и r2. Заголовок s является объединением заголовков r1 и r2. Тело s включает каждый кортеж, соответствующий заголовку s и являющийся надмножеством некоторого кортежа из тела r1 и некоторого кортежа из тела r2.

[править] Операция реляционной дизъюнкции

Пусть s обозначает результат операции r1 <OR> r2. Для обеспечения возможности выполнения операции требуется, чтобы если <A, T1> $\in$ Hr1 и <A, T2> $\in$ Hr2, то должно быть T1 = T2 (одноименные атрибуты должны быть определены на одном и том же типе).
Тогда:
Из схемы результата удаляются атрибуты-дубликаты;
если у операндов нет общих атрибутов, то в тело результирующего отношения входят все такие кортежи ts, которые являются объединением кортежей tr1 и tr2, соответствующих заголовкам отношений-операндов, и хотя бы один из этих кортежей принадлежит телу одного из операндов; если у операндов имеются общие атрибуты, то в тело результирующего отношения входят все такие кортежи ts, которые являются объединением кортежей tr1 и tr2, соответствующих заголовкам отношений-операндов, если хотя бы один из этих кортежей принадлежит телу одного из операндов, и значения общих атрибутов tr1 и tr2 совпадают;
если же схемы отношений-операндов совпадают, то тело отношения-результата является объединением тел операндов. Операция <OR> является реляционной дизъюнкцией и обобщением того, что ранее называлось объединением. Заголовок s есть объединение заголовков r1 и r2. Тело s состоит из всех кортежей, соответствующих заголовку s и являющихся надмножеством либо некоторого кортежа из тела r1, либо некоторого кортежа из тела r2.

[править] Полнота алгебры A

Алгебра A является полной, т. е. на основе введенных операций выражаются все операции алгебры Кодда. Операция <REMOVE> — аналог операции PROJECT. Операция переименования атрибутов <RENAME> — аналог операции RENAME. UNION является частным случаем операции <OR>, TIMES, INTERSECT и NATURAL JOIN – частные случаи операции <AND>. Через операции Алгебры A выражаются операции взятия разности MINUS (если отношения r1 и r2 совместимы по объединению, то r1 MINUS r2 = r1 <AND> <NOT> r2), ограничения (WHERE), соединения общего вида (JOIN) и реляционного деления (DIVIDE BY).

Категории: Незавершённые статьи по информатике | Реляционные алгебры