Базы Данных, 09 лекция (от 05 октября)

Материал из ESyr's Wiki pages.

Базы данных 05.10.06

Алгебра А

Операция отрицания: S = <NOT> r H(s) = H(r) B(s) = {t(s) : exist 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) : exists t(r) exists v (t(r) принадлежит B(r) and v принадлежит Т and <A, T ,v> принадлежит t(r) and t(s) = t(r) minus {<A, T, v>})} //v – значение типа Т Это (NOT?) формула, которую будем использовать при вычислении кортежей. Это (REMOVE) смешанная формула, в которой жве кортежные переменные и одна доменная. Обе формулы являются формулами исчисления предикатов первого порядка. Предикаты только на русском языке называются переменными. Чем старше тсановишься, тем больше задумываешься, что же такое понимал до сих пор (что аткое переменная). На английском – предикат – placeholder – заменитель.

Кстати, чтобы мы не жумали, чот вот, если человек чиатет эту алгкбру А. Пришедший со стороны, думает, что люди, которые писали алгебру А, аткие умные, написали такие определения. На саомм деле Это не Дейта и ... придумали, им помог математик, который занимался аналогичной вещью.

Переименование: <RENAME> s = r <RENAME> (A, B) //А прееименовывается в В условие: существует Т такой, что (<A, T> принадлежит H(r) and не принадлежит H(r)) H(s) = (H(r) minus {<A, T>}) union {<B, T>} B(s) = {t(s) : exists t(r) exists v (t(r) принадлежит B(r) and v принадлежит T and <A, T, v> принадлежит 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) : exists t(r1) exists t(r2) (t(r1) принадлежит B(r1) and t(r2) принадлежит 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=k. Тогда мы получим результат степени n=m=k. Тогда мы получим результат, когда при опрелделении кортежей мы получим ... . То есть пересечение.

Когда совпадение частично. Тогда получим кортеж степени n+m-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) : exists t(r1) exists t(r2) (t(r1) принадлежит B(r1) or t(r2) принадлежит B(r2) and t(s) = t(r1) union t(r2))}

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

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

Если нет общих атрибутов, то есть схемы совпадают. Тогда в результат попадёт кортеж, когда он соотв заголовку либо первого опреанда, либо второго, и тогда мы получаем объединение кортежей.

Если есть общие атрибуты. Сделаем перерыв, подумайте, что будет получаться.

//Педедыв

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

Зачем такое нужно: с уровня знаний, которые лектор пытался валожить, рни для чего не нужно.

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

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

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

Полнота.

На данный момент определили операции <NOT>, <AND>, <OR>, <RENAME>, <REMOVE>. Теперь надо показать выражение через них все операции алгебры Кодда.

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

Крроме того, лектор удивляется, почему мы не спрашиваем, какого шута мы определяем операцию RENAME, если мы ей нигде в алгебре А не пользуемся.

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

Ограничение: Пускай есть наши любимые служащие Слу_Ном Слу_Имя Слу_Отд Когда мы это формулируем, мы ыформулируем некоторые предикаты. Служ Слу_Ном имеет имя Слу_имя и работае в отделе Слу_Отд Это те самые 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> <:=> Оба базисы минимальны, сократить их невозможно.