Structured Query Language (SQL) is the most used relational database query language in the world. In modern applications, data volume, variety, and connectivity have increased. Querying data should not become a bottleneck in data-intensive applications.
Query processors in relational databases can assign SQL queries to various measurements, such as cardinality, cost, and execution time estimations [1]. The optimization of the query heavily depends on the estimates. Usually, the problem is solved with machine learning, dynamic programming, or integer programming. Quantum computers are reaching the level where they can be part of various applications on a small scale. We believe that databases and quantum computers will be co-designed in the future so that combinatorically hard database optimization problems can be solved efficiently and with high quality on quantum computers. As far as we know, our work is the first attempt to apply quantum computing and quantum circuit learning as a part of the SQL query optimization pipeline. Even if we cannot beat the classical methods with the current quantum hardware, we can point out its limitations, understand quantum computing frameworks in a circuit learning context, and propose novel methods to model the problems with quantum computing algorithms. Especially quantum computing and machine learning are a promising combination because both are based on linear algebra and probability theory.
We utilize methods from quantum natural language processing (QNLP) [2] and quantum circuit learning [3]. First, we parse SQL queries and represent them using context-free grammar (CFG) diagrams. The CFG diagrams are functorially mapped to pregroup grammar diagrams. We perform a rewriting process for the pregroup grammar diagrams to optimize and reduce their size. We functorially translated them into parameterized quantum circuits. We will optimize the circuit parameters using standard quantum circuit learning pipelines. A quantum computer or a simulator is used to evaluate the circuit, but the actual training happens on classical hardware.
This is still ongoing work. Currently, we are at the phase where we can represent SELECT-FROM-WHERE type of SQL queries with complex filtering and join expressions using pregroup grammar diagrams and parametrized circuits. The corresponding results from QNLP are promising. We are excited to be able to express complex SQL queries as parametrized circuits and utilize the quantum circuit learning methods.
[1] Lan, H., Bao, Z. & Peng, Y. A Survey on Advancing the DBMS Query Optimizer: Cardinality Estimation, Cost Model, and Plan Enumeration. Data Sci. Eng. 6, 86–101 (2021). https://doi.org/10.1007/s41019-020-00149-7 [2] Meichanetzidis, K., Gogioso, S., De Felice, G., Chiappori, N., Toumi, A., & Coecke, B. (2020). Quantum natural language processing on near-term quantum computers. arXiv preprint arXiv:2005.04147. [3] Mitarai, K., Negoro, M., Kitagawa, M., & Fujii, K. (2018). Quantum circuit learning. Physical Review A, 98(3), 032309.