ответы к зачёту по Базам Данных (2009), страница 3

кортеж 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, что».

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

• Hs = Hr (заголовок результата совпадает с заголовком операнда);

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

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

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

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

Фактически, берем любую таблицу (отношение), и удаляем один столбец.

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.

Фактически, берем таблицу, меняем название столбца, получаем результат.

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> работает как расширенное декартово произведение;

  • если схемы отношений полностью совпадают, то результатом операции является пересечение двух отношений-операндов.

Заголовок rs является объединением заголовков r₁ и r₂. Тело s включает каждый кортеж, соответствующий заголовку s и являющийся надмножеством некоторого кортежа из тела r₁ и некоторого кортежа из тела r₂.  Смотрите лучше пример =)

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₂ совпадают;

  • если же схемы отношений-операндов совпадают, то тело отношения-результата является объединением тел операндов.

Заголовок s есть объединение заголовков r₁ и r₂. Тело s состоит из всех кортежей, соответствующих заголовку s и являющихся надмножеством либо некоторого кортежа из тела r₁, либо некоторого кортежа из тела r₂. Смотрите лучше пример =)

1. Полнота алгебры А. Определение операций алгебры Кодда через алгебру А.

Более подробно – на стр. 83-92.

Покажем, что Алгебра A является полной, т. е. на основе введенных операций выражаются все операции алгебры Кодда, рассмотренной в предыдущей лекции.

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

MINUS

r1 MINUS r2 = r1 <AND> <NOT> r2.

WHERE

Для простоты будем считать, что множества значений доменов в БД ограничено значениями, содержащимися в теле отношения. Рассмотрим ограничения с простыми условиями вида(имя отношения – REL):

• a comp_op const(=) Для выражения условий равенства в терминах алгебры а заводится вспомогательное отношение(CONST_REL), содержащее необходимые атрибуты и кортежи. Потом просто берется REL <AND> CONST_REL(эквивалентно REL WHERE а = const)

• a comp_op const(>) Опять строим вспомогательное отношение, содержащее необходимые нам данные(они считаются ручками, да) и снова делаем REL <AND> CONST_REL(эквивалентно REL WHERE а > const)

• a comp_op const(!=) собственно, все то же самое…

• a comp_op b(=) Для проверки этого ограничения(пример – СЛУ_НОМЕР = РУК_НОМЕР) строится следующая конструкция: <REMOVE>’ом удаляются все «лишние» атрибуты заголовка, затем переименовываются оставшийся атрибут(он должен быть из одного домена со сравниваемым атрибутом), чтобы совпадали имена у проверяемых значений и берется <AND> построенной и исходной таблицы

• a comp_op b(!=, >, <,…) Аналогично – используется техника работы со вспомогательными таблицами, удалением ненужных атрибутов и переименованием нужных. Ну и <AND>, куда ж без него…

JOIN

Взятие расширенного декартова произведения TIMES является частным случаем операции <AND>, ограничение построено, значит можно выразить JOIN.