XQuery Query Processing in Relational Systems
Yingwen Chen · UWSpace (University of Waterloo) · 2004
Syntax Tree . . . . . . . . . . . . . . . . . . . 27 3.4 Relational Algebra Tree Construction . . . . . . . . . . . . . . . . . 28 3.4.1 Relational Operations . . . . . . . . . . . . . . . . . . . . . 29 3.4.2 Mapping SQL Templates to Relational Algebra Trees . . . . 34 3.5 SQL Query Generation . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.5.1 The Translation of Relational Operations . . . . . . . . . . 48 3.5.2 Optimization of the SQL Query Generation . . . . . . . . . 53 3.6 Physical Plan Translation . . . . . . . . . . . . . . . . . . . . . . . 61 4 Optimization of the XQuery-to-SQL Translation 62 4.1 SQL Translation Templates Optimization . . . . . . . . . . . . . . . 62 4.1.1 The Simplified Templates for XQuery Basic Operations . . 63 4.1.2 The Simplified Templates for the FOR Expression . . . . . 63 4.1.3 The Simplified Templates for the WHERE Expressions . . . 64 4.2 Simplified Translation for Sequences of Basic Operations . . . . . . 67 4.3 Merge-join Approach to FLWR Expressions . . . . . . . . . . . . . 69 4.3.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 4.3.2 The Nested-FOR Pattern . . . . . . . . . . . . . . . . . . . 73 4.3.3 The Multi-FOR Pattern . . . . . . . . . . . . . . . . . . . . 92 4.4 XQuery Rewriting Rules . . . . . . . . . . . . . . . . . . . . . . . . 98 4.4.1 Rewriting Rules for Nested-FOR Pattern . . . . . . . . . . . 98 4.4.2 Rewriting Rules for Multi-FOR Pattern . . . . . . . . . . . . 102 4.4.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 4.5 The XQuery Optimizer . . . . . . . . . . . . . . . . . . . . . . . . . 106 viii 5 Experiments 108 5.1 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 5.1.1 Methodology . . . . . . . . . . . . . . . . . . . . . ...