Cardinality estimation of graph data base queries

Cardinality estimation is an essential component of database management systems, as it enables the prediction of the number of results a query will generate and the selection of the most efficient execution plans. This information is key to optimising query performance and improving load balancing in distributed environments.

Although this issue is widely studied in relational databases, graph databases present more complex structural characteristics that make the application of traditional methods difficult. The uniformity and independence assumptions on which many of these estimators are based are often not met, which reduces their accuracy and impacts the overall system performance.

In this context, the project analyses and evaluates the most advanced cardinality estimators for graph databases, with the aim of identifying the technique, or combination of techniques, that offers the best performance for the graph database management system that Microsoft is developing.

The project’s results will contribute to improving query optimisation and system efficiency, enabling faster, more accurate and scalable execution over large volumes of connected data.