• search hit 5 of 84
Back to Result List

Quantum Optimisation of General Join Trees

  • Recent advances in the manufacture of quantum computers attract much attention over a wide range of fields, as early-stage quantum processing units (QPU) have become accessible. While contemporary quantum machines are very limited in size and capabilities, mature QPUs are speculated to eventually excel at optimisation problems. This makes them an attractive technology for database problems, many of which are based on complex optimisation problems with large solution spaces. Yet, the use of quantum approaches on database problems remains largely unexplored. In this paper, we address the long-standing join ordering problem, one of the most extensively researched database problems. Rather than running arbitrary code, QPUs require specific mathematical problem encodings. An encoding for the join ordering problem was recently proposed, allowing first small-scale queries to be optimised on quantum hardware. However, it is based on a faithful transformation of a mixed integer linear programming (MILP) formulation for JO, and inherits all limitations of the MILP method. Most strikingly, the existing encoding only considers a solution space with left-deep join trees, which tend to yield larger costs than general, bushy join trees. We propose a novel QUBO encoding for the join ordering problem. Rather than transforming existing formulations, we construct a native encoding tailored to quantum systems, which allows us to process general bushy join trees. This makes the full potential of QPUs available for solving join order optimisation problems.

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics
Metadaten
Author:Manuel SchönbergerORCiD, Immanuel Trummer, Wolfgang MauererORCiDGND
URL / DOI:https://ceur-ws.org/Vol-3462/QDSM2.pdf
Parent Title (English):Joint Workshops at 49th International Conference on Very Large Data Bases (VLDBW’23) — International Workshop on Quantum Data Science and Management (QDSM’23), August 28 - September 1, 2023, Vancouver, Canada (CEUR Workshop Proceedings)
Publisher:RWTH Aachen, Sun SITE Central Europe
Place of publication:Aachen
Document Type:conference proceeding (article)
Language:English
Year of first Publication:2023
Release Date:2023/10/13
First Page:1
Last Page:12
Institutes:Fakultät Informatik und Mathematik
Fakultät Informatik und Mathematik / Labor für Digitalisierung (LFD)
research focus:Digitalisierung
Licence (German):Creative Commons - CC BY - Namensnennung 4.0 International