# A General Cardinality Estimation Framework for Subgraph Matching in Property
Graphs

Wilco van Leeuwen, George Fletcher, Nikolay Yakovets W.J. van Leeuwen, G.H.L.
Fletcher and N. Yakovets are with TU Eindhoven. E-mail: {w.j.v.leeuwen,
g.h.l.fletcher<EMAIL_ADDRESS>work has been submitted to the IEEE for
possible publication. Copyright may be transferred without notice, after which
this version may no longer be accessible.

###### Abstract

Many techniques have been developed for the cardinality estimation problem in
data management systems. In this document, we introduce a framework for
cardinality estimation of query patterns over property graph databases, which
makes it possible to analyze, compare and combine different cardinality
estimation approaches. This framework consists of three phases: obtaining a
set of estimates for some subqueries, extending this set and finally combining
the set into a single cardinality estimate for the query. We show that (parts
of) many of the existing cardinality estimation approaches can be used as
techniques in one of the phases from our framework. The three phases are
loosely coupled, this makes it possible to combine (parts of) current
cardinality estimation approaches. We create a graph version of the Join Order
Benchmark to perform experiments with different combinations of techniques.
The results show that query patterns _without_ property constraints can be
accurately estimated using synopses for small patterns. Accurate estimation of
query patterns _with_ property constraints require new estimation techniques
to be developed that capture correlations between the property constraints and
the topology in graph databases.

###### Index Terms:

Cardinality estimation, selectivity estimation, query optimization, graph
databases, property graph data model.

##  1 Introduction

Cardinality estimation can be defined as the task of estimating the number of
results returned by a given query over a given database instance. This is a
fundamental data management problem, important across many practical
scenarios, e.g., in query planning, approximate query evaluation, and query
execution progress estimation. The basic evaluation criteria for cardinality
estimation techniques are: estimation accuracy, estimation time, memory cost,
and preparation time. Different applications might value these dimensions
differently, leading to trade-offs, e.g., between estimation accuracy and
memory footprint. It has been shown that poor query plans are regularly
produced by the query optimizers of current database management systems and
that cardinality estimation errors are the main reason for these bad query
plans [1, 2]. Hence, while a classical topic heavily studied for decades,
cardinality estimation remains a significant challenge in practice.

In this work, we survey cardinality estimation solutions for query patterns on
property graph databases. Property graphs are a popular data model in
industry, part of the upcoming ISO graph database query language standard [3].
Essentially, a property graph is a graph where both nodes and edges can have
labels (e.g., Person) and have a set of associated key-value pairs, which are
called the properties, where the property key specifies the meaning of the
property value (e.g., MemberSince = 2008-11-10). A query pattern (also known
as a conjunctive graph query, or a subgraph matching query [4]) specifies a
graph pattern of interest (e.g., Persons and the Movies they ActIn) and also
possibly constraints on attributes (e.g., only those Persons who became a
member after 1990-12-08). Query Patterns are fundamental in both theory and
practice, forming the backbone of virtually all queries expressed in
contemporary graph database query languages [4, 5, 3]. Cardinality estimation
for query patterns over property graph databases gives rise to new challenges
due to the schemaless design of graph databases and the correlation between
the data (property values and labels) and the topology (connectivity) of the
graph. The focus of our survey allows us to shed deep light on an important,
timely, highly challenging, and broadly applicable subclass of the cardinality
estimation problem. Further, many of the concepts of our survey generalize to
other typical settings, for example conjunctive queries on relational
databases.

There is a large and rich literature on cardinality estimation for queries on
database instances which can be used for query patterns on property graphs.
Each technique requires specialized statistics or indexes and uses a set of
simplifying assumptions to overcome missing information or to improve on
criteria of interest (i.e., accuracy, time, space, etc.). Hence, it is very
difficult for practitioners, systems designers, and researchers to navigate
the state of the art and understand which solutions work or not for a given
application scenario. The most recent and complete survey here is the
groundbreaking G-CARE framework [6]. G-CARE performs extensive experiments on
different cardinality estimation approaches with queries of varying sizes,
result sizes and topologies, on both real and synthetic data sets. This study
addresses two limitations of G-CARE. First, G-CARE studies cardinality
estimation techniques for query patterns without predicates on the properties.
This study includes extensive experiments on property predicates. Our
experiments show that properly handling property predicates is essential for
accurate cardinality estimation. Second, the focus of G-CARE is on comparing
different cardinality estimation approaches. In this study, we also focus on
combining parts of different cardinality estimation approaches with the aim of
producing superior estimation techniques.

Our contribution in this survey is to introduce a framework that makes it
possible to explain the state of the art and systematically analyze, compare
and combine the current cardinality estimation techniques for query patterns
on property graphs. We start by viewing a query pattern as a specification of
a set of constraints (Section 2). We then highlight the basic ingredients of
contemporary estimators and how they together are used to define concrete
cardinality estimation solutions in a general framework (Section 3). The first
phase of the framework consists of estimation techniques for individual
constraints (Section 4) and of estimation techniques for multiple constraints
(Section 5). The second phase consists of methods for extending partial
estimates (Section 6). Finally, the third phase consists of methods for
combining partial estimates in order to obtain a final estimate for the
complete query (Section 7).

We leverage our framework to undertake a comprehensive comparative analysis of
the state of the art cardinality estimators, shedding fresh light on their
trade-offs and relative strengths and weaknesses (Sections 8-10). Given these
new deep insights, we conclude the survey with recommendations for
practitioners and researchers (Section 11). With this work we aim to help move
the field forward towards more effective cardinality estimation solutions in
practical graph data management.

##  2 Preliminaries

###  2.1 Basic Property Graph Query Pattern

A basic property graph query pattern, or shortly query pattern, consists of a
set of vertices and a set of edges. Vertices and edges have unique
identifiers. Each edge is associated with exactly one source vertex and one
target vertex. Vertices and edges can have a (possibly empty) set of label and
a (possibly empty) set of key-value properties.

A query pattern $Q$ is defined as the tuple (${\mathtt{E}}$, ${\mathtt{V}}$,
${\mathtt{I}}$, $\rho$, $\lambda$, $\sigma$, $\Theta$, ${\mathtt{Lab}}$,
${\mathtt{Prop}}$, ${\mathtt{Val}}$).111We use the dot notation to refer to an
element in $Q$ or $G$, e.g. $Q.\sigma$ The set of edge identifiers
${\mathtt{E}}$ and the set of vertex identifiers ${\mathtt{V}}$ are disjoint,
and ${\mathtt{I}}{}={\mathtt{E}}\cup{\mathtt{V}}$. The total function $\rho$:
${\mathtt{E}}$ $\rightarrow$ (${\mathtt{V}}$ $\times$ ${\mathtt{V}}$) maps
each edge identifier to a pair of source-target vertex identifiers. The total
function $\lambda:{\mathtt{I}}{}\rightarrow$ $\mathcal{P}({\mathtt{Lab}})$,
where ${\mathtt{Lab}}$ is a finite set of labels and
$\mathcal{P}({\mathtt{Lab}})$ is the powerset of ${\mathtt{Lab}}$, maps edge
and vertex identifiers to a (possible empty) set of labels. The partial
function
$\sigma:({\mathtt{I}}{}\times{\mathtt{Prop}}\times\Theta)\rightarrow{\mathtt{Val}}$
defines the key-property constraints of vertices and edges, where
${\mathtt{Prop}}$ is a finite set of properties, ${\mathtt{Val}}$ is a set of
values and $\Theta$ is a set of binary predicates, i.e. set of functions
$\theta:({\mathtt{Val}}\times{\mathtt{Val}})\rightarrow\\{True,False\\}$.
Table I summarizes our notation for query patterns.

###### Example 2.1

The formal description of the query pattern in Figure 1 is $Q_{example}$ =
(${\mathtt{E}_{ex}}$, ${\mathtt{V}_{ex}}$, $\rho_{ex}$, $\lambda_{ex}$,
$\sigma_{ex}$, ${\mathtt{Lab}_{ex}}$, ${\mathtt{Prop}_{ex}}$,
${\mathtt{Val}_{ex}}$, $\Theta_{ex}$), where:

${\mathtt{E}}_{ex}$ = {id1, id3, id5, id7}
${\mathtt{V}}_{ex}$ = {id0, id2, id4, id6, id8}
${\mathtt{I}}{}_{ex}$ = {id0, id1, $\dots$, id8}
$\rho$ex(id1)=(id0,id2), $\dots$
$\lambda$ex(id0) = {’title’},$\lambda$ex(id1) = {’budget’}, $\dots$
$\sigma_{ex}$(id6, ’note’, IN) = "{’(producer)’,’(executive producer)’}",
$\sigma_{ex}$(id8, ’gender’, =) = "m",
$\sigma_{ex}$(id8, ’name’, CONTAINS) = "Tim"
Labex = {’title’, ’votes’, $\dots$}
Propex = {’note’, ’gender’, ’name’}
Valex = {"{’(producer)’,’(executive producer)’}", ’m’, ’Tim’}
$\Theta_{ex}$={=, IN, CONTAINS}

###  2.2 Property Graph Data Model

A property graph instance is defined as a tuple $G$ = (${\mathtt{E}}$,
${\mathtt{V}}$, ${\mathtt{I}}$, $\rho$, $\lambda$, $\sigma$, ${\mathtt{Lab}}$,
${\mathtt{Prop}}$, ${\mathtt{Val}}$). Only the equality operator is allowed
for $\Theta$ in $\sigma$ in this definition, therefore $\Theta$ is irrelevant.
Let $\ell_{e}(G)\subseteq G.$${\mathtt{Lab}}$ be the set of labels that occur
on edges in graph $G$ and $\ell_{v}(G)\subseteq G.$${\mathtt{Lab}}$ be the set
of all labels that occur on vertices in graph $G$. Table I summarizes our
notation.

Table I: Notation for Query Patterns and Property Graph Instances $Q$ | Query Pattern | $G$ | Property graph instance
---|---|---|---
$Q.$${\mathtt{Lab}}$ |  Set of labels in $Q$ |  $G.$${\mathtt{Lab}}$ |  Set of labels in $G$
$Q.$${\mathtt{Prop}}$ |  Set of property keys in $Q$ |  $G.$${\mathtt{Prop}}$ |  Set of property keys in $G$
$Q.$${\mathtt{Val}}$ |  Set of property values in $Q$ |  $G.$${\mathtt{Val}}$ |  Set of property values in $G$
$Q.\Theta$ |  Set of binary predicates used in $Q$ |  |
$Q.$${\mathtt{E}}$ |  Set of edge ids in $Q$ |  $G.$${\mathtt{E}}$ |  Set of edge ids in $G$
$Q.$${\mathtt{V}}$ |  Set of vertex ids in $Q$ |  $G.$${\mathtt{V}}$ |  Set of vertex ids in $G$
$Q.{\mathtt{I}}{}$ | $Q.{\mathtt{E}}\cup Q.{\mathtt{V}}$ | $G.{\mathtt{I}}{}$ | $G.{\mathtt{E}}\cup G.{\mathtt{V}}$
$Q.$$\rho$ | $Q.{\mathtt{E}}\rightarrow(Q.{\mathtt{V}}\times Q.{\mathtt{V}})$ |  $G.$$\rho$ | $G.{\mathtt{E}}\rightarrow(G.{\mathtt{V}}\times G.{\mathtt{V}})$
$Q.$$\lambda$ | $Q.{\mathtt{I}}{}\rightarrow\mathcal{P}(Q.{\mathtt{Lab}})$ |  $G.$$\lambda$ | $G.{\mathtt{I}}{}\rightarrow\mathcal{P}(G.{\mathtt{Lab}})$
$Q.\sigma$ | $(Q.{\mathtt{I}}{}\times Q.{\mathtt{Prop}}\times Q.\Theta)\rightarrow Q.{\mathtt{Val}}$ | $G.\sigma$ | $(G.{\mathtt{I}}{}\times G.{\mathtt{Prop}})\rightarrow G.{\mathtt{Val}}$
|  | $G.\ell_{e}$ | $\cup_{e\in G.E}G.\lambda(e)$
|  | $G.\ell_{v}$ | $\cup_{v\in G.V}G.\lambda(v)$
Table II: Notation (section where notation is introduced) ${\mathsf{m}}_{D\rightarrow R}$ |  A mapping that maps each element in the domain $D$ to an element in range $R$ (2.3)
---|---
$\mathcal{M}_{D\rightarrow R}$ |  Set of all possible mappings ${\mathsf{m}}_{D\rightarrow R}$ (2.3)
$|S|$ |  Cardinality of set $S$ (2.3)
${\mathsf{c}}$ |  A constraint (2.4)
${\mathsf{C}}{}$ |  A set of constraints (2.4)
${\mathsf{C}}{}(Q)$ |  Set of constraints defined by $Q$ (2.4)
${\mathsf{C}}{}.{\mathtt{I}}{}$ |  Set of query ids contained in ${\mathsf{C}}$ (2.4)
$SAT_{{\mathsf{c}}}^{D\rightarrow G.{\mathtt{I}}{}}$ |  Set of all mappings in $\mathcal{M}{}_{D\rightarrow G.{\mathtt{I}}{}}$ that satisfy constraint ${\mathsf{c}}$ (2.5)
$\Pr[SAT_{{\mathsf{c}}}^{D\rightarrow G.{\mathtt{I}}{}}]$ $\Pr[\mathcal{S}_{{\mathsf{c}}}]$ |  Fraction of all mappings in $\mathcal{M}{}_{D\rightarrow G.{\mathtt{I}}{}}$ that satisfy constraint ${\mathsf{c}}$ (2.5)
$\Pr[\mathcal{S}_{{\mathsf{C}}{}}]$ |  Fraction of all mappings in $\mathcal{M}{}_{D\rightarrow G.{\mathtt{I}}{}}$ that satisfy all constraints in ${\mathsf{C}}$ (2.5)
$PE$ |  Partial Estimate (3)
$PE.s$ |  Selectivity value of $PE$ (3)
$PE.{\mathsf{C}}{}$ |  Set of constraints in $PE$ (3)
$PET$ |  Partial Estimation Technique (3)
$PES$ |  Partial Estimate Set (3)
$EPEST$ |  Extend PES Technique (3)
$EPES$ |  Extended PES (3)
$CPES$ |  Complete PES (3)
CT |  Combine Technique (3)

###  2.3 Semantics of Query Patterns

Consider a query pattern $Q$ and a property graph instance $G$. Let mapping
${\mathsf{m}}_{Q.{\mathtt{I}}{}\rightarrow G.{\mathtt{I}}{}}$ be a total
function from the edge and vertex identifiers in $Q$ to edge and vertex
identifiers in $G$, i.e. ${\mathsf{m}}$: $Q.{\mathtt{I}}{}\rightarrow
G.{\mathtt{I}}{}$. Let $\mathcal{M}_{Q.{\mathtt{I}}{}\rightarrow
G.{\mathtt{I}}{}}$ be the set of all possible mappings from $Q$ to $G$. Table
II shows a summary of the notation used in this document.

A mapping ${\mathsf{m}}$ is called a homomorphic match222Some systems require
isomorphic matches, which can be obtained by adding the requirement MR5: For
each $i,j\in Q.{\mathtt{I}}{}$: if $i\neq j$, then ${\mathsf{m}}$($i$) $\neq$
${\mathsf{m}}$(j). See [7] for more advanced isomorphic-based semantics, like
no-repeated-node and no-repeated-edge semantics. from $Q$ on $G$ if and only
if the following match requirements are satisfied:

  1. MR1:

For each $v\in Q.$${\mathtt{V}}$: ${\mathsf{m}}$($v$) $\in G$.${\mathtt{V}}$;

  2. MR2:

For each $e\in Q$.${\mathtt{E}}$: if $Q.$$\rho$($e$)=($s$,$t$),
then
$G.$$\rho$(${\mathsf{m}}$($e$))=(${\mathsf{m}}$($s$),${\mathsf{m}}$($t$));

  3. MR3:

For each $i\in Q.{\mathtt{I}}{}$ and $l\in Q.{\mathtt{Lab}}$:
if $l$ $\in$ Q.$\lambda$($i$), then $l$ $\in$
$G.$$\lambda$(${\mathsf{m}}$($i$));

  4. MR4:

For each $i\in Q.{\mathtt{I}}{},k\in Q.{\mathtt{Prop}},\theta\in Q.\Theta$ and
$v\in Q.$${\mathtt{Val}}$: if $Q.$$\sigma$($i$, $k$, $\theta$) = $v$, then
$G.$$\sigma$(${\mathsf{m}}$($i$), $k$) = $w$ and $w\theta v$333Here, we use
the infix notation of the binary predicate $\theta$ holds for some $w\in
G.$${\mathtt{Val}}$.

Here, MR1 and MR2 require that the mapping agrees with the topology defined in
the query. Notice that MR1 is required when the query contains disconnected
vertices. MR3 defines constraints on the existence of labels and MR4 defines
constraints on the existence of properties.

Finding all matches for a query pattern is also called subgraph pattern
matching and is at the core of many query languages[7], e.g.
SPARQL444https://www.w3.org/TR/rdf-sparql-query/,
Cypher555https://neo4j.com/developer/cypher/, PGQL[8], G-CORE[9].

The total number of mappings is $|\mathcal{M}_{Q,G}|$, where $|S|$ denotes the
cardinality of set $S$. The number of these mappings that are matches is
called the cardinality of $Q$ on $G$ and the fraction is called the
selectivity.

###  2.4 Query Constraints

Given a query pattern $Q$, the set of constraints of $Q$, ${\mathsf{C}}{}(Q)$,
is defined as follows:

  1. 1.

For each vertex id $v\in Q.{\mathtt{V}}$: vertex($v$) $\in{\mathsf{C}}{}(Q)$

  2. 2.

For each edge id $e\in Q.{\mathtt{E}}$: edge($e$) $\in{\mathsf{C}}{}(Q)$

  3. 3.

For each edge id $e\in Q.{\mathtt{E}}$:
if $Q.$$\rho$($e$)=($s$,$t$),
then src(s,e) $\in{\mathsf{C}}{}(Q)$ and trg(t,e) $\in{\mathsf{C}}{}(Q)$

  4. 4.

For each $i\in Q.{\mathtt{I}}{}$ and $l\in Q.{\mathtt{Lab}}$:
If $l\in Q.\lambda(i)$,
then hasLabel($i$,$l$) $\in{\mathsf{C}}{}(Q)$

  5. 5.

For each $i\in Q.{\mathtt{I}}{},k\in Q.{\mathtt{Prop}}$, $\theta\in Q.\Theta$
and $v\in Q.{\mathtt{Val}}$:
If $Q.\sigma(i,k,\theta)=v$,
then hasPropKey($i$,$k$) $\in{\mathsf{C}}{}(Q)$ and
hasProp($i$,$k$,$\theta$,$v$) $\in{\mathsf{C}}{}(Q)$

  6. 6.

${\mathsf{C}}{}(Q)$ does not contain any other constraints

A single constraint is denoted by ${\mathsf{c}}$, a set of constraints by
${\mathsf{C}}{}$ and the set of all constraints of $Q$ by ${\mathsf{C}}{}(Q)$.
A constraint contains one or two identifiers from a query $Q$. Let
${\mathsf{C}}{}.{\mathtt{I}}{}$ represent the set of query identifiers
contained in the constraints ${\mathsf{C}}{}$.

Given a ${\mathsf{c}}$ constraint, a mapping
${\mathsf{m}}_{\\{{\mathsf{c}}\\}.{\mathtt{I}}{}\rightarrow G.{\mathtt{I}}{}}$
and a graph $G$, it is possible to verify if ${\mathsf{m}}$ satisfies
${\mathsf{c}}$ in $G$:

  * •

If ${\mathsf{c}}=$vertex($i$), then verify if ${\mathsf{m}}(i)\in
G.{\mathtt{V}}$

  * •

If ${\mathsf{c}}=$edge($i$), then verify if ${\mathsf{m}}(i)\in
G.{\mathtt{E}}$

  * •

If ${\mathsf{c}}=$src($v$,$e$), then verify if
$G.$$\rho$(${\mathsf{m}}(e)$)=(${\mathsf{m}}(v)$,$v^{\prime}$) for some
$v^{\prime}\in G.{\mathtt{V}}$

  * •

If ${\mathsf{c}}=$trg($v$,$e$), then verify if
$G.$$\rho$(${\mathsf{m}}(e)$)=($v^{\prime}$,${\mathsf{m}}(v)$) for some
$v^{\prime}\in G.{\mathtt{V}}$

  * •

If ${\mathsf{c}}=$hasLabel($i$,$l$), then verify if
$l\in\lambda({\mathsf{m}}(i))$

  * •

If ${\mathsf{c}}=$hasPropKey($i$,$k$), then verify if
$G.\sigma({\mathsf{m}}(i),k)=w$ is defined for some $w\in G.{\mathtt{Val}}$

  * •

If ${\mathsf{c}}=$hasProp($i$,$k$,$\theta$,$v$), then verify if
$G.\sigma({\mathsf{m}}(i),k)=w$ and $w\theta v$ holds for some $w\in
G.{\mathtt{Val}}$

A mapping ${\mathsf{m}}_{Q.{\mathtt{I}}{}\rightarrow G.{\mathtt{I}}{}}$
satisfies all constraints ${\mathsf{C}}{}(Q)$ of query $Q$ in graph $G$, if
and only if ${\mathsf{m}}_{Q.{\mathtt{I}}{}\rightarrow G.{\mathtt{I}}{}}$ is a
homomorphic match from $Q$ to $G$. Table III shows the categorization of
constraints based on what they primarily deal with: _topology_ or _data_.

###### Example 2.2

The constraints ${\mathsf{C}}{}(Q)$ of the query pattern $Q$ in Figure 1 are
given as follows:

${\mathsf{c}}_{0}$: vertex(id0),…, ${\mathsf{c}}_{4}$: vertex(id8),
${\mathsf{c}}_{5}$: edge(id1),…, ${\mathsf{c}}_{8}$: edge(id7),
${\mathsf{c}}_{9}$: src(id0,id1),…, ${\mathsf{c}}_{16}$: trg(id8,id7),
${\mathsf{c}}_{17}$: hasLabel(id0,title),…, ${\mathsf{c}}_{25}$:
hasLabel(id8,person),
${\mathsf{c}}_{26}$: hasProp(id6,note,IN,[’(producer)’,’
(executive producer)’]),
${\mathsf{c}}_{27}$: hasProp(id8,gender,=,’m’),
${\mathsf{c}}_{28}$: hasProp(id8,name,CONTAINS,’Tim’),
${\mathsf{c}}_{29}$: hasPropKey(id6,note),
${\mathsf{c}}_{30}$: hasPropKey(id8,gender),
${\mathsf{c}}_{31}$: hasPropKey(id8,name).

id8:person gender=’m’ name CONTAINS ’Tim’ id2:movieInfo id0:title
id4:movieInfoIdx id6:cast_info note IN [’(producer)’,’(executive producer)’]
id7:cast_info_person id5:cast_info_movie id1:budget id3:votes  Figure 1: JOB
query 18a visualized as a query pattern Table III: Categorization of
constraints Query Pattern Constraints
---
Query Pattern Schema Constraints | Property-value Constraints
Labeled Topological Constraints | Property Constraints
Topological Constraints | Data Constraints
vertex($i$) | edge($i$) | src($v$,$e$) | trg($v$,$e$) | hasLabel($i$,$l$) | hasPropKey($i$,$k$) | hasProp($i$,$k$,$\theta$,$v$)

###  2.5 Probability, Selectivity and Cardinality

Consider obtaining a random mapping ${\mathsf{m}}_{Q.{\mathtt{I}}{}\rightarrow
G.{\mathtt{I}}{}}$ from $\mathcal{M}_{Q.{\mathtt{I}}{}\rightarrow
G.{\mathtt{I}}{}}$ by throwing a fair $|G.{\mathtt{I}}{}|$-sides dice for
every $i\in Q.{\mathtt{I}}{}$ to obtain ${\mathsf{m}}(i)$. This gives a sample
space of $G.{\mathtt{I}}{}_{1}\times\dots\times
G.{\mathtt{I}}{}_{|Q.{\mathtt{I}}{}|}$. Then, the probability of obtaining
mapping ${\mathsf{m}}=(\omega_{1},\dots,\omega_{|Q.{\mathtt{I}}{}|})$ is

$\displaystyle\Pr[(\omega_{1},\dots,\omega_{|Q.{\mathtt{I}}{}|})]$
$\displaystyle=\Pr[\omega_{1}]\cdot...\cdot\Pr[\omega_{|Q.{\mathtt{I}}{}|}]=(1/|G.{\mathtt{I}}{}|)^{|Q.{\mathtt{I}}{}|},$

because the outcomes of the dice throws are mutually independent.

Subsets of the sample space are called events. Let
$SAT_{{\mathsf{c}}}^{Q.{\mathtt{I}}{}\rightarrow G.{\mathtt{I}}{}}$ be the
event that contains all mappings in $\mathcal{M}_{Q.{\mathtt{I}}{}\rightarrow
G.{\mathtt{I}}{}{}}$ that satisfy the constraint ${\mathsf{c}}$:

$\displaystyle SAT_{{\mathsf{c}}}^{Q.{\mathtt{I}}{}\rightarrow
G.{\mathtt{I}}{}}$
$\displaystyle=\\{{\mathsf{m}}\in\mathcal{M}_{Q.{\mathtt{I}}{}\rightarrow
G.{\mathtt{I}}{}{}}\mid{\mathsf{m}}\text{ satisfies constr }{\mathsf{c}}\\}.$

Since each element from our sample set has the same probability, the
probability of event $SAT_{{\mathsf{c}}}^{Q.{\mathtt{I}}{}\rightarrow
G.{\mathtt{I}}{}}$ is defined as:

$\displaystyle\Pr[SAT_{{\mathsf{c}}}^{Q.{\mathtt{I}}{}\rightarrow
G.{\mathtt{I}}{}}]$
$\displaystyle=\frac{|SAT_{{\mathsf{c}}}^{Q.{\mathtt{I}}{}\rightarrow
G.{\mathtt{I}}{}}|}{|\mathcal{M}_{Q.{\mathtt{I}}{}\rightarrow
G.{\mathtt{I}}{}{}}|}=\frac{|SAT_{{\mathsf{c}}}^{{\mathsf{c}}.{\mathtt{I}}{}\rightarrow
G.{\mathtt{I}}{}}|}{|\mathcal{M}_{{\mathsf{c}}.{\mathtt{I}}{}\rightarrow
G.{\mathtt{I}}{}}|}$

The event “${\mathsf{m}}$ satisfies all constraints in ${\mathsf{C}}{}$” can
be expressed as:
$\bigcap_{{\mathsf{c}}\in{\mathsf{C}}{}}\mathcal{S}_{{\mathsf{c}}}$666Whenever
$Q$ and $G$ are clear from the context or not relevant for the discussion, we
write $\mathcal{S}_{{\mathsf{c}}}$ instead of
$SAT_{{\mathsf{c}}}^{Q.{\mathtt{I}}{}\rightarrow G.{\mathtt{I}}{}}$.. This
will be written shortly as $\mathcal{S}_{{\mathsf{C}}{}}$. Notice that the
event $\mathcal{S}_{{\mathsf{C}}{}_{i}\cup{\mathsf{C}}{}_{j}}$ represents the
set of mappings that satisfy all constraints in ${\mathsf{C}}{}_{i}$ and all
constraints in ${\mathsf{C}}{}_{j}$. This corresponds to
$\mathcal{S}_{{\mathsf{C}}{}_{i}}\cap\mathcal{S}_{{\mathsf{C}}{}_{j}}$.
Whereas the event
$\mathcal{S}_{{\mathsf{C}}{}_{i}}\cup\mathcal{S}_{{\mathsf{C}}{}_{j}}$
represents the set of mappings that satisfies all constraints in
${\mathsf{C}}{}_{i}$ or all constraints in ${\mathsf{C}}{}_{j}$. Figure 2
shows an example with the notation introduced in this section.

Within the database literature, the term “selectivity of ${\mathsf{c}}$” is
usually used to represent the probability $\Pr[\mathcal{S}_{{\mathsf{c}}}]$.
In this document, we will use both terms interchangeably, since they mean the
same thing. The _goal_ in this document is to estimate the selectivity
$\Pr[\mathcal{S}_{{\mathsf{C}}{}(Q)}]$, since multiplying this with
$|\mathcal{M}_{Q.{\mathtt{I}}{}\rightarrow G.{\mathtt{I}}{}{}}|$ (which is
equal to $|G.{\mathtt{I}}{}|^{|Q.{\mathtt{I}}{}|}$) gives an estimate for the
cardinality $|\mathcal{S}_{{\mathsf{C}}{}(Q)}|$.

$Q$q1 q3 q2 $G$$\Omega_{G}=\\{g1,g2,g3,g4\\}$g1 g3 g2 g4 $\mathcal{M}{}=\\{(g1,g1,g1),\dots,(g3,g4,g1),\dots,(g4,g4,g4)\\}$ $\mathcal{S}_{\text{{vertex(q1)}}}$ | $=\\{(g1,*,*),(g3,*,*)\\}$
---|---
$\mathcal{S}_{\text{{vertex(q3)}}}$ | $=\\{(*,*,g1),(*,*,g3)\\}$
$\mathcal{S}_{\text{{edge(q2)}}}$ | $=\\{(*,g2,*),(*,g4,*)\\}$
$\mathcal{S}_{\text{{src(q1,g2)}}}$ | $=\\{(g1,g2,*),(g3,g4,*)\\}$
$\mathcal{S}_{\text{{trg(q3,q2)}}}$ | $=\\{(*,g2,g3),(*,g4,g1)\\}$
where $(x,*,*)$ expands to $(x,g1,g1),(x,g1,g2),\dots,(x,g4,g4)$ $\mathcal{S}_{{\mathsf{C}}{}(Q)}$ | $=\bigcap_{{\mathsf{c}}\in{\mathsf{C}}{}(Q)}\mathcal{S}_{{\mathsf{c}}}$
---|---
|
$=\mathcal{S}_{\text{{vertex(q1)}}}\cap\dots\cap\mathcal{S}_{\text{{trg(q3,q2)}}}$
| $=\\{(g1,g2,g3),(g3,g4,g1)\\}$
Figure 2: The set $\mathcal{S}_{{\mathsf{C}}{}(Q)}$ can be obtained by taking
the intersection of the events $\mathcal{S}_{{\mathsf{c}}}$ for
${\mathsf{c}}\in{\mathsf{C}}{}(Q)$.

##  3 Selectivity Estimation Framework

The task of obtaining an estimate for the selectivity of a query can be
simplified by first obtaining estimates for _subsets_ of the query constraints
and then _combining_ those estimates.

An estimate for a subset of the query constraints is called a partial estimate
(PE). A PE contains a set of constraints (PE.${\mathsf{C}}$) and a selectivity
estimate (PE.$s$) for that set of constraints, such that
$\Pr[\mathcal{S}_{PE.{\mathsf{C}}{}}]$ is approximated by $PE.s$. The set of
all PEs for a query will be called its partial estimate set (PES).

Techniques that are able to obtain PEs are called Partial Estimation
Techniques (PETs). A PET requires specific statistics or indexes
(prerequisites) in order to obtain a PE for a specific set of constraints
(targeted set of constraints) using a specialized procedure (estimation
procedure). For each PET, these three elements will be described (summarized
in Table V). Techniques that rely on the existence of other partial estimates
are called Extend PES Techniques (EPESTs). They add PEs to the PES by
combining several PEs using specialized assumptions. The resulting set of PEs
is called an Extended PES (EPES). Finally, a selectivity estimate for a query
pattern is obtained by combining all PEs of a complete PES (CPES) using a
general combine technique (CT).

Notice that a PES777We will refer to EPES and CPES usually as PES when it will
not lead to ambiguity. should be complete before it can be combined. A PES is
complete w.r.t. a query $Q$, when every constraint from ${\mathsf{C}}{}(Q)$
occurs is at least one partial estimate from the PES. Therefore, it must hold
that $\bigcup_{PE\in PES_{Q}}PE.{\mathsf{C}}{}={\mathsf{C}}{}(Q)$. A PES can
be made complete by adding a PE of each missing constraint with a default
selectivity value.

The general framework is illustrated in Figure 3, where the gray dashed boxes
are considered as input and the green dashed box as output. 888The statistics
collection procedure, i.e. the step from graph instance to statistics, is
separate from the estimation procedure. It can be executed after batch loading
of a graph instance, at user’s request, at low system utilization, at periodic
intervals or at demand. Some statistics can also be obtained using a feedback
loop after executing queries. Processes are shown as boxes with sharp corners
and input and output are shown as boxes with rounded corners. The blue boxes
represent the three phases of the framework, for which multiple techniques are
available. Partially overlapping blue boxes mean that zero or more options can
be chosen. Algorithm 1 shows the whole framework in more detail.

Data: $Q$: a query pattern

Data: $stats_{G}$: available statistics for instance $G$

Data: $PETs$: A set of partial estimation techniques

Data: $EPESTs$: A set of extend PES techniques

Data: $CT$: Combination technique

Result: Selectivity estimate for $Q$ on graph instance $G$, i.e. an estimate
for $\Pr_{G}[\mathcal{S}_{{\mathsf{C}}{}(Q)}]$,

$PES_{Q}$ = {};

for  _each partial estimation technique $PET$ in $PETs$_ do

$cSets$ $\leftarrow$ find all sets of constraints (subsets of
${\mathsf{C}}{}(Q)$) that belong to the targeted set of constraints of $PET$;

for  _each $cSet$ in $cSets$_ do

if  _required stats are available in $stats_{G}$ to obtain an estimate for
$cSet$ using $PET$_ then

$selEst$ $\leftarrow$ obtain selectivity estimate for $cSet$ using statistics
and estimation procedure from $PET$;

add $(cSet,selEst)$ to $PES_{Q}$;

end for

end for

$EPES_{Q}$ = {};

$EPES_{Q}$.addAll($PES_{Q}$);

for  _each Extend PES Technique $EPEST$ in $EPESTs$_ do

$EPEs\leftarrow$ obtain extended partial estimates using $EPEST(PES_{Q},Q)$;

$EPES_{Q}$.addAll($EPEs$);

end for

$CPES_{Q}$ = makeComplete($EPES_{Q},Q$);

$selEst\leftarrow$ combine all PEs in $CPES_{Q}$ using $CT$;

return $selEst$;

Algorithm 1 Selectivity Estimation Framework Figure 3: Selectivity Estimation
Framework

##  4 PETs for Individual Constraints

This section deals with PETs for obtaining estimates for individual
constraints. The targeted set of constraints consists of individual
constraints of a specific type. The following subsections will describe the
estimation procedures and prerequisites for each type.

Vertex constraints. The constraint vertex($i$) is satisfied for every mapping
that maps query id $i$ to an element in $G.{\mathtt{V}}$. All other query ids
can be mapped to any element in $G.{\mathtt{I}}{}$. This gives a total of
$|G.{\mathtt{V}}|\cdot|G.{\mathtt{I}}{}|^{|Q.{\mathtt{I}}{}|-1}$ mappings in
event $SAT_{\text{{vertex($i$)}}}^{Q.{\mathtt{I}}{}\rightarrow
G.{\mathtt{I}}{}}$. Therefore,
$\Pr[\mathcal{S}_{\text{{vertex($i$)}}}]=\frac{|G.{\mathtt{V}}|\cdot|G.{\mathtt{I}}{}|^{|Q.{\mathtt{I}}{}|-1}}{|G.{\mathtt{I}}{}|^{|Q.{\mathtt{I}}{}|}}=\frac{|G.{\mathtt{V}}|}{|G.{\mathtt{I}}{}|}$.
The required prerequisites are stored values for $|G.{\mathtt{V}}|$ and
$|G.{\mathtt{I}}{}|$.

Edge constraints. The selectivity of edge($i$) constraints, where $i\in
Q.{\mathtt{I}}{}$, is $|G.{\mathtt{E}}|/|G.{\mathtt{I}}{}|$. Required
prerequisites are stored values for $|G.{\mathtt{E}}|$ and
$|G.{\mathtt{I}}{}|$.

Src/Trg constraints. The constraint src($i_{1}$,$i_{2}$) is satisfied if
$i_{1}$ is mapped to an element $v\in G.{\mathtt{V}}$ and $i_{2}$ is mapped an
element in $e\in G.{\mathtt{E}}$ such that $G.$$\rho$($e$)=($v$,$v^{\prime}$)
for some $v^{\prime}\in G.{\mathtt{V}}$. Each edge has exactly one source
vertex, therefore $i_{2}$ can be mapped to any element in $G.{\mathtt{E}}$,
then there remains only one option for $i_{1}$. All other query ids can be
mapped to any element in $G.{\mathtt{I}}{}$. This gives a total of
$|G.{\mathtt{E}}|\cdot 1\cdot|G.{\mathtt{I}}{}|^{|Q.{\mathtt{I}}{}|-2}$
mappings in $SAT_{\text{{src($i_{1}$,$i_{2}$)}}}^{Q.{\mathtt{I}}{}\rightarrow
G.{\mathtt{I}}{}}$. Therefore,
$\Pr[\mathcal{S}_{\text{{src($i_{1}$,$i_{2}$)}}}]=\frac{|G.{\mathtt{E}}|\cdot|G.{\mathtt{I}}{}|^{|Q.{\mathtt{I}}{}|-2}}{|G.{\mathtt{I}}{}|^{|Q.{\mathtt{I}}{}|}}=\frac{|G.{\mathtt{E}}|}{|G.{\mathtt{I}}{}|^{2}}$.
Required prerequisites are $|G.{\mathtt{E}}|$ and $|G.{\mathtt{I}}{}|$. The
selectivity of trg($i_{1}$,$i_{2}$) is the same, because each edge also has
exactly one target vertex.

Label constraints. When the number of different labels ($|G.{\mathtt{Lab}}|$)
is small, $\Pr[\mathcal{S}_{\text{{hasLabel($i$,$l$)}}}]$ can be precomputed
for every $l\in G.{\mathtt{Lab}}$ (prerequisites). Otherwise, it is possible
to treat them as property values with a special property key, e.g. ’hasLabel’,
and use one of the selectivity estimation methods for property-value
constraints.

Property-key constraints. When the number of different property keys
($|G.{\mathtt{Prop}}|$) is small,
$\Pr[\mathcal{S}_{\text{{hasPropKey($i$,$k$)}}}]$ can be precomputed for every
$k\in G.{\mathtt{Prop}}$ (prerequisites). Otherwise, it is possible to treat
them as property values with a special property key, e.g. ’hasKey’, and use
one of the selectivity estimation methods for property-value constraints.

Property-value constraints. The remaining constraints are the property-value
constraints, e.g. hasProp($i$,birthyear,$\leq$,2000). Storing the exact
selectivity of every property constraint in a synopsis (prerequisites)
requires only a synopsis lookup (estimation procedure) to obtain the exact
selectivity. However, storing exact selectivities can be prohibitively
expensive as the set $G.$${\mathtt{Val}}$ can be very large in property graph
instances. This requires specialized techniques to obtain estimates for the
selectivity of those constraints.

One way is to assign default selectivity values based on the operator used,
i.e. property constraints with equality operator get a selectivity estimate of
$1/10$, with inequality get $9/10$ and with other operators get $1/3$[10]. We
will call this technique “Default values”. This technique has no prerequisites
and the estimation procedure consist of applying simple rules, i.e. if
operator is ’=’, then selectivity is $1/10$.

Another way is to store a small sample of the whole data and compute the
selectivity of a constraint on that sample when needed. Use that selectivity
as an approximation of the selectivity on the whole data. Prerequisite for
this technique is a sample of $G.{\mathtt{I}}{}$. Sampling is very diverse,
but is known to have problem with highly selective constraints and requires
large estimation times [11].

Property constraints with a comparison operator, i.e. $=,\neq,<,\leq,>,\geq$,
can be approximated using histograms. A histogram summarizes the distribution
of a collection of element by partitioning them into buckets. Different
partitioning schemes have been introduced[12, 13] which makes it possible to
choose between construction complexity and estimation accuracy. Assumptions
are used to approximate the values and their frequencies within the buckets.
Prerequisites are histograms for the property keys.

Property constraints with a substring operator, i.e. ’CONTAINS’ or ’LIKE’ in
SQL, can be approximated using pruned suffix trees (PSTs) [14].

A summary of the different techniques is given in Table IV. The different
approaches all have their own advantages and disadvantages, which makes them
useful in different scenarios. Also, multiple techniques can be used. Most
frequently occurring query constraints can be precomputed. Histograms can be
constructed for property keys that occur in many constraints with comparison
operators. While the remaining constraints can be estimated using sampling or
using default values.

Table IV: Obtain estimates for individual constraints Technique | Prerequisites | Acc | EstTime | Mem | PrepTime
---|---|---|---|---|---
Synopsis Lookup |  Exact selectivity of all indiv. constraints | \+ + | \+ + | \- - | \- -
Default values | None | \- - | \+ + | ++ | \+ +
Sampling |  Sample of $G.$${\mathtt{I}}$ | +/- | - | + | +
Histograms/PSTs |  Histogram/PST for every property key | +/- | + | - | -

##  5 PETs for Multiple Constraints

Previous section showed techniques for estimating the selectivity of every
individual constraint. The techniques described in this section are able to
obtain estimates for multiple constraints (Table V shows a summary), but are
not applicable in general to obtain an estimate for _any_ possible query
pattern. Section 7 shows how all estimates obtained for multiple constraints
(in this section) and for each individual constraint (in the previous section)
can be combined to obtain a final estimate for any query pattern.

When the estimation procedure obtains a cardinality estimate $c$ for the set
of constraints ${\mathsf{C}}$, then the selectivity estimate
$\Pr[\mathcal{S}_{{\mathsf{C}}{}}]$ is
$c/|G.{\mathtt{I}}{}|^{|{\mathsf{C}}{}.{\mathtt{I}}{}|}$.

Table V: Summary of different PETs for obtaining estimates for multiple constraints. Technique |  Targeted Set of Constraints |  Prerequisites |  Estimation Procedure
---|---|---|---
Topological Synopsis |  Topological Patterns |  Topological Synopsis |  Synopsis Lookup
Labeled Topological Synopses [15] |  Labeled Topological Patterns |  Labeled Topological Synopsis |  Synopsis Lookup
System R’s Join Size Estimation [10] |  Labeled Star Patterns |  Cardinality and the number of distinct source and target vertices of every labeled edge pattern |  Apply inclusion and uniform distribution assumptions
BoundSketch [16] |  Any Labeled Topological Pattern |  Cardinality and maximum degree for every vertex in every partition |  Use upper bound as cardinality estimate. Obtain upper bound by using degree statistics and partitioning.
Characteristic Sets [17] |  Source/Target Labeled Topological Patterns |  For each CS in the data: the number of vertices that have that CS and the count for each label in that CS |  Find the CSs in the data that are supersets of the query CS and sum their contributions.
Multidimensional Histograms [18, 19] |  Property-value constraints to same query id |  The multidimensional histograms |  Sum the fractions of the buckets in the histogram that satisfy the constraints.
Sampling |  Any set of query pattern constraints on a specific pattern type |  A random sample of all patterns in the data that belong to a specific pattern type |  Use the fraction of the sample that satisfies the constraints as selectivity estimate.
Wander Join [20] |  Any set of constraints such that a valid walk plan (ordering of the query edges) exists |  Indexes to efficiently perform a random walk |  Perform random walks. If the walk satisfies the constraints, then add 1/(probability of obtaining that walk) to the result. Divide the result by the number of random walks performed to obtain the cardinality estimate

###  5.1 Estimation for Topological Constraints

The topology of a graph refers to its vertices, edges and their connectivity.
Different topological patterns can be defined, which are subclasses of general
query patterns:

  * •

An edge pattern, $i_{1}$$i_{3}$$i_{2}$, consists of a single edge together
with its source and target vertices.

  * •

A chain pattern,
$i_{1}$$i_{3}$$\dots$$i_{x-2}$$i_{x}$$i_{2}$$i_{4}$$i_{x-3}$$i_{x-1}$, is a
chain of edge patterns in one direction. Let $ep_{1},ep_{2},\dots ep_{n}$ be
edge patterns. Then, $ep_{1}/ep_{2}/\dots/ep_{n}$ is a chain pattern when the
target vertex of $ep_{j}$ is the source vertex of $ep_{j+1}$ for all $1\leq
j\leq n-1$.

  * •

A star pattern is a set of edge patterns that all have a common vertex. When
all edge patterns have a common source vertex, then the pattern is also called
a source star pattern, $i_{1}$$\dots$$\dots$$\dots$ . When all edge patterns
have a common target vertex, then the pattern is also called a target star
pattern, $i_{1}$$\dots$$\dots$$\dots$ .

Other frequently occurring patterns in the query workload can be used, e.g.
triangles, cycles, trees, etc. See Bonifati et al. [5] for a study of
frequently occurring query patterns.

The size of a topological pattern is defined as the number of edge patterns
involved in that pattern.

###### Example 5.1

The query pattern in Figure 1 contains, among others, four subpatterns that
are edge patterns, two subpatterns that are size-2 chain patterns and two
subpatterns that are size-2 source star patterns.

####  5.1.1 Topological Synopsis Lookup

A topological synopsis contains the cardinalities of topological patterns. For
example, it can contain the cardinalities of a chain pattern of size $2$ and
source star patterns of size $2$ and $3$. The cardinalities can be precomputed
and stored at a small cost, when the patterns are small.

Targeted Set of Constraints. All topological subpatterns of the query pattern
for which the synopsis stores its cardinality.

Prerequisites. The topological synopsis.

Estimation Procedure. The cardinality can be obtained using a lookup in the
synopsis.

###  5.2 Estimation for Labeled Topological Constraints

Vertices and edges can have labels, which can have a large impact on the
cardinality of a query.

Labeled topological patterns are an extension of topological patterns, where
each query id is allowed to have at most one label e.g., a labeled edge
pattern, labeled chain pattern, etc.

####  5.2.1 Labeled Topological Synopsis Lookup

A labeled topological synopsis contains cardinalities of labeled topological
patterns belonging to a specific class, e.g. labeled edge patterns or labeled
chain patterns of size $2$.

The specific pattern class and its size are considered the parameters of a
labeled topological synopsis. For example, a labeled topological synopsis can
be specified by labTopSyn(chain, $2$), which represents a synopsis which
stores the cardinality of all labeled chain patterns of size $2$.

Aboulnage et al. [15] introduced a synopsis for labeled chain pattern up to
size $n$ and used that synopsis to obtain estimates for labeled chain patterns
of size $m>n$ using Markov Chains:

$\displaystyle\Pr[\mathcal{S}_{{\mathsf{C}}{}(t_{1}/\dots/t_{m})}]=$
$\displaystyle\Pr[\mathcal{S}_{{\mathsf{C}}{}(t_{1}/\dots/t_{n})}]\cdot\prod_{i=1}^{m-n}\frac{\Pr[\mathcal{S}_{{\mathsf{C}}{}(t_{1+i}/\dots/t_{n+i})}]}{\Pr[\mathcal{S}_{{\mathsf{C}}{}(t_{1+i}/\dots/t_{n+i-1})}]}$

where $t_{i}/\dots/t_{j}$ represents a chain of labeled edge patterns $t_{x}$
for $i\leq x\leq j$. This formula is a special case of the combination
technique based on conditional independence (with sorting strategy based on
maximum overlap), which is explained in detail in Section 7.1.

Targeted Set of Constraints. All subpatterns of the query pattern belonging to
the pattern class of the labeled topological synopsis.

Prerequisites. The labeled topological synopsis.

Estimation Procedure. The cardinality can be obtained using a lookup in the
synopsis.

####  5.2.2 System R’s Join Size Estimation using Inclusion and Uniform
Distribution Assumptions

Join size estimation in relational databases has its origin from System R
[10]. Considering each labeled edge pattern as a relation, with an attribute
for the source vertex id, edge id and target vertex id, allows us to apply
System R’s join size estimation method in the context of this document.

System R uses the cardinality and column cardinality of each relation (i.e.
number of edges and number of distinct source and target vertices for each
labeled edge pattern), and three assumptions to estimate the cardinality of
any sequence of equality joins (i.e. any labeled topological pattern). The
three assumptions are 1) the inclusion assumption (all values in the joining
attribute with the lowest number of distinct values are included in the set of
values of the other joining attribute), 2) the uniform distribution assumption
(all distinct values of an attribute have the same frequency) and 3) the
preservation of value set assumption (all distinct values in the non-joining
attributes are preserved after the join).

