Изменения
бра
==== Преобразование подзапросов ====
Чуть ли не на уровне парсера у нас реляционное исчисление преобразуется в реляционную алгебру. Если была запись в реляционном исчислении, то у нее вынесли кванторы и преобразовали в реляционную алгебру на основе подхода . Для любого запроса в терминах реляционного исчисления можно построить запрос в терминах реляционной алгебры.
Начиная с этого момента оперируем '''только реляционной алгеброй'''
* Преобразуются в реляционную алгебру
==== Преобразование соединений ====
Первое что происходит - избавляемся от внешних соединений. Внешние соединения - это надстройка над обычными соединениями и более простыми операциями.
*Внешние соединения
**$R_1 ⟗_θ R_2 ⇒ (R_1 ⟕_θ R_2) ∪ (R_1 ⟖_θ R_2)$
**$R_1 ⟕_θ R_2 ⇒ σ_θ(R_1 × R_2) ∪ (R_1 - π_{R_1}(σ_θ(R_1 × R_2)))$
**$R_1 ⟖_θ R_2 ⇒ σ_θ(R_1 × R_2) ∪ (R_2 - π_{R_2}(σ_θ(R_1 × R_2)))$
Избавляемся от декартового произведения сказав, что это просто естественное соединения. При необходимости переименуем совпадающие атрибуты, чтобы они случайно не совпали. В будущем будет считать, что совпадающие атрибуты мы переименовываем автоматически. Можем безболезненно делать, така как переименование атрибутов "бесплатно", т.e. O(1). В рантайме никто не оперирует названиями, есть просто номера колонок. Названия просто преобразуются в индексы. На этом уровне нам переименование ровно ничего не стоит.
*Декартово соединение
**$R_1 × R_2 ⇒ R_1 ⋈ R_2$
=== Унарные операции ===
Мы минимизировали набор операций. Что у нас осталось? У нас остались унарные операции - фильтр и проекция.
==== Повторная фильтрация ====
Если есть два повторных применения фильтрации, то давайте отфильтруем по конъюнкции. Если внутреннее условие очень слабо фильтрует, то в лучшем случае мы ускоримся в два раза.
*Правило
**Повторное применение фильтрации заменяется одинарным
**$σ_{cond_1}(σ_{cond_2}(R)) ⇒ σ_{cond_1 ∧ cond_2}(R)$
Давайте сразу объединим фильтр связанный с естественным соединением и фильтр по номеру группы в общий фильтр с конъюнкцией.
*Пример
**$π_{FirstName}(σ_{Name=M34391}(σ_{S.GId=G.GId}(S × G))) ⇒ π_{FirstName}(σ_{Name=M34391 ∧ S.GId=G.GId}(S × G))$
==== Повторная проекция ====
Если есть несколько проекций, то можно заменить на одну внешнюю проекцию.
*Правило
**Повторное применение проекции заменяется внешней
**$π_{A}(π_{B}(R)) ⇒ π_{A}(R)$
Сразу все спроецируем на имя студента.
*Пример
**$π_{FirstName}(π_{FirstName, Name}(S × G)) ⇒ π_{FirstName}(S × G)$
==== Проекция и фильтрация ====
Как работать со смесью проекций и фильтраций? Утверждение: мы всегда можем осуществлять фильтрацию до проекций.
*Правило
**Фильтрация осуществляется до проекции
**$σ_{cond}(π_{A}(R)) ⇒ π_{A}(σ_{cond}(R))$
Сначала спроецировали, потом отфильтровали и опять спроецировали. Давайте перенесем фильтр во внутрь проекции. Две внешние операции оказываются проекциями. Можем склеить их в одну проекцию с конъюнкцией.
*Пример
** $π_{FirstName}(σ_{Name=M34391}(π_{FirstName, Name}(S × G))) ⇒ π_{FirstName}(π_{FirstName, Name}(σ_{Name=M34391}(S × G))) ⇒ π_{FirstName}(σ_{Name=M34391}(S × G))$
Обратим внимание, что в обратном порядке мы делать не можем, не можем вытаскивать фильтр из-под проекции, так как фильтр может зависеть от тех столбцов, которые проекция удалит.
=== Алгебраические свойства операций ===
