G-CORE is a query language with two key characteristics: It is closed under graphs and incoporates paths as rst-class citizens. Currently G-CORE does not have recursion. In this paper we propose this extension and show how to code classical polynomial graph algorithms with it. G-CORE is a graph database query language designed by a working group belonging to the Linked Data Benchmark Council [1]. One of its most novel features is the ability to express paths as rst-class citizens. However, path queries are still not enough to express a wide variety of "natural" queries, particularly classical graph algorithms like topological sort, BFS, Eulerian circuit, etc. We propose to extend G-CORE with (linear) recursive functionalities by introducing a syntax and a semantics that essentially follow the ideas of similar constructs in SQL and SPARQL1. What is more novel is that we take the core basic polynomial algorithms in graph theory and show, rst, that they cannot be coded in standard G-CORE; and second, how to write queries that code them in G-CORE extended with linear recursion. Finally, we tested the code in an evaluator for G-CORE that is being developed by Roberto Garc a at the University of Talca. Basic Notions. A Path Property Graph (PPG) is an edge and node labeled graph where edges and nodes additionally have property-value pairs. In addition, a PPG may also have a collection of paths, where a path is a concatenation of existing, adjacent, edges in the graph. A basic G-CORE query is an expression of the form: CONSTRUCT f MATCH
ON G WHERE
(1)
where f is a full construct pattern, is a full graph pattern and a Boolean
condition [
The graph algorithms BFS and DFS were implemented in [
For SPARQL, Reutter et al [
Adding a Recursive Operator to G-CORE
Among the main issues when adding recursion to query languages are the
complexity of the evaluation, the expressiveness and the e orts to keep the
declarative character of queries. From a theoretical point of view, recursive operators
are based on the theory of least xed points [
Proposed Syntax of linear recursive queries.
WITH RECURSIVE t AS f qbase UNION qrec g qout; (2) where t is a temporary PPG, qbase is a usual G-CORE query, qrec is a positive GCORE query that can use the temporary graph t and qout a recursive G-CORE query itself.
Semantics of recursive queries. First, recall that the queries qbase and qrec are usual G-CORE queries, therefore, are of the form (1). Second, recall that the evaluation of a usual query of the form (1) against a PPG G outputs a binding table M (G), and from it the CONSTRUCT clause returns the PPG consisting of the union of f (`) for each ` 2 M (G). In what follows we will denote by Mb the binding table and by Cb(`) the PPG returned by the CONSTRUCT clause of over the row ` of Mb of the base query qbase. Similarly we denote Cr and Mr respectively for the query qrec. Proposed Semantics of linear recursive queries. Let q be a recursive G-CORE query (like (2)) and G be a PPG. The answer ans(q; G) of the query corresponds to the least xed point of the sequence given by:
G0 = G;
G 1 = ;; Gi+1 = Gi [ fans(qrec; G + (Gi
Gi 1))g;
where: (1) the di erence (Gi Gi 1) is similar to the G-CORE di erence operator
de ned in [
The answer ans(q; G) of the recursive G-CORE query q over G is given by the following procedure: Algorithm 1 Computing the answer of a recursive query in G-CORE Data: PPG G, Queue of PPG'S Q = ;, PPG t = ; for each row l of the binding table Mb(G) do
Insert(Cb(l); Q) while Q 6= ; do
Set r Extract(Q) t t [ r for each row l of the binding table Mr(G + r) do
Insert(Cr(l); Q) return ans(qout; t + G)
The idea is simple: rst with the base query we construct the base case. Then with the recursive query we recursively construct a temporary graph which codes the solution that the output query will use.
Thus, rst we begin with the queue Q empty and the temporary graph t empty. Then we evaluate the matching clause of qbase and for each row of the produced binding table Mb(G), insert Cb(l) into Q. Then we enter the while loop. As long as Q 6= ;, we extract the top element of Q and update the temporary graph with it. Then for each row ` of the binding table Mr(G + r) obtained from the query qrec against G + r (recall that this means that it could use the original graph G as well as the recently obtained graph r), we insert into the queue Q the new results obtained by the recursive construct Cr(l). When we exhaust the queue Q the temporary graph t is nally ready to be used, and the query qout is evaluated against t + G. If qout is a standard G-CORE query the process outputs the result. If qout is a recursive G-CORE query, we proceed as before again.
Notice that the xed point exists whenever the query is monotone. On the form of query de nition in (2) and tis semantics restricts queries to be linear [3{5, 11], that is, you can consult only the new elements added to t.
In graph theory there are problems that have been widely studied and can be solved recursively in polynomial time. Due to space restriction, we will show as an example how the case of topological sort can be coded in recursive G-CORE.
The classic algorithm to obtain the topological sort given an acyclic directed graph is Kahn algorithm (1962). It is not di cult to see that topological sort cannot be expressed in G-CORE. The next query illustrates with the graph of Fig. 1 how to code topological sort in G-CORE:
CONSTRUCT (n) SET n.depth :=0,
CONSTRUCT (x) SET x.depth:=n.depth+1,
The above query rst looks for those nodes which have no outgoing edges (base case) and are assigned with depth equal to 0 as a property. Then the recursive case comes and the nodes which have out edges to the nodes of the base case are added with property depth equal to 1 and so on until all the nodes in G have been added. Finally, we order by depth and we take the maximum value of the property depth.