Jes Ús Camacho-Rodríguez

Dario Colazzo
email: dario.colazzo@dauphine.fr.

Ioana Manolescu
email: ioana.manolescu@inria.fr.

Jesús Camacho-Rodríguez
email: jesus.camachorodriguez@inria.fr

PAXQuery: Efficient Parallel Processing of Complex XQuery

Keywords: XQuery processing, XQuery parallelization, XML data management

Increasing volumes of data are being produced and exchanged over the Web, in particular in tree-structured formats such as XML or JSON. This leads to a need of highly scalable algorithms and tools for processing such data, capable to take advantage of massively parallel processing platforms. This work considers the problem of efficiently parallelizing the execution of complex nested data processing, expressed in XQuery. We provide novel algorithms showing how to translate such queries into PACT, a recent framework generalizing MapReduce in particular by supporting many-input tasks. We present the first formal translation of complex XQuery algebraic expressions into PACT plans, and demonstrate experimentally the efficiency and scalability of our approach.

INTRODUCTION

To scale data processing up to very large data volumes, platforms are increasingly relying on implicit parallel frameworks [START_REF] Battré | Nephele/PACTs: a programming model and execution framework for web-scale analytical processing[END_REF], [START_REF] Dean | MapReduce: Simplified Data Processing on Large Clusters[END_REF], [START_REF] Zaharia | Resilient distributed datasets: a fault-tolerant abstraction for in-memory cluster computing[END_REF]. The main advantage of using such frameworks is that processing is distributed across many sites without the application having to explicitly handle data fragmentation, fragment placement etc.

By far the most widely adopted framework, MapReduce [START_REF] Dean | MapReduce: Simplified Data Processing on Large Clusters[END_REF] features a very simple processing model consisting of two operations, Map which distributes processing over sets of (key, value) pairs, and Reduce which processes the sets of results computed by Map for each distinct key. However, the simplicity of this processing model makes complex computations hard to express. Therefore, high-level data analytics languages such as Pig [START_REF] Olston | Pig Latin: A Not-So-Foreign Language for Data Processing[END_REF], Hive [START_REF] Thusoo | Hive -a PB scale data warehouse using Hadoop[END_REF] or Jaql [START_REF] Beyer | Jaql: A Scripting Language for Large Scale Semistructured Data Analysis[END_REF], that are translated (compiled) into MapReduce programs, have emerged. Still, complex processing translates to large and complex MapReduce programs, which may miss parallelization opportunities and thus execute inefficiently.

Recently, more powerful abstractions for implicitly parallel data processing have emerged, such as the Resilient Distributed Datasets [START_REF] Zaharia | Resilient distributed datasets: a fault-tolerant abstraction for in-memory cluster computing[END_REF] or Parallelization Contracts [START_REF] Battré | Nephele/PACTs: a programming model and execution framework for web-scale analytical processing[END_REF] (PACT, in short). In particular, PACT generalizes MapReduce by (i) manipulating records with any number of fields, instead of (key, value) pairs, (ii) enabling the definition of custom parallel operators by means of second-order functions, and (iii) allowing one parallel operator to receive as input the outputs of several other such operators. The PACT model lies at the core of the Stratosphere platform [START_REF]Stratosphere Platform[END_REF], which can read data from and write data to the Hadoop Distributed File System (HDFS) [START_REF]Apache Hadoop[END_REF].

In this work, we are interested in the implicit parallelization of XQuery [START_REF] Robie | XQuery 3.0: An XML Query Language, W3C Proposed Recommendation[END_REF], the W3C's standard query language for XML data. The language has been recently enhanced with features geared towards XML analytics [START_REF] Eisenberg | XQuery 3.0 is nearing completion[END_REF], such as explicit grouping. Given a very large collection of documents, evaluating an XQuery query that navigates over these documents and also joins results from different documents raises performance challenges, which may be addressed by parallelism. In contrast with prior work [START_REF] Bidoit | Processing XML queries and updates on map/reduce clusters (demo)[END_REF], [START_REF] Choi | HadoopXML: A suite for parallel processing of massive XML data with multiple twig pattern queries (demo)[END_REF], [START_REF] Khatchadourian | Having a ChuQL at XML on the cloud[END_REF], we are interested in implicit parallelism, which does not require the application (or the user) to partition the XML input nor the query across many nodes.

The contributions of this work are the following:

1) We present a novel methodology for massively parallel evaluation of XQuery, based on PACT and previous research in algebraic XQuery optimization. 2) We provide a translation algorithm from the algebraic operators required by a large powerful fragment of XQuery into operators of the PACT parallel framework. This enables parallel XQuery evaluation without requiring data or query partitioning effort from the application.

Toward this goal, we first translate XML data instances (trees with identity) into PACT nested records, to ensure XML query results are returned after the PACT manipulations of nested records. Second, we bridge the gap between the XQuery algebra, and in particular, many flavors of joins [START_REF] Deutsch | The NEXT Logical Framework for XQuery[END_REF], [START_REF] Manolescu | XML Tuple Algebra[END_REF], [START_REF] May | Strategies for query unnesting in XML databases[END_REF] going beyond simple conjunctive equality joins, and PACT operators which (like MapReduce) are fundamentally designed around the equality of key values in their inputs.

Our translation of complex joins into PACT is of interest beyond the XQuery context, as it may enable compiling other high-level languages [START_REF] Beyer | Jaql: A Scripting Language for Large Scale Semistructured Data Analysis[END_REF], [START_REF] Olston | Pig Latin: A Not-So-Foreign Language for Data Processing[END_REF], [START_REF] Thusoo | Hive -a PB scale data warehouse using Hadoop[END_REF] into PACT to take advantage of its efficiency. 3) We fully implemented our translation technique into our PAXQuery platform. We present experiments demonstrating that our translation approach (i) effectively parallelizes XQuery evaluation taking advantage of the PACT framework, and (ii) scales well beyond alternative approaches for implicitly parallel XQuery evaluation, in particular as soon as joins across documents are present in the workload. The remainder of the paper is organized as follows. Section 2 introduces the problem by means of an example. Section 3 provides background on XML, XQuery, and the PACT model. Section 4 overviews our complete solution and characterizes the XQuery algebras targeted by our translation. Section 5 presents the translation algorithm from XQuery plans to PACT, at the core of this work. Section 6 describes our experimental evaluation. Section 7 discusses related work and then we conclude.

MOTIVATION

Example 1. Consider the following XQuery that extracts the name of users, and the items of their auctions (if any): let $pc := collection( ' people ' ), $cc := collection( ' c l o s e d a u c t i o n s ' ) for $p in $pc/site/people/person, $i in $p/@id let $n := $p/name let $r := for $c in $cc//closed_auction, $b in $c/buyer/@person, $s in $c/seller/@person let $a := $c/itemref where $i = $b or $i = $s return $a return <res>{$n,$r}</res> ⋄ We would like to evaluate this query over two large collections of documents (concerning people, respectively closed auctions) stored in HDFS. Evaluating the query in a massively parallel fashion as previously proposed, e.g., in [START_REF] Khatchadourian | Having a ChuQL at XML on the cloud[END_REF] requires the programmer to explicitly insert parallelization primitives in the query, which requires time and advanced expertise. Alternatively, one could partition the XML data, as in [START_REF] Bidoit | Processing XML queries and updates on map/reduce clusters (demo)[END_REF], [START_REF] Choi | HadoopXML: A suite for parallel processing of massive XML data with multiple twig pattern queries (demo)[END_REF], and run the query as such. This also requires human input (potentially different for each query); moreover, for complex XQuery queries like the one in Example 1, it also requires manual decomposition of the query into (i) "embarrassingly parallel" subqueries which can be directly run in parallel over many documents, and (ii) a "recomposition" query that applies the remaining query operations.

In contrast, given this query, PAXQuery generates in a fully automated fashion the PACT program shown in Figure 1. We outline here its functioning while on purpose omitting details, which will be introduced later on. The xmlscan('people') and xmlscan('closed auctions') operators scan (in parallel) the respective collections and transform each document into a record. Next, the map operators navigate in parallel within the records thus obtained, following the query's XPath expressions, and bind the query variables. The next operators in the PACT plan (cogroup) go beyond MapReduce. In a nutshell, a cogroup can be seen as a reduce operator on multiple inputs: it groups together records from all inputs sharing the same key value, and then it applies a user-defined function on each group. In this example, the functions are actually quite complex (we explain them in Section 5). The difficulty they have to solve is to correctly express (i) the disjunction in the where clause of the query, and (ii) the outerjoin semantics frequent in XQuery: in this example, a <res> element must be output even for people with no auctions. The output of both cogroup operators is received by the reduce, which builds join results between people and closed auctions, while the last xmlstore builds and returns XML results.

This approach enables us to take advantage of the Stratosphere platform [START_REF]Stratosphere Platform[END_REF] in order to automatically parallelize complex XML processing, expressed in a rich dialect of XQuery. In contrast, state-of-the-art solutions require partitioning, among nodes and by hand, the query and/or the data. Moreover, using PACT gives PAXQuery a performance advantage over MapReduce-based systems, because PACT's more expressive massively parallel operators allow more efficient query implementations.

BACKGROUND

In the following, we provide background on the XML data model and XQuery dialect we target (Section 3.1), and the PACT programming model used by Stratosphere (Section 3.2).

XML and XQuery fragment

XML data. We view XML data as a forest of ordered, nodelabeled, unranked trees, as outlined by the simple grammar:

Tree d ::= si | li[f ] Forest f ::= () | f,f | d
A tree d is either a text node (s i ), or an element node having the label l i and a forest of children; in accordance with the W3C's XML data model, each node is endowed with a unique identity, which we materialize through the i index. A forest f is a sequence of XML trees; () denotes the empty forest. For the sake of presentation we omitted attributes in our grammar. XQuery dialect. We consider a representative subset of the XQuery 3.0 language [START_REF] Robie | XQuery 3.0: An XML Query Language, W3C Proposed Recommendation[END_REF]. Our goal was to cover (i) the main navigating features of XQuery, and (ii) key constructs to express analytical style queries, e.g., aggregation, explicit grouping, or rich comparison predicates. However, extensions to support other XQuery constructs, e.g., if or switch expressions, can be integrated into our proposal in a straightforward manner. The full presentation of our XQuery dialect, including the grammar, can be found in Appendix A. Figure 2 provides three sample queries. A path starts from the root of each document in a collection found at URI Uri, or from the root of one document at URI Uri, or from the bindings of a previously introduced variable. The path expression dialect Path belongs to the XPath {/,//,[]} language [START_REF] Miklau | Containment and equivalence for an XPath fragment[END_REF]. We support two different types of comparators in predicates: (ValCmp) to compare atomic values, and (NodeCmp) to compare nodes by their identity. Finally, the group by clause groups tuples based on variable values.

In Figure 2, queries Q 1 and Q 2 use only one collection of documents while query Q 3 joins two collections. Further, Q 2 and Q 3 construct new XML elements while Q 1 returns the result of an aggregation over nodes from the input documents.

PACT framework

The PACT model [START_REF] Battré | Nephele/PACTs: a programming model and execution framework for web-scale analytical processing[END_REF] is a generalization of MapReduce, based on the concept of parallel data processing operators. PACT plans are DAGs of implicit parallel operators, that are optimized and translated into explicit parallel data flows by Stratosphere.

