Álgebra Relacional para Otimização de Consulta

Quando uma consulta é colocada, ela é primeiro escaneada, analisada e validada. Uma representação interna da consulta é então criada, como uma árvore de consulta ou um gráfico de consulta. Em seguida, estratégias de execução alternativas são concebidas para recuperar os resultados das tabelas do banco de dados. O processo de escolha da estratégia de execução mais apropriada para o processamento de consultas é chamado de otimização de consultas.

Problemas de otimização de consulta em DDBMS

No DDBMS, a otimização da consulta é uma tarefa crucial. A complexidade é alta, pois o número de estratégias alternativas pode aumentar exponencialmente devido aos seguintes fatores -

A presença de vários fragmentos.
Distribuição dos fragmentos ou tabelas em vários sites.
A velocidade dos links de comunicação.
Disparidade nas capacidades de processamento local.

Conseqüentemente, em um sistema distribuído, o objetivo geralmente é encontrar uma boa estratégia de execução para o processamento de consultas, em vez da melhor. O tempo para executar uma consulta é a soma do seguinte -

É hora de comunicar as consultas aos bancos de dados.
Hora de executar fragmentos de consulta local.
É hora de reunir dados de diferentes sites.
Hora de exibir os resultados para o aplicativo.

Processamento de Consulta

O processamento de consulta é um conjunto de todas as atividades, começando da colocação da consulta até a exibição dos resultados da consulta. As etapas são mostradas no diagrama a seguir -

Álgebra Relacional

A álgebra relacional define o conjunto básico de operações do modelo de banco de dados relacional. Uma sequência de operações de álgebra relacional forma uma expressão de álgebra relacional. O resultado desta expressão representa o resultado de uma consulta ao banco de dados.

As operações básicas são -

Projection
Selection
Union
Intersection
Minus
Join

Projeção

A operação de projeção exibe um subconjunto de campos de uma tabela. Isso fornece uma partição vertical da tabela.

Syntax in Relational Algebra

$$ \ pi _ {<{AttributeList}>} {(<{Nome da tabela}>)} $$

Por exemplo, vamos considerar o seguinte banco de dados de alunos -

STUDENT
Roll_No	Name	Course	Semester	Gender
2	Amit Prasad	BCA	1	Masculino
4	Varsha Tiwari	BCA	1	Fêmea
5	Asif Ali	MCA	2	Masculino
6	Joe Wallace	MCA	1	Masculino
8	Shivani Iyengar	BCA	1	Fêmea

Se quisermos exibir os nomes e cursos de todos os alunos, usaremos a seguinte expressão de álgebra relacional -

$$ \ pi_ {Nome, Curso} {(ALUNO)} $$

Seleção

A operação de seleção exibe um subconjunto de tuplas de uma tabela que satisfaz certas condições. Isso fornece uma partição horizontal da tabela.

Syntax in Relational Algebra

$$ \ sigma _ {<{Condições}>} {(<{Nome da Tabela}>)} $$

Por exemplo, na tabela do Aluno, se quisermos exibir os detalhes de todos os alunos que optaram pelo curso MCA, usaremos a seguinte expressão de álgebra relacional -

$$ \ sigma_ {Curso} = {\ pequeno "BCA"} ^ {(ALUNO)} $$

Combinação de operações de projeção e seleção

Para a maioria das consultas, precisamos de uma combinação de operações de projeção e seleção. Existem duas maneiras de escrever essas expressões -

Usando sequência de projeção e operações de seleção.
Usando a operação de renomeação para gerar resultados intermediários.

Por exemplo, para exibir os nomes de todas as alunas do curso BCA -

Expressão de álgebra relacional usando sequência de projeção e operações de seleção

$$ \ pi_ {Nome} (\ sigma_ {Gênero = \ pequena "Mulher" AND \: Curso = \ pequena "BCA"} {(ALUNO)}) $$

Expressão de álgebra relacional usando operação de renomeação para gerar resultados intermediários

$$ FemininoBCAStudent \ leftarrow \ sigma_ {Gênero = \ pequeno "Feminino" AND \: Curso = \ pequeno "BCA"} {(ALUNO)} $$

$$ Result \ leftarrow \ pi_ {Name} {(FemaleBCAStudent)} $$

União

