In this paper, we report on our ongoing work in which we formalize MongoDB, a widely adopted document database system managing complex (tree structured) values represented in a JSON-based data model, equipped with a powerful query mechanism. We study the expressiveness of the MongoDB query language, showing its equivalence with nested relational algebra, and we investigate the computational complexity of significant fragments of it.
In the past decade numerous database (DB) architectures and data models have been
proposed as attempts to better address the varying demands of modern data-intensive
applications. Many of these new systems do not rely on the relational model but instead
adopt a semi-structured data format, and alternative query mechanisms, which combine
an increased flexibility in data handling, with a higher efficiency (at least for the most
common operations). These systems are generally categorized under the term NoSQL
(which stands for “not only SQL”) [
A popular design among these non-relational systems consists in organizing data in
collections of semi-structured, tree-shaped documents in the JavaScript Object Notation
(JSON) format. Such documents can be seen as complex values [
Unsurprisingly, many similarities can be observed between non-relational
languages for querying JSON collections having rich capabilities (see, e.g., [
In this work, we conduct the first major study into the formal foundations and properties of the data model and query language of MongoDB, a widely adopted distributed JSON-based document database. MongoDB provides rich querying capabilities by means of the aggregation framework1. In this framework, a query is a multi-stage pipeline, where each stage defines a transformation, using a MongoDB-specific operator, applied to the set of documents produced by the previous stage.
Our first contribution is a formalization of the MongoDB data model and of the fragment of the aggregation framework query language that includes the match, unwind, project, group, and lookup operators, and which we call MQuery. Each of these operators roughly corresponds to an operator of NRA: match corresponds to select, project to project, lookup to left join, group to nest, and unwind to unnest.
Our second contribution is a characterization of the expressive power of MQuery obtained by comparing it with NRA. We devise translations in both directions between the two languages showing that they are equivalent in expressive power.
Finally, we carry out an investigation of the computational complexity of MMUPGL and of various fragments of it. Interestingly, since our translations between MQuery and NRA are compact (i.e., polynomial), they allow us also to carry over complexity results between MQuery and NRA.
We provide here only an overview, and refer to the full version for more details [
Objects in the JSON format are defined inductively as consisting 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 terminals are written 1 https://docs.mongodb.com/core/aggregation-pipeline/
id 4 []
0 1 ffgg ffgg award by year award by year RPorsiizneg ANsosrDowcaeitagatiiaonn 1999 TAuwrainrdg ACM 2001 awards 2
ffgg award by year voInEENEeuJmohannn IEEE 2001
Medal ffgg birth 1926-08-27 contribs death [] name
2002-08-10 0 1 OOP Simula
ffgg first last Kristen Nygaard
Fig. 3. The tree representation of the MongoDB document in Figure 1 ' ::= p = v j 9p j ' _ ' j ' ^ ' j :' d ::= v j p j [d; : : : ; d] j j ::= p = p j p = v j v = v j 9p j d _ d j d ^ d j :d ::= (d?d:d)
P ::= p j p=d j p; P j p=d; P G; A ::= p=p0 j p=p0; G
s ::= ' j !pn j nPi j G:A j pp1=C:p2 MQuery ::= C . s . . s in black, and non-terminals in blue). The set of key-value pairs constituting a JSON object may not contain the same key twice. A MongoDB database stores collections of documents, where each collection has a name, and consists of a finite set of documents. Each document is a JSON object (not nested within any other object) with a special key ‘ id’, which is used to identify the document. Figure 1 shows a MongoDB document in which, apart from id, the keys are birth, name, awards, etc. Intuitively, a collection corresponds to a table in a (nested) relational database, and a document to a row in a table. We formalize documents as finite unordered, unranked, node-labeled, and edge-labeled trees, and collections as forests. The tree corresponding to the document in Figure 1 is depicted in Figure 3.
MongoDB is equipped with a powerful query mechanism provided by the aggregation framework. As a first contribution, we formalize the core aspects of such query language. We call our language MQuery, and consider also different fragments of it. An MQuery is a sequence of stages s, also called a pipeline, applied to a collection name C, where each of the stages roughly corresponds to a relational algebra operation, and transforms a forest into another forest. Here we are not concerned with syntactic aspects of MQuery, and instead propose for it an algebra, shown 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. MQuery allows for five types of stages: – match ', selecting trees according to the criterion ', which is a Boolean combination of atomic conditions that express either the equality of a path p to a value v, or the existence of a path p. – unwind !p and !p+, which flatten an array reached through a path p in the input tree, and output a tree for each element of the array; the latter operator preserves a tree even when the array does not exist or is empty. – project P and Pid , which modify trees by projecting away paths, renaming paths, or introducing new paths; the latter version projects away id, which otherwise is kept by default. Here P is a sequence of elements of the form p or q=d, where p is a path to be kept, and q is a new path whose value is defined by d. Such a value definition d can provide for q a constant v, the value reached through a path p (i.e., renaming path p to q), a new array defined through its values, the value of a Boolean expression , or a value computed through a conditional expression . Note that, in a Boolean value definition , one can also compare the values of two paths, while in a criterion ' one can only compare the value of a path to a constant value. Also note that each value definition can be evaluated to a Boolean value. – group G:A, which groups trees according to a grouping condition G and collects values of interest according to an aggregation condition A. Both G and A are (possibly empty) sequences of elements of the form p=p0, where p0 is a path in the input documents, and p a path in the output document. In these sequences, if p coincides with p0, then we simply write p instead of p=p. Each group in the output will have an id whose value is given by the values of p0 in G for that group. – lookup pp1=C:p2 , which joins input trees with trees in an external collection C, using a local path p1 and a path p2 in C to express the join condition, and uses a path p to store the matching trees in an array.
We consider also various fragments of MQuery, and we denote each fragment by M , where consists of the initials of the stages that can be used in queries in the fragment. Hence, MMUPGL denotes MQuery itself, e.g., MMUPG the fragment of MMUPGL that does not use lookup, and MMUP the fragment that additionally does not use group. 3
We study the expressiveness and the computational complexity of MQuery.
First, we show that for MongoDB instances of a certain regular structure, MQuery is essentially equivalent to nested relational algebra (NRA). Regularity of MongoDB instances allows for defining a nested relational view of MongoDB documents, which serves for establishing the correctness of the translations between MQuery and NRA, and hence the equivalence between MMUPGL and NRA. We also consider the MMUPG fragment, where we rule out the lookup operator, which allows for joining a given document collection with external ones, and establish that already MMUPG is equivalent to NRA over a single relation, and hence is capable of expressing arbitrary joins (within one collection), contrary to what is believed in the community of MongoDB practitioners and users.
Second, we obtain the exact complexity of MMUPGL and of some of its fragments:
– 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
LOGSPACEcomplete 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
PSPACEhard 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 [