Chapter -2

1. Query Processing:

Query processing is performed by the Relational Engine in SQL Server. It is the

process of taking the T-SQL statements you write and converting them into
something that can make requests to the Storage Engine and retrieve the results
needed.

SQL Server takes four steps to process a query: parsing, translating, optimizing,
and execution. They are shown in Figure 1. The first four steps are all performed
by the Relational Engine. The output of the third step is the optimized plan that
is scheduled, and during which calls are made to the Storage Engine to retrieve
the data that becomes the results of the query you are executing.

Parsing

During the parsing stage SQL Server performs basic checks on the source code
(your T-SQL batch). This parsing looks for invalid SQL syntax, such as incorrect
use of reserved words, column and table names, and so on.
If parsing completes without errors, it generates a parse tree, which is passed
onto the next stage of query processing, binding. The parse tree is an internal
representation of the query. If parsing detects any errors, the process stops and
the errors are returned.

Syntax for Parse tree:

Query

Select (Select list) from [from list] where [condition]

Eg:
Select studid, studname from student1 where age>20;

Query

Select [select list] from [from list] where [condition]

Attribute1 Attribute2 Relation_name attribute > value

Studid studname student1 age 20

Translation:
It is used to translate the given SQL query to low level language query
using relational algebra operations.
Basic operation:
σ- Selection which is used to select a tuple.
Π- Projection which is used to select an attributes.

Eg:
Select empname from employee where salary>10000;

Π empname (σ (employee))
salary>10000

Optimization:
It is used to optimize the query find low cost query. It maintains statistical
data as size of the table, query size, record size, running time etc with help of
data dictionary.

 SQL is a very high level language:

o The users specify what to search for- not how the search is actually
done
o The algorithms are chosen automatically by the DBMS.
 For a given SQL query there may be many possible execution plans.
 Amongst all equivalent plans choose the one with lowest cost.
 Cost is estimated using statistical information from the database catalog.

Execution Plan:
By this execution plan multiple low level language query is generated.

Evaluation:
It is used to determine low cost query.
 2. Query optimization:
It is the process of selecting an efficient execution plan for evaluating
the query.
After parsing of the query, parsed query is passed to query optimizer,
which generates different execution plans to evaluate parsed query and
select the plan with least estimated cost.
Catalog manager helps optimizer to choose best plan to execute query
generating cost of each plan.

Query optimization is used for accessing the database in an efficient manner.

It is an art of obtaining desired information in a predictable, reliable and
timely manner. Formally defines query optimization as a process of
transforming a query into an equivalent form which can be evaluated more
efficiently. The essence of query optimization is to find an execution plan that
minimizes time needed to evaluate a query. To achieve this optimization
goal, we need to accomplish two main tasks. First one is to find out the best
plan and the second one is to reduce the time involved in executing the query
plan.

3. Implementing relational operators:

 It is procedural query language.
 It collect instance of relations as input and give
occurrence of relation as output.
 It has various operations.
Unary Relational Operations

 SELECT (symbol: σ)
 PROJECT (symbol: π)
 RENAME (symbol: ρ)
Relational Algebra Operations from Set theory

 UNION (υ)
 INTERSECTION ( ),
 DIFFERENCE (-)
 CARTESIAN PRODUCT ( x )

Binary Relational Operations

 JOIN
 DIVISION

Let’s study them in detail with solutions:

SELECT (σ)

The SELECT operation is used for selecting a subset of the tuples according to a
given selection condition. Sigma(σ)Symbol denotes it. It is used as an expression
to choose tuples which meet the selection condition. Select operator selects
tuples that satisfy a given predicate.

σp(r)

σ is the predicate

r stands for relation which is the name of the table

p is prepositional logic

Example 1

σ topic = "Database" (Tutorials)

Output – Selects tuples from Tutorials where topic = ‘Database’.

Projection(π)

The projection eliminates all attributes of the input relation but those mentioned
in the projection list. The projection method defines a relation that contains a
vertical subset of Relation.

