Efficiently computing graph structures to help answer database queries

What is it about?

Many fundamental tasks, such as answering database queries via SQL, are known to have a high computational complexity, despite most instances of queries being easy to solve. Our work continues the line of research that looks at graph structures, called Hypertree Decomposition, to find queries that can be solved efficiently. Our contribution is a practical algorithm, that runs well on modern multi-core systems, and computes witnesses of such graph structures.

Featured Image

Photo by Alina Grubnyak on Unsplash

Photo by Alina Grubnyak on Unsplash

Why is it important?

On the basis of our work, one could develop efficient query plans, even for database queries that current database systems struggle with. The importance of efficient database systems should be self evident. In a world where ever larger amounts of data are collected and evaluated, leading to more and more applications, the most prominent of which are probably neural-network based AI systems, there is always a need to improve query answering times.