In this paper, we study MongoDB, a widely adopted but not formally understood database system managing JSON documents and equipped with a powerful query mechanism, called the aggregation framework. We define its formal abstraction MQuery, of which we study expressivity and computational complexity. We show the equivalence of MQuery and nested relational algebra, and obtain (tight) bounds in combined complexity, which range from LOGSPACE to alternating exponential-time with a polynomial number of alternations.
JavaScript Object Notation (JSON) is currently adopted extensively as the de-facto
standard format for representing nested data. JSON organizes data as semi-structured
tree-shaped documents, with a minimalistic set of node types, and as such is commonly
considered a lightweight alternative to XML. JSON documents can also be seen as
complex values [
Following its massive adoption by practitioners, recently JSON has also received
attention in the database theory community. A powerful (Turing-complete, in its full
generality) Datalog-like query language for JSON named JLogic is introduced in [
This is an abridged version of [
Differently from XML, where XQuery is the official standard query language, embraced also by the developer community, so far there is no standard query language for JSON. However, in terms of adoption, the MongoDB aggregation framework3 is currently the most prominent language providing rich querying capabilities over collections of JSON documents, and hence has become the de-facto standard language for JSON. This language is modeled on the flexible notion of a data processing pipeline, where a query consists of multiple stages, each defining a transformation using a specific operator, applied to the set of documents produced by the previous stage. As such, the language is very expressive and rich in features, but it has been developed in an ad-hoc manner, resulting in some counter-intuitive behavior.
We study the formal foundations and computational properties of the MongoDB
aggregation framework, which has many similarities with well-known query languages
for complex values, e.g., nested relational algebra (NRA) [
Our first contribution is a formalization of the JSON data model and of the aggregation framework query language, in which we deliberately abstract away some low-level features of MongoDB: we adopt set semantics (as opposed to bag or list semantics), and we abstract away from order within documents. Our formal language, which we call MQuery, includes the match, unwind, project, group, and lookup operators, roughly corresponding to the NRA operators select, unnest, project, nest, and left join, respectively. In our investigation, we consider various fragments of MQuery, which we denote by M , where consists of the initials of the stages allowed in the fragment.
Our second contribution is a characterization of the expressive power of MQuery obtained by devising translations in both directions between (a suitably defined welltyped fragment of) MQuery and NRA, showing that the two languages are equivalent in expressive power. Our translations are compact (i.e., polynomial), hence complexity results between MQuery and NRA carry over.
Our third contribution is an investigation of the computational complexity of MMUPGL and its fragments. We establish several tight bounds (in combined complexity), which range from LOGSPACE-complete for MM to TA[2nO(1); nO(1)]-complete for MQuery itself. As a byproduct, we also establish a tight lower bound for the combined complexity of Boolean query evaluation in NRA.
In the following, we assume familiarity with nested relational algebra (NRA) [
LIST<T> ::= " j LIST+ <T> LIST+ <T> ::= T j T , LIST+ <T> In this section, we propose a formalization of the syntax and the semantics of JSON documents. With respect to MongoDB, we abstract away the order of key-value pairs within a document.
A MongoDB database stores collections of documents, where a collection corresponds to a table in a (nested) relational database, and a document to a row in a table. We define the syntax of documents. Literals are atomic values, such as strings, numbers, and Booleans. A JSON object is a finite set of key-value pairs, where a key is a string and a value can be a literal, an object, or an array of values, constructed inductively according to the grammar in Figure 2 (where the terminals are ‘ff’, ‘gg’, ‘[’, ‘]’, ‘:’, and ‘,’). We require that the set of key-value pairs constituting a JSON object does not contain the same key twice. A (MongoDB) document is a JSON object not nested within any other object, with a special key ‘ id’, used to identify the document. Figure 1 shows a document with keys id, awards, birth, etc. Given a collection name C, a (MongoDB) collection for C is a finite set FC of documents, each identified by its value of id, i.e., each value of id is unique in FC . Given a set C of collection names, a MongoDB database instance D (over C) is a set of collections, one for each name C 2 C. We write D:C to denote the collection for name C.
We formalize JSON objects as finite unordered, unranked, node-labeled, and edgelabeled trees (see Figure 3 for the tree tKN corresponding to the document in Figure 1, where we have additionally labeled nodes with ni, to refer to them later). We assume three disjoint sets of labels: the sets K of keys and I of indexes (non-negative integers), used as edge-labels, and the set V of literals, containing the special elements null, true, and false, and used as node labels. A tree is a tuple (N; E; Ln; Le), where N is a set of nodes, E is the edge relation, Ln : N ! V [ ‘ffgg’; ‘[ ]’ is a node labeling function, and Le : E ! K [ I is an edge labeling function, such that (i) (N; E) forms a tree, (ii) a node labeled by a literal must be a leaf, (iii) all outgoing edges of a node labeled by ‘ffgg’ must be labeled by keys, and (iv) all outgoing edges of a node labeled by ‘[ ]’
Fig. 3. The tree tKN corresponding to the JSON document in Figure 1. must be labeled by distinct indexes. The type of a node x in a tree t, denoted type(x; t), is defined as literal if Ln(x) 2 V , object if Ln(x) = ‘ffgg’, and array if Ln(x) = ‘[ ]’. root(t) denotes the root of t. A forest is a set of trees.
We define inductively the value represented by a node x in a tree t, denoted value(x; t): (i) value(x; t) = Ln(x), if x is a leaf in t; (ii) let x1; : : : ; xm, be all children of x with Le(x; xi) = ki. Then value(x; t) is ffk1:value(x1; t); : : : ; km:value(xm; t)gg if type(x; t) = object, and [value(x1; t); : : : ; value(xm; t)], if type(x; t) = array. The JSON value represented by t is then value(root(t); t). Conversely, the tree corresponding to a value u, denoted tree(u), is defined as (N; E; Ln; Le), where N is the set of all xv such that v is an object, array, or literal value appearing in u, and for xv 2 N : (i) if v is a literal, then Ln(xv) = v and xv is a leaf; (ii) if v = ffk1:v1; : : : ; km:vmgg for m 0, then Ln(xv) = ‘ffgg’, and xv has m children xv1 ; : : : ; xvm with Le(xv; xvi ) = ki; (iii) if v = [v1; : : : ; vm] for m 0, then Ln(xv) = ‘[ ]’, and xv has m children xv1 ; : : : ; xvm with Le(xv; xvi ) = i 1. In the following, when convenient, we blur the distinction between JSON values and the corresponding trees. 3
MongoDB is equipped with an expressive query mechanism provided by the aggregation
framework (see [
An MQuery is a sequence of stages, also called a pipeline, applied to a collection name C, where each stage transforms a forest into another forest. The grammar of MQuery is given in Figure 4. In an MQuery, paths, which are (possibly empty) concatenations of keys, are used to access actual values in a tree, similarly to how attributes are used in relational algebra. We use " to denote the empty path. For two paths p and p0, we say that p0 is a (strict) prefix of p, if p = p0:p00, for some (non-empty) path p00. MQuery allows for five types of stages: – match ', which selects trees according to criterion '. Such criterion is a Boolean combination of atomic conditions p = v, expressing the equality of a path p to a value v, or 9p, expressing the existence of a path p. E.g., for '1 = ( id=4), '2 = (awards.award=”Turing Award”), and '3 = (name = fffirst: ”Kristen”gg), '1 and '2 select tKN, but '3 does not. ' ::= true j p = v j 9p j :' j ' _ ' j ' ^ ' d ::= v j p j [d; : : : ; d] j j ( ? d: d) s ::::== tr'uje!jppj=Pp jj pG=: Avjj 9ppp=Cj::p j _ j ^ P ::= p j p=d j p; P j p=d; P G ::= p=p j p=p; G A ::= p=p j p=p; A MQuery ::= C . s . . s
– unwind !p, which flattens an array reached through a path p in the input tree, and
outputs a tree for each element of the array. E.g., !awards applied to tKN produces
three trees, which coincide on all key-value pairs, except for the awards key, whose
values are nested objects such as, e.g., ffaward: ”Turing Award”, year: 2001, by: ”ACM”gg.
– project P , which modifies trees by projecting away paths, renaming paths, or
introducing new paths. Here P is a sequence of elements of the form p or q=d, where
p is a path to be kept, q is a new path whose value is defined by d, and among all such
paths p and q, there is no pair p, p0 where p is a prefix of p0. A value definition d can
provide for q: (i) a constant v, (ii) the value reached through a path p (i.e., renaming
path p to q), (iii) a new array defined through its values, (iv) the value of a Boolean
expression , or (v) a value computed through a conditional expression ( ? d1: d2).
E.g., bool=(birth=death); cond=((9awards)? contribs: id); newArray=[0;1] applied to tKN produces
ffbool: false, cond: [”OOP”, ”Simula”], newArray: [
For the formal semantics of MQuery, we first observe that a path p over a tree t is
interpreted as the set of nodes reachable via p from the root of t, where the indexes of
intermediate arrays encountered in the tree are skipped. Then, given a forest F and a
stage s, we can define the forest F . s (for a lookup stage, we also require an additional
forest F 0 as parameter) obtained by applying s to F . We refer to [
In this section we characterize the expressivity of MQuery in terms of nested relational
algebra (NRA), and we do so by developing translations between the two languages.
To make it possible to compare MQuery and NRA, we need to define how MongoDB
instances can be viewed as nested relations. In the case of a MongoDB instance with an
irregular structure, there is no natural way to define such a relational view. This happens
either when the type of a path in a tree is not defined, or when a path has different types
in two trees in the instance. Therefore, in order to define a schema for the relational view,
which is also independent of the actual MongoDB instances, we impose on them some
form of regularity. This is done by introducing the notion of type of a tree, which is
analogous to complex object types [
A forest F is of type if all its trees are of type , and it is well-typed if it is of some type . We can then associate to each type a relation schema rschema( ) in which, intuitively, attributes correspond to paths, and each nested relation corresponds to an array in . The names of sub-relations and of atomic attributes in rschema( ) are given by paths from the root in , and therefore are unique. And we can define the relational view rel(F ), of a well-typed forest F .
To define the relational view of MongoDB instances, we introduce the notion of (MongoDB) type constraints, which are given by a set S of pairs (C; ), one for each collection name C, where is a type. We say that a database D satisfies the constraints S if D:C is of type , for each (C; ) 2 S. For a given S, for each (C; ) 2 S, we refer to by C . Moreover, we assume that in rschema( C ), the relation name R C is actually C. Then, for a set S of type constraints and a MongoDB instance D satisfying S, the relational view rdbS (D) of D with respect to S is the instance frel(D:C) j (C; ) 2 Sg.
Finally, we define equivalence between MQueries and NRA queries. To this purpose, we also define equivalence between two kinds of answers: well-typed forests and nested relations. We say that a well-typed forest F is equivalent to a nested relation R, denoted F ' R, if rel(F ) = R. An MQuery q is equivalent to an NRA query Q w.r.t. type constraints S, denoted q S Q, if ansmo(q; D) ' ansra(Q; rdbS (D)), for each MongoDB instance D satisfying S (where ansra(Q; R) denotes the answer to the NRA query Q computed over the nested relation R).
We are now ready to establish the correspondence between NRA and MQuery. On the one hand, we show that MMUPGL captures NRA, while MMUPG captures NRA over a single collection. In our translation from NRA to MQuery, we have to deal with the fact that an NRA query in general has a tree structure where the leaves are relation names, while an MQuery contains one sequence of stages. So, we have to show how to “linearize” tree-shaped NRA expressions into a MongoDB pipeline. More precisely, we can show that it is possible to combine two MMUPG sequences q1 and q2 of stages into a single MMUPG sequence pipeline(q1; q2), so that the results of q1 and q2 can be accessed from the result of pipeline(q1; q2) for further processing. Having defined pipeline(q1; q2), we are ready to show how to translate NRA to MQuery. For a singleton set S = f(C; C )g of type constraints for a collection name C and an NRA query Q over the relation name C (with schema rschema( C )), we can define inductively on the structure of Q a pipeline nra2mq(Q), and then translate Q into the MMUPG query C . nra2mq(Q). We obtain that C . nra2mq(Q) S Q. This result can be generalized to NRA queries over multiple collections, by making use of lookup. We obtain: Theorem 1. MMUPG captures NRA over a single collection, while MMUPGL captures full NRA. Moreover there are polynomial translations from NRA to MMUPG/MMUPGL.
To define a translation from MQuery to NRA we want to exploit the structure, i.e., the stages of MQueries. Hence, we define a translation mq2nra(s) from stages s to NRA expressions such that, for an MQuery C . s1 . . sn, the corresponding NRA query is defined as C mq2nra(s1) mq2nra(sn)4, where we identify the collection name C with the corresponding relation schema in the relational view. However, such a translation might not always be possible, since MQuery is capable of producing non well-typed forests, for which the relational view is not defined. Therefore, we restrict our attention to MQueries with stages preserving well-typedness. It is possible to check whether an MQuery satisfies this property.
The translation mq2nra(s), for well-typed stages s, is quite natural, although it
requires some attention to properly capture the semantics of MQuery. It is given in [
We have studied the complexity of MMUPGL and of some of its fragments, and have
obtained the following results:
– What we consider the minimal fragment, namely MM, which allows only for match,
is LOGSPACE-complete in combined complexity.
– Projection and grouping allow one to create exponentially large objects, but by
representing intermediate results compactly as DAGs, one can still evaluate MMPGL queries
in PTIME. Specifically, MMP is PTIME-hard in query complexity and MMPGL is in
PTIME in combined complexity.
– For MMU, the use of unwind causes loss of tractability in combined complexity,
specifically it leads to NP-completeness, but the language remains LOGSPACE-complete in
query complexity.
– Further adding project in MMUP, or lookup in MMUL, leads again to NP-harness even
in query complexity, although MMUPL stays NP-complete in combined complexity.
– In the presence of unwind, grouping provides another source of complexity, since it
allows one to create doubly-exponentially large objects; indeed MMUG is PSPACE-hard
in query complexity.
– The full language MMUPGL and also the MMUPG fragment are complete for
TA[2nO(1); nO(1)] (i.e., exponential time with a polynomial number of
alternations [
The latter result provides also a tight TA[2nO(1); nO(1)] bound for the combined
complexity of Boolean query evaluation in NRA, whose exact complexity was open [
We have carried out a first formal investigation on the foundations and computational properties of the MongoDB aggregation framework, currently the most widely adopted 4 We follow the convention that (f g)(x) = g(f (x)). expressive query language for JSON. We proposed a clean abstraction for its five main operators, which we called MQuery. We have studied the expressivity of MQuery, establishing the equivalence between its well-typed fragment and NRA, by developing compact translations in both directions. This shows that, despite its design driven by practical requirements, the aggregation framework relies on solid foundations. Moreover, we analyzed the computational complexity of significant fragments of MQuery, obtaining several (tight) bounds. As a byproduct, we obtained also a tight bound for NRA.
We are currently working on applying our results to provide high-level access to
MongoDB data sources by relying on the standard ontology-based data access (OBDA)
paradigm [