Реляционная алгебра для оптимизации запросов

Когда запрос размещен, он сначала сканируется, анализируется и проверяется. Затем создается внутреннее представление запроса, такое как дерево запроса или граф запроса. Затем разрабатываются альтернативные стратегии выполнения для получения результатов из таблиц базы данных. Процесс выбора наиболее подходящей стратегии выполнения для обработки запроса называется оптимизацией запроса.

Проблемы оптимизации запросов в DDBMS

В DDBMS оптимизация запросов является важной задачей. Сложность высока, поскольку количество альтернативных стратегий может экспоненциально увеличиваться из-за следующих факторов:

Наличие ряда фрагментов.
Распространение фрагментов или таблиц по разным сайтам.
Скорость связи.
Несоответствие в возможностях локальной обработки.

Следовательно, в распределенной системе часто цель состоит в том, чтобы найти хорошую стратегию выполнения для обработки запросов, а не лучшую. Время выполнения запроса складывается из следующего:

Время передавать запросы к базам данных.
Пора выполнять фрагменты локального запроса.
Пора собирать данные с разных сайтов.
Пора отображать результаты в приложении.

Обработка запросов

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

Реляционная алгебра

Реляционная алгебра определяет базовый набор операций модели реляционной базы данных. Последовательность операций реляционной алгебры образует выражение реляционной алгебры. Результат этого выражения представляет собой результат запроса к базе данных.

Основные операции -

Projection
Selection
Union
Intersection
Minus
Join

Проекция

Операция проецирования отображает подмножество полей таблицы. Это дает вертикальное разделение таблицы.

Syntax in Relational Algebra

$$ \ pi _ {<{AttributeList}>} {(<{Имя таблицы}>)} $$

Например, давайте рассмотрим следующую базу данных студентов -

STUDENT
Roll_No	Name	Course	Semester	Gender
2	Амит Прасад	BCA	1	мужчина
4	Варша Тивари	BCA	1	женский
5	Асиф Али	MCA	2	мужчина
6	Джо Уоллес	MCA	1	мужчина
8	Шивани Айенгар	BCA	1	женский

Если мы хотим отобразить имена и курсы всех студентов, мы будем использовать следующее выражение реляционной алгебры -

$$ \ pi_ {Имя, Курс} {(СТУДЕНТ)} $$

Выбор

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

Syntax in Relational Algebra

$$ \ sigma _ {<{Условия}>} {(<{Имя таблицы}>)} $$

Например, в таблице «Студент», если мы хотим отобразить сведения обо всех студентах, которые выбрали курс MCA, мы будем использовать следующее выражение реляционной алгебры:

$$ \ sigma_ {Course} = {\ small "BCA"} ^ {(СТУДЕНТ)} $$

Комбинация операций проецирования и выбора

Для большинства запросов нам нужна комбинация операций проекции и выбора. Эти выражения можно записать двумя способами:

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

Например, чтобы отобразить имена всех студенток курса BCA -

Выражение реляционной алгебры с использованием последовательности операций проекции и выбора

$$ \ pi_ {Имя} (\ sigma_ {Gender = \ small "Female" AND \: Course = \ small "BCA"} {(СТУДЕНТ)}) $$

Выражение реляционной алгебры с использованием операции переименования для генерации промежуточных результатов

$$ FemaleBCAStudent \ leftarrow \ sigma_ {Пол = \ small "Женский" AND \: Course = \ small "BCA"} {(СТУДЕНТ)} $$

$$ Результат \ leftarrow \ pi_ {Имя} {(FemaleBCAStudent)} $$

Союз

Если P - результат операции, а Q - результат другой операции, объединение P и Q ($ p \ cup Q $) - это набор всех кортежей, которые находятся либо в P, либо в Q, либо в обоих без дубликатов. .

Например, чтобы отобразить всех студентов, которые либо учатся в семестре 1, либо проходят курс BCA -

$$ Sem1Student \ leftarrow \ sigma_ {Semester = 1} {(СТУДЕНТ)} $$

$$ BCAStudent \ leftarrow \ sigma_ {Course = \ small "BCA"} {(СТУДЕНТ)} $$