We introduce below the PACT data model and formalize the semantics of its operators. Data model. PACT plans manipulate records of the form:

r = ((f 1 , f 2 , . . . , f n ), (i 1 , i 2 , . . . , i k )) where 1 ≤ k ≤ n and: • (f 1 , f 2 , . . . , f n ) is an ordered sequence of fields f i .
In turn, a field f i is either an atomic value (string) or an ordered sequence (r ′ 1 , . . . , r ′ m ) of records. • (i 1 , i 2 , . . . , i k ) is an ordered, possibly empty, sequence of record positions in [1 . . . n] indicating the key fields for the record. Each of the key fields must be an atomic value. The key of a record r is the concatenation of all the key fields f i1 , f i2 , . . . , f i k . We denote by r[i] and r.key the field i and the key of record r, respectively. A ⊥-record is a record whose fields consist of null (⊥) values. Finally, R denotes the infinite domain of records. Path indexes are needed to describe navigation through records. A path index pi obeys the grammar pi := j.pi | ǫ, with j ≥ 0. Navigation through r along a path index j.pi first selects r[j]. If pi is empty (ǫ), then we are at the target field. Otherwise, if r[j] is a list of records (the field at position j is nested), pi navigation is performed on each record. Data sources and sinks are, respectively, the starting and terminal nodes of a PACT plan. The input data is stored in files; the function parameterizing data source operators specifies how to structure the data into records. In turn, data is output into files, with the destination and format similarly controlled by an output function. Semantics. Operators are data processing nodes in a PACT plan. Each operator manipulates bags of records; we write {{r 1 , r 2 , . . . , r n }} to indicate a bag of n records. From now on, for simplicity, we will call a PACT operator simply a PACT, whenever this does not cause confusion. As Figure 3 shows, a PACT consists of (i) a parallelization contract, (ii) a user function (UF in short) and (iii) optional annotations and compiler hints characterizing the UF behaviour. We describe these next.

1) Parallelization contract. A PACT can have k ≥ 1 inputs, each of which is a finite bag of records. The contract determines how input records are organized into groups.

2) User function. The UF is executed independently over each bag of records created by the parallelization contract, therefore these executions can take place in parallel. For each input bag of records, the UF returns a bag of records. 3) Annotations and/or compiler hints may be used to enable optimizations (with no impact on the semantics), thus we do not discuss them further. The semantics of the PACT op given as input k bags of records I 1 , . . . , I k , with I i ⊂ R, 1 ≤ i ≤ k, and having the parallelization contract c and the user function f is:

op(I 1 , . . . , I k ) = s∈c(I1,...,I k ) f (s)
In the above, c builds bags of records by grouping the input records belonging to bags I 1 , . . . , I k ; f is invoked on each bag produced by c, and the resulting bags are unioned. Predefined contracts. Although the PACT model allows creating custom parallelization contracts, a set of them for the most common cases is built-in:

• Map has a single input, and builds a singleton for each input record. Formally, given the bag I 1 ⊂ R of records, Map is defined as:

c mp (I 1 ) = {{{r} | r ∈ I 1 }}
• Reduce also has a single input and groups together all records that share the same key. Given a bag of input records I 1 : c rd (I 1 ) = {s = {{r 1 , r 2 , . . . , r m }} | r 1 , r 2 , . . . , r m ∈ I 1 and r 1 .key = r 2 .key = . . . = r m .key and ∃r ′ ∈ I \ s such that (r ′ .key = r 1 .key)} • Cross builds the cartesian product of two inputs.

• Match builds all pairs of records from its two inputs, which share the same key. Thus, given I 1 , I

OUTLINE

Our approach for implicit parallel XQuery evaluation is to translate XQuery into PACT plans as depicted in Figure 4.

The central vertical stack traces the query translation steps from the top to the bottom, while at the right of each step we show the data models manipulated by that step. First, the XQuery query is represented as an algebraic expression, on which multiple optimizations can be applied. XQuery translation into different algebra formalisms and the subsequent optimization of resulting expressions have been extensively studied [START_REF] Beeri | SAL: An Algebra for Semistructured Data and XML[END_REF], [START_REF] Boncz | MonetDB/XQuery: a fast XQuery processor powered by a relational engine[END_REF], [START_REF] Re | A Complete and Efficient Algebraic Compiler for XQuery[END_REF], [START_REF] Zhang | Honey, I shrunk the XQuery!: an XML algebra optimization approach[END_REF]. In Section 4.1, we characterize the class of XML algebras over which our translation technique can be applied, while we present the nestedtuple data model and algebra used by our work in Section 4.2.

Second, the XQuery logical expression is translated into a PACT plan; we explain this step in detail in Section 5.

Finally, the Stratosphere platform receives the PACT plan, optimizes it, and turns it into a data flow that is evaluated in parallel; these steps are explained in [START_REF] Battré | Nephele/PACTs: a programming model and execution framework for web-scale analytical processing[END_REF].

Assumptions on the XQuery algebra

Numerous logical algebras have been proposed for XQuery [START_REF] Beeri | SAL: An Algebra for Semistructured Data and XML[END_REF], [START_REF] Deutsch | The NEXT Logical Framework for XQuery[END_REF], [START_REF] Manolescu | XML Tuple Algebra[END_REF], [START_REF] Re | A Complete and Efficient Algebraic Compiler for XQuery[END_REF]. While the language has a functional flavor, most algebras decompose the processing of a query into operators, such as: navigation (or tree pattern matching), which given a path (or tree pattern) query, extracts from a document tuples of nodes matching it; selection; projection; join etc.

A significant source of XQuery complexity comes from nesting: an XQuery expression can be nested in almost any position within another. In particular, nested queries challenge the optimizer, as straightforward translation into nested plans leads to very poor performance. For instance, in Figure 2, Q 3 contains a nested subquery for $t ... return $t (shown indented in the figure); let us call it Q 4 and write Q 3 = e(Q 4 ). A naïve algebraic expression of such a query would evaluate Q 4 once per result of e in order to compute Q 3 results, which is typically inefficient.

Efficient optimization techniques translate nested XQuery into unnested plans relying on joining and grouping [START_REF] Deutsch | The NEXT Logical Framework for XQuery[END_REF], [START_REF] Manolescu | XML Tuple Algebra[END_REF], [START_REF] May | Strategies for query unnesting in XML databases[END_REF]. Thus, a smarter method to represent such query is to connect the sub-plans of Q 4 and e with a join in the plan of Q 3 ; the join condition in this example is $b=$i. Depending on the query shape, such decorrelating joins may be nested and/or outer.

Our goal is to complement existing engines, which translate from XQuery to an internal algebra, by an efficient compilation of this algebra into an implicit parallel framework such as PACT. This enables plugging a highly parallel back-end to an XQuery engine to improve its scalability. Accordingly, we aim to adapt to any XML query algebra satisfying the following two assumptions:

• The algebra is tuple-oriented (potentially using nested tuples). • The algebra is rich enough to support decorrelated (unnested) plans even for nested XQuery; in particular we consider that the query plan has been unnested before we start translating it into PACT. Three observations are in order here. First, to express complex queries without nesting, the algebra may include any type of joins (conjunctive/disjunctive, value or identity-based, possibly nested, possibly outer), as well as grouping; accordingly, we must be able to translate all such operators into PACT.

Second, a tuple-based algebra for XQuery provides border operators for (i) creating tuples from XML trees, in leaf operators of the algebraic plan; (ii) constructing XML trees out of tuples, at the top of the algebraic plan, so that XML results can be returned.

Finally, we require no optimization but unnesting [START_REF] May | Strategies for query unnesting in XML databases[END_REF] to be applied on the XML algebraic plan before translating it to PACT; however, any optimization may be applied before (and orthogonal to) our translation.

Algebra and data model

In the sequel, we present our work based on the algebra in [START_REF] Manolescu | XML Tuple Algebra[END_REF]. We describe the nested tuple data model manipulated by this algebra, then present its operators. Nested tuples data model for XML. The data model extends the W3C's XPath/XQuery data model with nested tuples to facilitate describing algebraic operations. Formally, a tuple t is a list of variable-value pairs:

(($V 1 , v 1 ), ($V 2 , v 2 ), . . . , ($V k , v k ))
where the variable names $V i are all distinct, and each value v i is either (i) an item, which can be an XML node, atomic value or ⊥, or (ii) a homogeneous collection of tuples (see below). Three flavours of collections are considered, namely: lists, bags and sets, denoted as (t 1 , t 2 , . . . , t n ), {{t 1 , t 2 , . . . , t n }}, and {t 1 , t 2 , . . . , t n }, respectively.

Tuple schemas are needed for our discussion. The schema S of a tuple t is a set of pairs {($V 1 , S 1 ), . . . , ($V n , S n )} where each S i is the schema of the value of the variable $V i . We use val to denote the type of (any) atomic value, and node to denote an XML node type. Further, a collection of values has the schema C{S} where C is list, bag, or set, depending on the kind of collection, and S is the schema of all values in the collection i.e., only homogeneous collections are considered.

The concatenation of two tuples t 1 and t 2 is denoted by t 1 +t 2 . Algebraic representation of XQuery. In the following, we introduce the translation process and the main operators by example. A methodology for translating our XQuery dialect into the algebra we consider was described in [START_REF] Arion | Algebra-Based identification of tree patterns in XQuery[END_REF], and detailed through examples in [START_REF] Manolescu | XQuery Midflight: Emerging Database-Oriented Paradigms and a Classification of Research Advances[END_REF]. The complete list of algebra operators and their semantics can be found in Appendix B.

Example 1 (continuation). The algebraic plan corresponding to the XQuery introduced in Section 2 is shown in Figure 5. For simplicity, we omit the variable types in the operators schema and only show the variable names. We discuss the operators starting from the leaves.

The XML scan operators take as input the 'people' (respectively 'closed auctions') XML forests and create a tuple out of each tree in them. XML scan is one of the border operators.

XPath and XQuery may perform navigation, which, in a nutshell, binds variables to the result of path traversals. Navigation is commonly represented through tree patterns, whose nodes carry the labels appearing in the paths, and where some target nodes are also annotated with names of variables to be bound, e.g., $pc, $i etc. The algebra we consider allows to consolidate as many navigation operations from the same query as possible within a single navigation tree pattern, and in particular navigation performed outside of the for clauses [START_REF] Arion | Algebra-Based identification of tree patterns in XQuery[END_REF], [START_REF] Deutsch | The NEXT Logical Framework for XQuery[END_REF], [START_REF] Michiels | Put a Tree Pattern in Your Algebra[END_REF]. Large navigation patterns lead to more efficient query execution, since patterns can be matched very efficiently against XML documents; for instance, if the pattern only uses child and descendant edges, it can be matched in a single pass over the input [START_REF] Chen | An efficient XPath query processor for XML streams[END_REF]. In the spirit of generalized tree patterns [START_REF] Chen | From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery[END_REF], annotated tree patterns [START_REF] Paparizos | Tree Logical Classes for Efficient Evaluation of XQuery[END_REF], or XML access modules [START_REF] Arion | XML Access Modules: Towards Physical Data Independence in XML Databases[END_REF], we assume a navigation (nav ) operator parameterized by an extended tree pattern (ETP) supporting multiple returning nodes, child and descendant axis, and nested and optional edges.

