Общие понятия реляционного подхода к организации бд. Основные концепции и термины Домен - umotnas.ru o_O
Главная
Поиск по ключевым словам:
Похожие работы
Название работы Кол-во страниц Размер
История развития средств компьютерной обработки данных. Обоснование... 1 131.1kb.
Правила проведения Акции «sportivный look» общие положения термины... 1 126.1kb.
Правила проведения Акции «Блондинки против Брюнеток» общие положения... 1 116.21kb.
Правила проведения Акции «Поездка в Вену на концерт группы Depeche... 1 146.81kb.
Общие понятия и термины по теме: ? Краткий план ответа 1 35.83kb.
Учебно-методическое и информационное обеспечение дисциплины Список... 1 13.28kb.
Термины и определения 1 53.04kb.
Термины и определения 1 63.75kb.
Программа экзамена по дисциплине «Информационный менеджмент» Основные... 1 13.97kb.
Специфика художественной речи. Диалог. Монолог 1 14.26kb.
Статья Основные понятия, используемые в настоящем законе используются... 1 148.08kb.
Тестовые вопросы по Дискретной математике 1 114.21kb.
Викторина для любознательных: «Занимательная биология» 1 9.92kb.

Общие понятия реляционного подхода к организации бд. Основные концепции и термины - страница №2/3

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


