2026-07-20T05:38:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8607 2024-03-06T10:42:27Z ddc:004 open_access

Expressivity and Complexity of MongoDB Queries Botoeva, Elena Calvanese, Diego Cogrel, Benjamin Xiao, Guohui MongoDB NoSQL aggregation framework expressivity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Elena Botoeva and Diego Calvanese and Benjamin Cogrel and Guohui Xiao 2018 Is Part Of LIPIcs, Volume 98, 21st International Conference on Database Theory (ICDT 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2018.9 urn:nbn:de:0030-drops-86074 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2018.9 eng https://creativecommons.org/licenses/by/3.0/legalcode