This paper presents an abstract data model for visualizing RDF data based on the notion of nested graphs. Our study gives theoretical results that shows directions to enhance the representation and visualization of RDF data.
The term data exploration refers to the process by which the user is able to visualize, browse and query the data. Data visualization involves selecting, transforming and representing abstract data in a form that facilitates human interaction and understanding.
RDF data is typically very large, highly interconnected, and heterogeneous
without following a fixed schema [
Current applications for exploring RDF data use different interfaces, each
one having its advantages and disadvantages. For example, circle-and-arrow
diagrams (e.g., IsaViz [
The objective of this paper is to show that underlying object-based
interfaces, there is a powerful data model which needs to be studied formally to take
advantage of its properties. In this sense, we analyze object-based interfaces. We
define a general framework based on the notion of nested graphs, a concept that
was introduced in the area of database modeling by the hypernode model [
The contribution of this paper is the formal definition of an abstract data model for visualizing RDF data based on nested graphs. We show that RDF graphs, nested graphs and graphsets are three equivalent representations for RDF data. We propose the nested graph model as an abstract representation for object-based interfaces.
The paper is organized as follows. In Section 2 we present the RDF model and we study object-based interfaces. A framework for nested graphs and graphsets is defined in Section 3. The abstract model for visualizing RDF data is presented in Section 4. Finally, Section 5 presents some conclusions. 2 2.1
Assume there are pairwise disjoint infinite sets U, B, L such that, U is the set of RDF URI references, L is the set of RDF literals, and B is the set of Blank nodes. We denote by T the union U∪B∪L.A tuple (v1, v2, v3) ∈ (U∪B)×U×T is called an RDF triple, where v1 is the subject, v2 the predicate1, and v3 the object. A set of RDF triples is called an RDF Graph. 2.2
Nowadays, there are many interfaces for browsing RDF data, each one having
its advantages and disadvantages. Among these interfaces we can mention the
following types:
– Keyword Search: It is suffices for simple information lookup, but not for
higher search activities such as browsing and querying (e.g., Swoogle [
It has the advantage that the language can be powerful enough to express any
query, however writing queries is difficult and requires schema knowledge.
– Graph Visualization: It is the most basic visualization model and is based
on circle-and-arrow diagrams (e.g. IsaViz [
We concentrate our effort in to study object-based interfaces. The following lists some characteristics of this kind of interface.
– The resource’s description includes outgoing and (possibly) incoming
properties, which are presented as a list of property-value pairs (recall that an
outgoing / incoming property comes from a statement where the resource
occurs as the subject / object respectively). An incoming property is
commonly represented by an expression “is property of”. For example see
property acquaintance in Figure 1.
– The nesting of resources is not necessarily hierarchical and cyclic references
are possible. For example in Figure 1, the node Tim Berners-Lee contains the
property is acquaintance of which introduces a cyclic reference to the root
resource David Li.
– Encapsulation of information is allowed because a non-expanded resource
hides its properties.
– There is redundant data, in that whenever an object is expanded more than
one level, for and outer property we will also found a “dual inner property”
in the opposite direction. As example, see the properties acquaintance and
is acquaintance of in Figure 1.
– The exploration begins in a root node (a resource that acts as the container),
and browsing is achieved by selecting a property-value which either shows a
new description (in the basic approach) or expands a node (in the complex
approach).
– Queries can be defined by either writing a query expression or constructing
graphically a graph pattern in a query-by-example style (e.g. The
Tabulator [
From the above features, we consider that object-based interfaces are a good approach for visualizing RDF data. In fact, we will show that underlying these interfaces there is a powerful data model which deserves to be studied formally to take advantage of its properties and features. 1 The predicate is also known as the property of the triple. continent value
value
In this section, we will define an abstract data model based on the notion of
nested graphs, a concept that was introduced in the area of graph database
modeling by the Hypernode Model [
Given a nested graph G = (u, N, E), u is called the name of G, N is the set of nodes of G, and E is the set of edges of G. Given a node n ∈ N , if n ∈ Σ then n is called a primitive node and name(n) = n; otherwise, if n = (u′, N ′, E′) ∈ NG then n is called a complex node and name(n) = u′.
Figure 2 presents graphically a nested graph named Peru. It contains primitive nodes (e.g. continent and "Nuevo Sol"), complex nodes (e.g. Lima) and edges (e.g. continent va→lue South America). The complex node Lima is a nested graph which is nested inside the nested graph Peru.
Definition 2. Let G = (u, N, E) be a nested graph and k > 1. The operator nodesk(G) is defined recursively as follows: (i) nodes1(G) = N ; and (ii) nodesk(G) = nodes1(G) ∪ SG′∈N∩NG nodesk−1(G′).
Then, nodesk(G) extracts nodes from G by examining recursively each nested graph in G until reaching the kth level of nesting.
Additionally, we define nodes∗(G) = Sj≥1 nodesj (G). continent value
value nickname value province value country value
A nested graph G is cyclic if G ∈ nodes∗(G) or if there exists G′ ∈ nodes∗(G) such that G′ is cyclic. If G is not cyclic then it is a hierarchical nested graph. A node n is encapsulated in G if n ∈ nodes∗(G). For example, the nested graph of Figure 2 is cyclic because the nested graph Peru occurs as node in the nested graph Lima, i.e., the nested graph Peru is encapsulated in itself. In this section we present the notion of graphset, a plain (or unnested) representation for a nested graph. The complexity of working with a nested structure is usually reduced by transforming it to a plain structure. In this sense, we define additional operators and properties for nested graphs in terms of graphsets. Definition 3. (Plain Graph) A Plain Graph is a nested graph (u, N, E) satisfying that N ⊂ Σ, i.e., a plain graph has no nested graphs as nodes.
Given two plain graphs G1 = (u1, N1, E1) and G2 = (u2, N2, E2), we say that G1 is a subgraph of G2, denoted G1 ⊆ G2, iff N1 ⊆ N2 and E1 ⊆ E2. We say that G1 and G2 are isomorphic, denoted G1 ≈ G2, if and only if G1 ⊆ G2 and G2 ⊆ G1. Additionally, consider the following operations between G1 and G2: Union: G1 ∪ G2 = (u3, N1 ∪ N2, E1 ∪ E2) Intersection: G1 ∩ G2 = (u3, N1 ∩ N2, E1 ∩ E2)
Difference: G1 − G2 = (u3, N1 \ N2, {(n1, n2, n3) ∈ N1 | ni ∈ N1 \ N2})
where u3 ∈ Σ is a fresh label. If name(G1) = name(G2) then u3 = name(G1).
Definition 4. (Graphset) A Graphset S is a set of plain graphs satisfying that,
for each two plain graphs G1 and G2 in S, name(G1) 6= name(G2) , i.e., a label
u ∈ Σ identifies at most one plain graph in S. We denote by GS the set of
graphsets.
The information capacity of a representation is given by the set of objects
modeled by such representation. Additionally, two complex object types are
absolutely equivalent if and only if they can both be reduced to a normal form
complex object types, which is based on some natural restructuring operators [
First, we introduce operations for transforming nested graphs into graphsets. Definition 5. (Flattening of Nested Graphs) Let G = (u, N, E) be a nested graph. We define the operators flat and flat∗ as follows: – flat(G) = (u, N ′, E′) where N ′ = {name(n) | n ∈ N } and
E′ = {(name(n1), name(n2), name(n3)) | (n1, n2, n3) ∈ E} – flat∗(G) = flat(G) ∪ {flat∗(G′) | G′ ∈ N ∩ NG} Then, flat(G) transforms the nested graph G into a plain graph by flattening its first level of nesting. Additionally, flat∗(G) flattens G and each nested graph G′ in G until a fixpoint is reached. For example, Figure 3 shows the graphset obtained by flattening the nested graph in Figure 2.
In the opposite direction, a graphset S can be transformed into a set of nested graphs by expanding the structure of each plain graph in S, i.e, by replacing simple nodes by complex nodes. The following definition formalizes this notion: Definition 6. (Expansion of Graphsets) Given a plain graph G and a graphset S, we define function integrate(G, S) recursively as follows: for each primitive node n ∈ nodes1(G), if there exists G′ ∈ S such that name(G′) = n, then replace n by integrate(G′, S). This procedure is applied until a fixpoint is reached. Additionally, we define integrate(S) = SG∈S integrate(G, S).
Note that integrate(S) returns a set of nested graphs, i.e, one for each plain graph in S. For example, if we expand the graphset in Figure 3, we will obtain the nested graph in Figure 2 plus the nested graph in Figure 4.
The following lemma defines the equivalence, in terms of representation, between nested graphs and graphsets.
Lemma 1. Let NG be the set of nested graphs and GS be the set of graphsets. Then: (i) for each nested graph G ∈ NG, G ∈ integrate∗(flat∗(G)); and (ii) for each graph set S ∈ GS, S = SG∈integrate∗(S) flat∗(G).
Lima nickname value province value country value
Consider a set of nested graphs M starting from a graphset S (i.e., M = integrate∗(S)), Then it holds that M models the same set of objects that S (because S = SG∈integrate∗(S) flat∗(G)). However, in some cases it can occur that a minimal subset M ′ of M is enough for modeling all the data modeled by the graphset S (i.e., we can obtain S by flattening each nested node in M ′). This minimal subset will be called the core of a set of nested graphs. Definition 7. Let M be a set of nested graphs. A Core of M is a minimal subset M ′ of M satisfying that SG′∈M′ flat∗(G′) = SG∈M flat∗(G).
For example, consider the nested graph presented in Figure 2 and call it G. If we flatten G, we have that S = flat∗(G) is the graphset presented in Figure 3. Now, we have that integrate∗(S) will contain the nested graphs of Figure 2 and Figure 4. Note that both nested graphs are a core of the graphset S, because any of them contains all the data modeled by S.
As we see, the core is not necessarily unique. Now, if the core of a set of nested graphs M is a single nested graph G, then G is called the single-source of M . In the context of graphsets, the above property introduces the notion of a single-source graphset.
Definition 8. (Single-source graphset) A graphset S is called a single-source graphset if the core of S is unique.
The notion of a core is useful for visualizing nested graphs. Consider the problem of selecting a good start point for navigation. If we use the core as a minimal set of navigation, we can reduce the number of visible or active nested graphs without losing data, such that all the data could be accessed by navigating through the nested graphs of the core. Clearly this problem could have a direct solution if we have a single-source graphset, then all the data can be accessed from a single nested graph.
Lemma 2. Determining if a graphset S is single-source can be computed in polynomial time.
Proof. Let S be a graphset. To construct a digraph G = (N, E), where the set of nodes N is the set of names of the graphs in S, and there is an arc from u1 to u2 in E if the name u2 occurs as node in the graph named u1. We say that S is single-source if G is connected and there is a unique spanning tree for G (i.e., there is a tree which connects all the nodes together).
Finally, the information capacity of a nested graph G is defined by the graphset flat∗(G). Additionally, the equivalence of two nested graphs is given by the equivalence in their information capacities, i.e., they can be reduced to the same graphset.
Definition 9. (Equivalence of nested graphs) Two nested graphs G1 and G2 are equivalent, denoted G1 ≈ G2, if and only if flat∗(G1) = flat∗(G2).
For example, the nested graphs presented in Figure 2 and Figure 4 are equivalent. Additionally, we say that G1 is a sub-nested graph of G2, denoted G1 ⊆ G2, if it holds that flat∗(G1) ⊆ flat∗(G2). 4 In this section, we define the abstract model for visualizing RDF data based on nested graphs.
Assume that NG∗ ⊂ NG is the set of nested graphs whose set of labels is given by U ∪ L (RDF URIs and labels), and each nested graph (u, N, E) in NG∗ satisfies: (i) u ∈ U; (ii) N ⊂ U ∪ L ∪ NG∗; (iii) E ⊆ ((N \ L) × {+} × N ) ∪ ((N \ L) × {−} × (N \ L)); and (iv) if n ∈ N then n occurs in some edge of E. We denote by GS∗ the set of graphsets having only plain graphs from NG∗.
Given an RDF graph2 GRDF , the following algorithm returns a graphset S ∈ GS∗ which models the same data as GRDF :
Let S be an empty graphset for each triple (v1, v2, v3) in GRDF do
G1 = (v1, N1, E1) where N1 = {v2, v3} and E1 = {(v2, +, v3)} S ← S ∪ G1 if v3 ∈ U then
G2 = (v3, N2, E2) where N1 = {v1, v2} and E2 = {(v2, −, v1)}
S ← S ∪ G2 end if end for
It means that for each resource u ∈ U occurring either as subject or object in some triple of GRDF , there exists a plain graph (u, N, E) where E contains: (i) an edge (n1, +, n2) for each triple (u, n1, n2) where u occurs as the subject; and (ii) an edge (n1, −, n2) for each triple (n2, n1, u) where u occurs as the object. In this sense, a plain graph (u, N, E) in S interprets a resource identified u whose outgoing and incoming properties are encapsulated by edges labeled “+′′ and “−′′ respectively. 2 We restrict our study to RDF graphs having no blank nodes.
David Li
type + family_name + Given name + acquaintance +
Person "Li" "David" Tim Berners−Lee
Type + seeAlso +
name + requested + acquaintance − acquaintance + personal mailbox +
Person http://dbpedia.org/resource/Tim_Berners−Lee "Tim Berners−Lee" http://dbpedia.org/resource/Tim_Berners−Lee David Li
. . .
From Lemma 1, we have that an RDF graph GRDF can also be represented by the set of nested graphs integrate∗(S), where S is the graphset constructed from GRDF (as defined above). It allow us to present the following proposition. Proposition 1. The nested graph model is an abstract representation for Objectbased interfaces.
For example, consider the object-based interface presented in Figure 1. The expanded node David Li can be represented, from an abstract point of view, by the nested graph presented in Figure 5. If we compare both figures, we can see that an expanded node in the interface can be represented by a nested graph, and outgoing and incoming properties are represented by edges labeled “+” and “-” respectively. For example, the incoming link is acquaintance of → David Li of Figure 1 is represented by the edge acquaintance→ David Li in Figure 5.
This abstract representation based on nested graphs enable us to study formally object-based interfaces. For example, the notion of single-source graphset can be used to select an object as the start point of navigation. A language for querying object-based interfaces could be based on the operators defined for nested graphs and graphsets. Exploration states can be stored, serialized or shared in the form of nested graphs or graphsets. 5
In this paper, we studied interfaces for visualizing RDF data, in particular objectbased interfaces. We present a formal framework for representing and querying of nested graphs. We showed that an RDF graph can be modeled in terms of nested graphs and graphsets (a plain representation for nested graphs). We show that studying formal properties of RDF graphs viewed as nested graphs (or graphsets) is possible to optimize some visualization parameters. Further work includes to analyze properties of the model and the definition of a query language. Acknowledgments. R. Angles was supported by Mecesup project No. UCH0109, and by FDI VAC650006, Faculty of Engineering, Universidad de Talca. The author wish to thank the reviewers for their comments.