Targeted Set of Constraints. Using all three assumptions, it is possible to
obtain cardinality estimates for any labeled topological pattern. Using only
the first two assumptions, it is possible to obtain estimates for any star
pattern, which will be the focus of this section.

Prerequisites. Let $S_{G}(ep)$ and $T_{G}(ep)$ be the multiset of source and
target vertices on the edges in $G$ that match labeled edge pattern $ep$. Let
$S^{\prime}_{G}(ep)$ and $T^{\prime}_{G}(ep)$ be the set versions of
$S_{G}(ep)$ and $T_{G}(ep)$, where duplicates are eliminated.

This approach can be applied to star pattern $S$ when the following statistics
are available for every edge pattern $ep$ in $S$ for graph instance $G$:

  * •

$n_{G}(ep)$: cardinality of $ep$ in $G$

  * •

$|S^{\prime}_{G}(ep)|$: the number of distinct source vertices of the edges in
$G$ that match $ep$

  * •

$|T^{\prime}_{G}(ep)|$: the number of distinct target vertices of the edges in
$G$ that match $ep$

Estimation Procedure. Let $f(M,v)$ represent the frequency of vertex $v$ in
multiset $M$. Consider a labeled star pattern that consists of labeled edge
patterns $\\{ep_{1},\dots,ep_{n}\\}$ and a center vertex $v$. Let
$X_{G}(ep_{i})$ be $S_{G}(ep_{i})$ if $v$ is the source vertex of $ep_{i}$ and
$T_{G}(ep_{i})$ if $v$ is the target vertex of $ep_{i}$.

