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

Вот алгоритм в общем случае:

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

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

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

DIVIDE BY

Пусть имеются отношения r1{A, B} и r2{B}.

r1 DIVIDE BY r2 совпадает с результатом выражения (r1 PROJECT A) MINUS (((r2 TIMES (r1 PROJECT A)) MINUS r1) PROJECT A) в терминах операций реляционной алгебры Кодда.

Тогда

r1 DIVIDE BY r2 =

(r1 <REMOVE> B) <AND> <NOT> (((r2 <AND> (r1 <REMOVE> B)) <AND> <NOT> r1) <REMOVE> B)

в терминах операций Алгебры A.

1. Реляционная алгебра А. Перечислить базовые операции. Избыточность алгебры А. Сокращение набора операций алгебры А.

Более подробно – вопрос 10 + стр. 92-95.

Базовые операции:

• Реляционное дополнение <NOT>

• Удаление атрибута r <REMOVE> A

• Операция переименования r <RENAME> (A, B)

• Операция реляционной конъюнкции r1 <AND> r2

• Операция реляционной дизъюнкции r1 <OR> r2

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

1) Для операций алгебры A <AND>, <OR>, <NOT> справедливы те же тождества, что и в классической булевой логике. Это проверяется по определению:

A AND B = NOT (NOT A OR NOT B)

A OR B = NOT (NOT A AND NOT B)

Мало того, для операций алгебры A существуют аналоги штриха Шеффера и стрелки Пирса:

<sh> (r1, r2) = <NOT> r1 <OR> <NOT> r2

<pi> (r1, r2) = <NOT> r1 <AND> <NOT> r2

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

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

Для иллюстрации воспользуемся отношением СЛУЖАЩИЕ из рис. ниже. Пусть нам нужен результат операции СЛУЖАЩИЕ <RENAME> (ПРО_НОМ, НОМЕР_ПРОЕКТА) (мы предполагаем, что множество значений домена атрибута ПРО_НОМ ограничено значениями, представленными в теле отношения СЛУЖАЩИЕ). Возьмем бинарное отношение ПРО_НОМ_НОМЕР_ПРОЕКТА , где каждый из кортежей содержит два одинаковых значения номера проекта и в тело отношения входят все значения домена атрибута ПРО_НОМ. Тогда, как показано на рис. , вычисление выражения (СЛУЖАЩИЕ <AND> ПРО_НОМ_НОМЕР_ПРОЕКТА) <REMOVE> (ПРО_НОМ) приводит к желаемому результату.

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

1. Реляционное исчисление: исчисление кортежей и доменов. Сравнение механизмов реляционной алгебры и реляционного исчисления на примере формулирования запроса.

Сравнение механизмов реляционной алгебры и реляционного исчисления

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

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

СЛУЖАЩИЕ {СЛУ_НОМ, СЛУ_ИМЯ, СЛУ_ЗАРП, ПРО_НОМ}

и

ПРОЕКТЫ {ПРО_НОМ, ПРОЕКТ_РУК, ПРО_ЗАРП}

В отношении ПРОЕКТЫ атрибут ПРОЕКТ_РУК содержит имена служащих, являющихся руководителями проектов, а атрибут ПРО_ЗАРП – среднее значение зарплаты, получаемой участниками проекта. Мы хотим узнать имена и номера служащих, которые являются руководителями проектов со средней заработной платой, превышающей 18000 руб.

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

(СЛУЖАЩИЕ JOIN ПРОЕКТЫ

WHERE

(СЛУ_ИМЯ = ПРОЕКТ_РУК AND ПРО_ЗАРП > 18000.00))

PROJECT (СЛУ_ИМЯ, СЛУ_НОМ)

Это выражение можно было бы прочитать, например, следующим образом:

1) Выполнить эквисоединение отношений СЛУЖАЩИЕ и ПРОЕКТЫ по условию

СЛУ_ИМЯ = ПРОЕКТ_РУК;

2) Ограничить полученное отношение по условию ПРО_ЗАРП > 18000.00;

спроецировать результат предыдущей операции на атрибут СЛУ_ИМЯ, СЛУ_НОМ.

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

Если же сформулировать тот же запрос с использованием реляционного исчисления то мы получили бы два определения переменных:

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

RANGE ПРОЕКТ IS ПРОЕКТЫ

и выражение

СЛУЖАЩИЙ.СЛУ_ИМЯ, СЛУЖАЩИЙ.СЛУ_НОМ WHERE EXISTS (СЛУЖАЩИЙ.СЛУ_ИМЯ = ПРОЕКТ.ПРОЕКТ_РУК AND ПРОЕКТ.ПРО_ЗАРП > 18000.00).

Это выражение можно было бы прочитать, например, следующим образом: выдать значения СЛУ_ИМЯ и СЛУ_НОМ для каждого кортежа служащих такого, что существует кортеж проектов со значением ПРОЕКТ_РУК, совпадающим со значением СЛУ_НОМ этого кортежа служащих, и значением ПРО_ЗАРП, большим 18000.00.

Во второй формулировке мы указали лишь характеристики результирующего отношения, но ничего не сказали о способе его формирования. В этом случае система сама должна решить, какие операции и в каком порядке нужно выполнить над отношениями СЛУЖАЩИЕ и ПРОЕКТЫ. Обычно говорят, что алгебраическая формулировка является процедурной, т. е. задающей последовательность действий для выполнения запроса, а логическая — описательной (или декларативной), поскольку она всего лишь описывает свойства желаемого результата.

Исчисление кортежей и доменов

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

1. Исчисление кортежей. Кортежная переменная. Правильно построенная формула. Пример. Способ реализации.

Более подробно –стр. 99-103

Исчисление кортежей. Кортежная переменная.

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

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

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

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

Правильно построенные формулы

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

Основой WFF являются простые условия, представляющие собой операции сравнения скалярных значений (значений атрибутов переменных или литерально заданных констант) - например, конструкции

СЛУЖАЩИЙ.СЛУ_НОМ = 2934

СЛУЖАЩИЙ.СЛУ_НОМ = ПРОЕКТ.ПРОЕКТ_РУК

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

Также если form – WFF, а comp – простое сравнение, то NOT form, comp AND form, comp OR form и IF comp THEN form являются WFF.

Способ реализации

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

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

1. Исчисление кортежей. Кванторы, свободные и связанные переменные. Целевые списки. Выражения реляционного исчисления.
   

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

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

Кванторы, свободные и связанные переменные

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