Consider the ETP e 1 in Figure 5. The node labeled $n:name is (i) optional and (ii) nested with respect to its parent node $p:person, since by XQuery semantics: (i) if a given $p lacks a name, it will still contribute to the query result; (ii) if a given $p has several names, let binds them all into a single node collection. The operator nav e1 concatenates each tuple successively with all @id attributes (variable $i) and name elements (variable $n) resulting from the embeddings of e 1 in the value bound to $pc. Observe that variable $n is nested into variable $t, which did not appear in the original query; in fact, $t is created by the XQuery to algebra translation to hold the nested collection with values bound to $n. The operator nav e2 is generated in a similar fashion. Therefore, in the previous query, ETPs e 1 and e 2 correspond to the following fragment:

for $p in $pc/site/people/person, $i in $p/@id let $n := $p/name let $r := for $c in $cc//closed_auction, $b in $c/buyer/@person, $s in $c/seller/@person let $a := $c/itemref
Above the nav operators in Figure 5, we find a nested join (nojoin l ρ ) on a disjunctive predicate ρ, which selects those people that appear as buyers or sellers in an auction.

Finally, the XML construction (constr L ) is the border operator responsible for transforming a collection of tuples to XML forests [START_REF] Fiebig | Algebraic XML Construction and its Optimization in Natix[END_REF], [START_REF] Shanmugasundaram | Querying XML Views of Relational Data[END_REF]. The information on how to build the XML forest is specified by a list L of construction tree patterns (CTPs in short), attached to the constr operator. For each tuple in its input, constr L builds one XML tree for each CTP in L [START_REF] Manolescu | XML Tuple Algebra[END_REF]. In our example, L contains a single CTP that generates for each tuple an XML tree consisting of elements of the form <res>{$n,$r}</res>. We omit further details here; the interested reader may find them in Appendix B. ⋄ Full operator set. We briefly comment below on the rest of operators that are handled by our translation.

The rest of unary operators are very close to their known counterparts in nested relational algebra. These are flatten (flat p ) which unnests tuples, selection (sel ρ ) based on a predicate ρ, projection (proj V ), aggregation (agg p,a,$r ) computing the usual aggregates over (nested) records, and value-based duplicate elimination (dupelim V ). One operator that is slightly different is group-by (grp G id ,Gv,$r ). In order to conform to XML semantics, the operator may group by identity based on the variables in G id , and/or by value on the variables in G v [START_REF] Deutsch | The NEXT Logical Framework for XQuery[END_REF], [START_REF] Manolescu | XML Tuple Algebra[END_REF].

Binary operators include the usual cartesian product (prod ), join (join ρ ), outer join (ojoin l ρ ) and nested outer join (nojoin l ρ ).

vi

→ ri i = 1 . . . n (($V 1, v1), . . . ($V n, vn)) → r1+ . . . +rn (TUPLE) v ::node v → (id (v), v) (XMLNODE) v ::val v → (v) (ATOMICVALUE) v :: C{S} v ≡ [t1, t2, . . . , tm] ti → ri i = 1 . . . m v → ( (r1, . . . , rm) ) (COLLVALUE)

XML ALGEBRA TO PACT

Within the global approach depicted in Figure 4, this section describes our contribution: translating (i) from the Extended XQuery Data Model (or EXDM, in short) into the PACT Data Model (Section 5.1) and (ii) from algebraic expressions into PACT plans (Section 5.2). The most complex technical issues are raised by the latter.

XQuery algebraic plans are translated into PACT plans recursively, operator by operator; for each XQuery operator, the translation outputs one or several PACT operators for which we need to choose (i) the parallelization contract (and possibly its corresponding key fields), and (ii) the user function, which together determine the PACT behavior. The hardest to translate are those algebraic operators whose input cannot be fragmented based on conjunctive key equalities (e.g., disjunctive joins) . This is because all massively parallel operators in PACT are based on key equality comparisons [START_REF] Battré | Nephele/PACTs: a programming model and execution framework for web-scale analytical processing[END_REF]. Translation rules. As in [START_REF] Re | A Complete and Efficient Algebraic Compiler for XQuery[END_REF], we use deduction rules to specify our translation. In a nutshell, a deduction rule describes how the translation is performed when some conditions are met over the input. Our rules rely on translation judgments, noted as J, J i , and are of the form: cond J 1 . . . J n J stating that the translation J (conclusion) is recursively made in terms of translations J 1 . . . J n (premises) when the (optional) condition cond holds. The translation judgments J i are optional; their absence denotes that the rule handles the "fixpoint" (start of the recursive translation).

Translating XML tuples into PACT records

Rules for translating instances of EXDM into those of PACT rely on translation judgments of the form t → r , or: "the EXDM instance t translates into the PACT record r".

The translation rules appear in Figure 6, where + denotes record concatenation. Rules produce records whose key fields are not set yet; as we will see in Section 5.2, the keys are filled in by the translation.

Rule (TUPLE) produces a record from a tuple: it translates each tuple value, and then builds the output record r by concatenating the results according to tuple order.

There are three rules that can be triggered by rule (TUPLE). First, rule (XMLNODE) translates an XML node into a record with two fields: the first one contains the XML ID, while the second is the text serialization of the XML tree rooted at the node. In turn, rule (ATOMICVALUE) translates an XML value. Finally, rule (COLLVALUE) translates a tuple collection into a single-field record that contains the nested collection of records corresponding to the tuples in the input.

Translating algebraic expressions to PACT

Rules for translating an algebraic expression into a PACT plan are based on judgments of the form A ⇒ P , or: "A translates into a PACT plan P". All rules are defined recursively over the structure of their input A; for instance, the translation of A = sel ρ (A ′ ) relies on the PACT plan P ′ resulting from the translation of the smaller expression A ′ , and so on.

The specific behavior of each rule is encoded in the choice of the parallelization contracts (and corresponding keys) and the user functions, so this is what we comment on below. Preliminaries. In the translation, we denote a PACT operator by its parallelization contract c, user function f and the list K of key field positions in the PACT input. In particular:

• a unary PACT is of the form c K f ; if K=∅, for simplicity we omit it and use just c f . • a binary PACT is of the form c K1,K2 f , assuming that the key of the left input records consists of the fields K 1 and that of the right input records of K 2 , respectively.

To keep track of attribute position through the translation, we use a set of helper functions associating to variables from S, the index positions of the corresponding fields in the PACT records. These functions are outlined in Table 1; we use the term S-records as a shortcut for records obtained by translating tuples that conform to schema S. The helper functions implementation details are quite straightforward.

A ⇒ P SA; L → L ′ constr L(A) ⇒ xmlwrite L ′ (P) (CONSTRUCTION) scan(f ) ⇒ xmlscan(f ) (SCAN)
Fig. 7. Border operators translation rules.

A ⇒ P SA; e → e ′ f := nav (e ′ ) nav e(A) ⇒ mp f (P) (NAVIGATION) A ⇒ P SA; G id → id G ′ id SA; Gv →v G ′ v K := G ′ id + G ′ v f := grp(K) grp G id ,Gv ,$r (A) ⇒ rd K f (P) (GROUP-BY) A ⇒ P SA; p →v pi f := flat(pi) flat p (A) ⇒ mp f (P) (FLATTEN) A ⇒ P SA; ρ → ρ ′ f := sel (ρ ′ ) sel ρ(A) ⇒ mp f (P) (SELECTION) A ⇒ P SA; V → id,v V ′ f := proj (V ′ ) proj V (A) ⇒ mp f (P) (PROJECTION) A ⇒ P SA; p →v pi if p.length = 1 then f := agg n (pi, a) U := mp f else K := ∅ f := agg(pi, a) U := rd K f agg p,a,$r (A) ⇒ U (P) (AGGREGATION) A ⇒ P SA; V →v K f := dupelim dupelim V (A) ⇒ rd K f (P) (DUPLELIM)
Fig. 8. Unary operators translation rules.

Border operators translation

Figure 7 outlines the translation of border operators. Rule (CONSTRUCTION) translates the logical constr L operator into a data sink that uses our output function xmlwrite. For each input record from P, xmlwrite generates XML content using the list of construction patterns in L ′ and writes the results to a file.

Rule (SCAN) translates the logical operator scan f into a data source built up by means of our input function xmlscan. For each XML document in f , xmlscan returns a single-field record holding the content of the document.

Unary operators translation

Unary operators are translated by the rules in Figure 8.

Rule (NAVIGATION) uses an auxiliary judgment that translates the input ETP e into e ′ using S A . Navigation is applied over each record independently, and thus we use a PACT with a Map contract. The UF is nav , which generates new records from the (possibly partial) embeddings of e ′ in each input record.

Rule (GROUP-BY) translates a group-by expression into a PACT with a Reduce contract, as the records need to be partitioned by the value of their grouping fields. The fields in K, which form the key used by the Reduce contract, are obtained appending G ′ v to G ′ id . K is also handed to the grp UF, which creates one record from each input collection of records. The new record contains the values for each field in K, and a new field which is the collection of the input records themselves.

Example 2. The following XQuery groups together the people that share interest in the same auctions: let $pc := collection( ' people ' ) for $p in $pc//people/person, $o in $p/watches/watch/@open_auction let $n := $p/name group by $o return <res><a>{$o}</a>{$n}</res>

The XML algebraic expression generated from this query is shown in Figure 9a. Using the judgments in Figure 8, the expression is translated into the PACT plan of Figure 9b. Observe that the grouping variable $o is translated into field position #6, used as key for the Reduce PACT. ⋄ Rule (FLATTEN) translates a flatten expression into a Map PACT, that applies the flattening UF flat on each input record independently. The path pi to the nested collection is obtained from p using S A .

Rule (SELECTION) produces a Map PACT that applies the selection to each record produced by P. Selection is performed by the sel UF, which uses the filtering condition ρ ′ obtained from ρ and S A .

Rule (PROJECTION) translates a projection expression into a PACT using a Map contract. The positions V ′ of the fields that should be kept by the projection are obtained from V using the schema S A .

The translation of (AGGREGATION) is interesting as it can use one PACT or another, depending on the path p to the variable being aggregated. If the variable is contained in a nested collection, i.e., p.length = 1, we produce a PACT with a Map contract; for each input record, the agg n UF executes the aggregation operation a over the field pointed by pi and outputs a record with the aggregation results.

A1 ⇒ P1 A2 ⇒ P2 f := concat prod (A1, A2) ⇒ cr f (P1, P2) (CARTESIANPRODUCT) A1 ⇒ P1 A2 ⇒ P2 SA 1 , SA 2 ; ρ → ρ ′ ρ ′ ⇀ l K1 ρ ′ ⇀r K2 f := concat join ρ (A1, A2) ⇒ mt K 1 ,K 2 f (P1, P2) (∧ JOIN= ) A1 ⇒ P1 A2 ⇒ P2 SA 1 , SA 2 ; ρ → ρ ′ ρ ′ ⇀ l K1 ρ ′ ⇀r K2 f := oconcat l ojoin l ρ (A1, A2) ⇒ cg K 1 ,K 2 f (P1, P2) (LO ∧ JOIN= ) A1 ⇒ P1 A2 ⇒ P2 SA 1 , SA 2 ; ρ → ρ ′ ρ ′ ⇀ l K1 ρ ′ ⇀r K2 f := noconcat l nojoin l ρ (A1, A2) ⇒ cg K 1 ,K 2 f (P1, P2) (NLO ∧ JOIN= )
Fig. 10. Cartesian product and conjunctive equi-join translation rules.