In general, the cardinality of the star pattern is

$\displaystyle\sum_{v\in X^{\prime}_{G}(ep_{1})\cap\dots\cap
X^{\prime}_{G}(ep_{n})}\prod_{1\leq i\leq n}f(X_{G}(ep_{i}),v)$

Assuming a uniform distribution gives:

$\displaystyle\approx\sum_{v\in X^{\prime}_{G}(ep_{1})\cap\dots\cap
X^{\prime}_{G}(ep_{n})}\prod_{1\leq i\leq
n}\frac{n_{G}(ep_{i})}{|X^{\prime}_{G}(ep_{i})|}$

The sum is independent of the value $v$:

$\displaystyle=|X^{\prime}_{G}(ep_{1})\cap\dots\cap
X^{\prime}_{G}(ep_{n})|\prod_{1\leq i\leq
n}\frac{n_{G}(ep_{i})}{|X^{\prime}_{G}(ep_{i})|}$

Now, use the inclusion assumption to estimate the size of the intersection:

$\displaystyle\approx
min(X^{\prime}_{G}(ep_{1}),\dots,X^{\prime}_{G}(ep_{n}))\prod_{1\leq i\leq
n}\frac{n_{G}(ep_{i})}{|X^{\prime}_{G}(ep_{i})|}$

