# Estimating the Cardinality of Conjunctive Queries over RDF Data Using Graph Summarisation

arXiv: https://arxiv.org/abs/1801.09619 · HTML: https://mlsanity.com/paper/1801.09619/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jan 2018.

## Built on by (most cited first, 4 of 4)

- [Cardinality Estimation over Knowledge Graphs with Embeddings and Graph Neural Networks](https://mlsanity.com/paper/2303.01140/) (2023)
- [Cardinality Estimation on Hyper-relational Knowledge Graphs](https://mlsanity.com/paper/2405.15231/) (2024)
- [Enhancing Datalog Reasoning with Hypertree Decompositions](https://mlsanity.com/paper/2305.06854/) (2023)
- [Fully Inductive Cardinality Estimation](https://mlsanity.com/paper/2607.28311/) (2026)

## Abstract (arXiv)

Estimating the cardinality (i.e., the number of answers) of conjunctive queries is particularly difficult in RDF systems: queries over RDF data are navigational and thus tend to involve many joins. We present a new, principled cardinality estimation technique based on graph summarisation. We interpret a summary of an RDF graph using a possible world semantics and formalise the estimation problem as computing the expected cardinality over all RDF graphs represented by the summary, and we present a closed-form formula for computing the expectation of arbitrary queries. We also discuss approaches to RDF graph summarisation. Finally, we show empirically that our cardinality technique is more accurate and more consistent, often by orders of magnitude, than the state of the art.