Otherwise, if the aggregation is executed on the complete input collection, we use a Reduce contract wrapping the input in a single group. The agg UF creates an output record having (i) a field with a nested collection of all input records and (ii) a field with the result of executing the aggregation a over the field pointed by pi .

Finally, rule (DUPLELIM) translates a duplicate elimination expression into a PACT with a Reduce contract. Each group handed to the UF holds the bag of records containing the same values in the fields pointed by K; the duplicate elimination UF, denoted by dupelim, outputs only one record from the group.

Binary operators translation

The rules are depicted in Figure 10; we assume that the inputs A 1 and A 2 of the algebraic binary operator translate into the PACT plans P 1 and P 2 . a) Cartesian product. This operator requires the simple concatenation UF, taking as input a pair of records, and outputting their concatenation: concat(r 1 , r 2 ) = r 1 +r 2 .

Rule (CARTESIANPRODUCT) translates a cartesian product into a Cross PACT with a concat UF. b) Joins with conjunctive equality predicates. This family comprises joins on equality predicates, which can be simple (natural) equi-joins, or outer joins (without loss of generality we focus on left outer joins). b.1) Conjunctive equi-join. The conjunctive equi-join operator is translated by rule (∧ JOIN = ), as follows. First, the predicate ρ over A 1 and A 2 translates into a predicate ρ ′ over records produced by P 1 and P 2 . Then, the list of fields pointed by the left (⇀ l ), resp. right (⇀ r ) of the condition ρ ′ are extracted, and finally they are used as the keys of the generated Match PACT. b.2) Left outer conjunctive equi-join. In the rule (LO ∧ JOIN = ), the output PACT is a CoGroup whose keys are taken from the fields of the translated join predicate ρ ′ . The CoGroup contract groups the records produced by P 1 and P 2 sharing the same key. Then, the oconcat l UF that we describe next is applied over each group, to produce the expected result.

Definition 1 (oconcat l ):

The left outer concatenation UF, oconcat l , of two record bags {{r 1 , . . . , r x }} and {{r ′ 1 , . . . , r ′ y }} is defined as:

• If y = 0, the cartesian product of the two bags.

• Otherwise, {{r 1 + ⊥ ′ , . . . , r x + ⊥ ′ }} i.e., concatenate each left input record with a ⊥-record having the schema (structure) of the right records. ⋄ b.3) Nested left outer conjunctive equi-join. Similar to the non-nested case, rule (NLO ∧ JOIN = ) translates the nested left outer conjunctive equi-join into a CoGroup PACT whose key is extracted from ρ ′ . However, we need a different UF in order to generate the desired right-hand side nested records, and we define it below.

Definition 2 (noconcat l ): The nested left outer concatenation UF, noconcat l , of the bags {{r 1 , . . . , r x }} and {{r ′ 1 , . . . , r ′ y }} is defined as:

• If y = 0, {{r 1 +(r ′ 1 , . . . , r ′ y ), . . . , r x +(r ′ 1 , . . . , r ′
A1 ⇒ P1 A2 ⇒ P2 SA 1 , SA 2 ; ρ → ρ ′ ρ ′ ≡ ρ ′ 1 ∨ . . . ∨ ρ ′ n ρ ′ k ⇀ l K 1k ρ ′ k ⇀r K 2k f k := pnjoin(ρ ′ , k-1) k = 1 . . . n U := {mt K 11 ,K 21 f 1 , . . . , mt K 1n ,K 2n fn } join ρ (A1, A2) ⇒ U (P1, P2) (∨ JOIN= ) A1 ⇒ P1 A2 ⇒ P2 SA 1 , SA 2 ; ρ → ρ ′ ρ ′ ≡ ρ ′ 1 ∨ . . . ∨ ρ ′ n ρ ′ k ⇀ l K 1k ρ ′ k ⇀r K 2k f k := nopnjoin l (ρ ′ , k-1) k = 1 . . . n U := {cg K 11 ,K 21 f 1 , . . . , cg K 1n ,K 2n fn } SA 1 K f ′ := opost l∨ ojoin l ρ (A1, A2) ⇒ rd K f ′ (U (P1, P2)) (LO ∨ JOIN= ) A1 ⇒ P1 A2 ⇒ P2 SA 1 , SA 2 ; ρ → ρ ′ ρ ′ ≡ ρ ′ 1 ∨ . . . ∨ ρ ′ n ρ ′ k ⇀ l K 1k ρ ′ k ⇀r K 2k f k := nopnjoin l (ρ ′ , k-1) k = 1 . . . n U := {cg K 11 ,K 21 f 1 , . . . , cg K 1n ,K 2n fn } SA 1 K f ′ := nopost l∨ nojoin l ρ (A1, A2) ⇒ rd K f ′ (U (P1, P2)) (NLO ∨ JOIN= )
Fig. 12. Disjunctive equi-join translation rules.

$b in $c/buyer/@person let $a := $c/itemref where $i = $b return $a return <res>{$n,$r}</res>
The query translates into the algebraic expression depicted in Figure 11a, while the corresponding PACT plan is shown in Figure 11b.

Rule (NLO ∧ JOIN = ) translates the nested left outer conjunctive equi-join into a PACT with a CoGroup contract that groups together all records having the same values in the fields corresponding to $i (K 1 ) and $b (K 2 ), and applies our noconcat l UF on them. ⋄ c) Joins with disjunctive equality predicates. Translating joins with disjunctive equality predicates is harder. The reason is that PACT contracts are centered around equality of record fields, and thus inherently not suited to disjunctive semantics.

To solve this mismatch, our translation relies on using more than one PACT for each operator, as we explain below. c.1) Disjunctive equi-join. In rule (∨ JOIN = ), the predicate ρ ′ is generated from ρ using S A1 S A2 . Then, for each conjunctive predicate ρ ′ k in ρ ′ , we create a Match whose keys are the fields participating in ρ ′ k . Observe that the UFs of these Match operators should guarantee that no erroneous duplicates are generated when the evaluation of more than one conjunctive predicates ρ ′ i , ρ ′ j , i = j is true for a certain record. To that purpose, we define the new UF pnjoin below, parameterized by k and performing a partial negative join.

Definition 3 (pnjoin):

Let ρ ′ = ρ ′ 1 ∨ ρ ′ 2 ∨ . . . ∨ ρ ′ n and k be an integer, with 0 ≤ k < n. Given two records r 1 , r 2 , the pnjoin(ρ ′ , k) UF evaluates ρ ′ 1 ∨ ρ ′ 2 ∨ . . . ∨ ρ ′ k over r 1 ,
K1 := (#6) K2 := (#6) K ′ 1 := (#6) K ′ 2 := (#8) ρ ′ := (#6=#6)∨ (#6=#8) xmlwrite L ′ mt pnjoin(ρ ′ ,0) mt pnjoin(ρ ′ ,1) mp nav (e ′ 1 ) mp nav (e ′ 2 )
xmlscan('people') xmlscan('closed auctions') rules respectively, are very similar; as illustrated next, the main difference resides in the different post-processing operations they adopt. The translation of these two operators is challenging because we want to ensure parallel evaluation of each conjunctive join predicate in the disjunction, and at the same time we need to:

K1 K ′ 1 K2 K ′ 2
1) Avoid the generation of duplicate records. We adopt a non trivial variation of the technique used previously for disjunctive equi-join. 2) Recognise records generated by the left hand-side expression which do not join any record coming from the right-hand side expression. We use the XML node identifiers in each left hand-side record to identify it uniquely, so that, after the parallel evaluation of each conjunction, a Reduce post-processing PACT groups all resulting combinations having the same left hand-side record; if none of such combinations exists, the left hand-side record representing a group is concatenated to a (nested) ⊥-record conforming to the right input schema, and the resulting record is output; otherwise the output record(s) are generated from the combinations. In the first step, we must evaluate in parallel the joins related to predicates ρ ′ i . A PACT with a CoGroup contract is built for each conjunctive predicate ρ ′ k . Each such PACT groups together all records that share the same value in the fields pointed by ρ ′ k , then applies the nopnjoin l UF (see below) on each group, with the goal of avoiding erroneous duplicates in the result; the UF is more complex than pnjoin though, as it has to handle the disjunction and the nesting. nopnjoin l is parameterized by k, as we will use it once for each conjunction ρ ′ k . Furthermore, nopnjoin l takes as input two bags of records and is defined as follows, along the lines of pnjoin.

Definition 4 (nopnjoin l ): Let ρ ′ = ρ ′ 1 ∨ ρ ′ 2 ∨ . . . ∨ ρ ′
n be a predicate where each ρ ′ i is conjunctive. Given two input bags {{r 1 , . . . , r x }} and {{r ′ 1 , . . . , r ′ y }}, the nopnjoin l (ρ ′ , k) UF is defined as follows:

• If the second input is empty (y = 0), return {{r 1 +(⊥ ′ ), . . . , r x +(⊥ ′ )}} i.e., concatenate every left input record with a field containing a nested list of one ⊥-record conforming to the schema of the right input. • Otherwise, for each left input record r i :

1) create an empty list c i ; 2) for each r ′ j,1≤j≤y , evaluate ρ ′ 1 ∨ ρ ′ 2 ∨ . . . ∨ ρ ′ k over r i and r ′ j , and add r ′ j to c i if the result is false; 3) if c i is empty, then insert into c i a ⊥-record with the schema of the right input; 4) output r i concatenated with a new field whose value is c i . ⋄

The second PACT produced by the (LO ∨ JOIN = ) and (NLO ∨ JOIN = ) rules uses a Reduce contract, taking as input the outputs of all the CoGroup operators; its key consists of the XML node identifiers in each left hand-side record (we denote by the extraction of these fields from the schema). This amounts to grouping together the records originated from the same left input record.

Depending on the join flavor though, this last PACT uses a different UF. For the plain (non-nested) join (LO ∨ JOIN = ), we use the opost l∨ UF producing records with an unnested right side. For the nested join (NLO ∨ JOIN = ), on the other hand, the nopost l∨ UF is used to produce nested records. Due to space constraints, we omit the definition of these UFs here and delegate their details to Appendix C.

Example 1 (continuation). Our algorithms translate the algebraic expression shown in Figure 5 into the PACT plan depicted in Figure 14; observe that it is the same PACT plan that was shown in less detail in Figure 1.

Rule (NLO ∨ JOIN = ) translates the nested left outer disjunctive equi-join into (i) two PACTs with CoGroup contracts, one for each disjunction, and (ii) a PACT with a Reduce contract that groups together records originating from the same

