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

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

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

Реляционная модель данных

Решение: возможность расширять ТД специальными значениями. При сравнениями с другими типами дают false, с собой — true.

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

2 года назад пришла идея соратнику Дейта Хью Гаррелу. предположим, что только в одном атрибуте могут находиться неопределённые значения. Тогда можно ввести два отношения. Не проходит ситуация, когда встречаются и когда не знаю, и когда неприменимо, но в этом случае можно завести несколько отношений.

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

Неопределённые соотношения в текущем SQL: В нём есть ситуации, когда

• NULL comp_op V = unknown
• NULL = NULL ≡ true — дубликат
• NULL = NULL ≡ false — если их пересчитывают

Ограничения реляционной модели

Ограничения сущности

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

Ограничения ссылок

«Внешний» ключ (foreign key)

Пусть есть R1(a₁, a₂, …, a_n), R2(b₁, b₂, …, b_n)

Пусть b1 — возможный ключ.

а_i — внешний ключ, если при любом значении a_i существует b₁ — внешний ключ или ссылка.

Существует операция эквисоединения, которая позволяет по a_i найти кортеж с соответствующим b₁.

Как звучит ссылочное ограничение у Кодда: для любого значения внешнего ключа либо существуют совпадающее с ним значение первого (возможного) ключа, либо значение внешнего ключа является полностью неопределённым (NULL).

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

Дубликаты

Дубликаты возникли ещё в System R в IBM под надзором Кодда. Они появились не потому, что они были идиоты или хотели принести гадость миру, а потому, что если у кортежа при выборке не нужен возможный ключ, могут получатся дубликаты.

В соответствии с моделью дубликаты надо было бы уничтожать. Но это БД. И одно из свойств БД — очень большие объёмы. Могут быть гигабайты данных. Универсальный способ — отсортировать, а это очень дорогая операция, самая дорогая, которая существует в СУБД. И поэтому мультимножества разрешены в SQL. Но и сохранять их тоже можно. Но если их можно получить в результате запроса, то и другими способами тоже можно добавлять.

Вторая возможность SQL: возможность определения возможного ключа с неопределённым значением. И если n возможных ключей, то 2ⁿ могут иметь неопределённые значения.

Правила сопоставления внешнего ключа с возможным

У Кодда — либо ссылается, либо не ссылается. В SQL — simple (…), partial (…), full (…).

Одна ссылка может указывать на несколько строк, если внешняя ссылка объявлена как partial.

Ограничения целостности

Спрашивается, как соблюдать ограничения целостности.

Внешние ключи: всё достаточно просто работает при вставке. Проблема, когда кортеж изменяется или меняется.

Способы решения:

1. Каскадное удаление
2. Запретить удалять, пока есть потомки
3. Детей объявлять беспризорниками

Ещё одна возможность в SQL: куда-нибудь пристроить детей.

Алгебра

В алгебре Кодда 10 операций. Делятся на группы:

1. Теоретико-множественные операции
   1. Объединение (union)
   2. Пересечение (intersect)
   3. Вычитание (minus)
   4. Декартово произведение (times)
2. Специальные реляционные операции
   1. Ограничение (where)
   2. Проекция (project)
   3. Соединение (join)
      Одна из самых неприятных ошибок на экзамене — перепутать объединение и соединение. Операция соединения — элементами результата являются конкатенации кортежей, степень результата будет (n+m), а количество кортежей сколько получится.
   4. Деление (divide by)
3. Дополнительные операции
   1. Присваивание
      Не совсем операция, но без неё трудно. В обычных ЯП это просто перенос результата, в БД же это гигантские куски внешней памяти. Как сказал Гайсарян, последней модой принято считать, что с каждой переменной связано некое абстрактное местоположение, единственным свойством которого является то, что в него можно записать, и оттуда считать. В БД присваивание связывает выражение с именем
   2. Переименование
      У Кодда не было, придумал Дейта. Эта операция очень важная. Позволяет взять отношение и переименовать атрибут.

Более содержательный рассказ

union, intersect, minus

Основной смысл этих операций понятен. Отношение — это множество, по идее, можно было бы применять эти операции к любым двум отношениям как к множествам. Например, применяем операцию к R1(a₁, b₁) и R2(a₂, c₂, d₂). Мы получили бы множество, но оно не было бы отношением. Это нехорошо, потому что мы хотим построить не алгебру множеств, а алгебру отношений. Вообще,чем замечательны алгебры? Тем, что они строятся таким образом, что в любом месте, где можно использовать значение, можно использовать выражение, которое это значение производит. Посему требование, что результатом любого действия должно быть отношение. Отсюда ограничение на операнды, которое называется условием совместимости по объединению. Звучит оно так. Операндами этих операций могут быть только операнды, которые обладают одинаковыми схемами. Но в этом случае мы никогда не могли бы объединить R1(a₁, b₁) с R2(a₂, b₂). Как раз здесь начинают работать операции переименования. Почти совместимость — два операнда почти совместимы, если их заголовки обладают одинаковыми степенями, и мы можем составить взаимо однозначное соответствие между атрибутами, тогда мы можем привести операнды в соответствие, применив нужное количество раз операцию переименования. До Дейты плохо жили люди. Один из выходов — использование точечной нотации. То есть считали, что атрибуты были вида R1.a1, R2.b2. Но при этом операции объединения не были бы коммутативны, так как возникал вопрос, как именовать атрибуты результата. Но это не алгебра, так как нельзя применить операцию к любым элементам множества.

Декартово произведение

В реляционной модели эта операция не имеет смысла. Поэтому Кодд ввёл понятие расширенного ДП. Если есть R1(a1...an), R2(b1...bn), то в результате ДП получаем (a₁, …, a_n, b₁, …, b_n). Фактически это объединение. Всегда ли можно выполнять эту операцию? Требуются отношения, у которых пересечение множества атрибутов пусто. Для расширенного ДП можно сделать любые отношения разными при помощи операции переименования. Если использовать точечную нотацию, то получаются громоздкие имена.

Избыточность этих трёх операций

Три операции избыточны, минус выбросить нельзя, потому что он некоммутативный, можно выбросить пересечение.

R Where condition

По определению это условие вычисляется для каждого кортежа операнда, и в результат попадают только те кортежи, для которых условие истинно.

R where (cond1&cond2) ≡ (R where cond1) intersect (r where cond2)

R where (cond1|cond2) ≡ (R where cond1) plus (r where cond2)

not R where (cond1) ≡ R minus (r where cond1)