Общие понятия реляционного подхода к организации БД (1122811), страница 2

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

Текст из файла (страница 2)

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

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

Выводимость операции взятия разности-если отношения r₁ и r₂ совместимы по объединению, то r₁ MINUS r₂ = r₁ <AND> <NOT> r₂.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• sh (A, A) NOT A;

• sh (NOT A, NOT B) A OR B и

• NOT sh (A, B) A AND B.

Аналогично,

• pi (A, A) NOT A;

• pi (NOT A, NOT B) A AND B и

• NOT pi (A, B) A OR B.

Аналогичные тождества справедливы для реляционных вариантов штриха Шеффера (<sh> (r1, r2) <NOT> r1 <OR> <NOT> r2) и стрелки Пирса (<pi> (r1, r2) <NOT> r1 <AND> <NOT> r2). Поэтому можно свести набор операций Алгебры A к трем операциям: <sh> (или <pi>), <RENAME> и <REMOVE>.

Избыточность операции переименования.

Наконец, покажем, что избыточна и операция <RENAME>. Ну там надо тупо добавить к таблице еще один столбец, копию столбца, который собираемся переименовывать, но уже с новым именем. А потом REMOVE столбец со старым названием.

Тем самым, можно сократить набор операций Алгебры A до двух операций: <sh> (или <pi>) и <REMOVE> и операции присваивания переменной отношения.

Реляционное исчисление кортежей

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

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

Для определения кортежной переменной используется оператор RANGE. Например, для того чтобы определить переменную СЛУЖАЩИЙ, областью определения которой является отношение СЛУЖАЩИЕ, нужно употребить конструкцию

RANGE СЛУЖАЩИЙ IS СЛУЖАЩИЕ

Как уже говорилось, из этого определения следует, что в любой момент времени переменная СЛУЖАЩИЙ представляет некоторый кортеж отношения СЛУЖАЩИЕ. При использовании кортежных переменных в формулах можно ссылаться на значение атрибута переменной (это аналогично тому, как, например, при программировании на языке C можно сослаться на значение поля структурной переменной). Например, для того, чтобы сослаться на значение атрибута СЛУ_ИМЯ переменной СЛУЖАЩИЙ, нужно употребить конструкцию СЛУЖАЩИЙ.СЛУ_ИМЯ.

Правильно построенная формула (Well-Formed Formula, WFF) служит для выражения условий, накладываемых на кортежные переменные.

Способ реализации, который приводит к получению области истинности рассмотренной формулы, в действительности является наиболее общим (и зачастую неоптимальным) способом выполнения операций соединения (он называется методом вложенных циклов – nested loops join). ( два вложенных цикла, по первому переменной и по второй, применяется в случае формулы типа перем1.что-то=перем2.кто-то )

При построении WFF допускается использование кванторов существования (EXISTS) и всеобщности (FORALL). Если form – это WFF, в которой участвует переменная var, то конструкции EXISTS var (form) и FORALL var (form) представляют собой WFF. По определению, формула EXISTS var (form) принимает значение true в том и только в том случае, если в области определения переменной var найдется хотя бы одно значение (кортеж), для которого WFF form принимает значение true. Формула FORALL var (form) принимает значение true, если для всех значений переменной var из ее области определения WFF form принимает значение true.

Переменные, входящие в WFF, могут быть свободными или связанными. По определению, все переменные, входящие в WFF, при построении которой не использовались кванторы, являются свободными. Фактически, это означает, что если для какого-то набора значений свободных кортежных переменных при вычислении WFF получено значение true, то эти значения кортежных переменных могут входить в результирующее отношение. Если же имя переменной использовано сразу после квантора при построении WFF вида EXISTS var (form) или FORALL var (form), то в этой WFF и во всех WFF, построенных с ее участием, var является связанной переменной. Это означает, что такая переменная не видна за пределами минимальной WFF, связавшей эту переменную. При вычислении значения такой WFF используется не одно значение связанной переменной, а вся область ее определения.

Итак, WFF обеспечивают средства формулировки условия выборки из отношений БД. Чтобы можно было использовать исчисление для реальной работы с БД, требуется еще один компонент, который определяет набор и имена атрибутов результирующего отношения. Этот компонент называется целевым списком (target list).

Целевой список строится из целевых элементов, каждый из которых может иметь следующий вид:

• var.attr, где var – имя свободной переменной соответствующей WFF, а attr – имя атрибута отношения, на котором определена переменная var;

• var, что эквивалентно наличию подсписка var.attr₁, var.attr₂, ..., var.attr_n, где {attr₁, attr₂, ..., attr_n} включает имена всех атрибутов определяющего отношения;

• new_name = var.attr; new_name – новое имя соответствующего атрибута результирующего отношения.

Последний вариант требуется в тех случаях, когда в WFF используется несколько свободных переменных с одинаковой областью определения. Фактически применение целевого списка к области истинности WFF эквивалентно действию алгебраической операции проекции, а последний из приведенных вариантов представляет собой некоторую разновидность алгебраической операции переименования атрибута.

Выражением реляционного исчисления кортежей называется конструкция вида target_list WHERE WFF. Значением выражения является отношение, тело которого определяется WFF, а множество атрибутов и их имена – целевым списком.

Реляционное исчисление доменов.

В исчислении доменов областью определения переменных являются не отношения, а домены.

Основным формальным отличием исчисления доменов от исчисления кортежей является наличие дополнительного множества предикатов, позволяющих выражать так называемые условия членства. Если R – это n-арное отношение с атрибутами a₁, a₂, ..., a_n, то условие членства имеет вид R (a_i1 : v_i1, a_i2 : v_i2, ..., a_im : v_im) (m n), где v_ij – это либо литерально задаваемая константа, либо имя доменной переменной. Условие членства принимает значение true в том и только в том случае, если в отношении R существует кортеж, содержащий указанные значения указанных атрибутов. Если v_ij – константа, то на атрибут a_ij накладывается жесткое условие, не зависящее от текущих значений доменных переменных; если же v_ij – имя доменной переменной, то условие членства может принимать разные значения при разных значениях этой переменной.

Функциональные зависимости, замыкание множества функциональных зависимостей, аксиомы Армстронга, замыкание множества атрибутов. Минимальное покрытие множества функциональных зависимостей

Пусть задана переменная отношения R, и X и Y являются произвольными подмножествами заголовка R («составными» атрибутами). В значении переменной отношения R атрибут Y функционально зависит от атрибута X в том и только в том случае, если каждому значению X соответствует в точности одно значение Y. В этом случае говорят также, что атрибут X функционально определяет атрибут Y (X является детерминантом (определителем) для Y, а Y является зависимым от X). Будем обозначать это как R.X R.Y.

Характеристики

Список файлов ответов (шпаргалок)