Synthesizing Document Database Queries using Collection Abstractions

Qikang Liu, Yang He, Yanwen Cai, Byeongguk Kwak, Yuepeng Wang · 2024

Read Synthesizing Document Database Queries using Collection Abstractions by Qikang Liu, Yang He, Yanwen Cai, Byeongguk Kwak, Yuepeng Wang (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-06102.txt.

Introduction

Qikang Liu, Yang He, Yanwen Cai, Byeongguk Kwak, and Yuepeng Wang presented a method that writes document database queries from examples in two thousand twenty-four. Document databases store flexible, nested records, which makes their queries hard to write by hand. Their system aims to generate the query automatically.

They first design a small language that expresses a representative set of such queries in algebraic style. Their synthesis method then uses an abstraction of collections to prune the search space with logical deduction. That pruning lets it find the target query fast. On one hundred ten benchmarks from mixed sources, it solved one hundred eight, usually within tens of seconds from a few examples.

Catalog record

CREATORQikang Liu, Yang He, Yanwen Cai, Byeongguk Kwak, Yuepeng Wang
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE98 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-06102

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Synthesizing Document Database Queries using Collection Abstractions Qikang Liu, Yang He, Yanwen Cai, Byeongguk Kwak, Yuepeng Wang Abstract Document databases are increasingly popular in various applications, but their queries are challenging to write due to the flexible and complex data model underlying document databases. This paper presents a synthesis technique that aims to generate document database queries from input-output examples automatically. A new domain-specific language is designed to express a representative set of document database queries in an algebraic style. Furthermore, the synthesis technique leverages a novel abstraction of collections for deduction to efficiently prune the search space and quickly generate the target query. An evaluation of 110 benchmarks from various sources shows that the proposed technique can synthesize 108 benchmarks successfully. On average, the synthesizer can generate document database queries from a small number of input-output examples within tens of seconds. I Introduction Document databases like MongoDB [ 29 ] and CouchDB [ 10 ] have become increasingly popular in various real-world scenarios, such as online commercial platforms, financial services, gaming, and social media applications [ 30 ] . Different from traditional relational databases that primarily use structured data like tables, document databases persist data in a semi-structured format such as JSON and BSON. While the semi-structured data format provides developers with great flexibility in storing and querying complex data structures directly, it also raises significant challenges for users to write queries for document databases. To help users write document database queries in an easy and convenient fashion, we develop a synthesis technique to generate queries automatically. Inspired by prior work on automated synthesis of SQL queries for relational databases [ 53 , 46 , 14 ] , our technique aims to generate document database queries from input-output examples. Specifically, the user only needs to provide a small number of examples to demonstrate the query, where the input example is a small document database consisting of a few documents, and the output example is the desired query result over the input. The goal of our synthesis technique is to generate a document database query such that executing the query over the input example produces the output example. However, unlike synthesizing SQL queries, there are several key challenges to synthesizing queries for document databases. • Hierarchical and nested data structures . Document databases support hierarchical and nested data structures, such as arrays, documents, and their combinations. Since queries for document databases constantly operate over these complex data structures, it is crucial for synthesizers to reason about complex data structures efficiently for better performance. • Specialized query language . Query languages for document databases may use specialized operators over complex data structures that relational databases cannot handle. For instance, MongoDB uses a lookup operator in aggregation pipelines to query data over multiple collections. Synthesizers need to support an expressive query language for document databases while maintaining the efficiency of exploring a large search space of the target query. To address these challenges, we have designed a new domain-specific language based on the aggregation pipeline in MongoDB that can express a representative set of queries with core operators of document databases. The queries of this language are in an algebraic style similar to relational algebra but tailored towards document databases. Furthermore, prior work on program synthesis proposed an approach to speed up the synthesis process by deduction [ 14 , 13 ] . For fast synthesis of document database queries, we have adapted this approach to our setting and developed a novel abstraction for collections containing hierarchical and nested data structures to prune the search space efficiently. The key insight is that the “shape” and size of collections can help the synthesizer quickly prune incorrect queries, even if the query is partial. Thus, our abstraction consists of two pieces of information about the collection: First, it includes the type of documents inside the collection. Second, it includes a logical formula describing constraints over the size of the collection. More specifically, our synthesis technique is presented schematically in Figure 1 . At a high level, the synthesis technique takes an iterative approach and has two phases in each iteration. In the first phase, the synthesizer aims to find a query sketch, which is a partial query with some unknown constructs. In the second phase, it tries to complete the sketch into a full query that can satisfy all provided input-output examples. In general, it is not efficient to check if a sketch is feasible to be completed into a correct full query by checking all possible completions against the examples, because a sketch may have a large number of completions. To avoid such inefficiency, the key part of our synthesis technique is a deduction engine, which can check if a sketch is feasible to get a correct query without checking its completions. In particular, the deduction engine can directly evaluate the sketch over abstractions of collections and obtain an abstract collection. If the expected output example is a valid concretization of the resulting abstract collection, the synthesizer concludes the sketch is feasible to complete and proceeds to find a correct completion. Otherwise, the synthesizer can safely conclude the sketch is infeasible to complete, prune the search space accordingly, and propose a different sketch to the next iteration by refining the infeasible sketch. Fig. 1 : Schematic workflow. Based on this technique, we have developed a tool called Nosdaq that can synthesize document database queries from input-output examples. To evaluate the synthesis technique, we have collected 110 benchmarks from various application scenarios, including StackOverflow, Kaggle, MongoDB official documents, and Twitter API documents. The evaluation result shows that Nosdaq can successfully synthesize 108 document database queries within the 5-minute time limit. Furthermore, Nosdaq only uses 1 – 3 input-output examples and finishes query synthesis in an average of 25.4 seconds, which demonstrates the effectiveness and efficiency of our synthesis technique. Contributions. To summarize, the main contributions of this paper are as follows. 1. We develop a technique for synthesizing document database queries from input-output examples. 2. We design a new domain-specific language to express document database queries in algebraic style. 3. We design a novel abstraction for collections containing hierarchical and nested data structures and use this abstraction to speedup the synthesis of document database queries based on deduction. 4. We define the abstract semantics of document database queries based on our abstraction of collections. 5. We develop a tool called Nosdaq and evaluate it over 110 benchmarks from various sources. The evaluation result shows that Nosdaq is effective and efficient in synthesizing document database queries. Organization. The remainder of this paper is structured as follows. Section II provides a motivating example to illustrate our technique. Section III formalizes the synthesis problem, and Section IV introduces collection abstractions. Sections V and VI present the synthesis algorithm and its implementation details, respectively. Section VII presents the experimental setup and evaluation results. Section VIII discusses the related work, followed by a conclusion in Section IX . II Motivating Example To explain our synthesis technique, let us consider a concrete motivating example. Given a document database collected from the Kaggle website that stores a list of Reddit posts. The database only has one collection called posts with the

Read the complete text