CS计算机代考程序代写 SQL 2021/4/28 Query Translation

2021/4/28 Query Translation
Query Translation
Query Translation
Parsing SQL
Expression Rewriting Rules Relational Algebra Laws Query Rewriting
>>
COMP9315 21T1 ♢ Query Translation ♢ [0/10]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/qry-translation/slides.html 1/12

2021/4/28 Query Translation
∧ >>
❖ Query Translation
Querytranslation: SQLstatementtext→RAexpression
COMP9315 21T1 ♢ Query Translation ♢ [1/10]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/qry-translation/slides.html 2/12

2021/4/28 Query Translation
❖ Query Translation (cont)
Translationstep: SQLtext→RAexpression 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)
COMP9315 21T1 ♢ Query Translation ♢ [2/10]
<< ∧ >>
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/qry-translation/slides.html 3/12

2021/4/28 Query Translation
❖ Parsing SQL
Parsing task is similar to that for programming languages. Language elements:
keywords: create, select, from, where, … identiers: Students, name, id, CourseCode, … operators: +, -, =, <, >, AND, OR, NOT, IN, … constants: ‘abc’, 123, 3.1, ’01-jan-1970′, …
PostgreSQL parser …
implementedvialex/yacc (src/backend/parser) mapsallidentierstolower-case (A-Z→a-z)
needs to handle user-extendable operator set makesextensiveuseofcatalog (src/backend/catalog)
COMP9315 21T1 ♢ Query Translation ♢ [3/10]
<< ∧ >>
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/qry-translation/slides.html 4/12

2021/4/28 Query Translation
❖ Expression Rewriting Rules Since RA is a well-dened 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-efcient?) 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
COMP9315 21T1 ♢ Query Translation ♢ [4/10]
<< ∧ >>
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/qry-translation/slides.html 5/12

2021/4/28 Query Translation
❖ 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)
COMP9315 21T1 ♢ Query Translation ♢ [5/10]
<< ∧ >>
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/qry-translation/slides.html 6/12

2021/4/28 Query Translation
❖ Relational Algebra Laws (cont)
Selectionpushing (σ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
COMP9315 21T1 ♢ Query Translation ♢ [6/10]
<< ∧ >>
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/qry-translation/slides.html 7/12

2021/4/28 Query Translation
❖ 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 ⨝cS) ↔ πL(πM(R) ⨝c πN(S))
where
M and N must contain all attributes needed for c
MandNmustcontainallattributesusedinL (L⊂ M∪N)
COMP9315 21T1 ♢ Query Translation ♢ [7/10]
<< ∧ >>
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/qry-translation/slides.html 8/12

2021/4/28 Query Translation
❖ Query Rewriting Subqueries ⇒ convert to a join
Example: (onschemaCourses(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
COMP9315 21T1 ♢ Query Translation ♢ [8/10]
<< ∧ >>
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/qry-translation/slides.html 9/12

2021/4/28 Query Translation
<< ∧ >>
❖ 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)
COMP9315 21T1 ♢ Query Translation ♢ [9/10]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/qry-translation/slides.html 10/12

2021/4/28 Query Translation
<< ∧ ❖ Query Rewriting (cont) In PostgreSQL, views are implemented via rewrite rules a reference to view in SQL expands to its denition 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)
COMP9315 21T1 ♢ Query Translation ♢ [10/10]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/qry-translation/slides.html 11/12

2021/4/28 Query Translation
Produced: 5 Apr 2021
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/qry-translation/slides.html 12/12