K1 := (#6) K2 := (#6) K ′ 1 := (#6) K ′ 2 := (#8) ρ ′ := #6=#6∨ #6=#8 K3 := (#1, #3, #5) xmlwrite L ′ rd nopost l∨ cg nopnjoin l (ρ ′ ,0) cg nopnjoin l (ρ ′ ,1) mp nav (e ′ 1 ) mp nav (e ′ 2 )
xmlscan('people') xmlscan('closed auctions')

K1 K ′ 1 K2 K ′ 2 K3 K3
Fig. 14. PACT plan corresponding to the logical expression in Figure 5.

left-hand side record, i.e., K 3 holds field positions #1, #3, #5, which contain the XML node identifiers of $pc, $p, $i, respectively. ⋄ d) Joins on inequalities. Our XQuery subset also supports joins with inequality conditions. In this case, the translation uses Cross contracts. Further, just like for joins with disjunctive predicates, the non-nested and nested outer variants of the joins on inequalities require more than one PACT. The corresponding translation rules can be found in Appendix D.

Syntactically complex translation vs. performance Clearly, complex joins such as those considered in c) could be translated into a single Cross PACT over the pairs of records as in d). However, this would be less efficient and scale poorly (number of comparisons quadratic in the input size), as our experiments will demonstrate.

EXPERIMENTAL EVALUATION

We implemented our PAXQuery translation approach in Java 1.6, and relied on the Stratosphere platform [START_REF]Stratosphere Platform[END_REF] All documents are simply stored in HDFS (which replicates them three times), that is, we do not control the distribution/allocation of documents over the nodes. XML queries. We used a subset of XMark queries from our XQuery fragment, and added queries with features supported by our dialect but absent from the original XMark, e.g., joins on disjunctive predicates; all queries are detailed in Appendix E.

Table 2 outlines the queries: the collection(s) that each query carries over, the corresponding XML algebraic operators and their numbers of occurrences, and the parallelization contracts used in the plan generated by our translation framework. Queries q 9 -q 14 all involve value joins, which carry over thousands of documents arbitrarily distributed across the HDFS nodes.

PAXQuery scalability

Our first goal is to check that PAXQuery brings to XQuery evaluation the desired benefits of implicit parallelism. For this, we fixed a set of queries, generated 11.000 documents (34GB) per node, and varied the number of nodes from 1 to 2, 4, 8 respectively; the total dataset size increases accordingly in a linear fashion, up to 272GB.

Figure 15 shows the response times for each query. Queries q 1 -q 6 navigate in the input document according to a given navigation pattern of 5 to 14 nodes; each translates into a Map PACT, thus their response time follows the size of the input. These queries scale up well; we see a moderate overhead in Figure 15 as the data volume and number of nodes increases. Queries q 7 and q 8 apply an aggregation over all the records generated by a navigation. For both queries, the navigation generates nested records and the aggregation consists on two steps. The first step goes over the nested fields in each input record, and thus it uses a Map contract. The second step is executed over the results of the first. Therefore, a Reduce contract that groups together all records coming from the previous operator is used. Since the running time is dominated by the Map PACTs which parallelize very well, q 7 and q 8 also scale up well.

Queries q 9 -q 12 involve conjunctive equi-joins over the collections. Query q 13 executes a NLO disjunctive equi-join, while q 14 applies a NLO inequi-join. We notice a very good scaleup for q 9 -q 13 , whose joins are translated in many PACTs (recall the rules in Figure 12). In contrast, q 14 , which translates into a Cross PACT, scales noticeably less well. This validates the interest of translating disjunctive equi-joins into many PACTs (as our rules do), rather than into a single Cross, since, despite parallelization, it fundamentally does not scale.

Comparison against other processors

To evaluate the performance of our processor against existing alternatives, we started by comparing it on a single node with other popular centralized XQuery processors. The purpose is to validate our choice of an XML algebra as outlined in Section 4.2 as input to our translation, by demonstrating that single-site query evaluation based on such an algebra is efficient. For this, we compare our processor with BaseX 7.7 [START_REF]BaseX[END_REF], Saxon-PE 9.4 [START_REF]Saxon[END_REF] and Qizx/open 4.1 [START_REF]Qizx/open[END_REF], on a dataset of 11000 XML documents (34GB).

Table 3 shows the response times for each query and processor; the shortest time is shown in bold, while OOM stands for out of memory, and TO for timeout (above 2 hours). In Table 3, we identify two query groups. First, q 1 -q 8 do not feature joins; while the performance varies across systems, only BaseX and PAXQuery are able to run all these queries. PAXQuery outperforms other systems because, compiled in PACT, it is able to exploit the multicore architecture.

In the second group, queries q 9 -q 14 join across the documents. None of the competing XQuery processors completes their evaluation, while PAXQuery executes them quite fast. For these, the usage of outer joins and multicore parallelization are key to this good performance behavior.

We next compare our system with other alternatives for implicitly parallel evaluation of XQuery. As explained in the Introduction, no comparable system is available yet. Therefore, for our comparison, we picked the BaseX centralized system (the best performing in the experiment above) and used Hadoop-MapReduce on one hand, and Stratosphere-PACT on the other hand, to parallelize its execution.

We compare PAXQuery, relying on the XML algebra-to-PACT translation we described, with the following alternative architecture. We deployed BaseX on each node, and parallelized XQuery execution as follows:

1) Manually decompose each query into a set of leaf subqueries performing just tree pattern navigation, followed by a recomposition subquery which applies (possibly nested, outer) joins over the results of the leaf subqueries; 2) Parallelize the evaluation of the leaf subqueries through one Map over all the documents, followed by one Reduce to union all the results. Moreover, if the recomposition query is not empty, start a new MapReduce job running the recomposition XQuery query over all the results thus obtained, in order to compute complete query results. This alternative architecture is in-between ChuQL [START_REF] Khatchadourian | Having a ChuQL at XML on the cloud[END_REF], where the query writer explicitly controls the choice of Map and Reduce keys, i.e., MapReduce is visible at the query level, and PAXQuery where parallelism is completely hidden. In this architecture, q 1 -q 8 translate to one Map and one Reduce, whereas q 9 -q 14 feature joins which translates into a recomposition query and thus a second job.

Table 4 shows the response times when running the query on the 8 nodes and 272GB; the shortest time is in bold. First, we notice that BaseX runs 2 to 5 times faster on Stratosphere than on Hadoop. This is due to Hadoop's checkpoints (writing intermediary results to disk) while Stratosphere currently does not, trading reliability for speed. For queries without joins (q 1 -q 8 ), PAXQuery is faster for most queries than BaseX on Hadoop or Stratosphere; this simply points out that our inhouse tree pattern matching operator (physical implementation of nav) is more efficient than the one of BaseX. Queries with joins (q 9 -q 14 ) fail in the competitor architecture again. The reason is that intermediary join results grow too large and this leads to an out-of-memory error. PAXQuery evaluates such queries well, based on its massively parallel (outer) joins.

Conclusions of the experiments

Our experiments demonstrate the efficiency of an XQuery processor built on top of PACT. First, our scalability evaluation has shown that the translation to PACT allows PAXQuery to parallelize every query execution step with no effort required to partition, redistribute data etc., and thus to scale out with the number of machines in a cluster. The only case where scale-up was not so good is q 14 where we used a Cross (cartesian product) to translate an inequality join; an orthogonal optimization here would be to use a smarter dedicated join operator for such predicates, e.g. [START_REF] Okcan | Processing theta-joins using MapReduce[END_REF].

Secondly, we have shown that PAXQuery outperforms competitor XQuery processors, whether centralized or distributed over Hadoop and Stratosphere. None of the competing processors was able to evaluate any of our queries with joins across documents on the data volumes we considered, highlighting the need for efficient parallel platforms for evaluating such queries.

RELATED WORK

Massively parallel XML query processing. In this area, MRQL [START_REF] Fegaras | XML Query Optimization in Map-Reduce[END_REF] proposes a simple SQL-like XML query language implemented through a few operators directly compilable into MapReduce. Like our XQuery fragment, MRQL queries may be nested, however, its dialect does not allow expressing the rich join flavours that we use. Further, the XML navigation supported by MRQL is limited to XPath, in contrast to our richer navigation based on tree patterns with multiple returning nodes, and nested and optional edges.

ChuQL [START_REF] Khatchadourian | Having a ChuQL at XML on the cloud[END_REF] is an XQuery extension that exposes the MapReduce framework to the developer in order to distribute computations among XQuery engines; this leaves the parallelization work to the programmer, in contrast with our implicitly parallel approach which does not expose the underlying parallelism at the query level.

HadoopXML [START_REF] Choi | HadoopXML: A suite for parallel processing of massive XML data with multiple twig pattern queries (demo)[END_REF] and the recent [START_REF] Bidoit | Processing XML queries and updates on map/reduce clusters (demo)[END_REF] process XML queries in Hadoop clusters by explicitly fragmenting the input data in a schema-driven, respectively, query-driven way, which is effective when querying one single huge document. In contrast, we focus on the frequent situation when no single document is too large for one node, but there are many documents whose global size is high, and queries may both navigate and join over them. Further, we do not require any partitioning work from the application level.

After the wide acceptance of Hadoop, other parallel execution engines and programming abstractions conceived to run custom data intensive tasks over large data sets have been proposed: PACT [START_REF] Battré | Nephele/PACTs: a programming model and execution framework for web-scale analytical processing[END_REF], Dryad [START_REF] Isard | Dryad: Distributed Data-Parallel Programs from Sequential Building Blocks[END_REF], Hyracks [START_REF] Borkar | Hyracks: A flexible and extensible foundation for data-intensive computing[END_REF] or Spark [START_REF] Zaharia | Resilient distributed datasets: a fault-tolerant abstraction for in-memory cluster computing[END_REF]. Among these, the only effort at parallelizing XQuery is the ongoing VXQuery project [START_REF]Apache VXQuery[END_REF], translating XQuery into the Algebricks algebra, which compiles into parallel plans executable by Hyracks. In contrast, PAXQuery translates into an implicit parallel logical model such as PACT. Thus, our algorithms do not need to address underlying parallelization issues such as data redistribution between computation steps etc. which [START_REF] Borkar | Hyracks: A flexible and extensible foundation for data-intensive computing[END_REF] explicitly mentions.

XQuery processing in centralized settings has been thoroughly studied, in particular through algebras in [START_REF] Re | A Complete and Efficient Algebraic Compiler for XQuery[END_REF], [START_REF] Deutsch | The NEXT Logical Framework for XQuery[END_REF], [START_REF] May | Strategies for query unnesting in XML databases[END_REF], [START_REF] Manolescu | XML Tuple Algebra[END_REF]. Our focus is on extending the benefits of implicit large-scale parallelism to a complex XML algebra, by formalizing its translation into the implicitly parallel PACT paradigm.

XML data management has also been studied from many other angles, e.g., on top of column stores [START_REF] Boncz | MonetDB/XQuery: a fast XQuery processor powered by a relational engine[END_REF], distributed with [START_REF] Kling | Generating Efficient Execution Plans for Vertically Partitioned XML Databases[END_REF] or without [START_REF] Abiteboul | Dynamic XML Documents with Distribution and Replication[END_REF] an explicit fragmentation specification, in P2P [START_REF] Koloniari | Peer-to-peer management of XML data: issues and research challenges[END_REF] etc. We focus on XQuery evaluation through the massively parallel PACT framework, which leads to specific translation difficulties we addressed. Parallelizable nested languages. Recently, many high-level languages which translate into massively parallel frameworks have been proposed; some of them work with nested data and/or feature nesting in the language, thus somehow resemble XQuery.