Пусть s обозначает результат операции r (A, B). Для обеспечения возможности выполнения операции требуется, чтобы существовал некоторый тип T, такой, что http://citforum.ru/database/advanced_intro/isin.gifHr, и чтобы не существовал такой тип T, что http://citforum.ru/database/advanced_intro/isin.gifHr. (Другими словами, в схеме отношения r должен присутствовать атрибут A и не должен присутствовать атрибут B.) Тогда:

  • Hs = (Hr minus {}) union {}, т. е. в схеме результата B заменяет A;

  • Bs = {ts : exists tr exists v (tr http://citforum.ru/database/advanced_intro/isin.gifBr and v http://citforum.ru/database/advanced_intro/isin.gifT and http://citforum.ru/database/advanced_intro/isin.giftr and ts = (tr minus {}) union {})}, т. е. в кортежах тела результата имя значений атрибута A меняется на B.

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

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


Пусть s обозначает результат операции r1 r2. Для обеспечения возможности выполнения операции требуется, чтобы если http://citforum.ru/database/advanced_intro/isin.gifHr1 и http://citforum.ru/database/advanced_intro/isin.gifHr2, то T1=T2. (Другими словами, если в двух отношениях-операндах имеются одноименные атрибуты, то они должны быть определены на одном и том же типе (домене).) Тогда:

  • Hs = Hr1 union Hr2, т. е. заголовок результата получается путем объединения заголовков отношений-операндов, как в операциях TIMES и JOIN из предыдущей лекции;

  • Bs = { ts : exists tr1 exists tr2 ((tr1http://citforum.ru/database/advanced_intro/isin.gifBr1 and tr2http://citforum.ru/database/advanced_intro/isin.gifBr2) and ts = tr1 union tr2)}; обратите внимание на то, что кортеж результата определяется как объединение кортежей операндов; поэтому:

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

    • если пересечение схем операндов пусто, то работает как расширенное декартово произведение;

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

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

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


Пусть s обозначает результат операции r1 r2. Для обеспечения возможности выполнения операции требуется, чтобы если http://citforum.ru/database/advanced_intro/isin.gifHr1 и http://citforum.ru/database/advanced_intro/isin.gifHr2, то должно быть T1 = T2 (одноименные атрибуты должны быть определены на одном и том же типе). Тогда:

  • Hs = Hr1 union Hr2 (из схемы результата удаляются атрибуты-дубликаты);

  • Bs = { ts : exists tr1 exists tr2 ((tr1http://citforum.ru/database/advanced_intro/isin.gifBr1 or tr2http://citforum.ru/database/advanced_intro/isin.gifBr2) and ts = tr1 union tr2)}; очевидно, что при этом:

    • если у операндов нет общих атрибутов, то в тело результирующего отношения входят все такие кортежи ts, которые являются объединением кортежей tr1 и tr2, соответствующих заголовкам отношений-операндов, и хотя бы один из этих кортежей принадлежит телу одного из операндов;

    • если у операндов имеются общие атрибуты, то в тело результирующего отношения входят все такие кортежи ts, которые являются объединением кортежей tr1 и tr2, соответствующих заголовкам отношений-операндов, если хотя бы один из этих кортежей принадлежит телу одного из операндов, и значения общих атрибутов tr1 и tr2 совпадают;

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

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

Полнота алгебры A.

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


Выводимость операции взятия разности-если отношения r1 и r2 совместимы по объединению, то r1 MINUS r2 = r1 r2.

Интерпретация операции ограничения


мы определяли операцию ограничения r WHERE comp, где r – отношение, а comp – простое условие ограничения вида (a comp-op b), где а и b – имена атрибутов ограничиваемого отношения, для которых осмыслена операция сравнения comp-op, либо вида (a comp-op const), где а – имя атрибута ограничиваемого отношения, а const – литерально заданная константа. Операцией сравнения comp-op может быть «=», «http://citforum.ru/database/advanced_intro/ne.gif», «>», «<», «http://citforum.ru/database/advanced_intro/ge.gif», «http://citforum.ru/database/advanced_intro/le.gif». Покажем на нескольких примерах, как можно выразить операцию ограничения с помощью базовых операций Алгебры A для всех простых допустимых условий.

СЛУЖАЩИЕ_1 WHERE СЛУ_НОМЕР = РУК_НОМ. Получаем:

СЛУЖАЩИЕ_1 <AND> ((((СЛУЖАЩИЕ_1 <REMOVE> СЛУ_НОМЕР) <REMOVE>

СЛУ_ИМЯ) <REMOVE> СЛУ_ЗАРП) <RENAME> (РУК_НОМ, СЛУ_НОМЕР))



Соединения общего вида


При наличии того факта, что операция взятия расширенного декартова произведения TIMES является частным случаем операции , после того как мы научились с помощью Алгебры A выполнять ограничения, становится очевидно, что через операции Алгебры A выражаются и соединения общего вида. В общем случае, чтобы получить результат соединения общего вида произвольных отношений A и B, нужно:

  • выполнить над одним из отношений одну или несколько операций , чтобы избавиться от общих имен атрибутов;

  • выполнить над полученными отношениями операцию , производящую расширенное декартово произведение;

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

Реляционное деление


Пусть имеются отношения r1{A, B} и r2{B}. Утверждается, что результат r1 DIVIDE BY r2 совпадает с результатом выражения (r1 PROJECT A) MINUS (((r2 TIMES (r1 PROJECT A)) MINUS r1) PROJECT A) в терминах операций реляционной алгебры Кодда или (r1 B) (((r2 (r1 B)) r1) B) в терминах операций Алгебры A.

Действительно, результатом выполнения операции r1 PROJECT A является унарное отношение со схемой {A}, кортежи тела которого содержат все значения атрибута A из тела отношения r1. Результат выражения r2 TIMES (r1 PROJECT A) – это бинарное отношение со схемой {A, B}, в тело которого входят все возможные комбинации значений атрибута B в теле отношения r2 и атрибута A в теле отношения r1. В теле результата вычисления выражения (r2 TIMES (r1 PROJECT A)) MINUS r1 останутся только те кортежи, которые не входят во второй операнд, т. е. кортежи с таким значением атрибута A, что значение атрибута B, принадлежащее телу r2, не является значением атрибута B ни в одном кортеже тела отношения r1. Следовательно, если мы возьмем проекцию результата выражения (r2 TIMES (r1 PROJECT A)) MINUS r1 на атрибут A, то в результирующем унарном отношении останутся только те значения A, которые не должны попасть в результат операции r1 DIVIDE BY r2. После выполнения завершающей операции MINUS мы получим желаемый результат.


Избыточность алгебры A

В формальной математической логике стандартным базисом для выражения всех возможных булевских функций является набор {NOT, AND, OR} (отрицание, дизъюнкция и конъюнкция). Известно, что этот набор традиционен, но избыточен, поскольку верны тождества A AND B http://citforum.ru/database/advanced_intro/equiv.gifNOT (NOT A OR NOT B) и A OR B http://citforum.ru/database/advanced_intro/equiv.gifNOT (NOT A AND NOT B). Оказывается, что аналогичные тождества справедливы для операций , и Алгебры A. Тем самым, в наборе базовых операций Алгебры A можно оставить операции и (или и ).

Более того, в алгебре логики существуют две операции, через каждую из которых выражаются все три «базовые» операции: «штрих Шеффера» – sh (A, B) http://citforum.ru/database/advanced_intro/equiv.gifNOT A OR NOT B – и «стрелка Пирса» – pi (A, B) http://citforum.ru/database/advanced_intro/equiv.gifNOT A AND NOT B.

Легко видеть, что



  • sh (A, A) http://citforum.ru/database/advanced_intro/equiv.gifNOT A;

  • sh (NOT A, NOT B) http://citforum.ru/database/advanced_intro/equiv.gifA OR B и

  • NOT sh (A, B) http://citforum.ru/database/advanced_intro/equiv.gifA AND B.

Аналогично,

  • pi (A, A) http://citforum.ru/database/advanced_intro/equiv.gifNOT A;

  • pi (NOT A, NOT B) http://citforum.ru/database/advanced_intro/equiv.gifA AND B и

  • NOT pi (A, B) http://citforum.ru/database/advanced_intro/equiv.gifA OR B.

Аналогичные тождества справедливы для реляционных вариантов штриха Шеффера ( (r1, r2) http://citforum.ru/database/advanced_intro/equiv.gif r1 r2) и стрелки Пирса (
(r1, r2) http://citforum.ru/database/advanced_intro/equiv.gif r1 r2). Поэтому можно свести набор операций Алгебры A к трем операциям: (или
), и .
<< предыдущая страница   следующая страница >>