This makes it possible to estimate the cardinality of a star pattern $S$ using
only $n_{G}(ep),|S^{\prime}_{G}(ep)|$ and $|T^{\prime}_{G}(ep)|$ for every
edge pattern $ep$ in $S$.

####  5.2.3 Bound Sketch

Consider a size-2 labeled chain pattern $ep_{i}/ep_{j}$ =
$i_{1}:l_{1}$$i_{3}:l_{3}$$i_{5}:l_{5}$$i_{2}:l_{2}$$i_{4}:l_{4}$ where
$ep_{i}$ = $i_{1}:l_{1}$$i_{3}:l_{3}$$i_{2}:l_{2}$ and $ep_{j}$ =
$i_{3}:l_{3}$$i_{5}:l_{5}$$i_{4}:l_{4}$ are labeled edge patterns,
$i_{1},i_{2},\dots$ are ids and $l_{1},l_{2},\dots$ are labels.

If the cardinalities of $ep_{i}$ and $ep_{j}$ are known, then the cardinality
of $ep_{i}/ep_{j}$ is at most $|ep_{i}|\cdot|ep_{j}|$. This upper bound occurs
if every mapping from $ep_{i}$ matches with every mapping from $ep_{j}$, which
can be visualized as
$y$$\dots$$\dots$$\dots$$\dots$$\dots$$\dots$$:l_{2}$$:l_{4}$.

Let $d^{v}_{ep}$ be the maximum degree of vertices in ${\mathsf{m}}(v)$ in the
mappings from edge pattern $ep$. Above is a special case where
$d^{i_{3}}_{ep_{i}}=|ep_{i}|$ and where $d^{i_{3}}_{ep_{j}}=|ep_{j}|$.

When $d^{i_{3}}_{ep_{j}}$ is known, then each mapping from $ep_{i}$ can be
matched with at most $d^{i_{3}}_{ep_{j}}$ mappings from $ep_{j}$, which leads
to the upper bound $|ep_{i}|\cdot d^{i_{3}}_{ep_{j}}$ for the cardinality of
$ep_{i}/ep_{j}$. Similar, when $d^{i_{3}}_{ep_{i}}$ is known, then this leads
to the upper bound $d^{i_{3}}_{ep_{i}}\cdot|ep_{j}|$ for the cardinality of
$ep_{i}/ep_{j}$. When both $d^{i_{3}}_{ep_{j}}$ and $d^{i_{3}}_{ep_{i}}$ are
known, the upper bound can be obtained by taking the minimum of both upper
bounds.

Cai et al. [16] improve upon this kind of upper bounds, by partitioning the
data of the join attributes. Their data summary is called a Bound Sketch. For
example, above upper bound can be improved by partitioning the mappings of
$ep_{i}$ and $ep_{j}$ on their values for ${\mathsf{m}}(i_{3})$, and storing
the cardinality and maximum degree for each partition. Then, the cardinality
estimate of the pattern $ep_{i}/ep_{j}$ is the sum of the upper bound obtained
from each partition. The upper bound for the cardinality can be used as an
estimate for the cardinality.

Targeted Set of Constraints. Any labeled topological pattern.

Prerequisites. Cardinality and degree statistics for each partition.

Estimation Procedure. Obtain upper bounds for each bounding formula. Use the
lowest one as cardinality estimate. Obtain an upper bound by applying a
bounding formula to each partition and sum the results.

###  5.3 Estimation for Query Pattern Schema Constraints

The class of schema constraints extends the class of labeled topological
constraints with ’has property key’ constraints.

####  5.3.1 Characteristic Sets

Frequently, in graph instances, many vertices have the same property keys and
the same labels on adjacent edges. This insight was exploited by Neumann and
Moerkotte [17] and will be discussed in this section.

The set of labels on all outgoing edges of a vertex $v$ is called the
Characteristic Set (CS) of $v$, denoted by $CS(v)$ [17]. This definition was
defined on the RDF data model[21, 22]. In the RDF data model, properties are
encoded as edges, with the property key on the edge and the property value on
the target vertex. Since we are focusing on property graphs, we extend the
definition of $CS(v)$ to also include all property keys of vertex $v$.

Targeted Set of Constraints. For each labeled source star pattern, $P_{SS}$,
this approach can produce an estimate for the set of constraints that define
$P_{SS}$, i.e. ${\mathsf{C}}{}(P_{SS})$, together with all ’has property key’
constraints on its center vertex.

Prerequisites. Let $CS(G)$ be the set of all different CSs that occur in the
graph instance $G$. In theory, each vertex can have a different CS, but, in
practice, the number of CSs in an instance is usually much smaller[17].

For each CS $CS^{\prime}\in CS(G)$ in the graph instance $G$, store:

  * •

$|CS^{\prime}|$: The number of vertices $v$ in the data, such that the CS of
$v$ is equal to $CS^{\prime}$ (i.e. $CS(v)=CS^{\prime}$)

  * •

For each edge label $l\in CS^{\prime}$:

    * –

$CS^{\prime}.count(l)$: The total number of outgoing edges with label $l$ from
the vertices with CS $CS^{\prime}$

Each query id can have only one value for a property key in our model.
Therefore, for each property key $k\in CS^{\prime}$,
$CS^{\prime}.count(k)=|CS^{\prime}|$. Therefore, this does not need to be
stored explicitly for every property key in a CS.

A large number of different characteristic sets in a graph instance will lead
to slow estimation time, since finding all supersets of the CS of the query
will lead to a noticeable overhead (see Estimation Procedure). Neumann and
Moerkotte [17] propose to merge a CS into a CS that is a superset to limit to
total number of different CSs. They suggest to keep the $10000$ most frequent
CSs and merge the remaining CSs. Merging is first attempted directly by
finding the smallest possible superset (use the most frequent one as
tiebreaker). When no superset can be found, the set is first split (largest
possible set that is a subset of another CS, and ’the rest’) and then merging
both parts individually.

Estimation Procedure. Let $P^{\prime}_{SS}$ denote the a labeled source star
pattern extended with the ’has property key’ constraints on its center vertex.
Let $CS(P^{\prime}_{SS})$ be the CS of the (sub)query pattern
$P^{\prime}_{SS}$. Estimate the cardinality of $P^{\prime}_{SS}$ as:

$\displaystyle cardEst(P^{\prime}_{SS})\approx$
$\displaystyle\sum_{\\{CS^{\prime}\in CS(G)\mid CS^{\prime}\supseteq
CS(P^{\prime}_{SS})\\}}\left(|CS^{\prime}|\cdot\prod_{e\in
CS(P^{\prime}_{SS})}\frac{CS^{\prime}.count(e)}{|CS^{\prime}|}\right)$

Here, CSs in $CS(G)$ that includes statistics of interest to estimate of the
cardinality of $P^{\prime}_{SS}$ are those that are supersets of
$CS(P^{\prime}_{SS})$. The first part $|CS^{\prime}|$ gives the number of
vertices with CS $CS^{\prime}$. Each vertex with CS $CS^{\prime}$ can have
multiple edges with the label $l\in CS(P^{\prime}_{SS})$. A uniform
distribution is assumed, i.e. each vertex with CS $CS^{\prime}$ has
approximately $\frac{CS^{\prime}.count(l)}{|CS^{\prime}|}$ number of edges
with label $l$. If $e$ is a property key, then
$CS^{\prime}.count(e)=|CS^{\prime}|$.

###### Example 5.2

Our example query from Figure 1 has three CSs with at least two elements:
$C_{Q1}=\\{budget,votes\\}$,
$C_{Q2}=\\{cast\\_info\\_person,cast\\_info\\_movie,note\\}$ and
$C_{Q3}=\\{gender,name\\}$.

With minor differences, this technique can also be used for labeled target
star patterns.

###  5.4 Estimation for Property-value Constraints

All previous approaches focused on obtaining estimates for the topology of the
query and extensions that also include labels and ’has property key’
constraints. Combination of property-value constraints will be the focus of
this section.

####  5.4.1 Multidimensional Histogram

Section 4 showed that the distribution of property values for a specific
property key can be approximated using a histogram. Extension are developed to
approximate joint distributions of values from more than one property key [18,
19].

A difficult question is for which set of property keys to construct a
multidimensional histogram. Bruno and Chaudhuri [23] follow a workload driven
approach to find the combinations of constraints that will benefit most from
additional statistics.

Targeted Set of Constraints. A set of property-value constraints referring to
the same query id.

Prerequisites. A multidimensional histogram for a combination of all property
keys of the property-value constraints.

Estimation Procedure. Find the buckets in the multidimensional histogram that
contain elements that satisfy the constraints and estimate the fraction of the
element within those buckets that satisfy the constraint. The sum of those
values will be the cardinality estimate. Intra bucket estimation is done using
assumptions like the uniform spread and uniform distribution assumption.

###  5.5 Estimation for Query Pattern Constraints

This section will focus on estimation techniques for sets of constraints that
can include any combination of query pattern constraints.

####  5.5.1 Sampling

A sample of all graph instance ids can be used to obtain a cardinality
estimate for any query pattern by evaluating the query pattern on the sample
and scaling up the number of results obtained. However, evaluating a query
pattern over a sample can make the estimation time large, especially when the
sample size needs to be large in order to obtain accurate estimates (e.g. for
queries containing very selective constraints). Therefore, we focus on using
sampling to obtain estimates for small patterns together with all data
constraints on those patterns.

Each graph pattern in the graph instance that belongs to a specific pattern
type is sampled with a specific probability. The pattern type and probability
are considered as the parameters of this technique, i.e. $S(pt,pr)$. As
pattern type, one could think of: id, (labeled) vertex pattern, (labeled) edge
pattern, etc. The probability defines a trade-off between estimation time and
estimation accuracy. A larger probability, is expected to lead to a larger
sample size, a larger estimation time and a better estimation accuracy.

Targeted Set of Constraints. All subpatterns of the query pattern that belong
to the pattern type $pt$ together with all the data constraints on those
subpatterns.

Prerequisites. A random sample of all patterns in the graph instance of the
type $pt$, where each pattern is chosen with a probability of $pr$.

Estimation Procedure. The selectivity can be estimated by the fraction of the
patterns in the sample that satisfy all the data constraints. This approach
assumes that the sample is representative for the whole collection of
patterns, i.e. the fraction of patterns that satisfy the constraints is the
same in the sample and in the whole collection.

###### Example 5.3

$S(id,0.001)$ can obtain an estimate for the constraints vertex(id8),
hasLabel(id8,person), hasProp(id8,gender,=,m), hasProp(id8,name,CONTAINS,Tim)
from Figure 1, because they all refer to the same query id, namely $id8$.

####  5.5.2 Wander Join

Wander Join [20] is a sampling technique that obtains samples of the results
of a (sub)query by performing random walks over the topology of the
(sub)query.

Targeted Set of Constraints. Any set of constraints on the subpatterns of the
query pattern, such that there exists an ordering of the query edges
($e_{1},e_{2},\dots,e_{n}$) where $e_{i}$ has a common vertex with some
$e_{j}$ where $j<i$ and $e_{i}$ has an index on that vertex.

Prerequisites. Indexes to efficiently obtain all edges with a specific source
or target vertex, in order to perform efficient random walks.

Estimation Procedure. Perform $x$ random walks according to the valid order,
where $x$ is a parameter that defines the trade-off between estimation time
and estimation accuracy. Each random walk returns a value. For cardinality
estimation this would be either $1$ or $0$ (i.e. the random walk satisfies all
constraints or it does not). Divide the value by the probability of occurrence
of the walk that was obtained. Finally, take the average over the values
obtain by the $x$ random walks to obtain a cardinality estimate.

##  6 Extend PES Techniques

Techniques that can obtain partial estimates for query patterns that rely on
the existence of other partial estimates are covered in this section.

###  6.1 Implied Constraints

If the constraint src($i_{1}$,$i_{2}$) from query pattern $Q$ is satisfied for
a mapping ${\mathsf{m}}$ to graph $G$, then it must be the case that the
constraints vertex($i_{1}$) and edge($i_{2}$) are also satisfied. This
implication holds for any $i_{1},i_{2}\in Q.{\mathtt{I}}{}$, due to the
definition of the source constraint. Namely, if src($i_{1}$,$i_{2}$) is
satisfied in $G$, then $G.$$\rho$($i_{2}$)=($i_{1}$,$v^{\prime}$) for some
$v^{\prime}\in G.{\mathtt{V}}$. Since $\rho$ is defined as
${\mathtt{E}}\rightarrow({\mathtt{V}}\times{\mathtt{V}})$, it must hold that
$i_{2}\in{\mathtt{E}}$ and $i_{1}\in{\mathtt{V}}$, which is specified by the
constraints edge($i_{2}$) and vertex($i_{1}$).

If the PES contains an estimate for src($i_{1}$,$i_{2}$), for any
$i_{1},i_{2}\in Q.{\mathtt{I}}{}$, then a new PE will be added to the PES
consisting of the set of constraints {src($i_{1}$,$i_{2}$), vertex($i_{1}$),
edge($i_{2}$)} with the selectivity of the PE for src($i_{1}$,$i_{2}$). More
precisely, $\Pr[\mathcal{S}_{\\{\text{{src($i_{1}$,$i_{2}$)},
{vertex($i_{1}$)},
{edge($i_{2}$)}}\\}}]=\Pr[\mathcal{S}_{\text{{src($i_{1}$,$i_{2}$)}}}]$, for
any $i_{1},i_{2}\in Q.{\mathtt{I}}{}$.

Similarly, trg($i_{1}$,$i_{2}$) implies vertex($i_{1}$) and edge($i_{2}$) for
any $i_{1},i_{2}\in Q.{\mathtt{I}}{}$. Also, hasProp($i$,$k$,$\theta$,$v$)
implies hasPropKey($i$,$k$), for any $i\in Q.{\mathtt{I}}{},k\in
Q.{\mathtt{Prop}},\theta\in Q.\Theta,v\in Q.{\mathtt{Val}}$.

###  6.2 Implied Constraints Assumptions

