Exercise 4: Parsing SQL

Simple SQL Grammar from DSCB 16.1.2

<Query> ::= SELECT <SelList> FROM <FromList> WHERE <Condition>

<SelList> ::= <Attribute> , <SelList>
<SelList> ::= <Attribute> 

<FromList> ::= <Relation> , <FromList>
<FromList> ::= <Relation>

<Condition> ::= <Condition> AND <Condition>
<Condition> ::= <Attribute> IN ( <Query> )
<Condition> ::= <Attribute> =  <Attribute>
<Condition> ::= <Attribute> LIKE  <Pattern>

DSCB Ex. 16.1.1.

Add to or modify the rules for <Query> to include simple versions of the following features of SQL select-from-where expressions:

a) The ability to produce a set with the DISTINCT keyword.

b) A GROUP BY clause and a HAVING clause

c) Sorted output with the ORDER BY clause

d) A query with no where-clause

DSCB Ex 16.1.2.

Add to the rules for <Condition> to allow the following features of SQL conditionals:

a) Logical operators OR and NOT

b) Comparisons other thab =.

c) Parenthesized conditions.

d) EXISTS expressions.

DSCB Ex 16.1.3.

Using the simple SQL grammar exhibited in this section, give parse trees for the following queries about relations R(a,b) and S(b,c):

a) SELECT a, c FROM R, S WHERE R.b=S.b;

b) SELECT a FROM R WHERE b IN (SELECT a FROM R, S WHERE R.b = S.b);