Expressivity and Complexity of MongoDB Queries

Botoeva, Elena, Calvanese, Diego, Cogrel, Benjamin, Xiao, Guohui (2018) Expressivity and Complexity of MongoDB Queries. In: Leibniz International Proceedings in Informatics. 21st International Conference on Database Theory, ICDT 2018, March 26-29, 2018, Vienna, Austria. LIPIcs , 98. 9:1-9:23. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany ISBN 978-3-95977-063-7. (doi:10.4230/LIPIcs.ICDT.2018.9) (The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided) (KAR id:91266)

The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided. (Contact us about this Publication)
Official URL: https://doi.org/10.4230/LIPIcs.ICDT.2018.9

Abstract

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.

Item Type:	Conference or workshop item (Paper)
DOI/Identification number:	10.4230/LIPIcs.ICDT.2018.9
Uncontrolled keywords:	MongoDB; NoSQL; aggregation framework; expressivity
Subjects:	Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions:	Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User:	Amy Boaler
Date Deposited:	02 Nov 2021 14:06 UTC
Last Modified:	03 Nov 2021 11:19 UTC
Resource URI:	https://kar.kent.ac.uk/id/eprint/91266 (The current URI for this page, for reference purposes)

University of Kent Author Information

Botoeva, Elena.

Creator's ORCID:
CReDIT Contributor Roles:

Depositors only (login required):

Altmetric

Download Statistics

Total unique views for this document in KAR since July 2020. For more details click on the image.