$$ Результат \ leftarrow Sem1Student \ cup BCAStudent $$

Пересечение

Если P является результатом операции, а Q - результатом другой операции, пересечение P и Q ($ p \ cap Q $) - это набор всех кортежей, которые находятся в P и Q обоих.

Например, учитывая следующие две схемы -

EMPLOYEE

EmpID	название	город	Отдел	Зарплата

PROJECT

PId	город	Отдел	Положение дел

Чтобы отобразить названия всех городов, в которых находится проект, а также проживает сотрудник -

$$ CityEmp \ leftarrow \ pi_ {Город} {(СОТРУДНИК)} $$

$$ CityProject \ leftarrow \ pi_ {Город} {(ПРОЕКТ)} $$

$$ Результат \ leftarrow CityEmp \ cap CityProject $$

Минус

Если P является результатом операции, а Q - результатом другой операции, P - Q - это набор всех кортежей, которые находятся в P, а не в Q.

Например, чтобы перечислить все отделы, у которых нет текущего проекта (проекты со статусом = текущий) -

$$ AllDept \ leftarrow \ pi_ {Отдел} {(СОТРУДНИК)} $$

$$ ProjectDept \ leftarrow \ pi_ {Отдел} (\ sigma_ {Status = \ small "в процессе"} {(ПРОЕКТ)}) $$

$$ Результат \ leftarrow AllDept - ProjectDept $$

Присоединиться

Операция соединения объединяет связанные кортежи двух разных таблиц (результаты запросов) в одну таблицу.

Например, рассмотрим две схемы, клиент и филиал в базе данных банка, как показано ниже:

CUSTOMER

CustID	AccNo	ТипOfAc	BranchID	DateOfOpening

BRANCH

BranchID	BranchName	IFSCcode	Адрес

Чтобы перечислить данные о сотрудниках вместе с данными филиала -

$$ Результат \ leftarrow CUSTOMER \ bowtie_ {Customer.BranchID = Branch.BranchID} {BRANCH} $$

Перевод SQL-запросов в реляционную алгебру

Перед оптимизацией запросы SQL переводятся в эквивалентные выражения реляционной алгебры. Запрос сначала разбивается на более мелкие блоки запроса. Эти блоки переводятся в эквивалентные выражения реляционной алгебры. Оптимизация включает оптимизацию каждого блока, а затем оптимизацию запроса в целом.

Примеры

Давайте рассмотрим следующие схемы -

РАБОТНИК

EmpID	название	город	Отдел	Зарплата

ПРОЕКТ

PId	город	Отдел	Положение дел

РАБОТАЕТ

EmpID	PID	Часы работы

Пример 1

Чтобы отобразить подробную информацию обо всех сотрудниках, которые получают зарплату МЕНЬШЕ, чем средняя зарплата, мы пишем SQL-запрос:

SELECT * FROM EMPLOYEE 
WHERE SALARY < ( SELECT AVERAGE(SALARY) FROM EMPLOYEE ) ;

Этот запрос содержит один вложенный подзапрос. Итак, это можно разбить на два блока.

Внутренний блок -

SELECT AVERAGE(SALARY)FROM EMPLOYEE ;

Если результатом этого запроса является AvgSal, то внешний блок -

SELECT * FROM EMPLOYEE WHERE SALARY < AvgSal;

Выражение реляционной алгебры для внутреннего блока -

$$ AvgSal \ leftarrow \ Im_ {AVERAGE (Salary)} {EMPLOYEE} $$

Выражение реляционной алгебры для внешнего блока -

$$ \ sigma_ {Salary <{AvgSal}>} {EMPLOYEE} $$

Пример 2

Чтобы отобразить идентификатор проекта и статус всех проектов сотрудника Аруна Кумара, мы пишем SQL-запрос -

SELECT PID, STATUS FROM PROJECT 
WHERE PID = ( SELECT FROM WORKS  WHERE EMPID = ( SELECT EMPID FROM EMPLOYEE 
            WHERE NAME = 'ARUN KUMAR'));

Этот запрос содержит два вложенных подзапроса. Таким образом, его можно разбить на три блока, а именно:

