In this paper, based on SPARQL CONSTRUCT query, we present a new query form called SPARQL Analyze Query, which integrates graph analytics with graph querying. SPARQL Analyze Query extends SPARQL by performing graph algorithms via WITH and PRODUCE operators, where WITH is used for invoking a graph algorithm and PRODUCE for designating results of variables. SPARQL Analyze Query supports two classes of graph algorithms over the weighted RDF graph w.r.t. nodes and shortest paths. Besides, we illustrate the feasibility of the SPARQL Analyze Query in expressing PageRank.
(G; !) where ! denotes the weight function, and shortest path introduced
in [
Inspired by Neo4j, SPARQL Analyze Query supports two classes of graph algorithms w.r.t. nodes and shortest paths, which are PageRank (PR), Betweenness Centrality (BC), Closeness Centrality (CC), Shortest Path (SP), Single Source Shortest Path (SSSP) and All Pair Shortest Path (ALSP). 2
We provide an example of expressing PageRank over a social network to
directly illustrate how SPARQL Analyze Query performs. For clarity, the following
example is based on our semantics introduced in Section 4 while the SPARQL
CONSTRUCT query introduced in [
The following CONSTRUCT query Qc generates a social network which consists of all people that ?p1 knows. The generated weighted RDF graph is shown in Figure 2 where A, B, : : :, H are nicknames of each person respectively.
WHERE f ?m knows ?n. ?m nickName ?p1.
?n nickName ?p2. g
Based on Figure 1, we provide a SPARQL Analyze Query with PageRank algorithm in Figure 3 that reveals the person whose nickname is E has the greatest interpersonal in uence in the social network.
A CONSTRUCT-based Query for Weighted RDF Graph Analytics
PRODUCE ?node ?pr ORDER BY DESC (?pr) LIMIT 3 ?node ?pr
E 0.776535 G 0.604325 H 0.579038 Given a CONSTRUCT query Qc, a SPARQL Analyze query QA is de ned as follows:
Qc WITH C PRODUCE v sq [ORDER BY] [LIMIT] where { Qc is a SPARQL CONSTRUCT query; { C is an analyzing clause of one of the following six forms:
Given a weighted RDF graph S, let NH and EH be sets of nodes and edges occurring in H respectively, where nodes and edges can be variables or constants.
PR : PR (NH ; EH ; n; dF ), where n 2 N+ is the number of iterations in PageRank and dF 2 (0; 1) is the damping factor; BC : BC (NH ; EH ); CC : CC (NH ; EH ); SP : SP (NH ; EH ; u; v) where u; v 2 I [ L; SSSP : SSSP (NH ; EH ; u) where u 2 I [ L;
ALSP : ALSP (NH ; EH ); { PRODUCE v sq designates the output of a SPARQL Analyze Query of variables, where v sq is de ned as a sequence of two variables (v1; v2), v1; v2 2 V , and the parentheses () denote an ordered sequence of variables; { [ORDER BY] and [LIMIT] are standard SPARQL fragments. They are optional to use for controlling the order and the number of solutions. 4
To be compatible with weighted RDF graphs, we extend the semantics
introduced in [
We introduce some new terminology for SPARQL Analyze Query. Let VN 2 V and VE 2 V be the sets of disjoint node and edge variables respectively. Given a node u, a shortest path , and let A be the set of real numbers. We have two mappings : VN ! N , : VE ! E and two functions f : u ! a and g : ! a, where f 2 F , g 2 G and a 2 A. F = fP R; BC; CCg and G = fSP; SSSP; ALSP g are two function sets where each function represents the computation of a graph algorithm. For example, the betweenness centrality of u is obtained by BC(u).
For a SPARQL Analyze Query QA, we say that Q = Qc WITH C is the analytical part of QA. Given a graph pattern P , a weighted RDF graph S, a CONSTRUCT query Qc and an analyzing clause C. The semantics of an analytical part Q of QA returns a set of pairs , denoted by JQKS , de ned as follows:
Q S = J K 8>f(u; f (u)) j < >:f( ; g( )) j ; 2 JP KS ; f (u) 2 Ag
On the above formalization and given an ordered sequence of variables v sq. The semantics of a SPARQL Analyze Query QA, denoted by JQAKS , is de ned as follows: where jv1;v2 is the restriction of
JQAKS = JQ PRODUCE v sqKS = f j(v1;v2) j 2 JQKS g
to (V; V ) correspondingly of its domain. 5
In this paper, we present SPARQL Analyze Query which integrates graph querying with graph analytics. Our approach provides a logical foundation for integrating querying with analytics, which makes it possible to study graph querying and analytics in a uni ed way theoretically. In future work, we will study some fundamental problems of SPARQL Analyze Query such as expressivity and complexity as well as its generalization of more graph algorithms.
This work is supported by the National Key Research and Development Program of China (2017YFC0908401) and the National Natural Science Foundation of China (61972455, 61672377). Xiaowang Zhang is supported by the Peiyang Young Scholars in Tianjin University (2019XRX-0032).