Syntax translation between SELECT expressions and LET assignment

LeeF asked (a couple of week ago now) about the equivalence of SELECT 
expressions and LET (assignment) as syntax forms.  Here is a description 
of translations from SELECT expr to LET and from LET to SELECT expr.

 Andy


== SELECT to LET

We are translating

SELECT (?a+1 AS ?b), ?c, (?d+1 AS ?e)
{
   pattern
}

=>
This follows the algebra translation but generates synatx, not algebra 
expressions.

----

Step SL-1:

Split into two lists, expressions and projections.

[] for lists.

AS-Expressions [(?b, ?a+1) , (?e, ?d+1)]
Projection: [?b, ?c, ?e]

-----


To get a LET apply the following:

Step SL-2:
Generate the projection-only SELECT, from the original projected 
variables and the AS variables.

"SELECT ?b ?c ?e"

Step SL-3:

Generate the SELECT WHERE clause, up to the "}"

"""
SELECT ?b, ?c, ?e
{
    pattern
"""

Step SL-4: Insert LET

For each AS-expression (var, expr)
  Generate "LET(?var := expr)"

Step SL-5:
Generate "}"

so that gives:

"""
SELECT ?b, ?c, ?e
{
   pattern
   LET (?b := ?a+1)
   LET (?e := ?d+1)
}
"""

The order of the projection is preserved.

== LET to SELECT (part 1)

We first look at a simple case:

{
   pattern
   LET (?b := ?a+1)
   LET (?e := ?d+1)
}


Step LS-1-1:

Split into:
  The WHERE part: pattern
  Any assignments: (?b, ?a+1) (?e, ?d+1)

Determine variables used in pattern (same as SELECT * { Pattern })
We use VAR(pattern) here for that.

Step LS-1-2:

Generate "SELECT VAR(pattern)"

Step LS-1-3:
For each assignment
   Generate "(" expr "AS" var ")"

SELECT VAR(pattern) (?a+1 AS ?b) (?d+1 AS ?e)

Step LS-1-4:
Generate { pattern }

giving
"""
SELECT VAR(pattern) (?a+1 AS ?b) (?d+1 AS ?e)
{ pattern }

== LET to SELECT (part 2)

The general case is:

{
   pattern1
   LET (?b := ?a+1)
   pattern2
   LET (?e := ?d+1)
   pattern3
}

Informally, this will become:

{
   {
     {
       pattern1
       LET (?b := ?a+1)
     }
     pattern2
     LET (?e := ?d+1)
   }
   pattern3
}

where the part 1 steps applied at each pattern boundary.

Algorithmically:

Set P = empty pattern
Set X = [], the empty list.

-- First LET:

At LET (?b := ?a+1) do the following:

Append VARS(pattern1) to X
Generate a SELECT clause with the projection variables from X and the 
assignment written as AS
Generate pattern1, in {}

"SELECT X1 (?a+1 AS ?b)
{ pattern1 }
"
where X1 is the value of list X at this point.

Assign this to P
Append "?b" to X

-- Second LET:
At LET (?e := ?d+1)  do the following:

Append VARS(pattern2) to X
Generate a SELECT clause with the projection variables from X and the 
assignment written as AS
Start {
Generate P as a nested SELECT
Generate pattern2
End }

"""
SELECT X2 (?d+1 AS ?e)
{
   { SELECT X1 (?a+1 AS ?b)
   { pattern1 }
   }
   pattern2
}
"""
where X2 is the value of X at this point.

Assign this to P
Append "?e" to X

-- End of {}

Append VARS(pattern3) to X
Generate a SELECT clause with the projection variables from X and the 
assignment written as AS
Start {
Generate P as a nested SELECT
Generate pattern3
End }

"""
SELECT X3
{
   { SELECT X2 (?d+1 AS ?e)
     {
       { SELECT X1 (?a+1 AS ?b)
        {
           pattern1
        }
       }
      pattern2
     }
   }
   pattern3
}
"""

Notes:

1 --  The "First LET" step can be the same as the rest by generating a 
subselect on the empty pattern because { SELECT * {} } is the join identity.

2 -- pattern2 can use ?b; pattern3 can use ?b and ?e

3 -- LETs end BGPs.  Scope is maintained by using subSELECTs

Received on Sunday, 29 November 2009 21:38:19 UTC