This helps to extract the values of specified attributes to eliminates duplicate

values. (pi) symbol is used to choose attributes from a relation. This operator
helps you to keep specific columns from a relation and discards the other
columns.

Example of Projection:

Consider the following table

CustomerID CustomerName Status

1 Google Active
2 Amazon Active
3 Apple Inactive
4 Alibaba Active

Here, the projection of CustomerName and status will give

Π CustomerName, Status (Customers)

CustomerName Status
Google Active
Amazon Active
Apple Inactive
Alibaba Active

Rename (ρ)

Rename is a unary operation used for renaming attributes of a relation.

ρ (a/b)R will rename the attribute ‘b’ of relation by ‘a’. Here a is new attribute
name and b is old attribute name.

Eg: Rename the attribute id as studid in student table.

Ρ (studid/id) student

Union operation (υ)

UNION is symbolized by ∪ symbol. It includes all tuples that are in tables A or in

B. It also eliminates duplicate tuples. So, set A UNION set B would be expressed
as:

The result <- A ∪ B

For a union operation to be valid, the following conditions must hold –

 R and S must be the same number of attributes.

 Attribute domains need to be compatible.
 Duplicate tuples should be automatically removed.

Example

Consider the following tables.

Table A Table B
column 1 column 2 column 1 column 2
1 1 1 1
1 2 1 3
A ∪ B gives

Table A ∪ B
column 1 column 2
1 1
1 2
1 3

Set Difference (-)

– Symbol denotes it. The result of A – B, is a relation which includes all tuples
that are in A but not in B.

 The attribute name of A has to match with the attribute name in B.

 The two-operand relations A and B should be either compatible or Union
compatible.
 It should be defined relation consisting of the tuples that are in relation A,
but not in B.

Example

A-B
Table A – B
column 1 column 2
1 2
Intersection

An intersection is defined by the symbol ∩

A∩B

Defines a relation consisting of a set of all tuple that are in both A and B.
However, A and B must be union-compatible.

Visual
Definition of Intersection
Example:

A∩B
Table A ∩ B
column 1 column 2
1 1

Join Operations

Join operation is essentially a cartesian product followed by a selection criterion.

Join operation denoted by ⋈.

JOIN operation also allows joining variously related tuples from different
relations.

Types of JOIN:

Various forms of join operation are:

Inner Joins:

Outer join:

 Left Outer Join

  Right Outer Join
 Full Outer Join

Inner Join:

In an inner join, only those tuples that satisfy the matching criteria are included,
while the rest are excluded. Let’s study various types of Inner Joins:

For example:

A⋈ [Link] 2 = [Link] 2 (B)

A ⋈ [Link] 2 = [Link] 2 (B)
column 1 column 2
1
EQUI join is the most difficult operations to implement efficiently using SQL in
an RDBMS and one reason why RDBMS have essential performance problems.

OUTER JOIN

In an outer join, along with tuples that satisfy the matching criteria, we also
include some or all tuples that do not match the criteria.

Left Outer Join(A B)

In the left outer join, operation allows keeping all tuple in the left relation.
However, if there is no matching tuple is found in right relation, then the
attributes of right relation in the join result are filled with null values.

Consider the following 2 Tables

A
Num Square
2 4
3 9
4 16

B
Num Cube
2 8
3 18
5 75
A B
A⋈B
Num Square Cube
2 4 8
3 9 18
4 16 –

Right Outer Join: ( A B)

In the right outer join, operation allows keeping all tuple in the right relation.
However, if there is no matching tuple is found in the left relation, then the
attributes of the left relation in the join result are filled with null values.

A B
A⋈B
Num Cube Square
2 8 4
3 18 9
5 75 –
Full Outer Join: ( A B)

In a full outer join, all tuples from both relations are included in the result,
irrespective of the matching condition.

A B
A⋈B
Num Cube Square
2 4 8
3 9 18
4 16 –
5 – 75