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_s. Formally, when the degree of the query graph Δ(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_s = {U\U_c}, where for every u ∈ U_s, deg(u) = 1. The decomposition of the query multigraph 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...