Вордовские лекции (1121814), страница 6

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

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

Когда совпадение частично. Тогда получим кортеж степени 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> <:=>

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

Базы данных 06.10.06

Лектор хочет устроить контрольную через 4 пары.

r1 DIVIDE BY r2

r1{A, B} r2{B}

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

<AND> <NOT> - MINUS

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

На время мы простимся с алгеброй.

Основной механизм манипулирования БД –

Реляционное исчисление

1. Кортежей

2. Доменов

РассмотримЖ

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

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

Мы хотим узнать имена и номера служащих – начальников отжела со средней заработной платой 11500 рублей.

(СЛУЖАЩИЕ JOIN ПРОЕКТЫ WHERE (СЛУ_НОМ = ПРОЕКТ_РУК AND ПРО_ЗАРП > 11500)) PROJECT (СЛУ_ИМЯ, СЛУ_НОМ)

Это мощные операции, но если отвлечься от этого, то это обычные операции.

Сейчас люди говорят раньше на SQL, чем на русском.

В 60 х языках провели исследование, как лучше писать запросы, на SQL (коммандном языке) или на алгебре. На SQL начали через два дння, в алгебре через 2 недели. Но через месяц на SQL делали в три раза больше ошибок.

Этот же запрос на языке реляционного исчисления кортежей:

Вводятся две кортежные переменные:

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

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

СЛУЖАЩИЙ.СЛУ_ИМЯ, СЛУЖАЩИЙ.СЛУ_НОМ

WHERE EXISTS ПРОЕКТ

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

//Я очень старался всех сотрудников вычистить, но кое-где остались.

На операцию соединения очень сильно намекает СЛУЖАЩИЙ.СЛУ_НОМ = ПРОЕКТ.ПРОЕКТ_РУК.

EXISTS можно выбросить, так как по смыслу квантора существования его можно выбросить, не нарушая смысл выражения.

Почем уквантор существования полезен – пример эквисоединения, который является полусоединением (было ещё на первой лекции)

Реляционная алгебра, при том, что это совершенно фундаментальная вещь, она показывает много хороших св-в, тем не менее, на самой алгебре языков БД практически не было. На памяти лектора в 70х годах был только один язык, QUEL (?). А на исчислении доменов языки существовали и один из них существует до сих пор.

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

Список файлов лекций