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>