Each query id can have many property constraints associated with it. Neumann
and Moerkotte [17] noticed that usually one property-value constraint is
extremely selective, which (nearly) implies the other property-value
constraints. This means that, when the most selective property-value
constraint on a query id is satisfied, then all other property-value
constraints on that query id are (usually) satisfied too.

Whenever detailed statistics about combinations of those constraints are not
available, instead of assuming independence between those constraints,
assuming an _implication_ from the most selective one to the others might be
more appropriate.

###### Example 6.1

Consider a graph $G$ to which the query from Figure 1 is executed. If $G$ has
less ids that have the property key “name” that contains the word “Tim”
(${\mathsf{c}}_{28}$ from Example 2.2) than ids that have the property key
“gender” with the value “m” (${\mathsf{c}}_{27}$), i.e.
$\Pr[\mathcal{S}_{{\mathsf{c}}_{28}}]<\Pr[\mathcal{S}_{{\mathsf{c}}_{27}}]$,
then constraint ${\mathsf{c}}_{28}$ is assumed, by this approach, to imply
${\mathsf{c}}_{27}$. This gives
$\Pr[\mathcal{S}_{\\{{\mathsf{c}}_{27},{\mathsf{c}}_{28}\\}}]=\Pr[\mathcal{S}_{{\mathsf{c}}_{28}}]$.

This idea can be extended to a more general form, which requires as input a
pattern class and a class of constraints. Above description has ’Id’ as
pattern class and ’Property-value constraints’ as class of constraints, which
will be identified as IP(Id, PropValueConstrs).

The generalized procedure works as follows. Let the defined pattern class be
$x$ and the class of constraints be $y$. For every pattern $x_{i}$ in the
query pattern that belongs to the class $x$, find $PE(x_{i},y)$. The set
$PE(x_{i},y)$ consists of all PEs in the PES where all constraints belong to
the class $y$ and where the query ids in the constraints of the PE is a subset
of the query ids in the constraints of $x_{i}$, i.e.
$(PE.{\mathsf{C}}{}).{\mathtt{I}}{}\subseteq{\mathsf{C}}{}(x_{i}).{\mathtt{I}}{}$.
An implication assumption is applied from the constraints in the PE in
$PE(x_{i},y)$ with the lowest selectivity estimate (PE.$s$) to the union of
all constraints in the PEs in $PE(x_{i},y)$. More precisely,
$PE_{min}(x_{i},y).{\mathsf{C}}{}$ is assumed to imply $\bigcup_{PE\in
PE(x_{i},y)}PE.{\mathsf{C}}{}$, where $PE_{min}(x_{i},y)$ is the PE in
$PE(x_{i},y)$ that has the lowest selectivity.

##  7 Combine Techniques

This section will show different techniques to combine the partial estimates
of complete PESs into a single selectivity estimate. The different approaches
that will be discussed are summarized in Table VI. Notice that these
techniques do not depend on the availability of specific statistics or
indexes, therefore they can be applied in all cases (on PESs that are
_complete_). Statistical assumptions are used to combine PEs. This part of the
estimation procedure can introduce a large estimation error. Therefore, it is
important to make the best out of the available partial estimates, since they
are obtained using available statistics instead of rough assumptions.

Table VI: General Combine Techniques Technique | Assumptions made
---|---
CondIndep |  Conditional Independence between sets of constraints
MaxEnt |  Most uniform probability mass function that satisfies all constraints from the $PES$
Upper Bound | Worst case scenario (from comp. perspective)
Lower Bound | Best case scenario (from comp. perspective)

###  7.1 Conditional Independence Assumptions

The most simple way of combining all partial estimates for the individual
constraints (using techniques from Section 4) is by assuming independence
between the different constraints. This makes it possible to obtain an
estimate by multiplying the individual selectivity estimates:

$\Pr[\mathcal{S}_{{\mathsf{C}}{}(Q)}]=\prod_{{\mathsf{c}}\in{\mathsf{C}}{}(Q)}\Pr[\mathcal{S}_{{\mathsf{c}}}]$
(1)

This formula implies independence between all constraints and does not make
use of the partial estimates obtained for multiple constraint using techniques
from Section 5.

If a partial estimate set $PES_{Q}$ is complete, w.r.t. query $Q$, then the
intersection of all events $\mathcal{S}_{PE.{\mathsf{C}}{}}$ for $PE\in
PES_{Q}$ gives the event $\mathcal{S}_{{\mathsf{C}}{}(Q)}$. Therefore, the
probability of all query constraints can be defined in terms of a complete
partial estimate set $PES_{Q}$:

$\Pr[\mathcal{S}_{{\mathsf{C}}{}(Q)}]=\Pr[\bigcap_{PE\in
PES_{Q}}\mathcal{S}_{PE.{\mathsf{C}}{}}].$

Assuming some order of the partial estimates in $PES_{Q}$, makes it possible
to apply the chain rule of probability:

$\displaystyle\Pr[\bigcap_{PE\in PES_{Q}}\mathcal{S}_{PE.{\mathsf{C}}{}}]$
$\displaystyle=\prod_{i\in[1,..,|PES_{Q}|]}\Pr[\mathcal{S}_{PE_{i}.{\mathsf{C}}{}}\mid\bigcap_{j=1}^{i-1}\mathcal{S}_{PE_{j}.{\mathsf{C}}{}}]$
$\displaystyle=\prod_{i\in[1,..,|PES_{Q}|]}\Pr[\mathcal{S}_{PE_{i}.{\mathsf{C}}{}}\mid\mathcal{S}_{\bigcup_{j=1}^{i-1}PE_{j}.{\mathsf{C}}{}}].$

This formula performs a product over all PEs in the PES. The values of the
product consist of the probability that the set of constraints (of the current
PE) hold, given that all previously considered constraints hold. If the PES is
complete, then all constraints are considered in the end.

We are limited to the PEs that are available in the PES. Therefore, the
probability will be approximated using conditional independence where
necessary. This gives:

$\displaystyle\Pr[\mathcal{S}_{{\mathsf{C}}{}(Q)}]$
$\displaystyle\approx\prod_{i\in[1,..,|PES_{Q}|]}\Pr[\mathcal{S}_{PE_{i}.{\mathsf{C}}{}^{\prime\prime}}\mid\mathcal{S}_{(\bigcup_{j=1}^{i-1}PE_{j}.{\mathsf{C}}{})^{\prime\prime}\cap
PE_{i}.{\mathsf{C}}{}^{\prime\prime}}]$
$\displaystyle=\prod_{i\in[1,..,|PES_{Q}|]}PE_{i}.s/\Pr[\mathcal{S}_{(\bigcup_{j=1}^{i-1}PE_{j}.{\mathsf{C}}{})^{\prime\prime}\cap
PE_{i}.{\mathsf{C}}{}^{\prime\prime}}]$

where $S^{\prime\prime}$ represents the set of all constraints in
${\mathsf{C}}{}(Q)$ implied by $S$, which can be obtain from the set $S$ as
follows:

  * •

add all elements from $S$ to $S^{\prime\prime}$;

  * •

for each src($i_{1}$,$i_{2}$) (or trg($i_{1}$,$i_{2}$)) where $i_{1},i_{2}\in
Q.{\mathtt{I}}{}$, add vertex($i_{1}$) and edge($i_{2}$) to
$S^{\prime\prime}$;

  * •

for each $G.$$\sigma$($i_{1}$,$k$,$\theta$)=$v$ where $i_{1}\in
Q.{\mathtt{I}}{}$, $k\in Q.{\mathtt{Prop}}$, $\theta\in Q.\Theta$, $v\in
Q.{\mathtt{Val}}$, add hasPropKey($i_{1}$,$k$).

The probability of a subset of the constraints in a partial estimate might be
needed due to the intersection in the ’given’ part of the conditional
probability. This selectivity might not be available. Therefore, the general
selectivity estimation process is called recursively on this subproblem. The
lower bound for this selectivity is set to
$\Pr[\mathcal{S}_{PE_{i}.{\mathsf{C}}{}}]$, because any subset of
$PE_{i}.{\mathsf{C}}{}$ imposes no more constraints than
$PE_{i}.{\mathsf{C}}{}$ does.

Notice that the resulting formula leads to (1) when the PES includes only PEs
for individual constraints and no constraints imply other constraints.

Different orderings of the PES can lead to different selectivity estimates.
Some possible options that can be used as sorting strategy are:

  1. 1.

Primary sort on the number of constraints in the partial estimates
(descending). Secondary sort on the selectivity value (ascending).

  2. 2.

Primary sort on the deviation from the independence assumption (descending).
Deviation from independence for partial estimate $PE$ is defined as:
$max(PE.s/\prod_{{\mathsf{c}}\in
PE.{\mathsf{C}}{}}\Pr[\mathcal{S}_{{\mathsf{c}}}],$ $\prod_{{\mathsf{c}}\in
PE.{\mathsf{C}}{}}\Pr[\mathcal{S}_{{\mathsf{c}}}]/PE.s)$. This gives the value
$1$ if the constraints in $PE$ are mutually independent and a higher value the
more dependent they are. Secondary sort on the selectivity value (ascending).

  3. 3.

Primary sort on the overlap between its constraints and the previously
considered constraints (descending). Secondary sort on the deviation from
independence (descending).

Algorithm 2 shows the general procedure of combining all partial estimates
using the chain rule of probability and conditional independence assumptions.
The algorithm uses sort(), impl() (short for implied) and selEst() as
subroutines. The first two are explained in the text above and the last one is
the general selectivity estimation process, which is shown in Algorithm 1. The
parameters involving the (sets of) techniques of choice and the available
graph instance statistics are shown as dots to keep the description clean.

Data: CPES: a complete partial estimate set

Result: Selectivity estimate for the conjunction of all constraints in the PEs
of CPES

sort(CPES);

constraintsDone = {};

currentEst = 1.0;

for  _each partial estimate $PE$ in CPES_ do

cDoneAndImplied = impl(constraintsDone);

cImpl = impl($PE.{\mathsf{C}}{}$);

intersection = cDoneAndImplied $\cap$ cImpl;

if  _intersection is empty_ then

currentEst *= $PE.s$;

else if  _intersection != cImpl_ then

currentEst *= $\frac{PE.s}{max(PE.s,\text{
}selEst(\text{intersection},\dots))}$;

constraintsDone = constraintsDone $\cup PE.{\mathsf{C}}{}$;

end for

return currentEst;

Algorithm 2 combineIndep(CPES, …)

###  7.2 The Maximum Entropy approach

Each constraint ${\mathsf{c}}_{i}\in{\mathsf{C}}{}(Q)$ can be modeled as a
Bernoulli variable, $X_{i}$, where
$\Pr[X_{i}]=\Pr[\mathcal{S}_{{\mathsf{c}}_{i}}]$. Then,
$\Pr[\mathcal{S}_{{\mathsf{C}}{}(Q)}]$ corresponds to the joint probability
$\Pr[X_{1}=True,X_{2}=True,\dots,X_{n}=True]$, where $n=|{\mathsf{C}}{}(Q)|$.

Instead of estimating only the joint probability
$\Pr[X_{1}=True,X_{2}=True,\dots,X_{n}=True]$, Markl et al. [24] approximate
the whole joint probability mass function $\Pr[X_{1}=x_{1},\dots,X_{n}=x_{n}]$
where $x_{i}$ is $True$ or $False$ for $1\leq i\leq n$. The idea is to assign
the probabilities such that:

  * •

each probability is $\geq 0$ and $\leq 1$;

  * •

the sum of all probabilities adds up to $1$;

  * •

for each partial estimate $PE$ it holds that: the sum of all items, where
$X_{i}=True$ for all $i$ such that ${\mathsf{c}}_{i}\in PE.{\mathsf{C}}{}$, is
equal to $PE.s$.

Since many probability mass functions might satisfy above requirements, the
one which maximizes the Entropy function will be chosen. This is the most
uniform probability mass function (i.e. the one with the largest uncertainty)
that is consistent with the information from the complete partial estimate set
(CPES).

####  7.2.1 Constraint Optimization Problem

Let $S\subseteq{\mathsf{C}}{}(Q)$, then
$\Pr[S\wedge\neg({\mathsf{C}}{}(Q)-S)]$ is the probability that all variables
$X_{i}$ are $True$ for all $i$ such that ${\mathsf{c}}_{i}\in S$ and all
variables $X_{j}$ are false for all $j$ such that
${\mathsf{c}}_{j}\in({\mathsf{C}}{}(Q)-S)$.

The task is now to find the joint probability
$\Pr[S\wedge\neg({\mathsf{C}}{}(Q)-S)]$, for each $S$ where
$S\subseteq{\mathsf{C}}{}(Q)$, such that

$\sum_{\\{S\mid
S\subseteq{\mathsf{C}}{}(Q)\\}}\Pr[S\wedge\neg({\mathsf{C}}{}(Q)-S)]=1$

and for each partial estimate $PE$

$\sum_{\\{S\mid PE.{\mathsf{C}}{}\subseteq
S\subseteq{\mathsf{C}}{}(Q)\\}}\Pr[S\wedge\neg({\mathsf{C}}{}(Q)-S)]=PE.s$

that maximizes the entropy function:

$-\sum_{\\{S\mid
S\subseteq{\mathsf{C}}{}(Q)\\}}\Pr[S\wedge\neg({\mathsf{C}}{}(Q)-S)]\text{ log
}\Pr[S\wedge\neg({\mathsf{C}}{}(Q)-S)]$

The resulting joint probability mass function makes it possible to estimate
the selectivity of the query $Q$ and all of its subqueries. The selectivity of
a subquery that contains only the constraints
$V^{\prime}\subseteq{\mathsf{C}}{}(Q)$ can be estimated by

$\sum_{\\{S\mid V^{\prime}\subseteq
S\subseteq{\mathsf{C}}{}(Q)\\}}\Pr[S\wedge\neg({\mathsf{C}}{}(Q)-S)]$

which sums all probabilities in the joint probability mass function where all
variables $X_{i}$ are $True$ for all $i$ such that ${\mathsf{c}}_{i}\in
V^{\prime}$. The remaining variable can be either $True$ or $False$.

The selectivity of query $Q$ is the probability in the estimated joint
probability mass function where all variable are true.

Markl et al. [24] solve this constraint optimization problem using an
iterative scaling algorithm based on Lagrange multipliers.

###  7.3 Obtaining Cardinality Bounds

The above methods all construct a single value as an estimate for the
cardinality of a query. The real cardinality can be very different from this
estimate. Therefore, this section will introduce a technique to obtain a lower
and an upper bound such that the real cardinality is likely to fall within
that range, depending on the error guarantees of the PEs in the PES.

####  7.3.1 Finding the Upper Bound

The selectivity of all constraints in ${\mathsf{C}}{}(Q)$ is less or equal
than the selectivity of a subset of ${\mathsf{C}}{}(Q)$. The PES of query $Q$
($PES_{Q}$) stores estimates for subsets of ${\mathsf{C}}{}(Q)$. Therefore, an
upper bound can be obtained directly from $PES_{Q}$:

$\displaystyle Pr[\mathcal{S}_{{\mathsf{C}}{}(Q)}]$ $\displaystyle\leq
min_{PE\in PES_{Q}}PE.s$ (2)

Now consider a special case: Let $PE_{k}$ and $PE_{l}$ be elements from
$PES_{Q}$. If $(PE_{k}.{\mathsf{C}}{}).{\mathtt{I}}{}$ and
$(PE_{l}.{\mathsf{C}}{}).{\mathtt{I}}{}$ are disjoint, then the events
$\mathcal{S}_{PE_{i}.{\mathsf{C}}{}}$ and
$\mathcal{S}_{PE_{j}.{\mathsf{C}}{}}$ are independent. This makes it possible
to obtain the selectivity of the intersection of both events as follows:
$\Pr[\mathcal{S}_{PE_{i}.{\mathsf{C}}{}}\cap\mathcal{S}_{PE_{j}.{\mathsf{C}}{}{}}]=\Pr[\mathcal{S}_{PE_{i}.{\mathsf{C}}{}}]\cdot\Pr[\mathcal{S}_{PE_{j}.{\mathsf{C}}{}}]=PE_{i}.s\cdot
PE_{j}.s$.

This can be generalized to any subset $S$ of $PES_{Q}$, such that the query
ids in the constraints of all pairs of PEs from $S$ are disjoint. Let
$indep(PES_{Q})$ represent all those sets. This gives

$\displaystyle Pr[\mathcal{S}_{{\mathsf{C}}{}(Q)}]$ $\displaystyle\leq
min_{I\in indep(PES_{Q})}\prod_{PE\in I}PE.s$ (3)

