# 5.6. Query matching procedure

In order to follow the working of the proposed query matching procedure, we formalize the notion of *core* and *satellite* vertices. Given a query graph *Q*, we decompose the set of query vertices *U* into a set of *core* vertices *U _{c}* and a set of

*satellite*vertices

*U*. Formally, when the degree of the query graph Δ(

_{s}*Q*) > 1,

*U*

_{c}= {

*u*|

*u*∈

*U*∧

*deg(u)*> 1}; however, when Δ(

*Q*) = 1, i.e. when the query graph is either a vertex or a multi-edge, we choose one query vertex at random as a

*core*vertex and hence |

*U*

_{c}| = 1. The remaining vertices are classified as satellite vertices, whose degree is always 1. Formally,

*U*, where for every

_{s}= {U\U_{c}}*u*∈

*U*= 1. The decomposition of the query multigraph

_{s}, deg(u)*Q*is depicted in Figure 5.4, where the satellite vertices are separated (vertices under the shaded region in Figure 5.4(a)), in order to obtain the query graph that is spanned only by the core vertices (Figure 5.4(b)). Thus, during query...