Abstract
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.