Note that (3) is an improvement upon (2).999Each set that consists of a single
$PE$ from $PES_{Q}$ is by definition an element of $indep(PES_{Q})$. Also
$PE.s\leq 1$. Therefore, (3) cannot lead to a larger upper bound than (2)

####  7.3.2 Finding the Lower Bound

For most PESs, there is not enough evidence that a query return at least one
result. This means that a lower bound of zero for
$\Pr[\mathcal{S}_{{\mathsf{C}}{}(Q)}]$ is common. Only when the selectivity
values of the PEs are large, it might be possible to obtain a lower bound
larger than $0$.

###### Example 7.1

For example, $PES_{Q}=\\{PE_{1}.s=0.8,PE_{2}.s=0.7,PE_{3}.s=0.9\\}$ gives a
lower bound $0.4$ for the selectivity
$\Pr[\mathcal{S}_{PK{}_{1}.{\mathsf{C}}{}\cup PK{}_{2}.{\mathsf{C}}{}\cup
PK{}_{3}.{\mathsf{C}}{}}]$.

By making the sets of mappings that satisfy the different PEs as disjoint as
possible, it is possible to obtain the smallest possible set of mappings that
must satisfy all partial estimates. This can be computed using the formula
$lbSel(PES_{Q})=1-\sum_{PE\in PES_{Q}}(1-PE.s)$, where $(1-PE.s)$ represent
the fraction of mappings that do not satisfy the constraints in
$PE.{\mathsf{C}}{}$. The final lower bound is $max(0,lbSel(PES_{Q}))$. A lower
bound larger than $0$ will only be obtained when $\sum_{PE\in
PES_{Q}}PE.s>|PES_{Q}|-1$, where $|PES_{Q}|$ is the number of PEs in the PES.

Notice that, in order to obtain the best lower bound, all PEs $PE_{i}$ need to
be removed for which there exists another PE $PE_{j}$ where
$PE_{i}.{\mathsf{C}}{}\subseteq PE_{j}.{\mathsf{C}}{}$.

##  8 Experimental Setup

The Join Order Benchmark (JOB) was introduced by Leis et al. [1, 2]. It
consists of a fixed database instance and a fixed query workload. The database
instance is a real instance of the Internet Movie Data Base (IMDB), which is
full of correlations and non-uniform distributions. The query workload
consists of 113 analytical SQL queries that were manually constructed to
represent questions that could have been asked by a movie enthusiast. The
queries contain 33 structures, each with several variants that differ in
selections (i.e. data constraints) only.

We have translated the relational database instance into a property graph
database instance and each SQL query in the workload into an openCypher query.
See Figure 4 for the graph schema. Table IX shows the abbreviations that will
be used in the experiment results and descriptions.101010A sorting strategy
will be abbreviated by a combination like SaNd, where Sa defines the primary
sorting criteria and Nd the secondary sorting criteria.

###  8.1 Translation from relational to graph instance

For the IMDB schema, we refer to Figure 2 in [2]. We partitioned the relation
into three sets $I,E$ and $V$, i.e. Identifying relations, Edge relations and
Vertex relations. A relation belongs to $I$ if it is only used to identify a
string value, i.e. it only has two attributes, the primary key and the string
value. A relation belongs to $E$ if it contains exactly two foreign key
attributes to relations not in $I$ and it does not have any references from
other relations to its primary key: movie_companies to title and company,
movie_link twice to title and movie_keyword to title and keyword.

The remaining relations belong to $V$.

I = {link_type, role_type, complete_cast_type, company_type, kind_type,
info_type}

E = {movie_companies, movie_link, movie_keyword}

V = {title, complete_cast, keyword, aka_title, company_name, movie_info,
movie_info_idx, cast_info, char_name, name, aka_name, person_info}

We created a vertex for each tuple in the relations in $V$. We assigned the
name of the relation as a label to the vertex. If a relation in $V$ contains a
foreign key (e.g. movie_id in aka_title), then an edge will be created between
the vertices associated with the tuple in the relation and the tuple to which
it refers.

For each tuple in the relations in $E$, we created an edge between the
vertices associated with the tuples to which both foreign keys refer. If the
relation contains only one attribute that is not a foreign key or primary key,
then the value of that attribute is used as edge label (e.g. company_type for
movie_companies). Otherwise, a label based on the name of the relation is
assigned, e.g. has_keyword for movie_keyword.

The remaining attributes are added as key-value properties to the vertices and
edges, where the key is the attribute name.

:title:company:keyword:aka_title:movieInfo:movieInfoIdx:complete_cast:cast_info:character:person:personInfo:aka_name[2]:has_keyword:aka_title[71][5]:complete_cast_movie:cast_info_movie:cast_info_character:cast_info_person[22]:aka_name:episode_of:movie_link
Figure 4: Graph schema for the data from the Join Order Benchmark. The edges
with label $[x]$, e.g. from :person to :personInfo, can have one of $x$
different labels, e.g. birth date, death date, height, mini biography, etc.

###  8.2 Basic Query and Data Statistics

Several statistics from Section 5 are tailored to specific patterns. If those
patterns do not occur frequently in the data and the queries, then those
statistics lose their benefit. Table VII shows the number of occurrences of
several patterns in the JOB query workload. There are much more source star
patterns than chain patterns and much more chain patterns than target star
pattern. Therefore, statistics for source star patterns have the potential to
improve the estimation accuracy for many queries. Table VIII shows some basic
statistics of the graph version of the JOB dataset.

Table VII: Types of patterns in the OpenCypher version of the JOB queries and the number of times they occur. Pattern | Occ.
---|---
Query edges | 464
Chains length $2$ | 201
Chains length $>2$ | 0
Source stars size $2$ | 356
Source stars size $3$ | 130
Source stars size $4$ | 20
Source stars size $>4$ | 0
Target stars size $2$ | 15
Target stars size $>2$ | 0

Table VIII: Basic statistics of the graph version of the JOB dataset. JOB data
stats
---
$|G.{\mathtt{E}}|$ | $119343754$
$|G.{\mathtt{V}}|$ | $52639796$
$|G.{\mathtt{I}}{}|$ | $171983550$
$|G.\ell_{v}|$ | $12$
$|G.\ell_{e}|$ | $106$

Table IX: Abbreviations used in the experiments. PETs for multiple constraints
---
EP | Labeled topological synopsis for edge patterns
SysR | System R’s join size estimation
cX |  Labeled topological synopses for chain patterns up to size $X$
sX |  Labeled topological synopses for source star patterns up to size $X$
tX |  Labeled topological synopses for target star patterns up to size $X$
CS | Characteristic Sets
S(pa,pr) |  Sampling with pattern pa and probability pr
EPESTs
IP(p,c) |  Implied constraints assumptions with pattern p and constraint type c
id | Pattern: Query identifier
ep | Pattern: Edge pattern
p | Constraint type: Property constraints
pv | Constraint type: Property-value constraints
a | Constraint type: All query pattern constraints
Combination Techniques (CTs)
condIndep | Conditional independence assumptions
maxEnt | Maximum Entropy
bounds | Upper and lower bounds
Sorting Strategies
a | ascending
d | descending
S | Selectivity value
N | Number of conjuncts
Di | Deviation from Independence assumption
Mo | Maximum Overlap

###  8.3 Notes on Disjunctions in JOB Queries

Some queries in the JOB contain disjunctions, e.g. [hasLabel(e1,’production
companies’) OR hasLabel(e1,’distributors’)]. The way we handled them is by
generating a set of queries without disjunctions and finally unifying their
results, by assuming that the sets of results are disjoint.

##  9 Example of the Estimation Process

Figure 5 shows an example of the estimation process for the query from Figure
1 on the property graph version of the JOB dataset.

The PET for the individual constraints that is used is synopsis lookup, where
the synopsis contains the precomputed selectivities of the required individual
constraints. The PETs for multiple constraints that are used are: SysR and EP.
The EPEST IP[id,p] is used, which assumes implied constraints between property
constraint referring to the same query id.

Using those PETs, EPEST and the combination technique condIndep(NdSa), the
cardinality of the query from Figure 1 is estimated to be almost $4$ in the
JOB dataset. The real cardinality of this query in the JOB dataset is $410$.

Each PE contains a selectivity estimate $\hat{s}$. For analysis, we also added
the exact selectivity values $s$ for each pattern for which a PE is available.
All estimates in green do not introduce any error. Estimates in yellow
introduce a very small errors (q-errors less than $2$). Estimates in orange
introduce some errors (q-errors between $2$ and $10$). Finally, estimates in
red introduce large errors (q-errors larger than $10$).

The errors introduced during the estimation process will be investigated in
the following subsections.

System R’s assumptions. The inclusion assumption and uniform distribution
assumption caused a very small overestimation error in the PE sysR1. The PE
sysR2 does not introduce any error, since each cast_info vertex (i.e. vertex
with the label cast_info) has exactly one outgoing edge with label
cast_info_movie to a title vertex and exactly one outgoing edge with label
cast_info_person to a person vertex. Therefore, inclusion and uniform
distribution assumptions hold.

Implied constraints assumptions. The implied constraints assumption (an
element whose name contains ’Tim’ determines that the element has gender ’m’)
in ip1 caused a small overestimation error.

Independence between labeled topological patterns.
$\Pr[\mathcal{S}_{{\mathsf{C}}{}(sysR2)}\mid\mathcal{S}_{{\mathsf{C}}{}(sysR1)}]$
is approximated by
$\Pr[\mathcal{S}_{{\mathsf{C}}{}(sysR2)}\mid\mathcal{S}_{{\mathsf{C}}{}(EP3)}]$.
This assumes conditional independence between the pattern $P_{bv}:$
:movieInfo:title:movieIndoIdx:budget:votes and $P_{p}:$
:cast_info:person:cast_info_person given $P_{m}:$
:cast_info:title:cast_info_movie. This did not introduce an estimation error.
The reason for this is that every cast_info vertex in the dataset has exactly
one outgoing edge with label cast_info_person to a person vertex and exactly
one outgoing edge with label cast_info_movie to a title vertex. Therefore
$P_{p}$ only depends on $P_{m}$ and not on $P_{bv}$.

Independence between property constraints and labeled topological pattern.
$\Pr[\mathcal{S}_{{\mathsf{C}}{}(ip1)}\mid\mathcal{S}_{{\mathsf{C}}{}(sysR1)\cup{\mathsf{C}}{}(sysR2)}]$
(which has real $s=3.55\cdot 10^{-3}$) is approximated by
$\Pr[\mathcal{S}_{{\mathsf{C}}{}(ip1)}]$ (which has real $s=5.27\cdot
10^{-5}$). The leads to a large q-error of $67.4$. Notice that
$\Pr[\mathcal{S}_{{\mathsf{C}}{}(ip1)}]$ itself is approximated using implied
constraints assumptions. This approximation causes a small overestimation,
which cancels out a part of the underestimation for using
$\Pr[\mathcal{S}_{{\mathsf{C}}{}(ip1)}]$ as an approximation for
$\Pr[\mathcal{S}_{{\mathsf{C}}{}(ip1)}\mid\mathcal{S}_{{\mathsf{C}}{}(sysR1)\cup{\mathsf{C}}{}(sysR2)}]$.
This eventually leads to a q-error of $23.7$.

Approximating
$\Pr[\mathcal{S}_{{\mathsf{C}}{}(ip1)}\mid\mathcal{S}_{{\mathsf{C}}{}(sysR1)\cup{\mathsf{C}}{}(sysR2)}]$
by
$\Pr[\mathcal{S}_{{\mathsf{C}}{}(ip1)}\mid\mathcal{S}_{\\{\text{{vertex(id8)}}\\}}]$
(which has real $s=1.72\cdot 10^{-4}$) would improve estimation accuracy
(q-error of $20.6$). However, approximating it by
$\Pr[\mathcal{S}_{{\mathsf{C}}{}(ip1)}\mid\mathcal{S}_{\\{\text{{vertex(id8)},
{hasLabel(id8,person)}}\\}}]$ (which has real $s=2.17\cdot 10^{-3}$) would
lead to a very accurate estimate (q-error of $1.6$). This shows a strong
positive correlation between property and label constraints.

Independence between property constraints with labeled topological pattern and
other property constraints.
$\Pr[\mathcal{S}_{{\mathsf{C}}{}(ip2)}\mid\mathcal{S}_{{\mathsf{C}}{}(sysR1)\cup{\mathsf{C}}{}(sysR2)\cup{\mathsf{C}}{}(ip1)}]$
(which has real $s=6.30\cdot 10^{-2}$) is approximated by
$\Pr[\mathcal{S}_{{\mathsf{C}}{}(ip2)}]$ (which has real $s=1.38\cdot
10^{-2}$). The leads to a q-error of $4.6$.

Approximating it using
$\Pr[\mathcal{S}_{{\mathsf{C}}{}(ip2)}\mid\mathcal{S}_{\\{\text{{vertex(id6)}}\\}}]$
(which has real $s=4.52\cdot 10^{-2}$) improves estimation accuracy (q-error
of $1.4$). Approximating it using
$\Pr[\mathcal{S}_{{\mathsf{C}}{}(ip2)}\mid\mathcal{S}_{\\{\text{{vertex(id6)},
{hasLabel(id6,cast\\_info)}}\\}}]$ (which has real $s=6.56\cdot 10^{-2}$)
would lead to an almost perfect estimate (q-error of $1.0$). This, again,
shows a strong positive correlation between property and label constraints.

Summary. The illustrated estimation process in Figure 5 introduces the largest
errors by assuming independence between each property constraint and the
labeled topological constraints. Therefore, the selectivity estimate can be
improved by adding partial estimates that contain combinations of property
constraints, edge or vertex constraints and label constraints.

Individual constraints: selectivity lookup
Vertexid..$\hat{s}=s=0.306$ Edgeid..$\hat{s}=s=0.694$
Sourceid..id..$\hat{s}=s=4.06\cdot 10^{-9}$ Targetid..id..$\hat{s}=s=4.06\cdot
10^{-9}$ Label:title$\hat{s}=s=0.015$: ..$\hat{s}=s=...$

Propertyid6 has key ’note’$\hat{s}=s=0.0994$id6.note IN
[’(producer)’,’(executive producer)’]$\hat{s}=s=0.0138$id8 has key
’gender’$\hat{s}=s=0.0157$id8.gender = ’m’$\hat{s}=s=0.0101$id8 has key
’name’$\hat{s}=s=0.0491$id8.name CONTAINS ’Tim’$\hat{s}=s=1.50\cdot 10^{-4}$

Multiple constraints: System R Join Size Estimation, LabTopSyn(EP)
sysR1:movieInfo:title:movieInfoIdx:cast_infoSystem R Join Size
Estimation$\hat{s}=4.26\cdot 10^{-52}$$s=4.11\cdot
10^{-52}$:cast_info_movie:budget:votes sysR2:person:title:cast_infoSystem R
Join Size Estimation$\hat{s}=2.41\cdot 10^{-34}$$s=2.41\cdot
10^{-34}$:cast_info_person:cast_info_movie

EP1:title:movieInfo:budgetLabTopSyn(EP)$\hat{s}=s=2.40\cdot 10^{-20}$

EP2:title:movieInfoIdx:votesLabTopSyn(EP)$\hat{s}=s=9.04\cdot 10^{-20}$

EP3:cast_info:title:cast_info_movieLabTopSyn(EP)$\hat{s}=s=7.13\cdot 10^{-18}$

EP4:cast_info:person:cast_info_personLabTopSyn(EP)$\hat{s}=s=7.13\cdot
10^{-18}$

Extend PES: IP(id, propConstrs)

ip1id8 has key ’gender’id8.gender=’m’id8 has key ’name’id8.name CONTAINS
’Tim’IP(id, propConstrs)$\hat{s}=1.50\cdot 10^{-4}$$s=5.27\cdot 10^{-5}$

ip2id6 has key ’note’id6.note IN [’(producer)’,’(executive producer)’]IP(id,
propConstrs)$\hat{s}=1.38\cdot 10^{-2}$$s=1.38\cdot 10^{-2}$

All constraints: Conditional independence using sort strategy nbConjDescSelAsc
Only the relevant part of the computation is shown

