Logical Algebra

 

Given an XQuery input, Timber first translate it into a logical plan that follows the grammar below. Detail information about the logical algebra and query translation from XQuery to logical plan can be found here.  

 

// node ids for pattern and constrct nodes are LCLs (they are referred as NREs in physical algebra)

// node ids for process nodes are independent of LCLs,

// hence there might be a pattern node with LCL=2 and a process node with id = 2

// they shouldn't be confused.

 

//tree

 

<tree> := <tree id> <node number> <tree root id> [<tree marker> ] <tree node list>

<tree node list> := (<node id>  <parent id> /n)*

<tree marker> := PATTERN_TREE | CONSTRUCT_TREE | PROCESS_TREE | MLCA_TREE

//Pattern Tree node

 

<pattern tree node>  := <document_ptn> | <regular_ptn> | <reference_ptn> | <value join pattern tree node> | <mlca-root node>

 

<document pattern tree node> := <node id> DOCUMENT <filename> <ANCS | PARENT>  <- | ? | * | +>

 

<regular_ptn> := <node id>  <ELEMENT | ATTRIBUTE>  <filename>  <tagname>  <operator> <value> <ANCS | PARENT>  <- | ? | * | +>

<operator> := EQN,NEN,LTN,LEN,GTN,GEN,EQS,NES,LTS,LES,GTS,GES,CONTAINS,CONTAINEDBY,STARTSWITH,NULL,ID_EQ,ID_NEQ

 

<reference pattern tree node> := <node id> REFERENCE <Reference LCL> <ANCS | PARENT>  <- | ? | * | +>

 

<value join pattern tree node> := <node id> VALUEJOIN <ANY|ONE> <left node LCL> <operator> <right node LCL>

<value join pattern tree node> := <node id> CARTESIAN

 

<mlca-root node> := <node id> MLCA-ROOT

 

//Construct Tree node

 

<construct pattern tree node> :=  <c_element pattern tree node> | <c_reference pattern tree node> | <c_attribute pattern tree node>

<c_element pattern tree node> := <node id> C_ELEMENT <tagname>

<c_attribute pattern tree node> := <node id> C_ATTRIBUTE <tagname> <Reference LCL>

<c_reference pattern tree node> := <node id> C_REFERENCE <Reference LCL> <TEXT|SUBTREE|NODE|OUTER> 

 

//Process Tree Node

 

<process tree node> := <select node> | <join node> | <project node>

                | <duplicate elimination node> | <aggregate function node>

                | <filter node> | <orfilter node> | <sort node> | <construct node> | <set node>

                | <delete node> | <update node> | <insert-file node> | <insert-element node>

                ...

 

<set node> := <node id> UNION | INTERSECTION | DIFFERENCE

<select node> := <node id> SELECT <pattern tree id>

<join node> := <node id> JOIN <pattern tree id>

<construct node> := <node id> CONSTRUCT <pattern tree id>

<project node> := <node id> PROJECT  <number of nodes to project>  <projection list using LCLs>

<duplicate elimination node> := <node id> DUPLICATE_ELIMINATION  <ID | TEXT> <LCL>

<filter node> := <node id> FILTER <reference node LCL> <operator> <CONST | REF> <value | LCL> <EVERY | SOME | EXACTLYONE>

<orfilter node> := <node id> ORFILTER <number of filters in OR> (<reference node LCL> <operator> <CONST | REF> <value | LCL> <EVERY | SOME | EXACTLYONE>)+

<sort node> :=  <node id> SORT <number of nodes to sort>  [<LCL> <KEY | VALUE> <ASCENDING | DESCENDING> <LEAST | GREATEST>]+

<aggregate function node> := <node id> AGGREGATE_FUNCTION <COUNT | MIN | MAX | SUM | AVERAGE> <reference node LCL> <new node id> <new node tagname>

<delete node> := <node id> DELETE <LCL> <TEXT | SUBTREE>

<update node> := <node id> UPDATE <LCL> <CONST | REF> <value | LCL>

<insert-file node> := <node id> INSERT_FILE <LCL> <filename>

<insert-element node> := <node id> INSERT_ELEMENT <LCL> <tagname> <CONST | REF> <value | LCL> <number of attributes>  [<tagname> <CONST | REF> <value | LCL>]+

<insert-attribute node> := <node id> INSERT_ATTRIBUTE <LCL> <tagname> <CONST | REF> <value | LCL>

<mlca node> := <node id> MLCA <pattern tree id> <number of nodes for mlca> <mlca list using LCLs>

 

 

//Query

 

<Query> :=

<Number of Pattern/Construct tree nodes>

<Number of Pattern/Construct trees>

<Number of Process tree nodes>

<List of Pattern/Construct tree nodes>

<List of Pattern/Construct trees>

<List of process tree nodes>

<Process tree structure>