• Query Translation
• Parsing SQL
• Expression Rewriting Rules
• Relational Algebra Laws
• Query Rewriting

❖ Query Translation

Query translation:   SQL statement text → RA expression

❖ Query Translation (cont)

Translation step:   SQL text → RA expression

Example:

SQL: select name from Students where id=7654321;
-- is translated to
RA:  Proj[name](Sel[id=7654321]Students)

Processes:  lexer/parser,  mapping rules,  rewriting rules.

Mapping from SQL to RA may include some optimisations, e.g.

select * from Students where id = 54321 and age > 50;
-- is translated to
Sel[age>50](Sel[id=54321]Students)
-- rather than ... because of index on id
Sel[id=54321&age>50](Students)

❖ Parsing SQL

Parsing task is similar to that for programming languages.

Language elements:

• keywords:   create,   select,   from,   where,   ...
• identifiers:   Students,   name,   id,   CourseCode,   ...
• operators:   +,   -,   =,   <,   >,   AND,   OR,   NOT,   IN,   ...
• constants:   'abc',   123,   3.1,   '01-jan-1970',   ...

PostgreSQL parser ...

• implemented via lex/yacc   (src/backend/parser)
• maps all identifiers to lower-case   (A-Z → a-z)
• needs to handle user-extendable operator set
• makes extensive use of catalog   (src/backend/catalog)

❖ Expression Rewriting Rules

Since RA is a well-defined formal system

• there exist many algebraic laws on RA expressions
• which can be used as a basis for expression rewriting
• in order to produce equivalent (more-efficient?) expressions

Expression transformation based on such rules can be used

• to simplify/improve SQL→RA mapping results
• to generate new plan variations to check in query optimisation

❖ Relational Algebra Laws

Commutative and Associative Laws:

• R ⨝ S  ↔  S ⨝ R,    (R ⨝ S) ⨝ T  ↔  R ⨝ (S ⨝ T)    (natural join)
• R ∪ S  ↔  S ∪ R,    (R ∪ S) ∪ T  ↔  R ∪ (S ∪ T)
• R ⨝_Cond S  ↔  S ⨝_Cond R    (theta join)
• σ_c ( σ_d (R))   ↔   σ_d ( σ_c (R))

Selection splitting (where c and d are conditions):

• σ_c∧d(R)   ↔   σ_c ( σ_d (R))
• σ_c∨d(R)   ↔   σ_c(R)  ∪  σ_d(R)

❖ Relational Algebra Laws (cont)

Selection pushing   ( σ_c(R ∪ S) and σ_c(R ∪ S) ):

• σ_c(R ∪ S)  ↔  σ_cR ∪ σ_cS,     σ_c(R ∩ S)  ↔  σ_cR ∩ σ_cS

Selection pushing with join ...

• σ_c (R ⨝ S)   ↔   σ_c(R)  ⨝  S    (if c   refers only to attributes from R )
• σ_c (R ⨝ S)   ↔   R  ⨝  σ_c(S)    (if c refers only to attributes from S )

If condition contains attributes from both R and S:

• σ_c′∧c″ (R ⨝ S)   ↔   σ_c′(R)  ⨝  σ_c″(S)
• c′ contains only R attributes, c″ contains only S attributes

❖ Relational Algebra Laws (cont)

Rewrite rules for projection ...

All but last projection can be ignored:

• π_L1 ( π_L2 ( ... π_Ln (R)))   →   π_L1 (R)

Projections can be pushed into joins:

• π_L (R  ⨝_c S)   ↔   π_L ( π_M(R)  ⨝_c  π_N(S) )

where

• M and N must contain all attributes needed for c
• M and N must contain all attributes used in L   (L ⊂ M∪N)

❖ Query Rewriting

Subqueries ⇒ convert to a join

Example:   (on schema Courses(id,code,...), Enrolments(cid,sid,...), Students(id,name,...)

select c.code, count(*)
from   Courses c
where  c.id in (select cid from Enrolments)
group  by c.code

becomes

select c.code, count(*)
from   Courses c join Enrolments e on c.id = e.cid
group  by c.code

❖ Query Rewriting (cont)

But not all subqueries can be converted to join, e.g.

select e.sid as student_id, e.cid as course_id
from   Enrolments e
where  e.sid = (select max(id) from Students)

has to be evaluated as

Val = max[id]Students

Res = π_(sid,cid)(σ_sid=ValEnrolments)

❖ Query Rewriting (cont)

In PostgreSQL, views are implemented via rewrite rules

• a reference to view in SQL expands to its definition in RA

Example:

create view COMP9315studes as
select stu,mark from Enrolments where course='COMP9315';
-- students who passed
select stu from COMP9315studes where mark >= 50;

is represented in RA by

COMP9315studes
  = Proj[stu,mark](Sel[course=COMP9315](Enrolments))
-- with query ...
Proj[stu](Sel[mark>=50](COMP9315studes))
-- becomes ...
Proj[stu](Sel[mark>=50](
  Proj[stu,mark](Sel[course=COMP9315](Enrolments))))
-- which could be rewritten as ...
Proj[stu](Sel[mark>=50 & course=COMP9315]Enrolments)