the problem of cardinality estimation (see Section \[From Containment to Cardinality\]).

From Containment to Cardinality {#From Containment to Cardinality}
-------------------------------

Using a containment rate estimation models, we can obtain cardinality estimates using the Cnt2Crd transformation, as depicted in the rightmost diagram in Figure \[fig:teaser\].

### The Cnt2Crd Transformation {#Cnt2Crd Transformation}

Given a containment rate estimation model[^4] $M$, we convert it to a cardinality estimation model using the Cnt2Crd transformation which returns a model $M'$ for estimating cardinalities. The obtained model $M'$ functions as follows. Given a “new” query, denoted as $Q_{new}$, as input to cardinality estimation, and assuming that there is an “old” query denoted as $Q_{old}$, whose FROM clause is the same as $Q_{new}$’s FROM clause, that has already been executed over the database, and therefore $|Q_{old}|$ is known, we:

-   Calculate $x\_rate = Q_{old} \subset_{\%} Q_{new}$ using $M$.

-   Calculate $y\_rate = Q_{new} \subset_{\%} Q_{old}$ using $M$.

-   Then, the cardinality estimate equals to: $$|Q_{new}| = \frac{x\_rate}{y\_rate} * |Q_{old}|$$

provided that $y\_rate = Q_{new} \subset_{\%} Q_{old}\  \neq 0$.

Given model $M$, we denote the obtained model $M'$, via the Cnt2Crd transformation, as Cnt2Crd($M$).

Queries Pool
------------

Our technique for estimating cardinality mainly relies on a queries pool that 