Pattern matching is the foundation for handling complex queries to graph databases. Commonly used algorithms stem from the realm of graph isomorphism and simulations, being well understood theoretical frameworks. On the practical side, there are established graph query languages that often allow for a wide variety of query tasks, often even beyond pattern matching. However, very little is known how graph queries from common query languages relate to graph pattern matching relations. In this paper, we propose a study in this respect for SPARQL, the W3C recommendation for querying RDF data. The homomorphic nature of the SPARQL semantics allows for a straight-forward formulation of graph-isomorphic matching. However, the somewhat arti cial nature of these queries motivates the study of sole basic graph patterns, the foundational concept of SPARQL. For basic graph patterns, we show a correspondence to strong simulation, an e cient graph pattern matching relation appreciated for its polynomial bound matches. In consequence, graph query languages are capable of serving as generating frameworks for established graph pattern matching relations.
Graph databases have gained lots of attention due to their popularity in emerging
applications like the Semantic Web, social network analysis, or bio-technology.
These graphs usually provide entity-centric data, in which nodes represent
entities, while the edges model relations between entities. Several graph database
query languages were developed, enabling users to query graph-structured data
in an SQL-like fashion. Most notably, SPARQL is the W3C standard for
querying Semantic Web data, and is also used for a wide range of applications [
S.Spielberg
fast algorithms, and insights on the semantics of the respective relations, whose
potential is, in our view, not yet fully exploited in the area of graph database
querying. Lately, some e ort were expended to use graph pattern matching
algorithms for matching relations di erent from classical subgraph isomorphism,
often appreciated due to their advantages in performance over traditional graph
querying languages [
In this paper, we study the relationship between graph pattern relations and graph query languages, here exempli ed by SPARQL. Our rst result is best explained by an example. Imagine a user writing a query to search for the directors and writers of movies that won an award, see Fig. 1(a). An isomorphic match to this query is, for instance, the movie Jurassic Park which won an Academy Award, was written by M. Crichton, and directed by S. Spielberg (cf. Fig. 1(b)). The same result is achieved by the SPARQL query, depicted in Fig. 2. The rst part, also called basic graph pattern, comprises variables for the graph pattern nodes and is arranged as triples representing the edges of the graph pattern. The lter condition at the end of the pattern ensures that each assignment to the variables is a bijective one, a necessary condition for graph-isomorphic matching. Being able to formulate such a query is not a coincidence. We prove, in Sect. 4, for every graph pattern there is a query returning every subgraph from a database that is isomorphic to the given pattern. A closer look at the lter condition raises the question, whether a user would be using such an arti cial formulation. Removing the lter allows for (possibly unintended) variable assignments, and may produce answers as depicted in Fig. 1(c). Solely relying on basic graph patterns yields answers showing a (dual-)simulating character upon the original graph pattern, being the result of Sect. 5.
We provide partial and complete characterizations of graph pattern matching
by SPARQL, based on basic graph patterns. We observe that dual simulation
cannot be fully characterized, since the matching relation allows for arbitrary
additions to matches, being also matches of the pattern. Strong simulation, an
extension of dual simulation, removes this arbitrariness and is a matching
relation renown for its e cient evaluation and its polynomial bound number of
matches [
FILTER ( ?vv1 != ?vv2 && ?vv1 != ?vv3 && ?vv1 != ?vv4 && ?vv2 != ?vv3 && ?vv2 != ?vv4 && ?vv3 != ?vv4 ) g Related work and conclusions are given in Sect. 2 and Sect. 6. Due to space limitations, full proofs of the theorems are included in the appendix of this paper. 2
Graph Pattern Matching is an extensively studied topic in various domains of
computer science [
Graph Query Languages basically all are founded on the idea of graph
pattern matching (with suitable substitutions) [
While we focus on graph isomorphism and simulations, the key question
behind this work is not restricted to those relations. Many more comparison
relations are discussed in the literature which may correlate very well with the
semantics of graph query languages. For instance, the linear-time branching-time
spectrum [
Variants of graph homomorphism are also studied in the context of graph
databases [
In this section, we de ne graphs, graph databases complemented by the general concept of graph pattern matching. Furthermore, we introduce an algebra of SPARQL.
A ( -)labeled directed graph is a triple G = (V; ; E), where V is a nite set of nodes, a nite alphabet, and E V V a labeled edge relation. We represent an edge (v; a; v0) 2 E by v a! v0. Labeled directed graphs range over by G; G1; G2; P with node sets V; V1; V2; VP , a xed alphabet common to all graphs, and edge relations E; E1; E2; EP with respective notations !; !1 ; !2; !P . A graph G1 is a subgraph of a graph G2, denoted G1 v G2, i V1 V2 and E1 E2 \ (V1 V1). Two graphs G1 and G2 are isomorphic, iwf rainttdenonGly1 i=f G(v2), i a!th2er(evi0s).a biisjeccatlilveed faunncistoiomnorp:hVis1m!beVt2weseunchGt1haatndv Ga!2. 1Fovr0 two nodes v; v0 of a graph G, we de ne the distance dist G(v; v0) to be the length of the shortest undirected path from v to v0. If there is no path between v and v0, dist G(v; v0) = 1. However, we are interested in connected graphs throughout the rest of the paper, i. e., for every two nodes v; v0, dist G(v; v0) 6= 1. The diameter of a graph G with node set V , denoted dia(G), is the greatest distance between nodes in this graph, i. e., dia(G) := maxfdist G(v; v0) j v; v0 2 V g.
Graph databases store objects from a countable universe O together with attributes over the objects as either relations between objects or properties of objects. As an example, consider an isFriendOf relation between objects referring to persons who are friends in social networks. Properties of objects are expressed as assignments of concrete data values, also called literals, from a usually in nite domain L, to an object, e. g., the age of a person as a positive integer. Inspired by the treatment of literals in RDF, objects as well as literals are represented as nodes in a graph database. Relation symbols and property symbols stem from a nite set, here . A graph database is a directed labeled graph DB = (V; ; E) with a nite set of database objects V O [ L.
A graph pattern is a connected graph P = (VP ; ; EP ). A subgraph G of a graph database DB is an isomorphic match of P (in DB) i P = G. By JP KD=B we denote the set of all isomorphic matches of P .
Since SPARQL aims at querying RDF-stored data, the basic building blocks
of the query language are triples of the form (s; p; o). Subjects (s) refer to objects
in O or variables being assigned by actual database objects during the querying
process. Objects (o) may further be associated with literals from L. Predicates
(p) are thought of as the relation and property symbols in gluing together
subjects with objects. Variables are place-holders for actual objects or literals
as present in concrete databases. The result of a SPARQL query process is
an assignment of objects and literals to the variables mentioned in a query
expression. We denote the set of all variables by V. Notation and semantics are
based on [
Sets of such (s; p; o)-triples are called basic graph patterns (BGP), which we will assume to be graphs. For every BGP B = f(s1; p1; o1); : : : ; (sk; pk; ok)g (k 0) where si 2 O [ V, pi 2 , and oi 2 O [ L [ V (i = 1; : : : ; k), the associated graph is (VB; ; B) such that VB = fs1; : : : ; sk; o1; : : : ; okg. Notice that the nodes in the graph may also be variables. In fact, from the next section on, we employ BGPs in which all nodes are variables. In this paper, BGP B and its graph representation are used interchangeably. By vars(B) we denote the set of all variables occurring in B.
The semantics of SPARQL BGPs B, and henceforth of SPARQL queries Q, is given in terms of assignments of objects and literals to variables in B (Q, respectively). An assignment is a partial function : V ! (O [ L). By (B) we reference the graph where each variable node v 2 vars(B) is replaced by (v). We de ne dom( ) := fv 2 V j (v) is de nedg. An assignment is valid w. r. t. B and a graph database DB i (a) dom( ) = vars(B) and (b) (B) is a subgraph of DB. Thus, is a graph homomorphism. The set of all valid assignments w. r. t. B and a graph database DB forms the foundation of the SPARQL query semantics. We denote this set by JBKDB.
The second concept of SPARQL we use is that of lter conditions, also called
built-in conditions. Filters are used to further restrict the set of (valid)
assignments of a SPARQL query. Thereby, we may check for equality (=) or inequality
(<; ; ; >) of variable assignments, objects, and literals. The usual
propositional connectives (^; _; :) are used to build complex constraints. For a full
list of features we refer to the W3C recommendation report [
Throughout the paper, we make use of BGPs adjoint with lter conditions. The last SPARQL concept we need throughout Sect. 5 is that of a join of two queries. Q1 and Q2 represents the join of Q1 and Q2. Given two assignments i 2 JQiKDB (i = 1; 2). Then they are compatible if for every v 2 dom( 1) \ dom( 2), 1(v) = 2(v). Compatible assignments may be joined, thus, JQ1 and Q2KDB := f 1 [ 2 j i 2 JQiKDB are compatible g. The remaining operations of union and optional queries are not needed in this paper.
Next, we show that for every graph pattern P , there is a SPARQL query QP that uses a BGP and a speci c lter condition to obtain all graph-isomorphic matches of P from a database DB. Please note that we assume graphs to be loop-free, throughout the paper, i. e., for each edge v1 a! v2, v1 6= v2. 4
A graph pattern P gives rise to a canonical BGP. In order to characterize isomorphic matches of P from some database DB, we need to adapt the nodes of P to obtain the possibility of arbitrary assignments of database objects/literals to the nodes of P . In SPARQL terms, this adaptation is performed by exchanging each node by a variable. Fig. 2 gives an example conversion in the where-clause, excluding the lter condition.
De nition 1. Let P = (VP ; ; EP ) be a graph pattern. De ne : VP ! V such that (v) := vv. The BGP of P is de ned as the graph P^ := (V^P ; ; E^P ) such that V^P = f (v) j v 2 VP g and ( (v); a; (v0)) 2 E^P i (v; a; v0) 2 EP . From a graph-theoretic perspective, it directly follows that each graph pattern P is isomorphic to its BGP P^ by isomorphism . Every assignment 2 JP^KDB is a homomorphism, but it is not guaranteed that each graph (P^) is isomorphic to P . We enforce bijectivity of by adding a lter condition checking that for each two distinct nodes v; v0 2 V^P , assigns di erent objects from the database. The P -query for isomorphism is Q=(P ) := P^ filter 'P .
De nition 2. Let P be a graph pattern with set of nodes VP = fv1; v2; : : : ; vng. De ne a lter condition for P alongside (Def. 1) as 'P = Vi<j (vi) 6= (vj ). Reconsider the query given in Fig. 2 as an example query for isomorphism. We now show that the assignments of a P -query for isomorphism are equivalent to the set of all isomorphic matches w. r. t. P . Batman awarded
J.V.Heart
wrote
Dracula
Theorem 1. Let DB be a graph database and P a graph pattern. Then G 2
JP KD=B if and only if there is an assignment 2 JQ=(P )KDB such that (P^) = G.
The proof exploits that assignments from respective queries already are
isomorphisms. This means that by using BGPs and a speci c lter condition, we
reach the same expressive power as isomorphic graph pattern matching. In a way,
Theorem 1 states that SPARQL is complete w. r. t. graph-isomorphic matching.
Graph isomorphism is among the strongest similarity-based matching relations
between graphs. Reducing the constructed SPARQL query in this section to only
the BGP yields a similar result between SPARQL and graph homomorphism,
since a valid assignment amounts to a graph homomorphism. However, as we
will see throughout the next section, BGPs themselves show an interesting
correspondence to graph pattern matching by similarity, or more speci cally, strong
simulation. Strong simulation is renown for its e cient evaluation, compared to
isomorphic matching, and its polynomial bound on the number of matches [
In this section, we rst show that every valid assignment of a BGP P^ corresponds
to a so-called dual simulating match of the underlying graph pattern P .
Thereupon, we argue that there is no reasonable way to capture all dual simulating
matches by a single SPARQL query, since a match may be extended arbitrarily,
even by database relations that are not mentioned by pattern P . The notion
of strong simulation extends dual simulation by restricting (1) the size of the
matches by the diameter of the pattern and (2) all occurring nodes and edges to
match nodes and edges in the pattern. We show this restriction to be su cient
to prove the existence of a SPARQL query that captures all strong simulating
matches. We introduce the necessary notions as needed.
Simulations stem from studies of (concurrent) system behavior [
De nition 3. Let Gi = (Vi; ; Ei) (i = 1; 2) be two graphs. A dual simulation between G1 and G2 is a relation S V1 V2 such that (a) for each node v1 2 V1, there is v2 2 V2 such that (v1; v2) 2 S and (b) for each (v1; v2) 2 S, 1. v1 a!1 v10 implies that there is a v20 2 V2 with v2 a!2 v20 and (v10; v20) 2 S, 2. v10 a!1 v1 implies that there is a v20 2 V2 with v20 a!2 v2 and (v10; v20) 2 S. Let DB be a graph database and Q be a graph pattern. A subgraph G of DB is a dual simulating match of Q in DB i Q D G. The set of all dual simulating matches of Q in DB is denoted by JQKDBD .
It is easy to show that the union of two dual simulations again yields a dual simulation. Since an assignment to a BGP is a homomorphism, we obtain only matches respecting at least the edge structure of a pattern. Therefore, each assignment corresponds also to a dual simulating match.
Proposition 1. Let DB be a graph database and P a graph pattern. Then for all 2 JP^KDB, it holds that (P^) 2 JP KDBD .
For every 2 JP^KDB, S = f(v; ( (v))) j v 2 VP g is the desired dual simulation. The converse does not hold, in general. This is because given a dual simulating match of a graph pattern P , every graph that contains this match as a subgraph is also a match. In theory, if the size of the database as well as the maximum in- and out-degrees of the database nodes are given, one could try to iteratively build BGPs extending the given graph pattern by structures allowed for dual simulation. Such a methodology is rather costly, since we may assume the database to be very large. In contrast, a query is often smaller, easily rendering the answers produced by the enlarged query useless. In fact, if there is at least one dual-simulating match in the graph database, then the graph database itself is also a match. Strong simulation overcomes these issues by limiting the size of matches by the diameter of the pattern. Matches to the graph pattern are locally bounded. Furthermore, irrelevant edges in the match are ltered out, letting a characterization of the respective SPARQL queries come in reach.
In order to exclude irrelevant edges, and thus, also nodes from a matching, the notion of match graph of a dual simulation S is introduced. In a match graph of S, each node and each edge play a role in the simulation. Formally, a graph G is a match graph w. r. t. dual simulation S i (a) for each node v of G, there is a pair (x; v) 2 S for some node x of the pattern, and (b) for each edge v1 a! v2, there is an edge u1 a! u2 in the pattern such that (ui; vi) 2 S (i = 1; 2). While strong simulation considers match graphs of special dual simulations, as we will explain in the next subsection, also dual simulation may bene t from this notion. By jGj we denote the size of G, de ned as the number of nodes in G. Considering all graphs G 2 JP KDBD for some graph pattern P , if G contains at most as many nodes as P , i. e., jGj jP j, then an assignment constructing the match G exists. Lemma 1. Let DB be a graph database and P a graph pattern. For all matches G 2 JP KDBD with dual simulation S such that jGj jP j and G is a match graph w. r. t. S, there is a 2 JP^KDB such that (P^) = G.
Proof. Let G be a dual simulating match of P under dual simulation S, as required. Then S is a homomorphism between P and G. Each node of the pattern has exactly one simulating node in G, since G is a match graph w. r. t. S (cond. (a)) and jGj jP j. As G dual simulates P , an edge in P is re ected by an edge in G, homomorphically. From match graph cond. (b), it follows that each edge in G is re ected by some edge in the pattern. By taking = S, we get (P^) = G. tu 5.2
Strong Simulating Matches
The last Lemma has given an exact characterization of valid assignments of
SPARQL BGPs in terms of matching by dual simulation. In this section, we
look at further restrictions on dual simulations, culminating to the notion of
strong simulation. Strong simulation is an extension of dual simulation, i. e., a
match still needs to dual simulate the pattern (e. g., reconsider Fig. 3(a) as not
strong simulating), but this time, a simulation S certifying for dual simulation
must be maximal, i. e., any other dual simulation is already contained in S.
Uniqueness of the maximal dual simulation is easy to show and may be found,
e. g., in [
Strong simulation aims at keeping possible matches locally constrained such
that the size of a match is bounded and also the overall number of matches is
non-exponential. In order to meet this locality requirement, matches are bounded
in the diameter d of the pattern in such a way that for every match, there is
a node having distance at most d to any other node, e. g., Fig. 3(b) is not
strong simulating to the graph pattern in Fig. 1(a), because the match graph
is disconnected. Therefore, the locality requirement is violated. Formally, we
require a match to be a subgraph of a so-called ball of the database DB. Let v
be a node of DB and r 2 N a radius. Then the subgraph of DB containing node
v and all nodes and edges reached from v in at most r steps (backwards and
forwards along the edges) is called a ball of DB, denoted DdB[v; r]. For strong
simulation, the radius is chosen to be the diameter of the graph pattern.
De nition 4. Let DB be a graph database and P a graph pattern (dia(P ) = d).
Subgraph G of DB is a strong simulating match of P in DB i there is a node v
such that G is a subgraph of DdB[v; d] containing v with the following properties:
(1) P D G by maximal dual simulation S and (2) G is the match graph of S.
By JP KDBS we denote the set of all strong simulating matches of P .
Both, Fig. 1(b) and Fig. 1(c) are strong simulating matches of the pattern in
Fig. 1(a). Ma et al. [
The rest of this section is devoted to proving the existence of a SPARQL query for graph pattern P , i. e., a P -query for strong simulation. Therefore, we rst look at the SPARQL answers, already giving us strong simulating matches, and join them to bigger answers, similar to the SPARQL and -operation (cf. Sect. 3). We then prove that for every strong simulating match there is a set of SPARQL assignments that amounts to the graph by joining the components. The resemblance of our join operator allows us to conclude that there is a SPARQL query re ecting the strong simulating matches of a graph pattern.
The join of two subgraphs of DB is the union of both graphs if they are compatible. Two graphs are compatible i they share at least one node. Remember that we assume only connected graphs as graph patterns, justifying this stronger condition compared to the and -operator of SPARQL.
De nition 5. Let DB be a graph database. Two subgraphs G1; G2 v DB are compatible i V1 \ V2 6= ;. The join of compatible graphs G1 and G2 is de ned as the graph G1 IJ G2 = (V1 [ V2; ; E1 [ E2).
Joining arbitrary strong simulating matches still yields dual simulating matches, but the locality requirement may be violated. Therefore, a second form of compatibility is necessary which restricts the possible combinations of strong simulating matches to be joined. For a graph G and radius r 2 N, C(G; r) denotes the set of center nodes of G w. r. t. r, i. e., all other nodes may be reached in at most r steps (ignoring the directions of the edges). Restricting IJ to only join center nodes w. r. t. the diameter of the pattern maintains the locality requirement of strong simulation.
De nition 6. Let DB be a graph database and r 2 N a radius. Compatible subgraphs G1; G2 v DB are r-compatible i V1 \ V2 C(G1; r) \ C(G2; r). While IJ alone is commutative and associative, we loose associativity requiring r-compatibility. Therefore, we assume left-associativity of IJ throughout the rest of the paper. The join of two strong simulating matches of a graph pattern P is again a strong simulating match of P if the matches are d-compatible with d = dia(P ). This is because the union of two (maximal) dual simulations yields a (maximal) dual simulation and, as long as only center nodes are joined, the distance requirement of strong simulation remain una ected. This insight paves the way for the main theorem of this section. Every strong simulating match of pattern P may be reconstructed out of assignments of query P^. Since empty matches are trivially constructible, from zero BGP assignments, we rule out this case in the next theorem.
Theorem 2. Let DB be a graph database, P a graph pattern with diameter d, and G 2 JP KDBS be non-empty. There are assignments 1; 2; : : : ; k 2 JP^KDB such that for each 0 < j < k, 1(P^) IJ : : : IJ j (P^) and j+1(P^) are dcompatible and 1(P^) IJ 2(P^) IJ : : : IJ k(P^) = G.
Corollary 1. Let DB be a graph database and P a graph pattern. Then there exists a P -query for strong simulation Q S (P ). 6
We provided novel insights into the relation between the widespread graph query languages, exempli ed by SPARQL, and graph pattern matching. Thereby, we obtained a fresh look at the expressive power of graph query languages w. r. t. well-understood graph pattern matching relations. To the best of our knowledge, this is the rst attempt that characterizes graph pattern matching relations by state-of-the-art graph query languages. Our ndings are general in that every query language complete w. r. t. the SPARQL semantics we used (cf. Sect. 3), may reproduce our theorems. By the homomorphic nature of the SPARQL semantics, it was possible to formulate simple queries consisting only of a BGP and a lter condition that constructs all isomorphic matches of a given graph pattern (cf. Theorem 1). Removing the somewhat arti cial lter condition from P -queries for graph isomorphism, thus only considering BGPs, yielded queries returning dual simulating matches. From a computational point of view, the construction of a query capturing all dual simulating matches is rather costly. However, limiting matches to relevant (w. r. t. the pattern) nodes and edges allows to fully characterize dual simulation in this spirit (cf. Lemma 1). Ultimately, we showed the existence of SPARQL queries for matching by strong simulation, an extension of dual simulation that locally restricts the size of the matches (cf. Theorem 2 and Corollary 1). As our rst point for future work, we would like to give a constructive proof of Theorem 2 in order to make our ndings applicable.
From a practical perspective, our results may be bene cial to query
processing performance in very large graph databases. It is known that the evaluation
of SPARQL queries itself is coNP-complete [
Assume for some i, the claim holds in case k = i and any smaller number. We need to show that the claim also holds in case k = i + 1. The induction hypothesis implies that for every match G with jGj i (jP j 1) + 1, there are at most i assignments constructing the match. This follows from the base case constructing graphs of size at most jP j, while any further addition contributes at most jP j 1 nodes to the graph, since by assumption at least one center node is involved in the join.
For case k = i + 1, we establish the following bound of the size of G, i + jP j = i (jP j induction hypothes}is | {z 1) + 1 +(jP j 1).
Towards a contradiction, suppose G is not constructible from the assignments of the BGP P^. Then there is a largest constructible subgraph G0 v G, which needs at most i assignments, and they exist by the induction hypothesis. The subgraph of G that has no shared nodes with G0 is bounded by jP j 1 due to the above equation. There is at least one edge v0 a! v (or v a! v0, resp.) with v0 is in G0 and v is in G but not in G0. Since G is a match of P , there is a smallest subgraph G00 of the database with G00 v G, containing v0 a! v (v a! v0, resp.) and dual simulating P . If G00 is not a sugraph of G, then there is an edge outside of G necessary to dual simulate pattern P ; establishing a contradiction to the assumption that G is a strong simulating match of P . Since the size of G00 is also bounded due to the equation above, G00 adds no more than jP j 1 nodes to G0. By Lemma 1, there is an assignment of P^ that amounts to G00. Since this step may be repeated until no more edges remain, constructibility of G is implied.