Jaql [START_REF] Beyer | Jaql: A Scripting Language for Large Scale Semistructured Data Analysis[END_REF] is a scripting language tailored to JSON data, which translates into MapReduce programs; Meteor [START_REF] Heise | Meteor/Sopremo: An Extensible Query Language and Operator Model[END_REF], also for JSON, translates into PACT. None of these languages handles XQuery semantics exactly, since JSON does not feature node identity; the languages are also more limited, e.g., Jaql only supports equi-joins.

The Asterix Query Language [START_REF] Behm | ASTERIX: Towards a Scalable, Semistructured Data Platform for Evolving-world Models[END_REF], or AQL in short, is based on FLOWR expressions and resembles XQuery, but ignores node identity which is important in XQuery and which we support. Like VXQuery, AQL queries are translated into Algebricks; recall that unlike our translation, its compilation to the underlying Hyracks engine needs to deal with parallelization related issues.

Finally, other higher level languages that support nested data models and translate into parallel processing paradigms include Pig [START_REF] Olston | Pig Latin: A Not-So-Foreign Language for Data Processing[END_REF] or Hive [START_REF] Thusoo | Hive -a PB scale data warehouse using Hadoop[END_REF]. Our XQuery fragment is more expressive, in particular supporting more types of joins. In addition, Pig only allows two levels of nesting in queries, which is a limitation. In contrast, we translate XQuery into unnested algebraic plans with (possibly nested, possibly outer) joins and grouping which we parallelize, leading to efficient execution even for (originally) nested queries. Complex operations using implicit parallel models. The problem of evaluating complex operations through implicit parallelism is of independent interest. For instance, the execution of join operations using MapReduce has been studied extensively. Shortly after the first formal proposal to compute equi-joins on MapReduce [START_REF] Yang | Map-reducemerge: Simplified Relational Data Processing on Large Clusters[END_REF], other studies extending it [START_REF] Blanas | A Comparison of Join Algorithms for Log Processing in MapReduce[END_REF], [START_REF] Jiang | MAP-JOIN-REDUCE: Toward Scalable and Efficient Data Analysis on Large Clusters[END_REF] or focusing on the processing of specific join types such as multi-way joins [START_REF] Afrati | Optimizing joins in a map-reduce environment[END_REF], set-similarity joins [START_REF] Vernica | Efficient Parallel Set-similarity Joins Using MapReduce[END_REF], or θ-joins [START_REF] Okcan | Processing theta-joins using MapReduce[END_REF], appeared. PAXQuery is the first to translate a large family of joins (which can be used outside XQuery), into the more flexible PACT parallel framework.

CONCLUSION AND FUTURE WORK

We have presented the PAXQuery approach for the implicit parallelization of XQuery, through the translation of an XQuery algebraic plan into a PACT parallel plan. We targeted a rich subset of XQuery 3.0 including recent additions such as explicit grouping, and demonstrated the efficiency and scalability of PAXQuery with experiments on collections of hundreds of GBs.

For future work, we contemplate the integration of indexing techniques into PAXQuery to improve query evaluation time. Further, we would like to explore reutilization of intermediary results in the PACT framework to enable efficient multiplequery processing.

APPENDIX A XQUERY DIALECT

Figure 16 depicts the grammar for our XQuery dialect.

A query is a FLWR expression, which is a powerful abstraction that can be used for many purposes, including iterating over sequences, joining multiple documents, and performing grouping.

The initial clause of the expression is a for or let. The for clause iterates over the items in the sequence resulting from its associated expression, binding the variable to each item. In turn, a let clause binds each variable to the result of its associated expression, without iteration.

