RDF is the data model of choice for Semantic Web applications. RDF graphs are often large and have heterogeneous, complex structure. Graph summaries are compact structures computed from the input graph; they are typically used to simplify users' experience and to speed up graph processing. We introduce a formal RDF summarization framework, based on graph quotients and RDF node equivalence; our framework can be instantiated with many such equivalence relations. We show that our summaries represent the structure and semantics of the input graph, and establish a sufficient condition on the RDF equivalence relation which ensures that a graph can be summarized more efficiently, without materializing its implicit triples.
Name Entailment rule rdfs2 (p; -d; o); (bs1 ; p; o1) ! (bs1 ; ; o) RDF statement Triple Shorthand rdfs3 (p; ,!r; o); (bs1 ; p; o1) ! (o1; ; o) Class assertion (s; rdf:type; o) (s; ; o) rdfs5 (p1; sp; p2); (p2; sp; p3) ! (p1; sp; p3) Property assertion (s; p; o) with p 6= rdf:type (s; p; o) rdfs7 (p1; sp; p2); (bs; p1; o) ! (bs; p2; o) rdfs9 (bs; sc; o); (bs1 ; ; bs) ! (bs1 ; ; o) RDFS statement Triple Shorthand rdfs11 (bs; sc; o); (o; sc; o1) ! (bs; sc; o1) Subclass (s; rdfs:subClassOf; o) (s; sc; o) ext1 (p; -d; o); (o; sc; o1) ! (p; -d; o1) Subproperty (s; rdfs:subPropertyOf; o) (s; sp; o) ext2 (p; ,!r; o); (o; sc; o1) ! (p; ,!r; o1) Domain typing (s; rdfs:domain; o) (s; -d; o) ext3 (p; sp; p1); (p1; -d; o) ! (p; -d; o) Range typing (s; rdfs:range; o) (s; ,!r; o) ext4 (p; sp; p1); (p1; ,!r; o) ! (p; ,!r; o) Table 1: RDF & RDFS statements (left) and sample RDF entailment rules (right). RDF Schema statements (at the bottom left of Ta- P ub t -d P ub ble 1, together with the shorthand notations of sc sc tshtreaiirnptsrorpeelarttiiensg) callalosswesspaencdi/foyrinpgroopnetrotlioegs.icTahl ecosne-- CP ub JP ub mantics of an RDF graph G is its saturation (or closure) G1, defined as the G triples together with r1 r2 r3 all the implicit triples that can be derived from a t t y t a a them and the entailment rules from the RDF stan- a1 t1 t2 y1 t3 a2 a3 dard. Table 1 (right) shows rules that use RDFS Fig. 1: Sample RDF graph G. constraints to derive implicit facts or implicit constraints. Figure 1 depicts a sample publications graph, where P ub stands for publication (CP ub in conferences and J P ub in journals), a for author, t for title and y for year; class nodes and RDFS triples appear in blue, for instance, the domain of t (title) is P ub. Solid arrows correspond to explicit G triples, and dotted arrows to implicit triples; all together, they depict G1.
Next, we call a class (resp. property) node any node of an RDF graph G whose value is used within G as a class (resp. property) in an RDF or RDFS statement; G nodes that are not class or property nodes are called data nodes. 3
Summarization framework We start by recalling the classical notion of graph quotient. Let G = (V; E) be a labeled directed graph whose edges E have labels from a set A. Let be an equivalence relation over the graph node set V . The quotient of G through , denoted G= , is a labeled directed graph having (i) a node nS for each set S of equivalent V nodes, and (ii) an a edge nS1 ! nS2 for some label a 2 A iff there exist two V nodes n1 2 S1 and n2 2 S2 a such that the edge n1 ! n2 2 E.
When summarizing an RDF graph, class and schema information (e.g., the blue part of Figure 1) should be preserved, as they encode its semantics. Thus, we define: Definition 1. Let be a binary relation between the nodes of an RDF graph. We say is an RDF equivalence relation iff (i) is reflexive, symmetric and transitive, (ii) any class node is only to itself, and (iii) any property node is only to itself. We define an RDF summary as a graph quotient w.r.t. a given RDF node equivalence: Definition 2. Given an RDF graph G and an RDF node equivalence relation , the summary of G by , which is an RDF graph denoted G= , is the quotient of G by . G= data nodes use fresh URIs, one for each set of equivalent G data nodes.
A Framework for Efficient Representative Summarization of RDF Graphs Different RDF equivalence relations lead to dif- P ub P ub ferent summaries. Figures 2 illustrates two of sc sc sc sc them on the saturated G1 from Figure 1; circles CP ub JP ub CP ub JP ub denote new-URI summary nodes, each of which represents a set of G nodes. For instance, at left, a ssienpgalreatneoddbeyrethpereirsesnettss or1f;try2p;ers3.;Baetloriwgh,tw, ethdeoy naoret a t y a t t y t a discuss any particular summary further; instead, t -d P ub t -d P ub we focus on our summarization framework, and Fig. 2: Sample summaries. its interplay with saturation.
For a summary to reflect (represent) a graph G, queries having answers on G should also have answers on the summary. Given an RDF query language Q, we define: Definition 3. Let G be any RDF graph. G= is Q-representative of G if and only if for any query q 2 Q such that q(G1) 6= ;, we have q((G= )1) 6= ;.
We target summaries representative of any query over the graph structure of G, including imprecise queries using variables in some property positions. Thus, we instantiate Q into Extended Relational Basic Graph Pattern Queries (RBGP*, in short), a core fragment of SPARQL, defined as follows. A query triple pattern belongs to V (U [ V) V or V f g U , where V is a set of variables. An RBGP* query q is of the form: q(x) t1; : : : ; tn where each ti is a query triple pattern, ft1; : : : ; tng is noted body(q), and x, called the answer variables, is a subset of the variables in body(q). A sample RBGP* query is: q (x1; x3) :- (x1; ; Book); (x1; author; x2); x2 y x3.
We show (the proof is in [
RBGP* representativeness ensures that any query specifying a certain graph pattern in G and/or querying the structure itself (by means of variables in property positions, such as y in the sample query above) which has answers on G, also has answers on G= .
In the presence of an RDF Schema, the semantics of G is its saturation G1. Thus, a representative summary must reflect both the explicit and the implicit triples of G. For instance, the summaries in Figure 2 show that some G1 resources (e.g., r1; r2; r3) are of type P ub, but the same summaries computed from G alone do not, as the corresponding triples are implicit in G. A simple way to obtain (G1)= is to compute G1 and then summarize it. We define a novel alternative shortcut method, which avoids saturating G, yet it constructs an RDF graph strongly isomorphic to (G1)= , as follows: Definition 4. A strong isomorphism between two RDF graphs G1; G2, noted G1 l G2, is an isomorphism which is the identity for the class and property nodes. Definition 5. Summarization through the RDF node equivalence relation shortcut iff for any RDF graph G, (G1)= l ((G= )1)= holds. admits a
The shortcut summarizes G, saturates the result, then summarize it again (the three green edges in Figure 3). Its result is essentially (G1)= , as the two have identical graph structures (guaranteed by the strong isomorphism), on which RBGP* representativeness is defined. They only differ in the new URIs of their nodes (circles in Figure 2).
What is the interest of the shortcut? If G= is much smaller than G, it is much faster to saturate G= (on the shortcut) than to saturate G; (G= )1 is also likely to be small,
Lemma 1 Theorem 1