Материал из eSyr's wiki.

Предыдущая лекция | Следующая лекция

[править] Алгебра А

[править] Операции алгебы А

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

• S = <NOT> r
• H_s = H_r
• B_s = {t_s : ∃ t_r (t_r ∉ B_r and t_s = t_r) }

Самая интересная операция — операция реляционной конъюнкции.

До этого ещё будут опредлены две операции.

[править] Удаление

Удаление атрибутов — операция, аналогичная операции проекции. Но тут указываются не те атрибуты, которые остаются, а те, которые удаляются.

• <REMOVE>
• s = r <REMOVE> A, A — атрибут заголовка H_r

Требуется, чтобы существовал тип Т, такой, что <A, T> Принадлежит H_r. Но в этом месте физтеховцы (лектор читает сокращенную версию курса пятикурсникам физтеха) прижучили — операции должны выполняться для любых операндов, и понятно, что можно её переделать так, чтобы оно так и было (ничего не делать). Третий манифест говорит, что пустые подмножества равноправны.

[править] Минус

• H_s = H_r minus {<A, T>}
• B_s = {t_s : ∃ t_r ∃ v (t_r &in; B_r and v &in; Т and <A, T ,v> &in; t_r and t_s = t_r minus {<A, T, v>})}
  • v — значение типа Т

Это (NOT?) формула, которую будем использовать при вычислении кортежей. Это (REMOVE) смешанная формула, в которой две кортежные переменные и одна доменная. Обе формулы являются формулами исчисления предикатов первого порядка. Предикаты только на русском языке называются переменными.

На английском предикат — placeholder — заменитель.

[править] Переименование