Se P é o resultado de uma operação e Q é o resultado de outra operação, a união de P e Q ($ p \ cup Q $) é o conjunto de todas as tuplas que estão em P ou em Q ou em ambos sem duplicatas .

Por exemplo, para exibir todos os alunos que estão no Semestre 1 ou no curso BCA -

$$ Sem1Student \ leftarrow \ sigma_ {Semester = 1} {(STUDENT)} $$

$$ BCAStudent \ leftarrow \ sigma_ {Course = \ small "BCA"} {(ALUNO)} $$

$$ Result \ leftarrow Sem1Student \ cup BCAStudent $$

Interseção

Se P é o resultado de uma operação e Q é o resultado de outra operação, a interseção de P e Q ($ p \ cap Q $) é o conjunto de todas as tuplas que estão em P e Q ambos.

Por exemplo, dados os dois esquemas a seguir -

EMPLOYEE

EmpID	Nome	Cidade	Departamento	Salário

PROJECT

PId	Cidade	Departamento	Status

Para exibir os nomes de todas as cidades onde um projeto está localizado e também onde um funcionário reside -

$$ CityEmp \ leftarrow \ pi_ {City} {(EMPLOYEE)} $$

$$ CityProject \ leftarrow \ pi_ {City} {(PROJECT)} $$

$$ Result \ leftarrow CityEmp \ cap CityProject $$

Menos

Se P é o resultado de uma operação e Q é o resultado de outra operação, P - Q é o conjunto de todas as tuplas que estão em P e não em Q.

Por exemplo, para listar todos os departamentos que não têm um projeto em andamento (projetos com status = em andamento) -

$$ AllDept \ leftarrow \ pi_ {Departamento} {(FUNCIONÁRIO)} $$

$$ ProjectDept \ leftarrow \ pi_ {Departamento} (\ sigma_ {Status = \ pequeno "em andamento"} {(PROJETO)}) $$

$$ Result \ leftarrow AllDept - ProjectDept $$

Junte-se

A operação de junção combina tuplas relacionadas de duas tabelas diferentes (resultados de consultas) em uma única tabela.

Por exemplo, considere dois esquemas, Cliente e Agência em um banco de dados do Banco da seguinte maneira -

CUSTOMER

CustID	AccNo	TypeOfAc	BranchID	DateOfOpening

BRANCH

BranchID	BranchName	IFSCcode	Endereço

Para listar os detalhes do funcionário junto com os detalhes da filial -

$$ Result \ leftarrow CUSTOMER \ bowtie_ {Customer.BranchID = Branch.BranchID} {FILIAL} $$

Traduzindo consultas SQL em álgebra relacional

As consultas SQL são traduzidas em expressões de álgebra relacional equivalentes antes da otimização. Uma consulta é primeiramente decomposta em blocos de consulta menores. Esses blocos são traduzidos em expressões de álgebra relacional equivalentes. A otimização inclui a otimização de cada bloco e, em seguida, a otimização da consulta como um todo.

Exemplos

Vamos considerar os seguintes esquemas -

EMPREGADO

EmpID	Nome	Cidade	Departamento	Salário

PROJETO

PId	Cidade	Departamento	Status

TRABALHO

EmpID	PID	Horas

Exemplo 1

Para exibir os detalhes de todos os funcionários que ganham um salário MENOS do que o salário médio, escrevemos a consulta SQL -

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

Esta consulta contém uma subconsulta aninhada. Então, isso pode ser dividido em dois blocos.

O bloco interno é -

SELECT AVERAGE(SALARY)FROM EMPLOYEE ;

Se o resultado desta consulta for AvgSal, o bloco externo será -

SELECT * FROM EMPLOYEE WHERE SALARY < AvgSal;

Expressão de álgebra relacional para bloco interno -

$$ AvgSal \ leftarrow \ Im_ {AVERAGE (Salário)} {FUNCIONÁRIO} $$

Expressão de álgebra relacional para bloco externo -

$$ \ sigma_ {Salário <{AvgSal}>} {FUNCIONÁRIO} $$

Exemplo 2

Para exibir o ID do projeto e o status de todos os projetos do funcionário 'Arun Kumar', escrevemos a consulta SQL -

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

Esta consulta contém duas subconsultas aninhadas. Assim, pode ser dividido em três blocos, da seguinte forma -

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

(Aqui, ArunEmpID e ArunPID são os resultados de consultas internas)