$\displaystyle\Pr[\mathcal{S}_{{\mathsf{C}}{}(Q)}]$
$\displaystyle=\Pr[\mathcal{S}_{{\mathsf{C}}{}(sysR1)}]\cdot\Pr[\mathcal{S}_{{\mathsf{C}}{}(sysR2)}\mid\mathcal{S}_{{\mathsf{C}}{}(sysR1)}]$
$\displaystyle\hskip
28.45274pt\cdot\Pr[\mathcal{S}_{{\mathsf{C}}{}(ip1)}\mid\mathcal{S}_{{\mathsf{C}}{}(sysR1)\cup{\mathsf{C}}{}(sysR2)}]$
$\displaystyle\hskip
28.45274pt\cdot\Pr[\mathcal{S}_{{\mathsf{C}}{}(ip2)}\mid\mathcal{S}_{{\mathsf{C}}{}(sysR1)\cup{\mathsf{C}}{}(sysR2)\cup{\mathsf{C}}{}(ip1)}]$
$\displaystyle\approx\Pr[\mathcal{S}_{{\mathsf{C}}{}(sysR1)}]\cdot\hbox{\pagecolor{green!20}$\Pr[\mathcal{S}_{{\mathsf{C}}{}(sysR2)}\mid\mathcal{S}_{{\mathsf{C}}{}(EP3)}]$}$
$\displaystyle\hskip
28.45274pt\cdot\hbox{\pagecolor{red!20}$\Pr[\mathcal{S}_{{\mathsf{C}}{}(ip1)}]$}\cdot\hbox{\pagecolor{orange!20}$\Pr[\mathcal{S}_{{\mathsf{C}}{}(ip2)}]$}$
$\displaystyle=sysR1.\hat{s}\cdot\frac{sysR2.\hat{s}}{EP3.\hat{s}}\cdot
ip1.\hat{s}\cdot ip2.\hat{s}$ $\displaystyle=2.98\cdot 10^{-74}$

$\displaystyle\rightarrow real$ $\displaystyle=3.55\cdot 10^{-3}$
$\displaystyle\rightarrow real$ $\displaystyle=6.30\cdot 10^{-2}$
$\displaystyle cardEst_{G}(Q)$
$\displaystyle=\Pr[\mathcal{S}_{{\mathsf{C}}{}(Q)}]\cdot|G.{\mathtt{I}}{}|^{|Q.{\mathtt{I}}{}|}$
$\displaystyle=(2.98\cdot 10^{-74})\cdot 171983550^{9}$
$\displaystyle=(2.98\cdot 10^{-74})\cdot(1.32\cdot 10^{74})$
$\displaystyle=3.93$

Figure 5: Example of an estimation process of the query from Figure 1.

##  10 Experiments

Section 9 identified different source of errors that can be introduced within
the estimation process. In the following sections, these error sources are
investigated further. All experiments are performed on the graph version of
the JOB dataset and using the OpenCypher version of the JOB query workload.

For all experiments, a synopsis lookup for individual constraints is used.
This allows us to focus on the estimation errors introduced by PETs for
multiple constraints, EPESTs and CTs. In a real world scenario, individual
constraints might be estimated using histograms or sampling.

Several experimental results are visualized using boxplots. The boxplot is
drawn, such that 50% of the values fall within the box, $90\%$ within the
whiskers. The remaining $10\%$ is shown as dots (top $5\%$ and bottom $5\%$).
The median is drawn as an orange line within the box.

Section 10.1 shows experiments regarding the errors introduced by some
(extend) partial estimation techniques. Experiments related to the errors that
are introduced by the combination techniques are shown in Section 10.2.

Key observations from the experiments:

  * •

for labeled star patterns, a combination of a labeled edge pattern synopsis
(PET EP) and conditional independence assumptions (CT condIndep) requires less
statistics than System R’s join size estimation (PET SysR) and its largest
Q-error is $7\times$ lower. The median Q-errors are similar. (Section 10.1.1);

  * •

for labeled source star patterns with property-key constraints, the PET CS has
better estimation accuracy than structural synopses combined with condIndep.
Its median Q-error is $60\times$ lower. (Section 10.1.2);

  * •

using implication assumptions instead of independence assumptions leads to a
median Q-error that is $20\times$ lower for estimating multiple property-value
constraints referring to the same query id. (Section 10.1.3)
Section 12 also supports this claim for general query patterns, independence
assumptions can lead to Q-errors that are $10^{24}\times$ larger than using
implication assumptions on the JOB subqueries with less than 7 edges;

  * •

sorting strategies (for CT condIndep) with primary sort Sd or Na should be
avoided (Section 10.2.1);

  * •

condIndep outperforms maxEnt and bounds (Section 10.2.1);

  * •

in the absence of property constraints, labeled structural synopses with CT
condIndep(MoDi) can obtain accurate estimates efficiently Section 10.2.1);

  * •

in the presence of property constraints, labeled structural synopses for
patterns that are larger than edge patterns do not improve estimation accuracy
when correlations between property and labeled topological constraints are not
captured (Section 10.2.2);

  * •

sampling improves estimation accuracy (median Q-error is $16\times$ lower),
but increases estimation time (median estimation time is $135\times$ higher),
compared to the best alternative using implication assumptions, on the JOB
subqueries with less than 7 edges (Section XII).

###  10.1 Estimation Error Experiments for PETs and EPESTs

Partial estimation techniques like c2 can obtain partial estimates that are
exact. However, PETs like CS or SysR can obtain partial estimates that are not
exact. Those techniques rely on a combination of specialized statistics and
assumptions. The assumptions can introduce errors in the partial estimates.
This section investigates on the estimation errors introduced by PETs and
EPESTs.

####  10.1.1 System R Join Size Estimation

The PET SysR (Section 5.2.2) can obtain estimates for labeled star patterns,
using labeled edge pattern statistics, inclusion assumptions and uniform
distribution assumptions. This section focuses on the accuracy of estimating
labeled star patterns, using SysR and alternative approaches.

Theoretical Analysis The full estimation error introduced by SysR on star
patterns is due to the inclusion assumptions and uniform distribution
assumptions. The inclusion assumption can _only_ lead to an overestimate. The
uniform distribution assumption can lead to both over- and underestimations.

The PET SysR underestimates in the case that 1) the degree distributions are
skewed, 2) vertices with a relative high number of edges in one edge pattern
also have a relatively high number of edges in other edge patterns and 3) the
inclusion assumption is approximately satisfied.

The PET SysR overestimates in the case that in inclusion assumption does not
hold (for example when $|T^{\prime}_{G}(ep1)\cap S^{\prime}_{G}(ep2)|$ is much
smaller than $min(|T^{\prime}_{G}(ep1),S^{\prime}_{G}(ep2)|)$ in a pattern
$ep1/ep2$), or when 1) the degree distributions are skewed and 2) vertices
with a relative high number of edges in one edge pattern have a relatively low
number of edges in other edge patterns.

Analysis on Star Patterns in JOB Queries. For each labeled star pattern in the
JOB queries with size $\geq 2$, the exact selectivity and estimates using SysR
and alternative approaches are obtained. Figure 6 shows a summary of these
results by plotting the values estimate/real in boxplots partitioned by the
size of the star patterns.

Figure 6: Estimation error for all star patterns in the JOB queries,
partitioned on the size of the star patterns, using different PETs. The CT
condIndep(MoDi) is used when the PETs are not able to produce an estimate for
the whole star pattern.

In order to compare the errors obtained using the PET SysR, alternative
approaches (labeled topological synopses) are also illustrated in Figure 6.
The PES will be combined using condIndep with sort strategy MoDi. For the
alternative approaches, all PEs are exact. Therefore, the full estimation
error is due to (conditional) independence assumptions that are made during
combining the PES using CT condIndep. For the PET SysR, combing the PES is not
necessary, since SysR can obtain an estimate for every star pattern.
Therefore, the full estimation error is due to the assumptions made by SysR.

From Figure 6, it can be seen that

  * •

PEs obtained using SysR will introduce estimation errors up to $3$ orders of
magnitude for the JOB queries on the JOB dataset;

  * •

larger star patterns lead to larger underestimations of the selectivity;

  * •

when statistics about labeled topological pattern (larger than edge patterns)
are available, then it is better to use PETs that use those statistics (e.g.
c2,s2,s3) and combine using conditional independence assumptions, instead of
using SysR;

  * •

the approach EP is performing comparable to SysR (and in many cases, slightly
better), while it requires less statistics than SysR.

The PET EP with CT condIndep(MoDi) gives a median and max Q-error of $2.0$ and
$205$, where SysR gives $2.1$ and $1515$, on the star patterns in the JOB
query workload. The max Q-error is $7\times$ larger for SysR, while it
requires more statistics than EP with condIndep. As a result, PET SysR is not
recommended.

####  10.1.2 Characteristic Sets

The PET CS (Section 5.3.1) can obtain estimates for labeled source star
patterns with ’has property key’ constraints on their center vertices. A
source star pattern with exactly one label on each edge together with the ’has
property key’ constraints on its center vertex will be called a csPattern.

For each csPattern in the JOB queries, which contains at least two edge
patterns, the exact selectivity and an estimate using CS are obtained. Figure
7 shows a summary of these results together with alternative techniques,
similar as was done in Section 10.1.1.

Figure 7: Estimation error for all csPatterns in the JOB queries, with at
least two edge pattern, partitioned on the size of the csPatterns, using
different PETs. The CT condIndep(MoDi) is used when the PETs are not able to
produce an estimate for the whole csPattern.

Figure 7 shows that CS performs very well compared to {EP,s2} and {EP,s3}. The
approaches {EP,s2} and {EP,s3} have to assume independence between the labeled
topological pattern and the ’has property key’ constraints, also between all
of the ’has property key’ constraints. Those independence assumptions lead to
many large underestimations. CS gives median and max Q-error of $1.1$ and
$184$, where {EP, s3} gives $68.0$ and $4762$. Therefore, the median Q-error
of CS is $60\times$ lower than for {EP, s3} on all csPatterns in the JOB query
workload.

Instead of assuming independence between all ’has property key’ constraints,
it is possible to assume implications using IP(id,p). Figure 7 shows that the
estimates using implied ’has property key’ constraints perform better than
assuming independence between the ’has property key’ constraints. However, the
selectivity of most csPatterns is still underestimated by more than an order
of magnitude. Another source of underestimation is the independence assumption
between the ’has property key’ constraints and the labeled topological
constraints. This source of underestimation can be removed by assuming
implications using IP(id,a). Figure 7 shows that most csPatterns are estimated
very accurately with techniques EP and IP(id,a). The addition of s2 and s3
helps to further improve the selectivity estimation accuracy.

The advantage for the CS approach compared to the approaches based on
implication assumptions is that CS is based on real statistics. Therefore, it
is expected to perform well even in cases where implication and independence
assumptions do not hold. However, the price that CS pays is an increase in
memory cost, preparation time and estimation time.

####  10.1.3 Implied Constraints Assumptions

The EPEST IP(id,pv) can obtain an estimate for all property-value constraints
that refer to the same query id. We obtained for each query id in each JOB
query all property-value constraints.

Figure 8: Estimation error for the set of all property-value constraints that
refer to the same query id, for each query id in the JOB queries.

With only the exact selectivities of the individual constraints (no additional
PETs and EPESTs), the full estimation error is caused by the CT. Figure 8
shows this using CT condIndep(MoDi). From the boxplot above (_,0), it can be
seen that assuming independence mostly leads to underestimations. However, it
can also lead a large overestimation.

With the EPEST IP(id,pv), an estimate for all constraints can be obtained.
Therefore, the full estimation error is caused by the implication assumptions
within IP(id,pv). Clearly, IP(id,pv) cannot lead to an underestimation of the
selectivity (when the PES contains only exact selectivity values, which is the
case for these experiments). However, it can lead to a large overestimation of
the selectivity. Here, IP(id,pv) gives a median and max Q-error of $1.6$ and
$1.1\cdot 10^{5}$, where independence gives $32.7$ and $8142$. Therefore, the
median Q-error of implication assumptions is $20\times$ lower than for
independence assumptions, but the max Q-error is $13\times$ larger.

For both approaches, the set $s1=${hasProp(id0,note,CONTAINS,(’producer’)),
hasProp(id0,role,=,’actor’)} caused the largest overestimation. A total of
$1436536$ graph ids satisfy the first constraint, $12670688$ graph ids satisfy
the second constraint, but only $13$ graph ids satisfy both constraints.

###  10.2 Estimation Error Experiments for CTs

PETs can obtain selectivity estimates for a specific subclass of query
patterns (e.g. only for star patterns, or only for all property constraints
referring to the same query id). In order to obtain a selectivity estimate for
every possible query pattern, a CT will combine all PEs into a single
selectivity estimate for the query pattern.

Section 10.2.1 focuses first on the estimation error introduced by combining
PEs consisting of only labeled topological constraints. After that, Section
10.2.2 focuses on the estimation error introduced by combing all PEs.

####  10.2.1 Combining Labeled Topological Constraints

For this section, we use all the subqueries, that have at most six edge
patterns, from all JOB queries. For each such subquery, the property
constraints have been removed. This allows us to focus on the error that is
introduced during combination of PEs consisting of labeled topological
constraints.

In order to focus on the estimation error caused by the combination
techniques, this section uses only PETs that add PEs that are exact (e.g.
labeled topological synopses).

Conditional Independence Assumptions. The CT condIndep requires a specific
sorting strategy. Table X shows the median (and max) q-error of the
selectivity estimates for different combinations of sorting strategies and
PETs. Those results clearly show that a primary sort on the selectivity value
of the PEs in descending order or a primary sort on the number of conjunct of
the PEs in ascending order should be avoided. Those sorting strategies have
the effect that essentially all partial estimates involving more than one
constraint are ignored. All other sort strategies perform much better and show
that adding more PETs, that use more advanced statistics, lead to better
estimation accuracy.

The median estimation time is between $1$ and $15$ milliseconds for the
different sort strategies and different PETs, and the maximum estimation time
lies between $10$ and $100$ milliseconds (due to page limit restrictions, we
omit the full table). The estimation time increases slightly when more PETs
are used. The estimation times for different sort strategies are comparable.
Only the strategies based on maximum overlap take a bit more time (compared to
other sorting strategies), which is required to find the overlap between the
different PEs.

Figure 9 shows the boxplots of the results for the sorting strategy MoDi,
where the subqueries are partitioned on the number of edge patterns. This
shows very accurate estimates for {EP, c2, s2, t2}, which have mean and max
Q-error of $1.0$ and $54.7$ and becomes even better for labeled structural
synopses for larger patterns.

Table X: The median (and max) q-error of the selectivity estimates using CT CondIndep with different sort strategies and different PETs. | {} | {EP} | {EP,c2,s2,t2} | {EP,c2,s4,t2}
---|---|---|---|---
SaNd | 4.54e+09 (4.29e+24) | 1.96 (204.48) | 1.0 (67.64) | 1.0 (19.86)
Sd | 4.54e+09 (4.29e+24) |  4.54e+09 (4.29e+24) |  4.54e+09 (4.29e+24) |  4.54e+09 (4.29e+24)
NdSa | 4.54e+09 (4.29e+24) | 1.96 (204.48) | 1.0 (67.64) | 1.0 (24.75)
NdSd | 4.54e+09 (4.29e+24) | 1.96 (204.48) | 1.0 (624.75) | 1.0 (56.16)
NaSd | 4.54e+09 (4.29e+24) |  4.54e+09 (4.29e+24) |  4.54e+09 (4.29e+24) |  4.54e+09 (4.29e+24)
NaSa | 4.54e+09 (4.29e+24) |  4.54e+09 (4.29e+24) |  4.54e+09 (4.29e+24) |  4.54e+09 (4.29e+24)
Di | 4.54e+09 (4.29e+24) | 1.96 (204.48) | 1.0 (15.59) | 1.0 (13.81)
MoNd | 4.54e+09 (4.29e+24) | 1.96 (204.48) | 1.0 (108.01) | 1.0 (43.68)
MoDi | 4.54e+09 (4.29e+24) | 1.96 (204.48) | 1.0 (54.72) | 1.0 (28.23)

Figure 9: Accuracy experiments for the CT condIndep on all subqueries (up to
six edge patterns) without property constraints.

Maximum Entropy. The combination technique based on the maximum entropy
principle is computational expensive (exponential in the number of
constraints). Therefore, a forced partitioning of the constraints is used, as
described by Markl et al. [24]. The number for the maximum partition size
(mps) is given as a parameter.

The maxEnt technique is performed for every partition and assumes independence
between the different partitions to obtain the final selectivity estimate.

Notice that the effect of partitioning the constraints is that all PEs are
lost that have constraints that belong to different partitions. Therefore, it
is expected that larger mps values lead to selectivity estimates with higher
accuracy, but require larger estimation times.

