1632
правки
Изменения
м
Чуть ли не на уровне парсера у нас реляционное Реляционное исчисление преобразуется в реляционную алгебру. Если была запись в реляционном исчислении, то у нее вынесли кванторы и преобразовали в реляционную алгебру на основе подхода . Для любого запроса в терминах реляционного исчисления можно построить запрос в терминах реляционной алгебры.
Первое что происходит - Сначала избавляемся от внешних соединений. Внешние соединения - — это надстройка над обычными соединениями и более простыми операциями.
Давайте сразу объединим фильтр связанный с естественным соединением и фильтр по номеру группы в общий фильтр с конъюнкцией.
Сразу все спроецируем на имя студента.
Сначала спроецировалиОбратим внимание, потом отфильтровали и опять спроецировали. Давайте перенесем что в обратном порядке мы делать не можем, не можем вытаскивать фильтр во внутрь из-под проекции, так как фильтр может зависеть от тех столбцов, которые проекция удалит. Две внешние операции оказываются проекциями. Можем склеить их в одну проекцию с конъюнкцией.
Обратим внимание, что в обратном порядке мы делать не можем, не можем вытаскивать фильтр из-под проекции, так как фильтр может зависеть от тех столбцов, которые проекция удалит.
1) Мы можем пользовать стандартными алгебраическими трюками. Предположим хотим отфильтровать объединение. Можем отфильтровать первый аргумент, потом второй, а потом объединить.
2'''Фильтрация''' Мы можем пользовать стандартными алгебраическими трюками. Предположим хотим отфильтровать объединение. Можем отфильтровать первый аргумент, потом второй, а потом объединить.{{Утверждение|statement=$σ_{cond}(R_1 ∪ R_2) Аналогично для пересечения⇒ σ_{cond}(R_1) ∪ σ_{cond}(R_2)$}}
3) Аналогично для разностипересечения{{Утверждение|statement=$σ_{cond}(R_1 ∩ R_2) ⇒ σ_{cond}(R_1) ∩ σ_{cond}(R_2)$}}
4) Естественное соединение. Если можем разделить условие на две части, одна из которых относится проверяет атрибуты только из левого атрибута, а вторая только из правого, то мы можем протолкнуть этот фильтр отдельно в левый и правый аргумент, а потом соединить только Аналогично для строк, удовлетворяющим своим половинкам фильтра. разности*Фильтрация** $σ_{cond}(R_1 ∪ R_2) ⇒ σ_{cond}(R_1) ∪ σ_{cond}(R_2)$Утверждение** $σ_{cond}(R_1 \cap R_2) ⇒ σ_{cond}(R_1) \cap σ_{cond}(R_2)$|statement=** $σ_{cond}(R_1 - R_2) ⇒ σ_{cond}(R_1) - σ_{cond}(R_2)$** $σ_{cond_1 ∧ cond_2}(R_1 ⋈ R_2) ⇒ σ_{cond_1}(R_1) ⋈ σ_{cond_2}(R_2)$
1Естественное соединение. Если можем разделить условие на две части, одна из которых относится проверяет атрибуты только из левого атрибута, а вторая только из правого, то мы можем протолкнуть этот фильтр отдельно в левый и правый аргумент, а потом соединить только для строк, удовлетворяющим своим половинкам фильтра. Аналогично для разности{{Утверждение|statement=$σ_{cond_1 ∧ cond_2}(R_1 ⋈ R_2) Можем безопасно проекцировать результат объединения⇒ σ_{cond_1}(R_1) ⋈ σ_{cond_2}(R_2)$}} '''Проекция'''
2) Не можем Можем безопасно проецировать проекцировать результат пересечения, потому что слева могли быть кортежи, которые кроме атрибута объединения{{Утверждение|statement=$A$ содержат еще какой-то дополнительный атрибут $X$. Они различались, вошли в пересечение и уже потом мы их спроецируем. Если же сначала сделать проекцию, то этот атрибут $X$ теряется и два кортежа с одинаковым атрибутом $A$ но разным атрибутом $Xπ_A(R_1 ∪ R_2) ⇒ π_A(R_1) ∪ π_A(R_2)$ для нас станут неразличимы.}}
3Не можем безопасно проецировать результат пересечения, потому что слева могли быть кортежи, которые кроме атрибута $A$ содержат еще какой-то дополнительный атрибут $X$. Они различались, вошли в пересечение и уже потом мы их спроецируем. Если же сначала сделать проекцию, то этот атрибут $X$ теряется и два кортежа с одинаковым атрибутом $A$ но разным атрибутом $X$ для нас станут неразличимы.{{Утверждение|statement=$π_A(R_1 ∩ R_2) ⇏ π_A(R_1) ∩ π_A(R_2) Аналогично для разности$}}
4) С естественным соединением все чуть сложнее. Протолкнем в проекцию только те атрибуты, которые были из левого аргумента, вправо только те, которые были из правого. Но зачем мы делаем $A ∪ R_2$, зачем $R_2$? Именно по $R_2$ мы будем соединять, по ним проводилось естественное соединение. Аналогично $A ∪ R_1$. Внешняя проекция нужна для того, чтобы избавиться от тех атрибутов, которые мы потенциально могли добавить в левой и правой части. разности. {{Утверждение*Проекция** $π_A(R_1 ∪ R_2) ⇒ π_A(R_1) ∪ π_A(R_2)$|statement=** $π_A(R_1 ∩ R_2) ⇏ π_A(R_1) ∩ π_A(R_2)$** $π_A(R_1 - R_2) ⇏ π_A(R_1) - π_A(R_2)$** $π_{A}(R_1 ⋈ R_2) ⇒ π_A(π_{(A ∪ R_2) ∩ R_1}(R_1) ⋈ π_{(A ∪ R_1) ∩ R_2}(R_2))$
За счет коммутативности можем выбирать какая сторона считается левой, а какая правой. Это полезно, потому что можем не делать дублирующиеся методы, когда они не симметричны.
Для ассоциативных операция можем выбирать порядок в котором будет эти ассоциативные операции применять. Мы можем рассматривать не конкретное дерево, которое получилось в результате разбора, а плоский набор отношений и ассоциативные операции между ними, а дальше в каком порядке будет выполнять операции и расставлять скобки зависит уже от нас.
Оценки, которые пренадлежат отдному и тому же студенту, причем оценка по первому предмету лучше, чем оценка по второму предмету и по второму предмету есть хотя бы 60 баллов. Замкнув предикат получим, что оценка по первому предмету строго больше 60 баллов ( > 60). Теперь есть условие, которое зависит только от первого экземпляра таблицы оценок и условие, зависящее только от второго экземпляра таблицы оценок. Протолкнем их во внутрь соединения. За счет замыкания предикатов получили новое условие, которое можно протолкнуть в один из операндов.
rollbackEdits.php mass rollback
По большому счету sql базы данных отличаются двумя вещами - тем, как они поддерживают транзакции и тем, насколько хорошо у них умеет работать планировщик запросов.
'''Общий план:'''
* На вход приходит sql.
* Отправляем его в разборщик запросов(парсер). Он на выходе выдаст реляционную алгебру.
* Реляционная алгебра передается в исполнитель запроса, который ее исполняет. Исполнитель запроса взаимодействует с источником данных в тот момент, когда ему понадобились данные для исполнения запросов.
'''Планировщики делятся на две части:'''
==== Перезапись и планировщик ====
Перезапись запроса. Составляет некоторый набор фиксированных правил, которые не зависят от конкретного запроса
==== Преобразование подзапросов ====
Начиная с этого момента оперируем '''только реляционной алгеброй'''
==== Преобразование соединений ====
*Внешние соединения
**$R_1 ⟗_θ R_2 ⇒ (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))$
Cразу объединим фильтр связанный с естественным соединением и фильтр по номеру группы в общий фильтр с конъюнкцией.
==== Повторная проекция ====
Если есть несколько проекций, то можно заменить на одну внешнюю проекцию.
**$π_{A}(π_{B}(R)) ⇒ π_{A}(R)$
*Пример
**$π_{FirstName}(π_{FirstName, Name}(S × G)) ⇒ π_{FirstName}(S × G)$
Сразу все спроецируем на имя студента.
==== Проекция и фильтрация ====
Как работать со смесью проекций и фильтраций? {{Утверждение: мы |statement=Фильтрацию всегда можем можно осуществлять фильтрацию до проекцийпроекции.}}
*Правило
**Фильтрация осуществляется до проекции
**$σ_{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))$
Сначала спроецировали, потом отфильтровали и опять спроецировали. Давайте перенесем фильтр во внутрь проекции. Две внешние операции оказываются проекциями. Можем склеить их в одну проекцию с конъюнкцией.
=== Алгебраические свойства операций ===
==== Дистрибутивность операций ====
С естественным соединением все чуть сложнее. Протолкнем в проекцию только те атрибуты, которые были из левого аргумента, вправо только те, которые были из правого. Но зачем мы делаем $A ∪ R_2$, зачем $R_2$? Именно по $R_2$ мы будем соединять, по ним проводилось естественное соединение. Аналогично $A ∪ R_1$. Внешняя проекция нужна для того, чтобы избавиться от тех атрибутов, которые мы потенциально могли добавить в левой и правой части.
{{Утверждение
|statement=
$π_{A}(R_1 ⋈ R_2) ⇒ π_A(π_{(A ∪ R_2) ∩ R_1}(R_1) ⋈ π_{(A ∪ R_1) ∩ R_2}(R_2))$
}}
==== Коммутативность операций ====
За счет коммутативности можем выбирать какая сторона считается левой, а какая правой. Это полезно, потому что можем не делать дублирующиеся методы, когда они не симметричны.
*Коммутативные операции
**$\div$, $⋇$
*Применение коммутативности
** Выбор левой и правой стороны для несимметричных методов исполнения
==== Ассоциативность операций ====
Для ассоциативных операция можем выбирать порядок в котором будет эти ассоциативные операции применять. Мы можем рассматривать не конкретное дерево, которое получилось в результате разбора, а плоский набор отношений и ассоциативные операции между ними, а дальше в каком порядке будет выполнять операции и расставлять скобки зависит уже от нас.
*Ассоциативные операции
**$\div$, $⋇$
*Применение ассоциативности
**Выбор порядка выполнения операций
**$a > b ∧ b > c ⇒ a > b ∧ b > c ∧ a > c$
Переразбить условие и запихнуть часть из них под соединение.
*Пример
**$σ_{P_1.p > P_2.p ∧ P_2.p ≥ 60}(P_1 ⋈_{P_1.SId = P_2.SId} P_2) ⇒ σ_{P_1.p > P_2.p ∧ P_2.p ≥ 60 ∧ P_1.p > 60}(P_1 ⋈_{P_1.SId = P_2.SId} P_2) ⇒ σ_{P_1.p > P_2.p}(σ_{p > 60}(P_1) ⋈_{P_1.SId = P_2.SId} σ_{p ≥ 60}(P_2))$
Оценки, которые принадлежат одному и тому же студенту, причем оценка по первому предмету лучше, чем оценка по второму предмету и по второму предмету есть хотя бы 60 баллов. Замкнув предикат получим, что оценка по первому предмету строго больше 60 баллов ( > 60). Теперь есть условие, которое зависит только от первого экземпляра таблицы оценок и условие, зависящее только от второго экземпляра таблицы оценок. Протолкнем их во внутрь соединения. За счет замыкания предикатов получили новое условие, которое можно протолкнуть в один из операндов.
==== КНФ и ДНФ ====
Некоторые базы данных преобразуют условия в дизъюнктивную или конъюнктивную нормальную форму исходя из соображения, что и ту и другую можно исполнять слева направо, пока не найдем первую лож для КНФ или первую истину для ДНФ. При этом можем пересортировать условия в нужном и удобном нам порядке. К примеру более быстрые условия поместить вперед. С другой стороны оптимизатор может более строгие условия, то есть те, которые отсеивают большее количество строк, перемещать вперед.
Превратили все в ассоциативный и коммутативный вид, что позволяет нам произвольным образом переупорядочивать конъюнкты, в случаю КНФ, или дизъюнкты, в случае ДНФ.
К тому же за счет правил более эффективно вычислять .
*Преобразование предикатов
**Конъюнктивная нормальная форма
**Неэквивалентные запросы
**Тот же результат
В частности , если, если нас просят спроецировать на имя студентов естественное соединение студентов и групп и мы знаем, что в $Students $ $GroupId $ является внешним ключом, то мы можем сделать вывод, что это просто проецирование на имя таблички студентов.
*Пример
**$π_{FirstName}(Students ⋈ Groups) ⇒ π_{FirstName}(Students)$, если $Students.GId ⊂ Groups.GId$