Expressões de álgebra relacional para os três blocos são -

$$ ArunEmpID \ leftarrow \ pi_ {EmpID} (\ sigma_ {Nome = \ small "Arun Kumar"} {(FUNCIONÁRIO)}) $$

$$ ArunPID \ leftarrow \ pi_ {PID} (\ sigma_ {EmpID = \ small "ArunEmpID"} {(TRABALHOS)}) $$

$$ Resultado \ leftarrow \ pi_ {PID, Status} (\ sigma_ {PID = \ small "ArunPID"} {(PROJETO)}) $$

Computação de operadores de álgebra relacional

O cálculo de operadores de álgebra relacional pode ser feito de muitas maneiras diferentes, e cada alternativa é chamada de access path.

A alternativa de computação depende de três fatores principais -

Tipo de operador
Memoria disponivel
Estruturas de disco

O tempo para realizar a execução de uma operação de álgebra relacional é a soma de -

É hora de processar as tuplas.
É hora de buscar as tuplas da tabela do disco para a memória.

Como o tempo para processar uma tupla é muito menor do que o tempo para buscar a tupla no armazenamento, particularmente em um sistema distribuído, o acesso ao disco é frequentemente considerado como a métrica para calcular o custo da expressão relacional.

Cálculo de Seleção

O cálculo da operação de seleção depende da complexidade da condição de seleção e da disponibilidade de índices nos atributos da tabela.

A seguir estão as alternativas de computação, dependendo dos índices -

No Index- Se a tabela não estiver classificada e não tiver índices, o processo de seleção envolve a varredura de todos os blocos de disco da tabela. Cada bloco é trazido para a memória e cada tupla no bloco é examinada para ver se ela satisfaz a condição de seleção. Se a condição for satisfeita, ela será exibida como saída. Esta é a abordagem mais cara, pois cada tupla é trazida para a memória e cada tupla é processada.
B+ Tree Index- A maioria dos sistemas de banco de dados são construídos sobre o índice B + Tree. Se a condição de seleção for baseada no campo, que é a chave deste índice B + Tree, então esse índice é usado para recuperar os resultados. No entanto, o processamento de instruções de seleção com condições complexas pode envolver um número maior de acessos de bloco de disco e, em alguns casos, a varredura completa da tabela.
Hash Index- Se índices hash são usados e seu campo-chave é usado na condição de seleção, então recuperar tuplas usando o índice hash torna-se um processo simples. Um índice hash usa uma função hash para encontrar o endereço de um depósito onde o valor da chave correspondente ao valor hash está armazenado. Para encontrar um valor-chave no índice, a função hash é executada e o endereço do depósito é encontrado. Os valores-chave no intervalo são pesquisados. Se uma correspondência for encontrada, a tupla real é buscada do bloco de disco para a memória.

Cálculo de Joins

Quando queremos unir duas tabelas, digamos P e Q, cada tupla em P deve ser comparada com cada tupla em Q para testar se a condição de junção é satisfeita. Se a condição for satisfeita, as tuplas correspondentes são concatenadas, eliminando campos duplicados e anexadas à relação de resultado. Conseqüentemente, esta é a operação mais cara.

As abordagens comuns para computar junções são -

Abordagem de loop aninhado

Esta é a abordagem convencional de junção. Ele pode ser ilustrado através do seguinte pseudocódigo (Tabelas P e Q, com tuplas tuple_p e tuple_q e juntando o atributo 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

Abordagem de classificação-mesclagem

Nessa abordagem, as duas tabelas são classificadas individualmente com base no atributo joining e, em seguida, as tabelas classificadas são mescladas. Técnicas de classificação externa são adotadas, pois o número de registros é muito alto e não pode ser acomodado na memória. Depois que as tabelas individuais são classificadas, uma página de cada uma das tabelas classificadas é trazida para a memória, mesclada com base no atributo joining e as tuplas unidas são gravadas.

Abordagem de Hash-join

Essa abordagem compreende duas fases: fase de particionamento e fase de sondagem. Na fase de particionamento, as tabelas P e Q são divididas em dois conjuntos de partições disjuntas. Uma função hash comum é decidida. Esta função hash é usada para atribuir tuplas a partições. Na fase de sondagem, as tuplas em uma partição de P são comparadas com as tuplas da partição correspondente de Q. Se elas corresponderem, serão gravadas.