Formalization and Complexity of MongoDB Queries (Extended Abstract)

Proc. of the 26th Italian Symp. on Advanced Database Systems (SEBD 2018). Volume 2161 of CEUR Workshop Proceedings, https://ceur-ws.org/. 2018.

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.

@inproceedings{SEBD-2018,
   title = "Formalization and Complexity of MongoDB Queries (Extended
Abstract)",
   year = "2018",
   author = "Elena Botoeva and Diego Calvanese and Benjamin Cogrel and
Guohui Xiao",
   booktitle = "Proc. of the 26th Italian Symp. on Advanced Database Systems
(SEBD 2018)",
   volume = "2161",
   publisher = "CEUR-WS.org",
   series = "CEUR Workshop Proceedings, https://ceur-ws.org/",
}