org.openanzo.glitter.query.rewriter
Class NormalFormRewriter

java.lang.Object
  org.openanzo.glitter.query.rewriter.NormalFormRewriter

All Implemented Interfaces:

TreeRewriter

public class NormalFormRewriter
extends java.lang.Object
implements TreeRewriter

 From the Semantics and Complexity of SPARQL paper, some equivalences:
 
 2.3.1
  (1) P1 AND P2 === P2 AND P1 ; P1 UNION P2 === P2 UNION P1
  (2) P1 AND (P2 UNION P3) === (P1 AND P2) UNION (P1 AND P3)
        similarly: AND(P1, P2, UNION(P3, P4)) === UNION(AND(P1, P2, P3), AND(P1, P2, P4))
        similarly: AND(P1, UNION(P2, P3, ..., Pk) === UNION(AND(P1, P2), AND(P1, P3), ..., AND(P1, Pk))
        similarly: AND(P1, UNION(P2, P3), UNION(P4, P5)) === 
                UNION(AND(P1, P2, P4), AND(P1, P2, P5), AND(P1, P3, P4), AND(P1, P3, P5))
      similarly: AND(P1, P2, ..., Pi, UNION(Q11, Q12, ..., Q1j), UNION(Q21, Q22, ..., Q2k), ..., UNION(Qm1, Qm2, ..., Qmn))
        ===  UNION(For Each (x1, x2, ..., xm) in CartesianProduct(Q11...Q1j, Q21...Q2k, Qm1...Qmn) AND(P1, P2, ..., Pi, x1, x2, ..., xm)) 
  (3) P1 OPT (P2 UNION P3) === (P1 OPT P2) UNION (P1 OPT P3)
      Similarly:
        OPT(P1, UNION(P2, P3, ..., Pk)) ===
                UNION(OPT(P1, P2), OPT(P1, P3), ..., OPT(P1, Pk)) 
  
  We also take advantage of associativity properties:
    P1 UNION (P2 UNION P3) = (P1 UNION P2) UNION P3 = (for that matter)
      UNION(P1, P2, P3) if naryUnion is allowed.
      
 TODO there's a bit more of a normal form in Theorem 6 (labelled (4)) in the
 paper; we may want to investigate that.
 
 TODO @@ Do these identities hold with FILTERs having Group scope?
 
 

Author:

Lee

Constructor Summary

NormalFormRewriter(boolean allowNaryUnion)
Constructor.

Method Summary

TreeNode

rewriteTreeNode(TreeNode node) Rewrites the given node from a SPARQL abstract syntax tree.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

NormalFormRewriter

public NormalFormRewriter(boolean allowNaryUnion)

Constructor.

Parameters:

allowNaryUnion -

Method Detail

rewriteTreeNode

public TreeNode rewriteTreeNode(TreeNode node)

Description copied from interface: TreeRewriter

Rewrites the given node from a SPARQL abstract syntax tree.

Specified by:

rewriteTreeNode in interface TreeRewriter

Parameters:

node - the node in question

Returns:

A tree node to replace the passed in tree node. Returning node leaves this spot in the AST unchanged. Returning null removes this node from the tree. (Note that it is possible that removing the node will leave the tree in an invalid state. Behavior in this case is undefined.)