Graph navigational languages de ne binary relations in terms of pair of nodes in a graph subject to the existence of a path satisfying a certain regular expression. The goal of this paper is to give a novel characterization of navigational languages in terms of the structure of the graph embracing the results of a query. We de ne novel graph-based query evaluation semantics and e cient algorithms able to represent and capture intermediate nodes/edges linking pairs of nodes in the answer. We enhance the language of Nested Regular Expressions (NREs) with our machineries, thus de ning the language of Structural NREs (sNREs).
Graph data pervade everyday's life; social networks, biological networks, and
Linked Open Data on the Web are just a few examples of its spread and
exibility. The limited support that relational query languages o er in terms of
recursion stimulated the design of graph query languages where navigation is a
rst-class citizen. Regular Path Queries (RPQs) and their variants allowing
conjunction (CRPQs) and inverse (C2RPQs) [
Queries expressible with these languages ask for pairs of nodes connected by
a path conforming to a regular language over binary relations. As an example,
Syd can nd that one of his co-authors at distance 3 is Mark; nevertheless, no
information about the structure (i.e., intermediate nodes/edges) of the graph
where the pair (Syd, Mark) appears is given. This missing piece of information
? An extended version of this work titled \Explaining Graph Navigational Queries"
will appear in proc. of the 14th Extended Semantic Web Conference (ESWC).
would allow to understand why a query has returned a certain set of (pairs of)
nodes and is useful in contexts where one needs to connect the dots, such as in
bibliographic networks, generic exploratory search or query debugging [
Related Work. There exists a solid body of work about graph query languages.
The core of such languages are Regular Path Queries (RPQs) that have been
extended with other features, among which, conjunction (CRPQs) [
Contributions and Outline. We make the following main contributions: (i) a structural characterization of Nested Regular Expressions that we call Structural NREs (sNREs), which to the best of our knowledge is the rst graph navigational language able to return graphs as the answer to a navigational query; (ii) formal semantics based on novel operators that work with graphs besides pairs of nodes; (iii) e cient algorithms for query evaluation under the novel semantics.
The remainder of the paper is organized as follows. Section 2 presents the sNREs language. Section 3 presents query evaluation algorithms and a study of their complexity. We conclude and sketch future work in Section 4. 2
We focus our attention on the Resource Description Framework (RDF). An
RDF triple is a tuple of the form hs; p; oi 2 I I I [ L, where I (IRIs) and
L (literals) are countably in nite sets; for ease of exposition we do not consider
blank nodes. An RDF graph G is a set of triples. The set of terms of a graph
will be terms(G) I [ L; nodes(G) will be the set of terms used as a subject
or object of a triple while triples(G) is the set of triples in G. Since SPARQL
property paths o er very limited expressive power we will consider the language
of Nested Regular Expressions (NREs) [
The syntax of sNREs is de ned by the following grammar: snrexp := #exp ( 2 ff ull; f ilt; setg) exp := a j ^a j exp=exp j expjexp j exp j exp[exp1] where a2 , ^ denotes backward navigation, = path concatenation, j path union, and [exp1] an existential test in the form of a nested expression. It is interesting to note that, syntactically, sNREs di ers from NREs (and other navigational languages) only for the construct . sNREs o ers a exible way of choosing the desired output. allows to specify di erent evaluation semantics that output: (i ) pairs of nodes (i.e., set) as in NREs; (ii) structural information in terms of the whole portion of the graph \touched" during the evaluation (f ull); (iii) structural information in terms of (union of) paths leading to some result (f ilt). On the expressiveness of sNREs. We compare sNREs with NREs and other languages that deal with paths/subgraphs. As for NREs, it is easy to see that the output of a sNREs query, when specifying structural information via f ull or f ilt, is richer than that of its corresponding NREs. This occurs because graph navigation is only referenced in the semantics of NREs as the means to get the resulting set of nodes. sNREs enrich NREs in terms of output produced via our reconstruction algorithms (see Section 3) thus indirectly allowing to ask a larger class of requests. As an example with sNREs one can ask to retrieve co-directors and get as by-product movies co-directed.
Languages like ERPQs [
Structural Graphs are used to formally capture the output of the evaluation of a sNRE and are the building blocks of the novel sNREs query semantics. De nition 1 (Structural Graph). Given a graph G, a sNRE expression ex and a set of starting node S nodes(G), a structural graph is a quadruple =(V; E; S; T ) where V nodes(G), E triples(G) and T V is a set of ending nodes, that is, nodes reachable from nodes in S via paths satisfying ex.
Consider the graph G in Fig. 1 and the sNRE a :knows :knows c =(:knows/:knows)j(:co-author/:co-author). The e answer with the semantics based on pairs of nodes b :co-author :co-author d (i.e., NREs semantics) is the set of pairs of nodes: Fig. 1. An example graph. (aare,ct)w,(obs,tda)r.tUinngdneordthese asNaRndEbs sferommanwthicisc,hstinhceeetvhaelureation produces results, one possibility would be to consider the Structural Graph (SG) capturing all results, that is, =(nodes(G); triple(G); fa,bg; fc,dg). However, one may note that there exists a path (via the node e) from a to d in the SG even if the pair (a,d) does not belong to the answer. This could lead to misinterpretation of the query results and their structural information. To avoid these situations, we de ne G-sound and G-complete SGs.
De nition 2 (G-Soundness). Given a graph G and a sNRE expression ex, a SG is G-sound if, and only if, all ending nodes are reachable from all the starting nodes via some paths satisfying ex.
De nition 3 (G-Completeness). Given a graph G and a sNRE expression ex, an SG is G-complete if, and only if, all nodes in a graph G reachable from some starting nodes, via some paths satisfying ex, are in the ending nodes.
The SG in the above example violates G-soundness because the only path existing (via the node e) from a to d (and from b to c) in does not satisfy the expression . The following lemma guarantees G-soundness and G-completeness.
single starting node v2nodes(G) are G-sound and G-complete.
We are now ready to de ne answer graphs that capture the output of sNREs. De nition 5 (Answer Graph). Given a sNRE expression ex and a graph G, an answer graph E is a set of G-sound and G-complete structural graphs. The answer graph of our previous example is the set E=f a; bg s.t.: 1. a=(fa,e,cg; fha; :knows; ei; he; :knows; cig; a; fcg) 2. b=(fb,e,dg; fha; :co-author; ei; he; :co-author; cig; b; fdg).
Note that E is an answer graph according to both f ull and f ilt semantics
since there are no edges that do not contribute to reach some result node.
Formal Semantics. We devised two di erent evaluation semantics for sNREs that
match the syntactic constructs f ilt and f ull. In particular, the f ull semantics
considers all the parts of G that were visited during the evaluation of an
expression, while the second one f ilt, only the portion of G that actually contributed
to build the answer; in other words, the set of SGs such that each v only
considers paths that starts from v2nodes(G) and satisfy the expression (i.e., union
of all the successful paths). For sake of space we do not report the semantics
that are available in an extended version of this paper [
We now describe algorithms for the evaluation of sNREs expressions under the novel semantics. The interesting result is that the evaluation of a sNRE expression e in this new setting can be done e ciently. Let e be a sNRE expression and G a graph. Let jej be the size of e, e the set of edge labels appearing in it, and jGj=jnodes(G)j + jtriples(G)j be the size of G. Algorithms that build answer graphs according to the f ull or f ilt semantics are automata-based and work in two steps. The rst step is shared and leverages product automata; the second step requires a marking phase only for the f ilt semantics and is needed to include nodes and edges that are relevant for the answer.
Building Product Automata. The idea is to associate to e (and to each
[exp]) a non deterministic nite state automaton with transitions Ae (Aexp,
resp.). Such automata can be built according to the standard Thomson
construction rules over the alphabet V oc(e)= e [ S[e1]2e, that is, by considering
also [e1] in e as basic symbols. The product automaton is a tuple G
hQe; V oc(e); e; Qe0; F ei where Qe is a set of states, e:Qe (V oc(e) [ ) !Ae2Q=e
is the transition function, Qe0 Qe is the set of initial states, and F e Qe is
the set of nal states. The building of the product automaton G Ae is based
on the algorithm used by [
Building Answer Graphs. We now discuss algorithms that leverage product automata (of the sNRE expression e and all nested subexpressions) to produce answer graphs according to the f ull and f ilt semantics. To access the elements of a structural graph (see De nition 1) we use the notation :x, with x 2 fV; E; S; T g. The main algorithm is Algorithm 1, which receives the sNRE expression and the type of answer graph to be built. In case of the f ilt semantics the data structure reached, which maintains a set of states (ni; qj ), is initialized via the procedure mark (line 3) reported in Algorithm 2; otherwise, it is initialized as the union of: (i) all the states of the product automaton G Ae; (ii) all the states of the product automata (G Aexp) of all the nested expressions in e (line 5). The procedure mark lls the set reached with all the states in all the product automata that contribute to obtain an answer; these are the states in a path from an initial state to a nal state in the product automata. As shown in Algorithm 2, reached is populated by navigating the product automata backward from the nal states to the initial ones.
A, set of states reached Input: product automaton G Build: set of states reached 1 reached = reached [ S(n;qf )2F e f(n; qf )g 2 visit = S(n;qf )2F e f(n; qf )g s.t. qf 2 F 3 visitN = ; 4 while visit 6= ; do 5 for all (n; q) in visit do 6 for all transition ((n0; q0); x) 2 G 7 if (n0; q0) 2= reached then 8 visitN = visitN [ f(n0; q0)g 9 reached = reached [ f(n0; q0)g 10 for all [exp] in x do 11 mark(G Aexp, reached) 12 visit = visitN 13 visitN = ; 14 return reached
Ae s.t. (n; q) 2 ((n0; q0); x) do
Ae, reached)
Then, the set of SGs composing an answer graph E are initialized (lines 6-7; 9) by adding to E an SG s for each initial state (s; q0) of G Ae. Moreover, the data structure seen is also initialized (line 8) by associating to each state (s; q0) the node s (associated to the initial state (s; q0)) from which it has been visited. Hence, seen maintains for each state, reached during the visit of the product automata, the starting nodes from which this state has already been visited.
The usage of seen avoids to visit the same state more than once for each starting node. The data structure visit is also initialized with the initial states of G Ae (line 10); it contains all the states to be visited in the subsequent step plus the set of starting nodes for which these states have to be visited. Then, the SGs are built via buildA (Algorithm 3). All the states in visit are considered (line 2) only once for the set Bn;q, which keeps starting nodes for which states in visit have to be processed (line 3). Then, for each state (n; q)2visit all its transitions are considered (line 7); in particular, for each state (n0; q0)2reached, reachable from some (n; q) 2 visit via some transitions (line 8), the set of \new" starting nodes (D) for which (n0; q0) has to be visited in the subsequent step is computed with a possible update of the sets visit and seen (lines 9-12).
A, reached, E , visit)
If the transition is labeled with a predicate symbol in G (line 13), the SGs corresponding to nodes s2Bn;q are populated by adding the corresponding nodes and edges (lines 14-16). Otherwise, if the transition is a nested expression the building of the answer graph E proceeds recursively by visiting the product automata associated to all nested (sub)expressions.
Theorem 6. Given a graph G and a sNRE expression e, the answer graph E (according to both semantics) can be computed in time O(jnodes(G)j jGj jej). Proof (Sketch). The answer graph built according to the f ull semantics can be constructed by visiting G Ae (Algorithm 3). In particular, for each starting state (n; q), the states and transitions of G Ae are all visited at most once (and the same also holds for the automata corresponding to the nested expressions of e). The starting and ending nodes of each answer graph are set during the visit of the product automaton. For each node s corresponding to a starting state (s; qo)2Qe0 a structural graph is created (Algorithm 1, lines 6-7); the set of nodes reachable from s is set to be s:T = fn j (n; q) 2 F e and (n; q) is reachable from (s; qo)g (Algorithm 3 lines 5-6). Thus, each structural graph can be computed by visiting each transition and each node exactly once with a cost O(jQej+P[exp]2e jQexpj+ j ej + P[exp]2e j expj) = O(jGj jej). Since the number of SGs to be constructed is bound by jnodes(G)j, the total cost of building the answer graph E , is O(jnodes(G)j jGj jej). This bounds also take into account the cost of building product automata. In the case of the f ilt semantics, the marking phase does not increase the complexity bound; this is because the set reachable, which keeps reachable states, is built by visiting at most once all nodes and transitions in all the product automata, with a cost O(jGj jej). tu
Note that in Algorithm 3, the amortized processing time per node is lower
than jGj jej when visiting the product automaton since the Breadth First
Search(es) from each starting state are concurrently run according to the
algorithm in [
We have studied the novel problem of characterizing graph languages from the
point of view of the structure of the graph where queries are evaluated. We picked
the language of NREs as yardstick because of its attractive computational
properties and showed how we can get more (in terms of structural information) at
the same computational cost. We had to face challenges in terms of formalization
of novel semantics that can deal with graphs and non-trivial (automata-based)
algorithms that can capture structural information in an e cient way. In an
extended version of this work [