SELECT EMPID FROM EMPLOYEE WHERE NAME = 'ARUN KUMAR'; 
SELECT PID FROM WORKS WHERE EMPID = ArunEmpID; 
SELECT PID, STATUS FROM PROJECT WHERE PID = ArunPID;

(Здесь ArunEmpID и ArunPID - это результаты внутренних запросов)

Выражения реляционной алгебры для трех блоков:

$$ ArunEmpID \ leftarrow \ pi_ {EmpID} (\ sigma_ {Name = \ small "Арун Кумар"} {(СОТРУДНИК)}) $$

$$ ArunPID \ leftarrow \ pi_ {PID} (\ sigma_ {EmpID = \ small "ArunEmpID"} {(РАБОТАЕТ)}) $$

$$ Результат \ leftarrow \ pi_ {PID, Status} (\ sigma_ {PID = \ small "ArunPID"} {(PROJECT)}) $$

Вычисление операторов реляционной алгебры

Вычисление операторов реляционной алгебры может выполняться разными способами, и каждая альтернатива называется access path.

Альтернатива вычисления зависит от трех основных факторов:

Тип оператора
Доступная память
Дисковые структуры

Время на выполнение операции реляционной алгебры складывается из -

Пора обработать кортежи.
Пришло время извлечь кортежи таблицы с диска в память.

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

Вычисление выбора

Вычисление операции выбора зависит от сложности условия выбора и наличия индексов для атрибутов таблицы.

Ниже приведены альтернативы вычислений в зависимости от индексов.

No Index- Если таблица не отсортирована и не имеет индексов, то процесс выбора включает сканирование всех дисковых блоков таблицы. Каждый блок помещается в память, и каждый кортеж в блоке исследуется, чтобы увидеть, удовлетворяет ли он условию выбора. Если условие выполнено, оно отображается как результат. Это самый затратный подход, поскольку каждый кортеж помещается в память и обрабатывается каждый кортеж.
B+ Tree Index- Большинство систем баз данных построены на индексе B + Tree. Если условие выбора основано на поле, которое является ключом этого индекса B + Tree, то этот индекс используется для получения результатов. Однако обработка операторов выбора со сложными условиями может включать большее количество обращений к блоку диска и в некоторых случаях полное сканирование таблицы.
Hash Index- Если используются хэш-индексы и его ключевое поле используется в условии выбора, то получение кортежей с использованием хэш-индекса становится простым процессом. Хеш-индекс использует хеш-функцию для поиска адреса корзины, в которой хранится значение ключа, соответствующее хеш-значению. Чтобы найти значение ключа в индексе, выполняется хеш-функция и определяется адрес корзины. Выполняется поиск ключевых значений в сегменте. Если совпадение найдено, фактический кортеж извлекается из дискового блока в память.

Вычисление объединений

Когда мы хотим объединить две таблицы, скажем, P и Q, каждый кортеж в P должен быть сравнен с каждым кортежем в Q, чтобы проверить, удовлетворяется ли условие соединения. Если условие удовлетворяется, соответствующие кортежи объединяются, удаляются повторяющиеся поля и добавляются к отношению результата. Следовательно, это самая дорогая операция.

Общие подходы к вычислению соединений:

Подход с вложенным циклом

Это обычный подход соединения. Это можно проиллюстрировать с помощью следующего псевдокода (таблицы P и Q, с кортежами tuple_p и tuple_q и атрибутом соединения a) -

For each tuple_p in P 
For each tuple_q in Q
If tuple_p.a = tuple_q.a Then 
   Concatenate tuple_p and tuple_q and append to Result 
End If 
Next tuple_q 
Next tuple-p

Подход сортировки-слияния

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

Подход хэш-соединения

Этот подход состоит из двух этапов: этапа разделения и этапа исследования. На этапе разделения таблицы P и Q разбиваются на два набора непересекающихся разделов. Выбирается общая хеш-функция. Эта хеш-функция используется для назначения кортежей разделам. На этапе проверки кортежи в разделе P сравниваются с кортежами в соответствующем разделе Q. Если они совпадают, они записываются.