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

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

Версия от 17:26, 3 февраля 2008; ESyr01 (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

Содержание

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

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

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

  • S = <NOT> r
  • Hs = Hr
  • Bs = {ts : ∃ tr (tr ∉ Br and ts = tr) }

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

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

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

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

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

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

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

  • Hs = Hr minus {<A, T>}
  • Bs = {ts : ∃ tr ∃ v (tr &in; Br and v &in; Т and <A, T ,v> &in; tr and ts = tr minus {<A, T, v>})}
    • v — значение типа Т

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

Чем старше становишься, тем больше задумываешься, что же такое понимал до сих пор (что такое переменная).

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

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

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

  • <RENAME>
  • s = r <RENAME> (A, B) //А прееименовывается в В
  • Условие: ∃ Т (<A, T> &in; Hr and <B, T> ∉ Hr)
  • Hs = (Hr minus {<A, T>}) union {<B, T>}
  • Bs = {ts : ∃ tr ∃ v (tr &in; Br and v &in; T and <A, T, v> &in; tr and tr = (tr minus {<A, T, v>} union {<B, T, v>})}

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

  • <AND>
  • s = r1 <AND> r2
  • Условие: Если атрибут <A, T1> принадлежит Hr1 и <A, T2> принадлежит Hr2, то тип T1 = T2. Знак равенства означает тождественность, эквивалентность, равны тогда и только тогда, когда являются одним объектом.
  • Hs = Hr1 union Hr2
  • Bs = {ts : ∃ tr1 ∃ tr2 (tr1 &in; Br1 and tr2 &in; Br2 and ts = tr1 union tr2)}

Пусть:

  • n — степень Hr1
  • m — степеннь Hr2
  • 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> принадлежит Hr1 и <A, T2> принадлежит Hr2, то тип T1 = T2. Знак равенства означкет тождественность, эквивалентность, равны тогда и только тогда, когда являются одним объектом.
  • Hs = Hr1 union Hr2
  • Bs = {ts : ∃ tr1 ∃ tr2 (tr1 &in; Br1 or tr2 &in; Br2 and ts = tr1 union tr2)}

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

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

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

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

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

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

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

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

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

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

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

[править] Ограничение (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> <:=>

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


Базы Данных


01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28


Календарь

пт чт пт чт пт чт пт чт пт чт
Сентябрь
01 07 14 15 21 22 28 29
Октябрь
  05 06 12 13 19 20 26 27
Ноябрь
  02 03 09 16 17 23 24 30
Декабрь
  07 08 14 15

Вопросы к экзамену
1999 2000 2001 2002 2003 2004 2005 2006


Дополнительная информация к экзамену


Эта статья является конспектом лекции.

Эта статья ещё не вычитана. Пожалуйста, вычитайте её и исправьте ошибки, если они есть.
Личные инструменты
Разделы