Cardinality estimation of graph data base queries

The database’s cardinality estimator is a key component for the selection of eficient execution plans and load balancing in distributed systems.

Cardinality estimation in relational databases is a well-studied problem, but graph databases rarely follow the uniformity and independence assumptions that these estimators make, and therefore lose precision.

The objective of the project is to select and evaluate state of the art cardinality estimators for graph databases, to find the technique or combination of techniques that work best for the graph database management system that Microsoft is developing.