Query optimization in JSON database systems lacks the robustness of more mature databases. To address this, we propose an algebra to manipulate collections of JSON documents. The algebra is defined at 3 levels: the individual document level; the collection (core) level; and the collection (extended) level. The third level includes operators that can be defined in terms of the second level, but are useful for optimization. The operators in all levels are tailored to JSON data. We also define equivalences that allow the generation of multiple (logical) query trees for a single query, therefore providing the basis for cost-based query optimization for JSON query languages.
The popularity of JSON as a data exchange format has led to the development of several data systems focused on JSON data (Asterix, MongoDB, CouchDB, and others). In spite of this, there is still relatively little work on query optimization for such systems. Several factors have contributed to this sparseness of results. First, there is no standard query language for JSON [1]; each system ofers its own query language. This makes it hard to propose and analyze general solutions. Another factor is that JSON, as a data model, presents several issues that are dificult to deal with. The heterogeneity of the data, and its mixed structure presents challenges to developing a query language with formal semantics: JSON is diferent from other hierarchical models like nested relations [2] and XML [1], which means that past research on nested relational algebra (NRA) or query languages for XML cannot be used without a substantial revision [2].
The goal of this research is to design a query language that: a) is closed on JSON (takes only JSON data as input, 2. Background and Related produces only JSON data as output); b) is declarative and has formal semantics; and c) provides a good base for Research (logical) query optimization. Our approach is based on Even though there are a few diferences in notation and defining an algebraic language, i.e. one that provides op- some ancillary aspects, the vast majority of the literature erators that take as input (and produce as output) JSON treats JSON data as an edge-labeled tree structure, with data. We divide the definition of the algebra in 3 levels: some constraints imposed by the JSON standard1. The level 1 manipulates individual documents; level 2 ma- labels of the outgoing edges of a document node are called nipulates collections (defined as multisets of documents), keys, and each subtree represents a value. For leaves, the and level 3 provides additional operators for collections value is an atomic value assigned to it; for internal nodes, the value is either a document or an array. Moreover, all internal nodes are of document type or of array type.
For a document node, all outgoing edges must be labeled by distinct strings; For an array node, the outgoing edges are labeled by “1", “2", “3", . . . and they are considered that are not primitive (they can be defined using level 2 operators) but are helpful for optimization. Finally, we provide a set of equivalences for the algebra that can be used to generate alternative query plans for a given query.
We stress that, even though the operators resemble those of Nested Relational Algebra, they are defined anew and tailored to JSON data. Thus, although some of the equivalences shown extend known relational equivalences to the JSON framework (others are new), they had to be proven from scratch.
The rest of this paper is structured as follows: Section 2 introduces the new challenges that the JSON data model presents and overviews related research. In Section 3, we introduce the 3 algebra levels. Due to lack of space, levels 1 and 2 are greatly summarized; we expand on level 3 as it is the most relevant for query optimization.
Next, in Section 4, we present the main properties of the operators introduced in the previous Section. Finally, we close the paper with an overview of future research.
ordered. Finally, the root node is always of document may be present. Similar problems exist with the unnest type. Thus, a JSON document means a document/tree operator. This in turn causes uncertainty as to which that respects all the constraints listed here. properties of NRA hold/do not hold when dealing with
Most JSON databases deal with collections of docu- JSON. For instance, the unnest of the nest of a relation ments. The definition of ’collection’ is not part of the is supposed to yield back, but this may not be the case JSON standard, and no universal definition seems to ex- with JSON data: assume a collection with documents ist. However, most existing systems treat collections as {a: 1, b: "foo"}, {a: 1} multisets, that is, groups of documents with no order If we nest by attribute ’a’, in most systems we would and where repetitions are allowed. We will follow this get practice. {a: 1, b:["foo"]}
Existing approaches to handling JSON data, like us- Since the second document does not contribute to the ing Nested Relational Algebra (NRA) or XML query lan- result, it is lost; no version of unnest will allow us to guages like XQuery, are not fully appropriate for JSON, recover the original collection. as JSON is diferent from nested relations or XML. In the Most past research on query languages for XML has nested relational model, the set constructor and the tuple focused on supporting XPath and XQuery. This has inconstructor strictly alternate [3], while in JSON, arrays lfuenced the development of approaches like JSONPath (the closest construct to nested relations) may contain [5, 6]. Document query languages need paths but tend to documents, atomic values or other arrays. Moreover, not navigate across axes like XPath. Research efort [ 1], nested relations have a fixed schema, and all tuples in a which adapts elements of XPath to work on JSON data, is relation must follow the schema. XML and JSON, on the a step in the right direction, but we believe it is only part other hand, are semi-structured; but they are diferent of the answer. One must also have operators that work on from each other in several aspects. First, in XML all data is collections of documents. In this sense, our work can be ordered (although most query languages for XML do not considered complementary to XPath-based approaches take advantage of this order), while JSON mixes ordered [5, 6, 1]: the navigation capabilities presented there could and unordered data. Second, JSON is structurally deter- be incorporated into the operators of our language, espeministic (in a tree representing a JSON document, each cially the selection operator (see next section).2 path from a leaf to the root is unique), while XML, is non- The rapid development of systems for JSON data has deterministic [1]. Related to this, JSON deals with groups led to a proliferation of diferent query languages -in most of related items by using arrays, while XML, which does cases, without formal semantics. For instance, MongoDB not have arrays, deals with groups of related items by and CouchDB use their own query languages, defined repeating tags. informally ([2]). Query optimization on these systems is
In spite of the diferences, some systems use NRA to mostly rule-based, with limited use of cost-based considdeal with JSON data, for instance, the Proteus system [4]. erations ([7, 8]). A recent proposal, SQL++ ([9]), has been However, the lack of a fixed schema leads to problems. adopted by CouchBase and Asterix. SQL++ ofers a great In the nested relational model, we can assign a schema to deal of flexibility, as several issues that arise with JSON a nested relational table , ℎ(). The definition data are treated as parameters that can be set by the user. of the operators in NRA depends on this schema. For in- However, SQL++ assumes a data model that is a superset stance, the projection 1,..., () is well-defined only of JSON, and it also lacks formal semantics. No query if {1, . . . , } ⊆ ℎ(). But given a collection optimization for SQL++ has been developed so far. Jaql , it can be the case that {1, . . . , } are not attributes ([10]) is a scripting system designed to run on Hadoop. of document for some ∈ -even as they are in Queries are expressed as sequences of statements, and other documents. One must decide what it means to query optimization is rule-based and guided by heurisproject on {1, . . . , } when some of these attributes tics. RumbleDB ([11]) is a system to process JSON queries are not present -in the extreme case (when no such at- using the JSONiq query language. JSONiq [12] provides tribute is present), should we return the empty docu- a declarative query language based on XQUERY FLWOR ment? In the case of projecting inside arrays, NRA of- expressions. J-Logic[13] gives a query language based fers no guidance. Other NRA operators are also afected on non-recursive Datalog. However, this work does not by this problem. The nest operator is traditionally de- discuss query optimization. The dificulty of querying noted by (1,...,)(), where ∈/ ℎ() and heterogeneous documents, which may cause the user 1, . . . , ∈ ℎ(). Intuitively, is ’grouped to write a query with incorrect paths, has motivated reby’ all attributes in ℎ() − { 1, . . . , }, and on search to correct such paths using information about the each group, the values of attributes 1, . . . , form a data ([14, 15]). nested relation called . Clearly, this definition does not work when diferent documents may have diferent at- 2Iattoisr,nwothaibleleotuhraatp[1p]rofoaccuhsiessctlhoesearntaolytshies mofoMreognegnoeDrBal’safggirnedgaotpioenrtributes ’outside’ of 1, . . . , -or not all of 1, . . . , pipeline.
We adopt the standard definition of JSON data, and see a JSON document as an edge-labeled tree. We use , ′, . . . as variables over documents. In the language, paths in the document/tree are denoted by sequences of labels (denoting the labels of the edges). Of course, an arbitrary sequence of labels may not exist in a given tree; in such cases, we say the path is not realized in the document. • merge(1, 2), where 1 and 2 are JSON documents, Complete paths (from the root node of the document is an operation that ’puts together’ both documents to a leaf) are called attributes. We use , 1, . . . , as under a common root. For instance, variables over paths, and , ′ as variables over sets merge({a: 1, b:{c:2, d:3}}, {e: 4, b: [5, 6]}) = {a: 1, b:{c:2, d:3}, of paths. The function (, ) provides the value of e: 4, b: [5, 6]} path in a document . When is not realized in , In particular, (, {}) = ({}, ) = . (, ) returns the special value undefined. When Note that have a technical issue in this operator: if the is realized, (, ) returns the subtree rooted at same path exists in both 1 and 24, the result is not a the node where the path ends, for internal nodes (note legal JSON document. The situation is similar to that that this may be a document or an array); when is an of (nested) relational algebra and Cartesian product, attribute (complete path), (, ) returns the atomic so we adopt the same solution: we assume a rename value attached to the leaf (this may include null). The operator allows us to change labels in a path as needed. schema of a document , in symbols ℎ(), is the set of all attributes in the document. A collection, denoted by ⟨, ⟩, is treated as a multiset of JSON documents. We use , 1, etc. as variables over collections. Since documents in a collection may have diferent schemas, we also define: path is realized in the document ( ∩ℎ() = ∅), the empty document (denoted {}) is returned. – This works for complete and incomplete paths. For instance, in = { : 1, : { : 2, : 3}}, () = { : { : 2, : 3}}; .() = { : { : 2}}.
Also, .() = () = ∅. In particular, we allow picking (parts of) values from within an array. () = ⋃︁ ℎ()
∈
When comparing two documents (especially in section 4) we use weak equality, which ignores order within arrays, i.e. two arrays are considered equal if they contain the same values, even in a diferent order.
We now describe the three levels of the algebra. Due to lack of space, for levels 1 and 2 we only describe operators at an intuitive level and mention only features that are particular to JSON data. We provide a full definition of level 3 operators, which are the focus of this paper.3
The first level focuses on operators that work on individual documents. This level allows us to define JSON documents as an abstract data type, independent from the representation of data, be it BISON, Mison [16], Pison [17] or any other schema. The operators are: • projection: given a set of paths , document , the projection of from , denoted (), takes the subtree of formed by all paths with a prefix in . Note the following, non-standard behavior: – if some paths are realized and others are not, the projection picks the paths that are realized in the document and ignores the rest. In particular, if no
Technical Report from the authors. • () (called the unnest of by ), where is a JSON document and is a path. This operator returns a collection, i.e. a multiset of documents, defined as follows: if (, ) is an array, for each value in the array, we create a document composed of: all of except the array , and the single value . If (, ) is not an array, () = ⟨⟩. • (), where is a JSON document and is a condition. Conditions are defined as usual: if , 1, 2 are paths, a constant, and a comparison operator, , 1 2, ∃ are conditions. In addition, conjunction, disjunction, and negation of conditions are also conditions. () returns one of ’true’, ’false’, ’unknown’ or ’undefined’ by evaluating in . The evaluation process is defined as usual; ’undefined’ is returned when a path used in is not realized in and ’unknown’ when a path used in evaluates to null. It is here that other approaches like JSONPath ([6]) could be incorporated into the language.
The second level provides basic operations on collections. The operators include project, select, nest, unnest, Cartesian product and union, intersection and diference , suitably modified from their usual meanings in (nested) relational algebra.5 As in level 1, we only provide a summary description. 4In fact, it’s enough that a path in 1 and a path in 2 start with the same label. 5A full description of this level (with some added operators like aggregate and order, which support typical query capabilities) is in the Technical Report.
and 2, then all documents where both paths are null form a group; all documents where both paths are not realized generate another group; all documents where 1 is not realized, 1 is realized and has the same value, form another group, and so on.
To accommodate group by/aggregate queries, we further specify what is collected under : for an aggregate function, we need to specify which function and to which attribute it applies. We assume, when no aggregate is specified, that the rest of the document (all but 1, . . . , ) is gathered as a value of the array . When a document has no ’rest’, an empty document is deposited in the array. Finally, we use a special aggregate function ’push’ that concatenates arrays, i.e. push([2, {a: 1}], ["foo", 4]) = [2, {a: 1}, "foo", 4]. 3.3. Third Level: Macro-operators • The selection operator, written (), takes as input a collection and as parameter a condition , defined as above, and picks documents within that satisfy the condition (with slight abuse of notation, we use for this operator, as context will help make clear which selection we are using). By rejecting documents where the condition evaluates to ’undefined’ or ’unknown’, we are following SQL semantics –obviously, this could be changed if desired.
() = ⟨ ∈ | () = ⟩
needed; we include all three at this level for simplicity.
9An issue that may introduce ambiguity in versions of NRA ([18]).
1 × 2 = ⟨(1, 2) | 1 ∈ 1, 2 ∈ 2⟩ Note that we assume renaming as needed. As in the case of the traditional operator, if either collection is empty, the product returns the empty collection. • The projection operator () takes as input a collection and as a parameter a set of path expressions .
Again, we abuse the notation to use the same symbol as the previously defined projection. While a projection on an individual document may return an empty docu- • the union, intersection and diference operators each ment, the projection on collections returns non-empty take as input two collections 1 and 2. These operadocuments only. Not all document systems follow this tors work exactly as in the traditional case for multisemantics;6 but this choice makes some properties that sets; for instance, the union 1 ∪ 2 is the collection of follow simpler and cleaner. documents in either 1 or 2, repeated as many times as the sum of their appearances; similarly for inter () = ⟨ () | ∈ ∧ () ̸= {}⟩ section 1 ∩ 2 and diference 1 − 2. Note that, in • The Cartesian product operator takes as input two col- the definition of intersection and set diference, ’weak’ lections 1 and 2: equality (where the order within arrays is ignored) is used to compare documents.8 The third algebra level contains operators which could be expressed using the ’basic’ ones, but that we want in our • the unnest operator takes as input a collection and as algebra for optimization reasons. A typical example of parameter a path expression . As in the case of selec- this is the (relational) join. We believe that in document tion and projection, we reuse the symbol for document algebra, several operations are similar to join in this reunnest. spect. Another important reason to have a separate level () = ⋃︁ () for ’basic’ operations is that having a short list of simple ∈ operators makes finding and proving equivalences much
Note that we use multiset union. easier. • the nest operator, :1,..., (), takes as input a col- The main additional operators are: lection and as parameter the path expressions : • join: as in the relational case, a join is a selection that 1, . . . , . Unlike nesting in NRA, here 1, . . . , follows a Cartesian product. Defining join in this mandenote the nesting (common) attributes, and , where ner settles what is meant exactly by a join with comwe want to place the array created by gathering the plex elements, regardless of whether the comparison nested (pushed down) attributes -which, in any doc- involves top-level attributes or nested ones.9 ument , are all attributes not among 1, . . . , . To form groups, all documents that have the same values 1 ⋉⋊ 2 = (1 × 2) for all paths in 1, . . . , are gathered. Here, ’same values’ includes the case where some paths are not realized in a document, so that their values are undefined.
For the purposes of nesting, nulls are all equal, and so are ’undefined’. 7 For instance, if we nest by paths 1 • semijoin, outerjoin, and antijoin: once joins are defined, we can also define these closely related operators. An important diference with the relational case is that documents in a collection without a match in the other are simply left as they are in the results -due to the lack of schema, no padding is necessary. Whenever 6For instance, MongoDB allows returning empty documents. 7In the absence of a standard, we follow SQL semantics. An alternative is to let the user decide how to deal with such cases, as is done in [9]; however, such approaches make it very hard to prove properties.
(1) ∩ (2) = ∅, the definition of such operators is similar to that of (flat, nested) relational algebra; otherwise, a problem arises that requires careful renaming. In order to avoid this, here we provide a non-standard definition that avoids the problem: (left semijoin) 1⋉ 2 = { ∈ 1 | {} ⋉⋊ 2 ̸= ∅} (left antijoin) 1 ◁ 2 = { ∈ 1 | {} ⋉⋊ 2 = ∅} (left outerjoin) 1 ⊐◁▷ 2 = (1 ⋉⋊ 2)∪(1◁ 2) • nest-join (NJ) and nest-outerjoin (NOJ): when there exists a 1-M relationship between two entities 1 and 2, document databases ofer the possibility of storing the data using embedding (in which case each document in 1 contains an array of 2 sub-documents) or in two diferent collections, one for 1 and another for 2, with some attributes serving as ’foreign keys’ to maintain the links among documents. In the latter case, a join will put together documents in 1 with related documents in 2, and a nesting by (the attributes of) 1 will result in a structure similar to the embedding.
The nest-join is an operation that combines both the join and nesting in a single step; similarly, we define nest outerjoin The goal here is to provide a target for optimization, since implementing this operator with a single algorithm in a single pass over the data can lead to improved plans.10 Note the similarity with ideas proposed in literature under names like groupjoin ([19]).
,(1, 2) = :(1)(1 ⋉⋊ 2) The nest-outerjoin operator is defined in the obvious similar manner:
,(1, 2) = :(1)(1 ⊐◁▷ 2) • narrow selection: when evaluating a condition involving a single value against an array in document , we ofer operators all and some, similar to those of SQL, to specify how the condition is to be interpreted. The ifnal result of such a comparison, however, is a single decision on whether qualifies for the answer. But what is sometimes wanted is the document , but with only those elements in the array that make the condition true (in other words, the array is filtered). A narrow selection ′ (), where is a condition as just described, does exactly this. For instance, in document {a:1, b:[2, 3, 4, 5]}, narrow selection ′>3 returns11 document {a:1, b:[4, 5]}. It is not hard to see that ′ can be defined in terms of basic operators (first, unnest the input; then apply a (regular) selection; ifnally, nest the result):
′ () = ( ( ())) 10In MongoDB’s aggregate pipeline, only this operator (called
lookup) is supported; join and outerjoin are not. 11Paths with arrays in a condition have an existential reading.
Note that if no element in the array makes the condition true, the whole document is erased from the result. • extended nest: sometimes we may want to nest documents creating several arrays. For instance, in a collection with documents {a:1, b:2, c:3}, {a:1, b:4, c:5} we may want to nest by ‘a’ and separate the ‘b’ and ‘c’ elements, to create result {a:1, b:[2, 4], c:[3, 5]}. The extended nest operator allows the specification of more than one nested component, to achieve exactly this result. It would seem that this can be achieved with regular nesting, by ifrst projecting the input collection into {a, b} and nesting the result by ’a’; projecting again the input into {a, c} and again nesting the result by ’a’; and ifnally joining the two previous results: ,,() = 1:( ,()) ⋉⋊1=2 2:( ,()) However, for this to work in general, we need to assume order -which, up to now, we have disregarded, even inside arrays. To see why, assume collection with documents ⟨{ : 1, : 2, : 3}, { : 1, : 4}, { : 1, : 5}⟩. If we extend nest all documents by , collecting and , we want to get the document { : 1, : [2, 4, {}], : [3, {}, 5]}, not { : 1, : [2, 4], : [3, 5]} (among other reasons, it’s the only way that extended nest and extended unnest will be inverses of each other). Note that nest will generate empty documents to mark where values of b or c are not present, but the resulting arrays need to be ’paired up’ consistently. Thus, in the definition of this operator, we assume that nesting has generated an ordered array, and has done so using the same order in both nestings.
Note that, for this operator, we require the user to specify ’grouping’ attributes but also specific ’grouped’ attributes to be collected in the array. It can be shown that this definition works for an arbitrary number of arrays. • extended unnest: similarly, the unnest operator is extended to maintain symmetry. Note that a regular unnest, applied twice to the previous result (document {a:1, b:[2, 4], c:[3, 5]}) in any order (even if applied separately to projections of the result and then combined) would yield not the original collection, but one with 4 documents (with all combinations of values in ’b’ and ’c’). Thus, the purpose of the extended unnest is to have an operation that undoes exactly what the extended nest does: the extended unnest of {a:1, b:[2, 4], c:[3, 5]} yields collection ⟨ {a:1, b:2, c:3}, {a:1, b:4, c:5} ⟩.
,,() = ( ( ,())) ⋉⋊ ( ( ,())) Note that both and must be paths to arrays.
First, we observe that the second level of the algebra (and, by extension, the third) have closure: all operators take in collections of JSON documents and produce as output collections of JSON documents. This does not apply to the first-level operators; however, these operators are not meant to be composed but used as ’auxiliary methods’ to manipulate individual documents.
To support query optimization, next we list properties of individual operators, both in the core (second-level) and the extended (third-level) of the algebra.12 Lemma 4.3. For any set of paths , 1, 2, collection , • ( ()) = (). • If 1 ⊆ 2, 1 ( 2 ()) = 1 ().
The behavior of projection with other operators is described by the next lemma.
Lemma 4.4. For any set of paths , condition , • (1 ⋉⋊ 2) = 1 (1) ⋉⋊ 2 2, where 1 =
∩ (1) and 2 = ∩ (2). • (1 ∪ 2) = (1) ∪ (2).
Note that (1 ∩ 2) ̸= (1) ∩ (2), as there may be 1 ∈ 1, 2 ∈ 2, 1 ̸= 2 such that (1) = (2). For the same reason, (1 − 2) ̸= (1) − (2). However, a weaker property holds: The reason to define these operators is that it is clear Another basic observation is that if a projection uses that a direct implementation can yield much better per- paths that are not realized in any document in a collection, formance than a rewriting. Consider, for instance, the such paths can be ignored.13 On the other hand, at least narrow selection as a one-pass operation on a collection one path must be present for the projection to consider a versus its rewriting. Also, the optimized implementation document. of the extended nest could easily enforce the same order for array formation, as it could do one-pass sorting/hash- Lemma 4.2. For any set of paths = {1, . . . , }, ing over the collection. collection ,
Other extended operators can be defined, for instance, • () = ∩()() to capture similar capabilities in SQL –like window ag- • () = ( ∃1∨...∨∃ ()) gregators or an extension matching the CASE statement.
On top of this, extended operators proposed for the re- The basic properties of projection are given in the next lational case may make sense here –for instance, the lemma.
MDA (Multi-Dimensional Aggregation) of [20].
(1 ∩ 2) ⊆ (1) ∩ (2). 4.1.1. Projection The behavior of projection in combination with nest and unnest is more complex, due to the issue of dupliFirst, we observe that our projection does not remove cates. To illustrate, the unnest of document { : 1, : duplicates. In our algebra, duplicate removal is accom- [2, 3]} would create two documents, { : 1, : 2} and plished by using nesting without any aggregate or gather- { : 1, : 3}, so that a projection on would need ing of results in an array a case denoted by ∅:1,..., (). to return two copies of { : 1} -hence, it cannot be This simply returns one document for any repeated com- pushed down. As for nesting, the opposite efect hapbination of values of 1, . . . , in . However, the nest pens: on the grouping attributes, nesting removes duplias defined will produce an empty document if there ex- cates. For instance, projecting on over the collection ists one or more documents in the input where none of ⟨{ : 1, : 2}, { : 1, : 3}⟩ would return two copies of 1, . . . , exists. To solve this, we define { : 1}; after a nesting by , the projection would return only one copy. Note that both transformations would 1,..., () = { ∈ ∅:1,..., () | ̸= {}} work for systems where projection removes duplicates; hence, we have the following.
It follows from this that projecting after a nest can be done simply by nesting on the projected attributes.
Lemma 4.1. If , ′ are sets of attributes with ⊆ ′, then ( ∅: ′ ()) = ().
For instance, if we have ( :,()) on collection ⟨{ : 1, : 2, : 3}, { : 1, : 2, : 4}⟩, the result is { : 1}, which we could obtain by simply doing a grouping by . 12Unfortunately, due to the lack of space, all proofs are omitted, and will be available on the Technical Report.
Lemma 4.5. For any set of paths , collection , • if ∈/ , ( () = () • if ∈ , ( :()) = () 13Note that is set of paths and () a set of attributes (complete paths); in the lemmas, their intersection denotes the set of ∈ such that is a prefix of some attribute in (). 4.1.2. Selection First, we define an auxiliary concept that will be useful.
Definition 4.6. Let be a condition, then ( ) is the set of paths mentioned in : • (1 2) = {1, 2} • ( ) = (∃) = {}
As for nest, we can decompose the nesting into two steps by using the ‘push’ aggregate on the second one (note that the first nesting creates arrays, so ‘push’ will combine such arrays).
Lemma 4.14. For any collections 1, 2, set of paths , : (1 ∪ 2) = ℎ(): ( : (1) ∪ : (2) (1 ⋉⋊ 2) = ( 1 (1)) ⋉⋊ ( 2 (2))
An immediate consequence of this lemma is that, if ( ) ⊆ (1), (1 ⋉⋊ 2) = (1) ⋉⋊ 2; and if ( ) ⊆ (2), (1 ⋉⋊ 2) = 1 ⋉⋊ (2).
Lemma 4.9. For any condition , we have: • ( ∧ ) = ( ∨ ) = ( ) ∪ ( ) As an example, let be the collection ⟨{ : 1, : 2}, { : 1, : 3}, { : 1, : 4}⟩ Lemma 4.7. For any conditions 1 , 2, be split into 1 = ⟨{ : 1, : 2}, { : 1, : 3}⟩ and • 1 ( 2 ()) = 2 ( 1 ()) 2 = ⟨{ : 1, : 4}⟩. Then • 1∧ 2 () = 1 ( 2 ()) :() = ⟨{ : 1, : [{ : 2}, { : 3}, { : 4}]}⟩; Lemma 4.8. Let , be conditions, with expressible as :(1) = ⟨{ : 1, : [{ : 2}, { : 3}]}⟩; 1 ∧ 2, ( ) ⊆ (), = 1, 2, then :(2) = ⟨{ : 1, : [{ : 4}]}⟩; ℎ():( :(1), :(2)) = ⟨{ : 1, : [{ : 2}, { : 3}, { : 4}]}⟩. Note that this idea can be extended to traditional (numerical) aggregates, and is similar to the way many modern distributed systems compute aggregate queries ([21]). 4.1.4. Nest and Unnest • ( ()) = ( ( ∪ ( )())) • (1 ∪ 2) = (1) ∪ (2) • (1 ∩ 2) = (1) ∩ (2) • (1 − 2) = (1) − 2= (1) − (2) Lemma 4.10. Let be a condition with ( ) ⊆ Then
( : ()) = : ( ())
That is, we can push a projection past a nest if all attributes in the condition are among the grouping attributes. This is similar to HAVING in relational scenarios: the selection qualifies all tuples in a group, or none. 4.1.3. Union Union properties are especially important for distributed computation: a collection distributed over the nodes of a cluster can be represented as a union of ‘pieces’, so when an operator can be ’pushed down’ past union, this means that it can be executed in the nodes of the cluster. In this context, lemma 4.12 is the basis for a ‘broadband’ join. • 1 ∪ 2 = 2 ∪ 1.
Lemma 4.11. For any collections 1, 2, 3, • (1 ∪ 2) ∪ 3 = 1 ∪ (2 ∪ 3).
Lemma 4.12. Let 2 = ⋃︀ =1 2 ; then 1 ⋉⋊ 2 = 1 ⋉⋊ ⋃︁ 2 = ⋃︁ (1 ⋉⋊ 2 )
=1 =1
We can push unnest past a union: Lemma 4.13. For any collections 1, 2, path , (1 ∪ 2) = (1) ∪ (2)
Nest and unnest are hard to combine; it is not true, in general, that :1,..., ( ()) = . To see this, let = ⟨{ : 1, : [2, 3]}, { : 1, : [4, 5]}⟩. Then the unnest of will produce a collection ⟨{ : 1, : 2}, { : 1, : 3}, { : 1, : 4}{ : 1, : 5}, ⟩, and the nesting . by will produce ⟨{ : 1, : [2, 3, 4, 5]}⟩. This is a well-known issue in NRA ([3]). However, it could be the case that unnesting acts as the inverse of nesting. This does not happen in JSON query languages with similar operators (for instance, MongoDB), but the following states that this property holds in our algebra.
Lemma 4.15. For any paths 1, . . . , , collection ,
( :1,..., () =
Recall that we use ⋉⋊ for joins, ⊐◁▷ for (left) outerjoin, ⋉ for (left) semijoin and ′ for narrow selection.
Lemma 4.16. (Joins) Joins are associative and commutative:
(1 ⋉⋊ 2) ⋉⋊ 3 = 1 ⋉⋊ (2 ⋉⋊ 3) Lemma 4.17. (Outerjoins, part 1) Whenever ⊆ (1), for any condition , (1 ⊐◁▷ 2) = (1)
Note that this does not work with projection without duplicate removal, since the outerjoin may introduce duplicates whenever a document in 1 matches more than one document in 2.
Following previous work [
′ ( :1,..., ()) = ( ( )()) attribute set if ( ) ⊈ – since is guaranteed not selection can be pushed down. If the condition attributes to be true when attributes in are not present on the are in , then the selection cannot be pushed down as it input. may also afect (and the same for condition attributes in ). As an example, in a collection with two documents Lemma 4.18. (Outerjoins, part 2) Let be a condition {a:1, b:2, c:5}, {a:1, b:4, c:6} grouping by with ( ) ⊆ (2), an arbitrary condition, then , collecting and , we get
(1 ⊐◁▷ 2) = 1 ⋉⋊ 2 {a:1, b:[2, 4], c:[5, 6]} A selection on afThat is, the outer join becomes a join when a selection fects the whole group, so either both documents in the involves attributes from the right side only -as this im- input pass it or don’t. A selection on , on the other plies that it ’rejects absents’ on the left side. Technically, hand, will take out the accompanying values of . For this holds only if (1)∩(2) = ∅; we assume instance, selecting > 3 in the input collections takes renaming when this is not the case. out the first document, and with it the value 5 of . But a narrow-select on the output collection wouldn’t take out Lemma 4.19. (Narrow Select, Part I) Narrow select and the value. A similar argument can be made with select unnest commute: for any condition , and unnest. The following lemma formalizes this: Lemma 4.21. Let be a condition with ( ) ⊆ Then .
As an example of the first statement, given collection with single document { : 1, : [2, 3, 4]}, ′≥ 3()) = ⟨{ : 1, : [3, 4]}⟩; and unnesting this yields ⟨{ : 1, : 3}, { : 1, : 4}⟩. If we apply the unnest first to , we Finally, we check that extended nest and unnest are get the collection ⟨{ : 1, : 2}, { : 1, : 3}, { : 1, : ‘well-behaved’ extensions of nest and unnest, in the fol4}⟩. If we start with this collection and run the same lowing sense: operators, we have an example of the second property. Lemma 4.22. Extended unnest and extended nest are
For the following property, we first need an additional inverses of each other, similarly to unnest and nest: definition: given condition , path , we say that is ,,(,,()) = p-centered if all paths in ( ) have as a prefix. Then, ,,(,,()) = the flattening of (in symbols, ( )) for p-centered , is defined as the condition obtained by substituting This is enabled by the caveat, noted when defining all paths . ∈ ( ) by (i.e. by removing the prefix the extended nest and extended unnest, that there is an from all paths in ). Constants and operators remain the assumption that order is used to make sure that elements same. inside the arrays are matched.
(,,()) = ,,( ()) (,,()) = ,,( ()) The same holds using ′ instead of .
Lemma 4.20. (Narrow Select, Part II) The narrow selection of a nest-join is the same as the nest-join with a regular select pushed down: let be a condition with ( ( )) ⊆ (2), then We have introduced an algebra for JSON documents with all operators well-defined in the presence of heterogeneous documents. We have designed the algebra in 3 ′ (1 , 2) = 1 , ( )(2) levels: a first one with operators to manipulate single The same holds true for the nest-outerjoin. documents; a second one with operators that manipulate collections of documents; and a third one also at the col
As an example, let 1 = { : 1, : 2} ∈ 1, 2 = lection level but with derived operators, which are not { : 1, : 4} and 3 = { : 1, : 5} both in 2; a (left) strictly necessary but ofer opportunities for optimization. nest-join of 1 and 2 on condition = will contain We have shown algebraic properties that can be used to the document { : 1, : 2, : 1, : [{ : 4}, { : 5}]}. optimize queries. Our work is independent of physical A narrow select on . > 4 will filter the first element implementation details (JSON formats, algorithms) and of the array, yielding { : 1, : 2, : 1, : [{ : 5}]}. therefore could be adapted by diferent systems, as far as However, if we use a regular selection with condition they ofer a query language that can be translated into > 4 on 2, we eliminate 3, and the (left) nest-join our algebra. We are currently developing a cost-based would combine 1 and 2 to produce the same result. query optimization framework for JSON data, centered
Selection (regular and narrow) can be also pushed past around the proposed document algebra. As part of this efextended nest and extended unnest, under the right con- fort, we will show that the core aspects of existing query ditions. Extended nest divides the cover of the input languages like MongoDB’s aggregate pipeline and SQL++ collection into 3 parts: a ‘flat’ part , an array and an can be translated into our algebra and that doing so ofers array . If the condition attributes are all in , then the opportunities for cost-based optimization.
Mohamed Khalefa is partially supported by NSF Grant Award #2131052.