The bindings for for clauses are generated from an expression PathExp. A path is evaluated starting from the root of each document in a collection available at URI Uri, from the root of a single document available at URI Uri, or from the bindings of a previously introduced variable. Path corresponds to the navigational path used to locate nodes within trees. In particular, Path belongs to the XPath {/,//,[]} language [START_REF] Miklau | Containment and equivalence for an XPath fragment[END_REF]. In turn, the bindings for let clauses can be an expression PathExp, another FLWR expression or an aggregation expression AggrExpr .

The middle clauses (for , let, where, or group by ) may appear multiple times and in any order. The where clause supports expressions formed with or and and, in disjunctive normal form (DNF). We support two different types of elementary comparators: (ValCmp) compares atomic values, while (NodeCmp) compares nodes by their identity or by their document order. The group by clause groups tuples based on the value of the variables specified in the clause.

Finally, the FLWR expression ends with a return clause. For each tuple of bindings, the clause builds an XML forest using an element construction expression EleConst or a list of variables Var+. When we use the element construction expression, the value in AVal follow the XML naming convention for attribute values, while AName and EName follow the restrictions associated to the XML node naming conventions.

APPENDIX B XML ALGEBRA OPERATORS

This section provides details about algebraic operators used by the algebra considered in this work. In the following, we denote by F the domain of XML forests, and we denote by T the domain of tuples.

B.1 Border operators

XML Construction (constr L ). The input to the operator is a collection of tuples, and from each tuple an XML forest is created: constr L : T * → F * . The information on how to build the XML forest is specified by a list L of construction tree patterns (CTPs in short), attached to the constr operator. For each tuple in its input, constr L builds one XML tree for each CTP in L [START_REF] Manolescu | XML Tuple Algebra[END_REF].

Formally, Construction Tree Patterns are defined as follows.

Definition 5 (Construction Tree Pattern): A Construction Tree Pattern is a tree c = (V, E) such that each node n ∈ V is labeled with (i) a valid XML element or attribute name, or (ii) a variable path p, which is $V 1 .p ′ where p ′ is in turn a variable path.

If a node n is labeled with a variable path p, and a descendant n desc of n is annotated with a variable path p desc , then p is a prefix of p desc .

Finally, we depict an optional construction subtree in c with a dashed edge. ⋄ Without loss of generality, we will assume from now on that in all CTPs, the paths are valid wrt the schema of tuples in the input to the constr operator.

The semantics of constr L for an input collection of tuples T and a list of CTPs L is depicted in Algorithm 1. We use an XML forest f , initially empty, to gather the resulting XML. XML content is built out of each tuple t ∈ T during a topdown, left-to right traversal of each CTP c ∈ L; constr is called recursively following this order (lines [START_REF] Arion | XML Access Modules: Towards Physical Data Independence in XML Databases[END_REF][START_REF] Arion | Algebra-Based identification of tree patterns in XQuery[END_REF][START_REF]BaseX[END_REF][START_REF] Battré | Nephele/PACTs: a programming model and execution framework for web-scale analytical processing[END_REF][START_REF] Beeri | SAL: An Algebra for Semistructured Data and XML[END_REF][START_REF] Behm | ASTERIX: Towards a Scalable, Semistructured Data Platform for Evolving-world Models[END_REF][START_REF] Beyer | Jaql: A Scripting Language for Large Scale Semistructured Data Analysis[END_REF][START_REF] Bidoit | Processing XML queries and updates on map/reduce clusters (demo)[END_REF]. Observe that if an intermediary node in c is labeled with a variable path p, p is followed to extract a nested collection of tuples within t, which is in turn used as input for the subsequent constr call (line 7). Thus, we can navigate over the nested collection of tuples to build the construction results. Afterwards, XML content for the current node r and its children (if any) is created and appended to f iff (i) r is not the root of an optional subtree, or (ii) r is the root of an optional subtree but following any variable path p r labeling a leaf under r leads to a non-⊥ value within t (lines [START_REF] Blanas | A Comparison of Join Algorithms for Log Processing in MapReduce[END_REF][START_REF] Boncz | MonetDB/XQuery: a fast XQuery processor powered by a relational engine[END_REF][START_REF] Borkar | Hyracks: A flexible and extensible foundation for data-intensive computing[END_REF][START_REF] Chen | An efficient XPath query processor for XML streams[END_REF][START_REF] Chen | From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery[END_REF][START_REF] Choi | HadoopXML: A suite for parallel processing of massive XML data with multiple twig pattern queries (demo)[END_REF][START_REF] Dean | MapReduce: Simplified Data Processing on Large Clusters[END_REF][START_REF] Deutsch | The NEXT Logical Framework for XQuery[END_REF][START_REF] Eisenberg | XQuery 3.0 is nearing completion[END_REF][START_REF] Fegaras | XML Query Optimization in Map-Reduce[END_REF][START_REF] Fiebig | Algebraic XML Construction and its Optimization in Natix[END_REF][START_REF] Heise | Meteor/Sopremo: An Extensible Query Language and Operator Model[END_REF].

T ′ ← T 9 L ′ ← children(n) 10 f ′ ← constr L ′ (T ′ ) 11 append f ′ to
In Figure 18a, we show four CTPs c 1 , . . . , c 4 , while Figure 18b shows three nested tuples and the four different XML forests produced out of these three tuples by the operator constr ci,1≤i≤4 . Regardless of the construction pattern used, there are three trees in the forest, each built from one input tuple. The root of each tree is a newly created node labeled person, as dictated by each of the four c i s. Further, in each tree of the forest built for c 1 , the children of the person node are deep copies 1 of the forests found in the $N attribute, respectively, in the nested $R.$Z and $R.$C attributes. Since in the third tuple the latter forests are empty, the third tree in the forest of c 1 only has a copy of n 3 as child. Observe that the same happens for c 2 , as the subtree rooted at address is optional and thus it is only built if $R.$Z or $R.$C are not bound to ⊥. Finally, note that when the CTP c 4 is used, 1. Following standard XQuery semantics [START_REF] Robie | XQuery 3.0: An XML Query Language, W3C Proposed Recommendation[END_REF], whenever an input node needs to be output under a new parent, a deep copy of the input node is used.

c 1 person $N $R.$Z $R.$C c 2 person $N address $R.$Z $R.$C c 3 person $N address $R $Z $C c 4 person $N $R address $Z $C
(a) Sample CTPs. the root node in each tree has as children (copies of) the $N nodes, as well as a newly created address node having the $Z and $C forests as children.

$N $R $Z $C n1 z1 c1 n2 z21 c21 z22 c22 n3 ⊥ ⊥ c1 c2 c3
Scan (scan). The scan operator takes as input an XML forest and creates a tuple out of each tree in the forest: scan : F → T * . The semantics of the scan operator whose input is an XML forest f is the following:

scan(f ) = {{ ($I, d.root) | d ∈ f }}

B.2 Unary operators

Navigation (nav e ). The operator is applied on a set of tuples and is parameterized by an extended tree pattern (ETP) [START_REF] Manolescu | XML Tuple Algebra[END_REF].

In the following we introduce ETPs formally.

Definition 6 (Extended Tree Pattern): An Extended Tree Pattern is a tree e = (V, E) where:

• The root r ∈ V is labeled with a variable $I.

• Each non-root node n ∈ V are labeled with (i) an element/attribute name and (ii) optionally, a variable $V .

• Each e = (x, y) ∈ E is either a child edge from x to y, denoted by a single line, or a descendant edge from x to y, denoted by a double line. Further, optional edges are depicted with dashed lines, and nested edges are labeled with n. ⋄ Figure 19a depicts some sample extended tree patterns. Given an ETP e and an XML tree d, an embedding generates the tuple that results from binding the root variable of e to d and mapping the nodes of e to a collection of nodes in d. The variables of the binding tuples are ordered by the preorder traversal sequence of e. Note that if e contains optional edges, a mapping may be partial: nodes connected to the pattern by these edges may not be mapped, in which case the node takes the ⊥ value. We denote by ϕ(e, d) all the embeddings from e to d. Then, we define the semantics of the navigation operator as:

$I $N $R $C root n1 c1 root n2 c21 c22 $I $N $R $Z root n1 z1 root n2 z21 z22 root n1 ⊥ $I $N $S $I $N $R $Z $C root n1 z1 c1 root n2 z21 c21 z22 c22 root n3 ⊥ ⊥ (
nav e (A) = t∈A {{t + t ′ | t ′ ∈ ϕ(e, t.$I)}}
In other words, the navigation operator nav is parameterized by a tree pattern e, whose root is labeled with a variable $I, that must appear in tuples returned by the input expression A. The nav operator concatenates t successively with all tuples binding returned by ϕ(e, t.$I), for any tuple t returned by A.

The semantics of the operator are illustrated with four examples in Figure 19b. Given a tuple with a variable $I bound to the XML tree shown in Figure 20, the navigation operator using e 1 extracts the name and city nodes of each person; observe that the variable $C is nested in $R and that the person without any city node does not generate any bindings. Instead, the navigation operator using e 4 generates bindings from all person nodes, as the subtree rooted at the address node is optional. The navigation result for ETPs e 2 , e 3 is extracted in the similar fashion. Group-By (grp G id ,Gv,$r ). The operator has three parameters: the set of group-by-id variables G id , the set of group-by-value variables G v and the result variable $r.

Let P (A, G id , G v ) be the set of tuple collections that results from partitioning the tuples output by A, such that the tuples in a collection have id-equal values for the variables of G id and equal values for the variables of G v . For each collection p ∈ P (A, G id , G v ), let t p id (respectively, t p v ) be the tuple consisting of the G id (respectively, G v ) variables together with their values in p. Then, the semantics of group-by operator is defined as follows.

grp G id ,Gv,$r (A) = {{t p id +t p v + ($r, p) | p ∈ P (A, G id , G v )}} Each tuple in the output of grp contains: the variables of G id and G v with their values, and a newly introduced variable $r, whose value is the group of input tuples whose G id attributes are ID-equal, and whose G v values are equal. Flatten (flat p ). This operator unnests tuples in the collection referenced by p.

In the following, we introduce the semantics when p.length = 1; the other cases can be easily worked out using the same approach. For each input tuple t ∈ A, let t ′ (respectively, t ′′ ) be the tuple containing the variables preceding (respectively, succeeding) p in t. Further, let t i be each of tuples contained in the collection t |p . Then, we formalize the semantics of the operator as follows:

flat p (A) = {{t ′ + t p i + t ′′ | t ′ + (p, t |p ) + t ′′ ∈ A and t p i ∈ t |p }} Selection (sel ρ ).
The selection operator is defined in the usual way based on a boolean predicate ρ to be tested on a tuple t. Formally, a selection over a stream of tuples generated by A is defined as: sel ρ (A) = {{t | t ∈ A and ρ(t) holds}} Projection (proj V ). The operator is defined by specifying a set of variable names V = {$V 1 , $V 2 , . . . , $V k } that are present in the schema of the input tuples and should be retained in the output tuples. More precisely: proj

V (A) = {{ ($V 1 , v 1 ), ($V 2 , v 2 ), . . . , ($V k , v k ) | t ∈ A
and ∀j ∈ {1..k}.$V j ∈ V and ($V j , v j ) ∈ t}} Aggregation (agg p,a,$r ). The operator has three parameters: the variable path p that references the variable over whose bound values we will execute the aggregation, the aggregation operation a (recall that we support count, avg, max, min and sum), and the result variable $r.

Let A(t, p, a) be the result of applying aggregation operation a on the values bound to variable path p in tuple t.

If the path p refers to a variable in a immediate nested collection, i.e. p.length = 2, the semantics of the aggregation operator are defined as follows.

agg p,a,$r (A) = {{t + t ′ | t ∈ A and t ′ = ($r, A(t, p, a)) }} The semantics of the aggregation with more levels of nesting, i.e. p.length > 2, is straightforward.

Finally, if we want to aggregate over a non-nested variable of the input tuples, i.e. p.length = 1, we proceed by nesting them under a new variable to produce the correct aggregation result. Thus, the semantics is defined as follows.

agg p,a,$r (A) = {{agg p,a,$r ({t}) | t = ($N, (A)) }} Duplicate elimination (dupelim V ). The operator is defined by specifying a set of variable names V that are present in the schema of the input tuples and whose bound value should be unique among the output tuples.

Recall P (A, G id , G v ) that partitions the tuples output by A, such that the tuples in a collection have id-equal values for the variables of G id and equal values for the variables of G v . Then, the semantics of the duplicate elimination operator is defined as follows.

dupelim V (A) = {t 1 | {{t 1 , . . . , t n }} ∈ P (A, (), V )}

B.3 Binary operators

The last family of operators are binary: they take in input two collections of tuples produced by the plans A 1 and A 2 respectively, and output a collection of tuples. We outline their semantics in the following.

Cartesian product (prod ). The cartesian product is standard.

prod (A 1 , A 2 ) = {{t 1 +t 2 | t 1 ∈ A 1 , t 2 ∈ A 2 }} Join (join ρ ).
The join relies on a boolean join predicate ρ(t 1 , t 2 ), and is defined as follows.

join

ρ (A 1 , A 2 ) = {{t 1 +t 2 | t 1 ∈ A 1 ,
l ρ (A 1 , A 2 )={{t 1 +t 2 | t 1 ∈ A 1 , t 2 ∈ A 2 and ρ(t 1 , t 2 )}} ∪ {{t 1 + ⊥ A2 | t 1 ∈ A 1 , ∃t 2 ∈ A 2 s.t. ρ(

APPENDIX C DISJUNCTIVE EQUI-JOINS POST-PROCESSING

The semantics of these UFs are introduced in the following. Definition 7 (opost l∨ ): Consider an input bag of records {{r 1 , . . . , r x }}. Each record r i,1≤i≤x is separated in left and right side, i.e. r i = r l i +r r i . Further, r r i contains a single field with a nested collection of records R i . We denote by opost l∨ the post-processing UF which:

• If all nested collections R i,1≤i≤x contain only ⊥-records, it outputs a single record r = r l i + ⊥ ′ , where r l i is the left side of any input record and ⊥ ′ is the ⊥-record conforming to the signature of the records in R i .

• Otherwise, it flattens the nested collections R i,1≤i≤x

excluding ⊥-records, and returns the result. ⋄ A1 ⇒ P1 A2 ⇒ P2 SA 1 , SA 2 ; ρ → ρ ′ f := pnjoin(ρ ′ ) join ρ (A1, A2) ⇒ cr f (P1, P2) Definition 8 (nopost l∨ ): Consider an input bag of records {{r 1 , . . . , r x }}. Each record r i,1≤i≤x is separated in left and right side, i.e. r i = r l i +r r i . Further, r r i contains a single field with a nested collection of records R i . We denote by nopost l∨ the post-processing UF that outputs a single record r = r l i +r ′ , where:

• If all nested collections R i,1≤i≤x contain only ⊥-records, r ′ contains a field with a nested collection with a ⊥record conforming to the signature of the records in R i . • Otherwise, r ′ contains a field with a nested collection with the records contained in R i,1≤i≤x , excluding ⊥records. ⋄

APPENDIX D JOINS ON INEQUALITIES

Our XQuery fragment also supports joins with inequality conditions. In this case, the translation uses Cross contracts. Further, just like for joins with disjunctive predicates, the nonnested and nested outer variants of the inequi-join require more than one PACT. We depict the corresponding translation rules in Figure 21. In the following, we explain the translation of this flavor of joins. 1) Inequi-join. Rule (INEQUI-JOIN) generates a PACT with a Cross input contract. The predicate ρ is transformed into ρ ′ , which is equivalent but replaces the EXDM variables by positions in the PACTs records. Then the pnjoin UF introduced in the following is applied over each pair of records.

Definition 9 (pnjoin): Given two records r 1 , r 2 and a predicate ρ ′ , the pnjoin(ρ ′ ) UF evaluates ρ ′ over r 1 , r 2 , and outputs r 1 +r 2 if it evaluates to true. ⋄

2) (Nested) left outer inequi-join. As it happens with the disjunctive equality predicates, the translation of the nonnested and nested variant of the outer inequi-join, described by the (LO INEQUI-JOIN) and (NLO INEQUI-JOIN) rules respectively, resemble each other. The translation of the non-nested and nested left outer inequi-join results in two steps. The first step consists of a PACT with a Cross contract. The UF of the PACT is ojoin l , a traditional left outer join, that we introduced in the following.

Definition 10 (ojoin l ): Given two records r 1 , r 2 and a predicate ρ ′ , the ojoin l (ρ ′ ) UF evaluates ρ ′ over r 1 , r 2 , and:

• If it evaluates to true, outputs r 1 +r 2 .

• Otherwise, it outputs r 1 + ⊥ 2 , where ⊥ 2 is the ⊥-record that conforms to the signature of r 2 . ⋄

The last PACT resulting from both translation rules uses a Reduce contract that groups together the records originated from the same left hand-side record. In the plain variant, the UF is opost l that produces unnested records; otherwise, the PACT uses the nopost l UF. We introduce both UFs in the following.

Definition 11 (opost l ): Consider an input bag of records {{r 1 , . . . , r x }}. Each record r i,1≤i≤x is separated in left and right side, i.e. r i = r l i +r r i . We denote by opost l the postprocessing UF which:

• If r r i,1≤i≤x are all ⊥-records, it outputs one of them. • Otherwise, it returns every r i,1≤i≤x where r r i is not a ⊥-record. ⋄ Definition 12 (nopost l ): Consider an input bag of records {{r 1 , . . . , r x }}. Each record r i,1≤i≤x is separated in left and right side, i.e. r i = r l i +r r i . We denote by nopost l the postprocessing UF that outputs a single record r = r l i +r ′ , where: • If r r i,1≤i≤x are all ⊥-records, r ′ contains a field with a nested collection with a ⊥-record that conforms to the signature of r r i . • Otherwise, r ′ contains a field with a nested collection with every r r i,1≤i≤x that is not a ⊥-record. ⋄ Example 5. Consider the following XQuery that extracts the name of users and (if any) the items they bought that were valued more than their monthly incoming: let $pc := collection( ' people ' ), $cc := collection( ' c l o s e d a u c t i o n s ' ) for $p in $pc/site/people/person let $n := $p/name let $r := for $c in $cc//closed_auction, $i in $p/@id, $b in $c/buyer/@person, $x in $p/profile/@income, $y in $c/price let $a := $c/itemref where $i = $b and $x < $y return $a return <res>{$n,$r}</res>

The XML algebra expression generated from this query is shown in Figure 22a. Using the rule (LO ∨ INEQUI-JOIN) in Figure 21, the algebraic expression corresponding to the query is translated into the PACT plan depicted in Figure 22b.

⋄

APPENDIX E EXPERIMENTAL QUERIES DETAIL

This section lists the XQuery queries used in the experimental section. They are based on the queries provided by the XMark benchmark [START_REF] Schmidt | XMark: A benchmark for XML data management[END_REF].

Fig. 1 .

 1 Fig. 1. Outline of the PACT program generated by PAX-Query for the XQuery in Example 1.

Q 1 let 3 letFig. 2 .

 132 Fig. 2. Sample queries expressed in our XQuery grammar.

Fig. 3 .

 3 Fig. 3. PACT operator outline.

Fig. 4 .

 4 Fig. 4. Translation process overview. c mt (I 1 , I 2 ) = {{(r 1 , r 2 ) | r 1 ∈ I 1 , r 2 ∈ I 2 and r 1 .key = r 2 .key}} • CoGroup can be seen as a "Reduce on two inputs"; it groups the records from both inputs, sharing the same key value. Formally, given I 1 , I 2 ⊂ R: c cg (I 1 , I 2 ) = {s = {{r 11 , . . . , r 1m , r 21 , . . . , r 2j }} | r 11 , . . . , r 1m ∈ I 1 and r 21 , . . . , r 2j ∈ I 2 and ∀r, r ′ ∈ s : r.key = r ′ .key and ∃r ′′ ∈ (I 1 ∪ I 2 ) \ s such that r ′′ .key = r 11 .key}

Fig. 5 .

 5 Fig. 5. Sample logical plan for the query in Example 1.

Fig. 6 .

 6 Fig. 6. Data model translation rules.

Fig. 9 .

 9 Fig. 9. Logical expression (a) and corresponding PACT plan (b) for the query in Example 2.

Fig. 11 .

 11 Fig. 11. Logical expression (a) and corresponding PACT plan (b) for the query in Example 3.

Example 3 .

 3 y )}} i.e., nest the right set as a new field concatenated to each record from the left.• Otherwise, {{r 1 +(⊥ ′ ), . . . , r x +(⊥ ′ )}} i.e., add to each left record a field with a list containing a ⊥-record conforming to the schema of the right records. ⋄ The following XQuery extracts the name of users and the items that they bought (if any): let $pc := collection( ' people ' ), $cc := collection( ' c l o s e d a u c t i o n s ' ) for $p in $pc/site/people/person, $i in $p/@id let $n := $p/name let $r := for $c in $cc//closed_auction,

  r 2 , and outputs r 1 +r 2 if they evaluate to false. ⋄ Note that the UF ensures correct multiplicity of each record in the result. ($pc, $p, $i, $r{$n}) S3:=($cc) S4:=($cc, $c, $b, $s) S5:=($pc, $p, $i, $r{$n}, $cc, $c, $b, $s) b)

Fig. 13 .Example 4 .

 134 Fig. 13. Logical expression (a) and corresponding PACT plan (b) for the query in Example 4.

Fig. 15 .

 15 Fig. 15. PAXQuery scalability evaluation.

Fig. 16 .

 16 Fig. 16. Grammar for the considered XQuery dialect.

AFig. 17 .

 17 Fig. 17. XML algebraic plan grammar.

Algorithm 1 : 1 for t ∈ T do 2 for c ∈ L do 3 r 7 following p within t else 8

 112378 XML Construction Input : Collection of tuples T , list of CTPs L Output: XML forest f ← () ← c.root; N ← children(r); fn ← () 4 for n ∈ N do 5 if n is not a leaf and n is labeled with a variable 6 path p then T ′ ← collection of tuples obtained by

  Resulting XML forests after applying the CTPs to a collection of tuples.

Fig. 18 .

 18 Fig. 18. Sample CTPs and corresponding XML construction results.

Fig. 20 .

 20 Fig. 20. Sample XML tree.

SA 1 ,Fig. 21 .

 121 Fig. 21. Inequi-join translation rules.

Query 1 : 3 ) 1 )Fig. 22 .Query 2 : 3 :Query 4 :

 13122234 Fig. 22. Logical expression (a) and corresponding PACT plan (b) for the query in Example 5. Query 2: List the names of items registered in Australia along with their descriptions. let $ic := collection( ' XMarkItems ' ) for $i in $ic/site/regions/australia/item let $n := $i/name/text(), $d := $i/description return <item name="{$n}">{$d}</item> Query 3: Return the names of all items in Europe whose description contains the word 'gold'. let $ic := collection( ' XMarkItems ' ) for $i in $ic/site//europe/item, $d in $i/description/text/text() let $n := $i/name/text() where contains($d, "gold") return $n Query 4: Print the keywords in emphasis in annotations of closed auctions.let $cc := collection( ' XMarkClosedAuctions ' ) for $a in $cc/site/closed_auctions/closed_auction/ annotation/description/parlist/listitem/ parlist/listitem/text/emph/keyword/text() return <text>{$a}</text>

TABLE 1

 1 Auxiliary functions details.Given the variable paths V bound to XML nodes according to S, returns the index path positions F in S-records corresponding to the XML node IDs.Given a list of variable paths V bound to XML nodes, atomic values or collections, according to S, returns the index path positions F of the values of those variables in S-records. S; V → id,v F "Union" of the two previous functions.Given a list of CTPs L, returns the CTPs L ′ where variables are replaced with corresponding fields in S-records.S; e → e ′ Given an ETP e whose root is a variable in S, builds a new ETP e ′ rooted with the corresponding field position in S-records. S; ρ → ρ ′As above (replace ETPs with predicates).

	Signature	Description
	S; V → id F
	S; L → L ′

S; V →v F S1, S2; ρ → ρ ′ Given a predicate ρ referencing variables in tuples in S1 and S2, generates a new predicate ρ ′ referencing field positions in S1and S2-records.

TABLE 3

 3 Query evaluation time (1 node, 34GB).

	Query	Evaluation time (seconds) BaseX Saxon-PE Qizx/open PAXQuery
	q1	206	145	90	72
	q2	629	OOM	OOM	125
	q3	600	OOM	OOM	120
	q4	189	OOM	84	51
	q5	183	125	183	51
	q6	233	162	109	70
	q7	181	111	88	54
	q8	599	OOM	OOM	126
	q9	TO	OOM	OOM	94
	q10	OOM	OOM	OOM	229
	q11	TO	TO	TO	236
	q12	TO	OOM	OOM	113
	q13	TO	OOM	OOM	424
	q14	OOM	OOM	OOM	331

TABLE 4

 4 Query evaluation time (8 nodes, 272GB).

		Evaluation time (seconds)
	Query	BaseX Hadoop-MR Stratosphere-PACT BaseX	PAXQuery
	q1	465	66	70
	q2	773	282	189
	q3	762	243	172
	q4	244	72	58
	q5	237	72	57
	q6	488	70	73
	q7	245	74	62
	q8	576	237	206
	q9	OOM	OOM	114
	q10	OOM	OOM	299
	q11	OOM	OOM	334
	q12	OOM	OOM	132
	q13	OOM	OOM	456
	q14	OOM	OOM	683

  fn 12 if r is not optional or any variable path pr labeling a leaf

	13
		under r leads to a non-⊥ value within t then
	14	fr ← ()
	15	if r is labeled with an element (resp. attribute) name
		l then
	16	fr ← new element/attribute labeled l
	17	else
	18	if r is a leaf labeled with variable path p then
	19	fr ← t |p
	20	if fr is not () then
	21	add fn as child of fr
	22	else
	23	fr ← fn
	24	append fr to f
	25	output f ; exit

  b) Resulting tuples after applying ETPs to a given tuple.

	Fig. 19. Sample ETPs and corresponding navigation
	results.
					root, people
	p1, person			p2, person			p3, person
	n1, name	a1, address	n2, name	a21, address	a22, address	n3, name	a3, address
	"Martin"	z1, zip	c1, city	"Bernard"	z21, zip	c21, city	z22, zip	c22, city	"Dubois"
		"75"	"Paris"		"69"	"Lyon"	"75"	"Paris"

  t 2 ∈ A 2 and ρ(t 1 , t 2 ) holds}} As stated previously, the join predicate is expressed in disjunctive normal form (DNF). Left outer join (ojoin l ρ ). Given two streams of tuples produced by A 1 , A 2 and a DNF predicate ρ, ojoin l ρ (A 1 , A 2 ) returns the pairs of tuples satisfying ρ, plus the tuples from the left input without a matching right tuple. Its semantics are defined as follows: ojoin

  t 1 , t 2 )}} where ⊥ A2 is a tuple having the schema of the tuples in A 2 and ⊥ values bound to its variables. As customary of left outer joins, the left tuples without a matching right tuple are concatenated to⊥ A2 . A2 ) | t 1 ∈ A 1 , ∃t 2 ∈ A 2such that ρ(t 1 , t 2 ) holds}} Thus, each tuple from the left input is paired with a new nested variable $r, encapsulating all the matching tuples from the right-hand input. If the left tuple does not have a matching right tuple, $r must contain a tuple ⊥ A2 .

	Nested left outer join (nojoin l ρ ). The operator semantics are
	defined as: nojoin l ρ (A

1 , A 2 ) = {{t 1 + ($r, (t 21 , t 22 , . . . , t 2n )) | t 1 ∈ A 1 and t 21 , t 22 , . . . , t 2n ∈ A 2 and ∀k ∈ {1..n}, ρ(t 1 , t 2k ) holds }} ∪ {{t 1 + ($r, ⊥

$ei := $ic/site/regions/europe/item for $p in $pc/site/people/person let $pn := $p/name/text() let $a := for $t in $ca, $i in $p/@id, $b in $t/buyer/@person where $i = $b return let $n := for $t2 in $ei, $ti2 in $t2/@id, $ti in $t/itemref/@item where $ti = $ti2 return $t2 let $in := $n/name/text() return <item>{$in}</item> return <person name="{$pn}">{$a}</person> Query 11: List all persons according to their interest; use French markup in the result. $cc := collection( ' XMarkClosedAuctions ' ) for $p in $pc/site/people/person let $n := $p/name/text() let $a := for $t in $cc/site/closed_auctions/closed_auction, $b in $t/buyer/@person, $i in $p/@id where $b = $i return $t let $c := count($a) return <item person="{$n}">{$c}</item> Query 13: List the name of users in France and the items that they bought or sold in an auction. let $pc := collection( ' XMarkPeople ' ), $cc := collection( ' XMarkClosedAuctions ' ) for $p in $pc/site/people/person, $i in $p/@id, $ad in $p/address/country/text() let $a := for $c in $cc//closed_auction, $b in $c/buyer/@person, $s in $c/seller/@person let $ir := $c/itemref where $i = $b or $i = $s return $ir let $n := $p/name where $ad = ' France ' return <res>{$n,$a}</res> Query 14: For each rich person, list the number of carsrelated items currently on sale whose price does not exceed 0.02% of the person's income. let $pc := collection( ' XMarkPeople ' ), $oc := collection( ' XMarkOpenAuctions ' ) for $p in $pc/site/people/person let $l := for $o in $oc/site/open_auctions/open_auction, $i in $o/initial/text(), $si in $p/profile/@income, $a in $o/annotation//text/text() let $x := 5000 * $i where $si > $x and contains($a,"car") return $i for $li in $p/profile/@income let $n := count($l) where $li > 200000 return <items person="{$li}">{$n}</items>