MaxEnt using mps values larger than $8$ made the estimation time of some
subqueries larger than a second. Experiments (omitted due to page limit) show
indeed that larger mps values improve estimation accuracy and increase
estimation times. More PETs, that use more advanced statistics, lead to better
estimation accuracy on average. However, it did not show a big improvement on
the worst case errors. Figure 10 also shows this phenomenon, where for large
subqueries, adding more advanced PETs does not help estimation accuracy. The
PEs obtain by those PETs typically include many constraints, which could not
all fit into a single partition. Therefore, due to forced partitioning, those
PEs are lost.

Comparing the results of the CTs condIndep and maxEnt, shows that condIndep
leads to more accurate estimates and requires lower estimation times, which
makes condIndep preferable over maxEnt.

Figure 10: Accuracy experiments for the CT maxEnt with mps=12 on all
subqueries (up to six edge patterns) without property constraints.

Upper Bound. The combination approach based on lower and upper bounds gives
the guarantee that the real cardinality is in between the lower and upper
bound (when the PEs did not introduce any error). Whenever the PES does not
contain a PE that includes all constraints for the query, then the lower bound
was $0$. Therefore, our focus is on the upper bound. Figure 11 shows how the
upper bounds improve when more advanced statistics become available.

Table XI shows the median (and max) q-errors and estimation times. The q-error
clearly decrease with the amount of detailed statistics that become available.
However, the actual errors are very large. Obtaining all independent set of
PEs by considering all subsets required time that is exponential in the number
of PEs in the PES. This caused the estimation time of some subqueries to take
more than $10$ seconds to obtain its upper bound, which makes it impractical
for applications of cardinality estimation like query planning.

Figure 11: Accuracy experiments for the CT upper bound on all subqueries (up to six edge patterns) without property constraints. Table XI: The median (and max) q-error and estimation time (in ms) using the CT based on exact upper bounds with different PETs. |  {} |  {EP} |  {EP,c2,s2,t2} |  {EP,c2,s4,t2}
---|---|---|---|---
Q-Error |  1.45e+21 (2.09e+47) |  2.75e+13 (1.80e+36) |  2.07e+06 (4.29e+27) |  1.0 (2.85e+21)
Est time (ms) |  14.7 (4.83e+03) |  28.5 (1.29e+04) |  42.8 (2.67e+04) |  43.0 (3.63e+04)

####  10.2.2 Combining Query Pattern Constraints

For this section we use all the subqueries, that have at most six edge
pattern, from all JOB queries (same as last section). For each such subquery,
all constraints are considered (different from last section, where the
property constraints were removed).

From last section, we observe that the the CT CondIndep outperforms the CTs
MaxEnt and upper bounds on both estimation time and estimation accuracy.
Therefore, this section focuses on the CT CondIndep.

Labeled Topological Synopses First we repeat the same experiment as in Figure
9, but now all subqueries keep their property constraints. The results are
shown in Figure 12. The labeled topological synopsis for edge patterns
improves the estimation accuracy. However, adding labeled topological synopses
for chain, source star and target star patterns do not further improve the
accuracy.

Notice that none of the PETs include PEs for combination of property
constraints or combination of property and labeled topological constraints.
This means that the error is dominated by the correlation between those
combinations of constraints.

Figure 12: Same experiment as in Figure 9, but now all subqueries keep their
property constraints.

Implied Constraints Assumptions. Using IP EPESTs can add PEs that contain
combinations of property and labeled topological constraints. Therefore, the
CT condIndep will not perform independence assumptions between those
constraints as was done in the previous section.

Figure 13 shows the accuracy results of experiments with different IP EPESTs
when only the PET EP is used. For this scenario, IP(id,a) with IP(ep,p)
performs the best. Here, {EP, IP(id,a), IP(id,p)} has a median and max Q-error
of $101$ and $3.5\cdot 10^{13}$, where {EP} has $1.1\cdot 10^{11}$ and
$3.0\cdot 10^{38}$. The maximum Q-error of independence assumptions is
$10^{24}\times$ larger than for implication assumptions.

The IP type IP(ep,a) is too strong. It essentially ignores the effect of many
constraints that are actually restricting the cardinality of the subqueries.
The other IP types are more conservative, i.e. they make less implication
assumptions (as a result, the CT might have to make more independence
assumptions).

Figure 13: Estimation accuracy experiments for different IP EPESTs. Table XII: The median (and max) estimation time (in ms) for the experiments from Figure 14. PETs and EPETs | #EdgeIds: 1 | #EdgeIds: 2 | #EdgeIds: 3 | #EdgeIds: 4 | #EdgeIds: 5 | #EdgeIds: 6
---|---|---|---|---|---|---
{} | 2.20 (36.4) | 6.14 (71.3) | 12.4 (126) | 23.4 (206) | 38.3 (297) | 57.3 (271)
{EP} | 2.86 (44.5) | 8.83 (93) | 19.1 (185) | 36.4 (314) | 62.8 (463) | 91.1 (468)
{EP, S(id,0.001)} | 711 (8.61e+03) | 1.26e+3 (1.77e+4) | 1.86e03 (2.08e04) | 2.77e+3 (2.43e+4) | 3.68e+03 (2.56e+4) | 4.37e+03 (2.72e+04)
{EP, S(id,0.001), S(ep,0.001)} | 1.32e+03 (1.16e+04) | 2.86e+3 (3.63e+4) | 4.68e+3 (6.28e+4) | 6.75e+3 (8.25e+4) | 8.12e+3 (9.61e+4) | 9.49e+3 (5.42e+4)
{EP,IP(id,a),IP(ep,p)} | 5.45 (108) | 17.7 (226) | 38.0 (372) | 73.8 (613) | 123 (939) | 185 (901)

Sampling techniques Sampling PETs are able to obtain PEs about combinations of
property and topological constraints. Figure 14 shows the results of accuracy
experiments for different sampling techniques. For the pattern parameter of
sampling, we experimented with $id$ and $ep$ and for the probability we used
$10^{-3}$. For comparison reasons, we also added the best technique using IP
EPESTs from the previous section. Here, {EP,S(id,0.001),S(ep,0.001)} gives as
median and max Q-error $6$ and $4.4\cdot 10^{12}$, where
{EP,IP(id,a),IP(ep,p)} gives $101$ and $3.5\cdot 10^{13}$. Therefore, the
median Q-error of sampling is $16\times$ better and max Q-error is $8\times$
better than the best approach based on implication assumptions.

Figure 14: Estimation accuracy experiment for different sampling techniques.

Clearly, sampling techniques improve the estimation accuracy, which highlights
the importance of capturing correlations between constraints referring to the
same $id$ or $ep$. Assuming independence can lead to large underestimations.
Assuming implications can lead to large overestimations.

The median and max estimation time (in ms) for {EP,S(id,0.001),S(ep,0.001)} is
$4890$ and $9.61\cdot 10^{4}$, and for {EP,IP(id,a),IP(ep,p)} it is $36$ and
$939$. Therefore, the median estimation time for sampling is $135\times$
higher and the max estimation time is $102\times$ higher. This raises the
question whether or not the large estimation time of sampling techniques is
worth the improvement in estimation accuracy. Table XII shows the estimation
times of the experiments in Figure 14.

##  11 Conclusions

Many cardinality estimation techniques have been proposed in the literature
which require specific statistics or indexes to be available and use a certain
set of simplifying assumptions. The framework introduced in this document
makes it possible to compare, and even combine, different techniques with the
goal of producing superior solutions.

The framework consists of obtaining estimates for subqueries (partial
estimates) using techniques (partial estimate techniques) that have specific
prerequisites, e.g. specialized statistics or indexes. All partial estimates
are stored in a partial estimate set (PES). This set can be extended and made
complete, such that every constraint from the query pattern is available in at
least one partial estimate in the PES. Finally, all partial estimates in the
PES are combined using a general combine technique (CT). A CT is a general
technique that uses simplifying assumption to combine partial estimates and
therefore can be applied for any complete PES, i.e. it does not require any
form of statistics.

Extensive experiments show that synopsis consisting of the cardinality of
small labeled topological patterns makes it possible to obtain accurate
estimates for query patterns that do not include property constraints. For
query patterns that include property constraints, capturing correlations
between property constraints and labeled topological constraints is essential.
When this information is insufficiently available, then, making implication
assumptions typically performs better than making independence assumptions.

##  12 Future work

###  12.1 Research Perspective

The framework proposed in this document allows new PETs, EPESTs and CTs to be
developed in isolation and finally used in combination with other existing
techniques. Future work consists of proposing new PETs that are able to
capture most important correlations between property and labeled topological
constraints, while keeping the estimation time low. For example, is it
possible to find subclasses of query patterns where sampling can be efficient
and accurate?

Another type of future work is to improve upon the combination techniques. For
example, defining metrics to obtain an optimal sorting strategy for CT
condIndep. The CT MaxEnt might be more valuable as an EPEST.

Instead of only obtaining a cardinality estimate, it would also be very useful
to obtain some sort of error guarantee, e.g. there is a 95% change that the
actual cardinality is between $[100,250]$.

Extensions w.r.t. the query class needs to be considered in the future, e.g.
estimate the cardinality for UCRPQs[4]. UCRPQs is an extension of query
patterns that allows path navigation of arbitrary length, which are specified
using regular expressions.

###  12.2 Practitioners Perspective

In order to benefit from recently developed cardinality estimation techniques,
it is possible to implement our general cardinality estimation framework, i.e.
Algorithm 1. This makes it possible to implement current cardinality
estimation techniques as PETs. Our framework then allows to combine different
techniques by selecting the PETs of interest (depending on trade-offs, e.g.
estimation time and estimation accuracy). For each query, a decision about
what combination of techniques to be used can be made. For example, complex
analytical queries that are expected to run for a long time might afford to
spend more time in the query optimizer, therefore using PETs with higher
estimation times might be allowed.

For the CT, condIndep is recommended since it outperformed the other CTs in
both estimation accuracy and estimation time.

Considering a system with a classical setup for cardinality estimation, e.g.
some (multidimensional) histograms and some form of sampling. Then those
implementations can be transformed into PETs, which allows them to be used in
combination with each other.

Experimental evaluation over the JOB dataset showed that instead of using the
PET SysR (which uses the uniform distribution and inclusion assumptions), it
is recommended to use labTopSyn(EP) in combination with condIndep (which uses
conditional independence assumptions).

## References

  * [1] V. Leis, A. Gubichev, A. Mirchev, P. Boncz, A. Kemper, and T. Neumann, “How good are query optimizers, really?” _Proceedings of the VLDB Endowment_ , vol. 9, no. 3, pp. 204–215, 2015.
  * [2] V. Leis, B. Radke, A. Gubichev, A. Mirchev, P. Boncz, A. Kemper, and T. Neumann, “Query optimization through the looking glass, and what we found running the join order benchmark,” _The VLDB Journal_ , vol. 27, no. 5, pp. 643–668, 2018.
  * [3] “GQL Standard,” https://www.gqlstandards.org, accessed: 2021-07-26.
  * [4] A. Bonifati, G. Fletcher, H. Voigt, and N. Yakovets, “Querying graphs,” _Synthesis Lectures on Data Management_ , vol. 10, no. 3, pp. 1–184, 2018\.
  * [5] A. Bonifati, W. Martens, and T. Timm, “An analytical study of large SPARQL query logs,” _VLDB J._ , vol. 29, no. 2-3, pp. 655–679, 2020.
  * [6] Y. Park, S. Ko, S. S. Bhowmick, K. Kim, K. Hong, and W. Han, “G-CARE: A framework for performance benchmarking of cardinality estimation techniques for subgraph matching,” in _SIGMOD_ , 2020, pp. 1099–1114.
  * [7] R. Angles, M. Arenas, P. Barceló, A. Hogan, J. Reutter, and D. Vrgoč, “Foundations of modern query languages for graph databases,” _ACM Computing Surveys (CSUR)_ , vol. 50, no. 5, pp. 1–40, 2017.
  * [8] O. van Rest, S. Hong, J. Kim, X. Meng, and H. Chafi, “Pgql: a property graph query language,” in _Proceedings of the Fourth International Workshop on Graph Data Management Experiences and Systems_ , 2016, pp. 1–6.
  * [9] R. Angles, M. Arenas, P. Barceló, P. Boncz, G. Fletcher, C. Gutierrez, T. Lindaaker, M. Paradies, S. Plantikow, J. Sequeda _et al._ , “G-core: A core for future graph query languages,” in _Proceedings of the 2018 International Conference on Management of Data_ , 2018, pp. 1421–1432.
  * [10] P. G. Selinger, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie, and T. G. Price, “Access path selection in a relational database management system,” in _Proceedings of the 1979 ACM SIGMOD international conference on Management of data_ , 1979, pp. 23–34.
  * [11] G. Cormode, M. Garofalakis, P. J. Haas, and C. Jermaine, “Synopses for massive data: Samples, histograms, wavelets, sketches,” _Foundations and Trends in Databases_ , vol. 4, no. 1–3, pp. 1–294, 2012.
  * [12] V. Poosala, P. J. Haas, Y. E. Ioannidis, and E. J. Shekita, “Improved histograms for selectivity estimation of range predicates,” _ACM Sigmod Record_ , vol. 25, no. 2, pp. 294–305, 1996.
  * [13] Y. Ioannidis, “The history of histograms (abridged),” in _Proceedings 2003 VLDB Conference_. Elsevier, 2003, pp. 19–30.
  * [14] H. Jagadish, R. T. Ng, and D. Srivastava, “Substring selectivity estimation,” in _Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems_ , 1999, pp. 249–260.
  * [15] A. Aboulnaga, A. R. Alameldeen, and J. F. Naughton, “Estimating the selectivity of xml path expressions for internet scale applications,” in _VLDB_ , vol. 1. Citeseer, 2001, pp. 591–600.
  * [16] W. Cai, M. Balazinska, and D. Suciu, “Pessimistic cardinality estimation: Tighter upper bounds for intermediate join cardinalities,” in _Proceedings of the 2019 International Conference on Management of Data_ , 2019, pp. 18–35.
  * [17] T. Neumann and G. Moerkotte, “Characteristic sets: Accurate cardinality estimation for rdf queries with multiple joins,” in _2011 IEEE 27th International Conference on Data Engineering_. IEEE, 2011, pp. 984–994.
  * [18] V. Poosala and Y. E. Ioannidis, “Selectivity estimation without the attribute value independence assumption,” in _VLDB_ , vol. 97, 1997, pp. 486–495.
  * [19] N. Bruno, S. Chaudhuri, and L. Gravano, “Stholes: a multidimensional workload-aware histogram,” in _Proceedings of the 2001 ACM SIGMOD international conference on Management of data_ , 2001, pp. 211–222.
  * [20] F. Li, B. Wu, K. Yi, and Z. Zhao, “Wander join: Online aggregation via random walks,” in _Proceedings of the 2016 International Conference on Management of Data_ , 2016, pp. 615–629.
  * [21] W. W. W. Consortium _et al._ , “Rdf 1.1 concepts and abstract syntax,” 2014\.
  * [22] A. T. Schreiber and Y. Raimond, “Rdf 1.1 primer,” 2014.
  * [23] N. Bruno and S. Chaudhuri, “Exploiting statistics on query expressions for optimization,” in _Proceedings of the 2002 ACM SIGMOD international conference on Management of data_ , 2002, pp. 263–274.
  * [24] V. Markl, P. J. Haas, M. Kutsch, N. Megiddo, U. Srivastava, and T. M. Tran, “Consistent selectivity estimation via maximum entropy,” _The VLDB journal_ , vol. 16, no. 1, pp. 55–76, 2007.

|  Wilco van Leeuwen is a PhD student in the department of Mathematics and
Computer Science at Eindhoven University of Technology. His current research
interest is on graph query languages, query planning, cardinality estimation
and approximate query evaluation.
---|---
|  George Fletcher is a full professor of computer science at Technische
Universiteit Eindhoven where he is chair of the Database Group. He defended a
PhD at Indiana University Bloomington in 2007. His research interests span
query language design and engineering, foundations of databases, and data
integration. His current focus is on management of massive graphs such as
social networks and linked open data.
---|---
|  Nikolay Yakovets is an assistant professor of computer science at
Technische Universiteit Eindhoven. He obtained his PhD from Lassonde School of
Engineering at York University in 2017. His current focus is on design and
implementation of core database technologies, management of massive graph
data, and efficient processing of queries on graphs.
---|---