• <RENAME>
• s = r <RENAME> (A, B) //А прееименовывается в В
• Условие: ∃ Т (<A, T> &in; H_r and <B, T> ∉ H_r)
• H_s = (H_r minus {<A, T>}) union {<B, T>}
• B_s = {t_s : ∃ t_r ∃ v (t_r &in; B_r and v &in; T and <A, T, v> &in; t_r and t_r = (t_r minus {<A, T, v>} union {<B, T, v>})}

[править] Конъюнкция

• <AND>
• s = r1 <AND> r2
• Условие: Если атрибут <A, T1> принадлежит H_r1 и <A, T2> принадлежит H_r2, то тип T1 = T2. Знак равенства означает тождественность, эквивалентность, равны тогда и только тогда, когда являются одним объектом.
• H_s = H_r1 union H_r2
• B_s = {t_s : ∃ t_r1 ∃ t_r2 (t_r1 &in; B_r1 and t_r2 &in; B_r2 and t_s = t_r1 union t_r2)}

Пусть:

• n — степень H_r1
• m — степеннь H_r2
• k — число совпадающих атрибутов

Тогда степень результата — n + m − k

• Сначала рассмотрим ситуацию, когда общих атрибутов нет, то есть пересечение пусто. Тогда степень объелинения — n + m. Тогда степень кортежа — n + m. Тогда для любых двух кортежей, которые принадлежат ... . Получим расширенное декартово произведение.
• Тогда пусть n = m&snbsp;= k. Тогда мы получим результат степени n = m&snbsp;= k. Тогда мы получим результат, когда при определении кортежей мы получим ... . То есть пересечение.
• Когда совпадение частично. Тогда получим кортеж степени n + m&snbsp;− k, когда k одинаковых значений. Тогды в результате получаем естественное соединение.

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

Почему это называется реляционной конъюнкицей: если посмотреть, как это работает с пустыми таблицами (table dee and table dum), то это будет конъюнкция. Это хорошая операция.

[править] Дизъюнкция

• <OR>
• s = r1 <OR> r2
• Условие: Если атрибут <A, T1> принадлежит H_r1 и <A, T2> принадлежит H_r2, то тип T1 = T2. Знак равенства означкет тождественность, эквивалентность, равны тогда и только тогда, когда являются одним объектом.
• H_s = H_r1 union H_r2
• B_s = {t_s : ∃ t_r1 ∃ t_r2 (t_r1 &in; B_r1 or t_r2 &in; B_r2 and t_s = t_r1 union t_r2)}

Для конъюнкции мы требовали склейку только тех кортежей, у которых первый принадлежит первому, второй — второму. Тут требуется принадлежность или первому, или второму.

• Пусть пересечение пустое. Тогда степень результата n + m. Берём первый кортеж. Пердположим, что он если он не принадлежит первому отношению, второму, если нет, то дальше. Предположим, что некоторое принадлежит, тогда смотрим на второй, и если да, то истина и объединяем. А если не принадлежит, то всё равно объединяем, так как уже истина. Таким образом, мы для каждого кортежа, который принажлдежит первому операнду, мы скеливаем со всеми вторыми кортежами, и вторых со всеми первыми. Таким образом получаем дизъюнктивный аналог расширенного дектартова произведения.
• Если нет общих атрибутов, то есть схемы совпадают. Тогда в результат попадёт кортеж, когда он соотв заголовку либо первого опреанда, либо второго, и тогда мы получаем объединение кортежей.
• Это дизъюнктивное соединение. Предположим, что выполняется первое условие – кортеж принадлеит заголовку первого операнда. Тогда кортжи, у которых пересечение совпадает, то они попадут в результат (парные). Если такого кортежа не найдётся, то мы его подыщем. В результат попадут все кортежи, которые конкатенируются со всеми кортежами из второго операнда плюс все из области определения, аналогично для второго.

Операция естеств соединения очень ценная. Если те отношения, которые подвергаются естественному соединению, были нормализованы, то всё хорошо. Но вот взяли мы и автомобиль разобрали. Но что нам мешает положить дополнительные детали? И мы в тот же ящичек положили. Ясно, что эти кусочки в результат не попадут. После того, как мы сделали декомпозицию, эти отношения могут начать жить совей жизнью. Иногда, когда мы выполняем соединение, мы теряем информацию. По этому поводу ещё Кодд на второй стадии развития реляционной модели, когда придумал неопрелеоённые значения, которые Дейта и лектор ненавидят, то можно немного обобщить соединение. Дейта предложил внешнее осединение: левое, правое и полное. Правое — соединяется с телом правого операнда, как при обычном, но если не находится пары, то берём кортеж из неопредёлённых значений (по Кодду). Левые — когда для левого, полное — когда для обоих. В полном — вся исходная информация, плюс та, что соединилась. По Кодду никак без неопределённых значений не обойдёшься. Вопрос, и как разобраться? Например, есть кортеж, у которого совпадающие операнды хорошие, остальные неопределны. И как его отличать? По этому поводу в SQL есть специальная возможность определить дополнительные столбцы, которые говорят о смысле неопределённого значения.

Дизъюнктивное сооединение — замена внешнего соединения. Мы ничего не теряем. Другой вопрос, от этого не становится легче. Так как не понятно, откуда взялся напарник — из операнда или из дополнения. Это честная операция, но чтобы понять смысл, нужно очень сильно изворачиваться.

Основной набор лектор рассказал.

Не смотря на всю ругань про дизъюнкцию, не надо на лектора обижаться. Она иногда даёт результаты, обладающие большой мощностью, с которыми трудно разобраться, но это полноправная операция.

[править] Полнота

На данный момент определили операции <NOT>, <AND>, <OR>, <RENAME>, <REMOVE>.

Теперь надо показать выражение через них все операции алгебры Кодда.

Чего не хватает: реляционного вычитания по Кодду (MINUS), ограничения (WHERE), JOIN, DIVIDE BY.

[править] Ограничение (MINUS)

A MINUS B = (A <AND> (<NOT> B))

[править] Ограничение (WHERE)

Пускай есть наши любимые служащие

Слу_Ном Слу_Имя Слу_Отд

Когда мы это формулируем, мы формулируем некоторые предикаты.

Служ Слу_Ном имеет имя Слу_имя и работает в отделе Слу_Отд

Это те самые placeholder'ы (Слу_Отд, Слу_Имя, …)

Это есть множество кортежей, каждый — множество значений.

Каждый кортеж — инстанциация предиката

Суть базы данных — все комбинации имени, номера, отдела, которые не входят в таблицу, принимают значение false.

Эта область инстанциации меняется от времени.

Допустим, мы хотим выполнить ограничение — оставить только тех сотрудников, у которых определённый отдел. Тогда предикат true для Имя_служащего = x и номер_служащего = y и номер_отдела = z и номер отдела = определённый.

Соответственно,

Служащие {СлуНом, СлуИмя, СлуОтд} <AND> СлуОтд = 4426

то мы получим тех служащих, у которых номер отдела 4426.

у Кодда z WHERE cond [a cond_op const, a cond_op b], равенство научились выражать с помощью реляционной конъюнкции.

Соответственно, выполняем реляционную конъюнкцию с отношением из одного кортежа и заголовком из одного атрибута, что ни чем ни хуже и не лучше константы. Диапазон — константа, у которой монго записей, самое неприятное — a не равно const.

Ограничение выражается с помощью реляционной конъюнкции.

О чём задуматься: если знать всё вот это вот, то теперь попробовать просто сократить алгебру Кодда. Интересный вопрос – что добавить или оставить, чтобы можно было выкинуть операцию ограничения, ну и про другие операции можно подумать.

[править] JOIN

У Кодда — переименование, декартово произведение, ограничение, проекция. Переименование есть, декартово произв есть, ограничение научились, проекция есть.

[править] приведение Алгебры А к минимальной

В завершение лекции, но не завершение темы, так как остаётся DIVIDE BY:

В алгебре А можно оставить три операции. Нужно оставить <REMOVE>. Легко доказать, что её выбросить нельзя. Только она единственная сокращает мощность схемы одного операнда.

<RENAME> — избыточная. Есть отношение, укоторого есть A, хотим переименовать в В. Заводим константу. Бинарную, у которой есть A и есть В. Потом делаем естественное соединение, а потом выкидываем А.

<NOT>, <AND>, <OR> — можно оставить одну операцию. Есть стрих Шеффера и стрелка Пирса.

• Шеффер
  • 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

Это верно и для реляционных аналогов. Тем самым можно спокойно выкинуть три операции и оставить только штрих или только стрелку.

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

1. <sh> <REMOVE> <:=>
2. <pi> <REMOVE> <:=>

Оба базисы минимальны, сократить их невозможно.