Expressivity and Complexity of MongoDB Queries

Proc. of the 21st Int. Conf. on Database Theory (ICDT 2018). Volume 98 of Leibniz International Proceedings in Informatics (LIPIcs). 2018.

In this paper, we consider 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 provide a clean formal abstraction of this query language, which we call MQuery. We study the expressivity of MQuery, showing the equivalence of its well-typed fragment with nested relational algebra. We further investigate the computational complexity of significant fragments of it, obtaining several (tight) bounds in combined complexity, which range from LogSpace to alternating exponential-time with a polynomial number of alternations.

@inproceedings{ICDT-2018,
   title = "Expressivity and Complexity of MongoDB Queries",
   year = "2018",
   author = "Elena Botoeva and Diego Calvanese and Benjamin Cogrel and
Guohui Xiao",
   booktitle = "Proc. of the 21st Int. Conf. on Database Theory (ICDT 2018)",
   pages = "9:1--9:23",
   volume = "98",
   publisher = "Schloss Dagstuhl--Leibniz-Zentrum für Informatik",
   series = "Leibniz International Proceedings in Informatics (LIPIcs)",
   doi = "10.4230/LIPIcs.ICDT.2018.9",
}