Free Essay

Inductive Triple Graphs

In: Computers and Technology

Submitted By labra
Words 5524
Pages 23
Inductive Triple Graphs: A purely functional approach to represent RDF
Jose Emilio Labra Gayo1 , Johan Jeuring2 , and Jose María Álvarez Rodríguez3
1 University of Oviedo Spain labra@uniovi.es Utrecht University, Open University of the Netherlands The Netherlands j.t.jeuring@uu.nl 3 South East European Research Center Greece jmalvarez@seerc.org

2

Abstract. RDF is one of the cornerstones of the Semantic Web. It can be considered as a knowledge representation common language based on a graph model. In the functional programming community, inductive graphs have been proposed as a purely functional representation of graphs, which makes reasoning and concurrent programming simpler. In this paper, we propose a simplified representation of inductive graphs, called Inductive Triple Graphs, which can be used to represent RDF in a purely functional way. We show how to encode blank nodes using existential variables, and we describe two implementations of our approach in Haskell and Scala.

1 Introduction
RDF appears at the basis of the semantic web technologies stack as the common language for knowledge representation and exchange. It is based on a simple graph model where nodes are predominantly resources, identified by URIs, and edges are properties identified by URIs. Although this apparently simple model has some intricacies, such as the use of blank nodes, RDF has been employed in numerous domains and has been part of the successful linked open data movement. The main strengths of RDF are the use of global URIs to represent nodes and properties and the composable nature of RDF graphs, which makes it possible to automatically integrate RDF datasets generated by different agents. Most of the current implementations of RDF libraries are based on an imperative model, where a graph is represented as an adjacency list with pointers, or an incidence matrix. An algorithm traversing a graph usually maintains a state in which visited nodes are collected. Purely functional programming offers several advantages over imperative programming [13]. It is easier to reuse and compose functional programs, to test properties of a program or prove that a program is correct, to transform a program, or to construct a program that can be executed on multi-core architectures.

2

Jose Labra et al

In this paper, we present a purely functional representation of RDF Graphs. We introduce popular combinators such as fold and map for RDF graphs. Our approach is based on Martin Erwig’s inductive functional graphs [10], which we have adapted to the intricacies of the RDF model. The main contributions of this paper are: – a simplified representation of inductive graphs – a purely functional representation of RDF graphs – a description of Haskell and Scala implementations of an RDF library This paper is structured as follows: Section 2 describes purely functional approaches to graphs. In particular, we present inductive graphs as introduced by Martin Erwig, and we propose a new approach called triple graphs, which is better suited to implement RDF graphs. Section 3 presents the RDF model. Section 4 describes how we can represent the RDF model in a functional programming setting. Section 5 describes two implementations of our approach: one in Haskell and another in Scala. Section 6 describes related work and Section 7 concludes and describes future work.

2 Inductive Graphs
2.1 General inductive graphs

In this section we review common graph concepts and the inductive definition of graphs proposed by Martin Erwig [10]. A directed graph is a pair G = (V, E) where V is a set of vertices and E ⊆ V × V is a set of edges. A labeled directed graph is a directed graph in which vertices and edges are labeled. A vertex is a pair (v, l), where v is a node index and l is a label; an edge is a triple (v1 , v2 , l) where v1 and v2 are the source and target vertices and l is the label. Example 21 Figure 1 depicts the labeled directed graph with V = {(1, a), (2, b), (3, c)}, and E = {(1, 2, p), (2, 1, q), (2, 3, r), (3, 1, s)}.

p 1 a s c 3 q r b 2

Fig. 1. Simple labeled directed graph

Inductive Triple Graphs

3

In software, a graph is often represented using an imperative data structure describing how nodes are linked by means of edges. Such a data structure may be an adjacency list with pointers, or an incidence matrix. When a graph changes, the corresponding data structure is destructively updated. A graph algorithm that visits nodes one after the other uses an additional data structure to register what part of the graph has been visited, or adapts the graph representation to include additional fields to mark nodes and edges in the graph itself. Implementing graph algorithms in a functional programming language is challenging as one has to either pass an additional parameter to all the functions with that data structure or use monads to encapsulate the imperative style. This style complicates correctness proofs and program transformations. Martin Erwig [9] introduces a functional representation of graphs where a graph is defined by induction. He describes two implementations that enable persistent graphs [8], and an implementation in Haskell [10], which we summarize in this section. He defines a graph as either 1) an empty graph or 2) an extension of a graph with a node v together with its label and a list of v’s succesors and predecessors that are already in the graph. The type of the values used in an extension of a graph is given by the type Context .
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

-- Context of a node in the graph type Context a b = (Adj b, Node, a, Adj b) -- Adjacent labelled nodes type Adj b = [(Node,b)] -- Labelled nodes type LNode a = (a,Node) -- Index of nodes type Node = Int -- Labelled edges type LEdge b = (Node,Node,b) A context of a node is a value (pred,node,lab,succ), where pred is the list of predecessors, node is the index of the node, lab is the label of the node and succ is the list of successors. Labelled nodes are represented by a pair consisting of a label and a node, and labelled edges are represented by a source and a target node, together with a label. Example 22 The context of node b in Figure 1 is:

1

([(1,’p’)],2,’b’,[(1,’q’),(3,’r’)]) Although the graph type is implemented as an abstract type for efficiency reasons, it is convenient to think of the graph type as an algebraic type with two constructors Empty and :&.

4

Jose Labra et al

1 2

data Graph a b = Empty | Context a b :& Graph a b

Example 23 The graph from Figure 1 can be encoded as:
1 2 3 4

([(2,’q’),(3,’s’)],1,’a’,[(2,’p’)]) :& ([],2,’b’,[(3,’r’)]) :& ([],3,’c’,[]) :& Empty

Note that there may be different inductive representations for the same graph. Example 24 Here is another representation of the graph in Figure 1:
1 2 3 4

([(2,’r’)],3,’c’,[(1,’s’)]) :& ([(1,’p’)],2,’b’,[(1,’q’)]) :& ([],1,’a’,[]) :& Empty The inductive graph approach has been implemented in Haskell in the FGL library4 . FGL defines a type class Graph to represent the interface of graphs and some common operations. The essential operations are:

1 2 3 4 5 6 7 8

class Graph gr where empty:: gr a b isEmpty:: gr a b -> Bool match:: Node -> gr a b -> (Context a b, gr a b) mkGraph::[LNode a] -> [LEdge b] -> gr a b labNodes :: gr a b -> [LNode a]

Fig. 2. Inductive graph representation using M. Erwig approach

A problem with this interface is that it exposes the management of node/edge indexes to the user of the library. It is for example possible to construct graphs with edges between non-existing nodes. Example 25 The following code compiles but produces a runtime error because there is no node with index 42:
4

http://web.engr.oregonstate.edu/~erwig/fgl/haskell

Inductive Triple Graphs

5

1 2 3 4

gErr :: Gr Char Char gErr = mkGraph [(’a’,1)] [(1,42,’p’)]

2.2

Inductive Triple graphs

We propose a simplified representation of inductive graphs based on three assumptions: – each node and each edge have a label – labels are unique – the label of an edge can also be the label of a node

r :q :p a b

Fig. 3. A triple graph with an edge acting also as a node

These three assumptions are motivated by the nature of RDF Graphs, which we will explain in the next section. As we will see in Section 2.3, our approach is general enough to represent any graph. One advantage of this representation is that a user does not have to be aware of node indexes. Also, there is no need for two different types for nodes/edges simplifying the development of an algebra of graphs. A graph of elements of type a is described by a set of triples where each triple has the type (a,a,a). We will call these kind of graphs TGraph (triple based graphs). We assume triple graphs are defined by the following datatype. Practical implementations may use a different representation.
1 2

data TGraph a = Empty | TContext a :& TGraph a where TContext a is defined as:

1 2

type TContext a = (a, [(a,a)], [(a,a)], [(a,a)]) A TContext of a node is a value (node,pred,succ,rels) where node is the node itself, pred is the list of predecessors, succ is the list of successors and rels is the list of pairs of nodes related by this node when it is an edge.

6

Jose Labra et al

Example 26 The graph from Figure 1 can be defined as:
1 2 3 4 5 6 7 8 9 10

(’a’,[(’c’,’s’),(’b’,’q’)], [(’p’,’b’)], []) :& (’b’,[],[(’r’,’c’)],[]) :& (’c’,[],[],[]) :& (’p’,[],[],[]) :& (’q’,[],[],[]) :& (’r’,[],[],[]) :& (’s’,[],[],[]) :& Empty With this representation it is easy to model graphs in which edges are also nodes. Example 27 The graph from Figure 3 can be defined by:

1 2 3 4 5 6

(’a’,[],[(’p’,’b’)],[]) :& (’b’,[],[],[]) :& (’p’,[],[(’q’,’r’)],[]) :& (’q’,[],[],[]) :& (’r’,[],[],[]) :& Empty As in Erwig’s approach, it is possible to have different representations for the same graph. Example 28 The previous graph can also be defined as follows, where we reverse the order of the nodes:

1 2 3 4 5 6

(’r’,[],[(’p’,’q’)],[]) :& (’q’,[],[],[]) :& (’p’,[],[],[(’a’,’b’)]) :& (’b’,[],[],[]) :& (’a’,[],[],[]) :& Empty In Haskell, we implement TGraph as a type class with the following essential operations: Using this simplified interface, it is impossible to create graphs with edges between non-existing nodes. 2.3 Representing Graphs at triple Graphs

We can represent general inductive graphs [10] using inductive triple graphs. The main difference between general inductive graphs and inductive triple graphs is that in general inductive graphs, labels of nodes and edges have an index (an Int), which does

Inductive Triple Graphs
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

7

class TGraph gr where -- empty graph empty :: gr a -- decompose a graph match :: a -> gr a -> (TContext a,gr a) -- make graph from triples mkGraph :: [(a,a,a)] -> gr a -- nodes of a graph nodes :: gr a -> [a] -- extend a graph (similar to :&) extend :: TContext a -> gr a -> gr a

Fig. 4. TGraph representation

not need to be different. We represent a general inductive graph using a record with a triple graph that stores either the index of the node or the index of the edge, and two maps, one from indexes to node labels and another from indexes to edge labels.
1 2 3 4 5 6

data GValue a b = Node a | Edge b data Graph a b = Graph { graph :: TGraph (GValue Int Int), nodes :: Map Int a edges :: Map Int b Example 29 The graph from example 24 can be represented as:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Graph { graph = (Node 1,[(Node 3,Edge 4), (Node 2,Edge 2)], [(Edge 1,Node 2)], [] :& (Node 2,[], [(Edge 3,Node 3)], []) :& (Node 3,[],[],[]) :& (Edge 1,[],[],[]) :& (Edge 2,[],[],[]) :& (Edge 3,[],[],[]) :& (Edge 4,[],[],[]) :& Empty,

8
16 17 18 19 20

Jose Labra et al

nodes = Map.fromList [(1,’a’),(2,’b’),(3,’c’)], edges = Map.fromList [(1,’p’),(2,’q’),(3,’r’),(4,’s’)] }

The conversion between both representations is straightforward and is available at http://github.com/labra/haws. Conversely, we can also represent inductive triple graphs using general inductive graphs. As we describe in Section 5, our Haskell implementation is defined in terms of Martin Erwig’s FGL library. 2.4 Algebra of graphs

Two basic operators on datatypes are the fold and the map [17] . The fold is the basic recursive operator on datatypes: any recursive function on a datatype can be expressed as a fold. Using the representation introduced above, we can define foldGraph:
1 2 3 4 5 6 7

foldTGraph :: TGraph gr => b -> (TContext a -> b -> b) -> gr a -> b foldTGraph e f g = case nodes g of [] -> e (n:_) -> let (ctx,g’) = match n g in f ctx (foldTGraph e f g’) The map operator applies an argument function to all values in a value of a datatype, preserving the structure. It is the basic functorial operation on a datatype. On TGraph ’s, it takes a function that maps a-values in the context to b-values, and preserves the structure of the argument graph. We define mapGraph in terms of foldGraph.

1 2 3 4 5 6 7 8 9 10 11 12 13 14

mapTGraph :: TGraph gr => (TContext a -> TContext b) -> gr a -> gr b mapTGraph f = foldTGraph empty (\ctx g -> extend (mapCtx f ctx) g) where mapCtx f (n,pred,succ,rels) = (f n, mapPairs f pred, mapPairs f succ, mapPairs f rels) mapPairs f = map (\(x,y) -> (f x, f y))

Inductive Triple Graphs

9

An interesting property of mapTGraph is that it maintains the graph structure whenever the function f is injective. Otherwise, the graph structure can be completely modified. Example 210 Applying the function mapTGraph (\_ -> 0) to a graph returns a graph with a single node. Using mapGraph, we define some common operations over graphs. Example 211 The following function reverses the edges in a graph.
1 2 3 4 5

rev :: (TGraph gr) => gr a -> gr a rev = mapTGraph swapCtx where swapCtx (n,pred,succ,rels) = (n,succ,pred,map swap rels)

We have defined other graph functions implementing depth-first search, topological sorting, strongly connected components, etc. 5

3 The RDF Model
The RDF Model was accepted as a recommendation in 2004 [1]. The 2004 recommendation is being updated to RDF 1.1, and the current version [5] is the one we use for the main graph model in this paper. Resources in RDF are globally denoted IRIs (internationalized resource identifiers [7]).6 Notice that the IRIs in the RDF Model are global identifiers for nodes (subjects or objects of triples) and for edges (predicates). Therefore, an IRI can be both a node and an edge. Qualified names are employed to shorten IRIs. For example, if we replace http://example.org by the prefix ex:, ex:a refers http://example.org/a. Throughout the paper we will employ Turtle notation [6]. Turtle supports defining triples by declaring prefix aliases for IRIs and introducing some simplifications. Example 31 The following Turtle code represents the graph in Figure 1.
1 2 3 4 5 6

@prefix : :a :b :b :c
5 6

:p :q :r :s

:b :a :c :a

. . . .

The definitions can be found on http://github.com/labra/haws. The 2004 RDF recommendation employs URIs, but the current working draft uses IRIs.

10

Jose Labra et al

An RDF triple is a three-tuple s, p, o ∈ (I∪B)× I× (I∪B∪L), where I is a set of IRIs, B a set of blank nodes, and L a set of literals. The components s, p, o are called, the subject, the predicate, and the object of the triple, respectively. An RDF graph G is a set of RDF triples. Example 32 The following Turtle code represents the graph in Figure 3.
1 2

:a :p :b . :p :q :r . Blank nodes in RDF are used to describe elements whose IRI is not known or does not exist. The Turtle syntax for blank nodes is _:id where id represents a local identifier for the blank node. Example 33 The following set of triples can be depicted by the graph in Figure 5.

1 2 3 4

:a :p _:b1 :a :p _:b2 _:b1 :q :b _:b2 :r :b

. . . .

:a

:p

_:b1

:p

:q

_:b2

:r

:b

Fig. 5. Example with two blank nodes

Blank node identifiers are local to an RDF document and can be described by means of existential variables [16]. Intuitively, a triple b1 , p, o where b1 ∈ B can be read as ∃b1 b1 , p, o . This predicate holds if there exists a resource s such that s, p, o holds. When interpreting an RDF document with blank nodes, arbitrary resources can be used to replace the blank nodes, replacing the same blank node by the same resource. Currently, the RDF model only allows blank nodes to appear as subjects or objects, and not as predicates. This restriction may be removed in future versions of RDF so we do not impose it in our graph representation model. Literals are used to denote values such as strings, numbers, dates, etc. There are two types of literals: datatype literals

Inductive Triple Graphs

11

and language literals. A datatype literal is a pair (val, t) where val ∈ L is a lexical form representing its value and t ∈ T is a datatype URI. In Turtle, datatype literals are represented as val^^t. A language literal is a pair (s, lang) where s ∈ L is a string value and lang is a string that identifies the language of the literal. In the RDF data model, literals are constants. Two literals are equal if their lexical form, datatype and language are equal. The different lexical forms of literals can be considered unique values. Although the current RDF graph model restricts literals to appear only as objects, we do not impose that restriction in our model. For simplicity, we only use lexical forms of literals in the rest of the paper.

4 Functional representation of RDF Graphs
An RDF document in the RDF model is a labeled directed graph where the nodes are resources. A resource can be modeled as an algebraic datatype:
1 2 3 4 5

data Resource = IRI String | Literal String | BNode BNodeId type BNodeId = Int The RDF graph model has three special aspects that we need to take into account: – edges can also be nodes at the same time (subjects or objects) – nodes are uniquely identified. There are three types of nodes: resource nodes, blank nodes and literals – the identifier of a blank node is local to the graph, and has no meaning outside the scope of the graph. It follows that a blank node behaves as an existential variable [16] To address the first two aspects we employ the triple inductive graphs introduced in Section 2.2, which support defining graphs in which edges can also appear as nodes, and both nodes and edges are uniquely identified. The existential nature of blank nodes can be modeled by logical variables [19]. The type of RDF graphs is defined as:

1 2

data RDFGraph = Ground (TGraph Resource) | Exists (BNodeId -> RDFGraph) Example 41 The graph from Figure 5 is defined as:

1 2 3 4 5 6

Exists (\b1 -> Exists (\b2 -> Ground ( (’a’,[],[(’p’,b1),(’p’,b2)],[]) :& (’b’,[(b1,’q’),(b2,’r’)],[],[]) :& (b1, [], [], []) :&

12
7 8 9 10 11

Jose Labra et al

(b2, [], [], []) :& (p, [], [], []) :& (q, [], [], []) :& (r, [], [], []) :& Empty)))

This RDFGraph encoding makes it easy to construct a number of common functions on RDF graphs. For example, two RDFGraph’s can easily be merged by means of function composition and folds over triple graphs.
1 2 3 4 5 6 7 8

mergeRDF :: RDFGraph -> RDFGraph -> RDFGraph mergeRDF g (Exists f) = Exists (\x -> mergeRDF g (f x)) mergeRDF g (Ground g’) = foldTGraph g compRDF g’ where compRDF ctx (Exists f) = Exists (\x -> compRDF ctx (f x)) compRDF ctx (Ground g) = Ground (comp ctx g) We define the map function over RDFGraphs by:

1 2 3 4 5 6

mapRDFGraph::(Resource -> Resource) -> RDFGraph -> RDFGraph mapRDFGraph h (Basic g) = Basic (gmapTGraph (mapCtx h) g) mapRDFGraph h (Exists f) = Exists (\x -> mapRDFGraph h (f x)) Finally, to define foldRDFGraph, we need a seed generator that assigns different values to blank nodes. In the following definition, we use integer numbers starting from 0.

1 2 3 4 5 6 7 8 9 10

foldRDFGraph :: a -> (Context Resource -> a -> RDFGraph -> a foldRDFGraph e h = foldRDFGraph’ e h 0 where foldRDFGraph’ e h seed (Ground foldTGraph e h g foldRDFGraph’ e h seed (Exists foldRDFGraph’ e h (seed+1) (f

a) ->

g) = f) = seed)

Inductive Triple Graphs

13

5 Implementation
We have developed two implementations of inductive triple graphs in Haskell7 : one using higher-order functions and another based on the FGL library. We have also developed a Scala implementation8 using the Graph for Scala library. 5.1 Implementation in Haskell

Our first implementation uses a functional representation of graphs. A graph is defined by a set of nodes and a function from nodes to contexts.
1 2 3

data FunTGraph a = FunTGraph (a -> Maybe (Context a, FunTGraph a)) (Set a) This implementation offers a theoretical insight but is not intended for practical proposes. The second Haskell implementation is based on the FGL library. In this implementation, a TGraph a is represented by a Graph a and a map from nodes to the edges that they relate.

1 2 3 4 5 6 7 8 9

data FGLTGraph a = FGLTGraph { graph :: Graph a a, nodeMap :: Map a (ValueGraph a) } data ValueGraph a = Value { grNode :: Node, edges :: Set (a,a) } nodeMap keeps track of the index of each node in the graph and the set of (subject,object) nodes that the node relates if it acts as a predicate. Any inductive triple graph can be converted to an inductive graph using Martin Erwig’s approach. 5.2 Implementation in Scala

In Scala, we define a Graph trait with the following interface:
1 2 3 4 5 6

trait TGraph[A] { def empty : TGraph[A] def mkTGraph (triples : Set((A,A,A))): TGraph[A]
7 8

Haskell implementations are available at http://github.com/labra/haws. Scala implementation is available at http://github.com/labra/wesin.

14
7 8 9 10 11 12 13

Jose Labra et al

def nodes : Set[A] def decomp (node : A): (Context[A],TGraph[A]) def extend (ctx : Context[A]): TGraph[A] The Scala implementation is based on the Graph for Scala library developed by Peter Empen. This library provides an in-memory Graph library with a default implementation using adjacency lists and Scala inner classes. It is important to notice that although the base library can employ an underlying non-purely functional approach, the API itself is purely functional. The library contains a generic trait Graph[N, E] to define graphs with nodes of type N and edges of kind E. There are four edge categories: hyperedge, directed hyperedge, undirected and directed edge. Each of these categories has predefined edge classes representing any combination of non-weighted, weighted, key-weighted, labeled and key-labeled. In our case, we will employ 3-uniform directed hypergraphs given that an edge relates three elements (origin, property and destiny). The library offers both a mutable and immutable implementation of graphs. The functions from the Graph for Scala library used in this paper are given in Table 1.
Table 1. Functions employed from the Graph for Scala library

empty nodes edges isEmpty +

Returns an empty Graph List of nodes of a graph List of edges of a graph. For each edge e, we can obtain its 3 components using e._1, e._2 and e.last Checks if graph is empty Adds an edge to a graph returning a new graph. A 3-edge between a, b and c is expressed as a~>b~>c

Our implementation defines a case class TGraphImpl which takes a Graph[ A,Triple] as a parameter. Triple is defined as an instance of DiHyperEdge restricted to hyperedges of rank 3 (triples). Figure 6 depicts the graph from Figure 3 using 3-ranked hyperedges. e1 and e2 are the hyperedges that relate the 2 triples. Following is a sketch of the TGraphImpl code:
1 2 3 4

case class TGraphImpl[A] (graph: Graph[A,Triple]) extends TGraph[A] {

Inductive Triple Graphs a _1 _2 _3 _1 e2 _2 q _3

15

e1

p

r

b Fig. 6. RDF graph as an hypergraph. ei are 3-hypergedges

5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

def empty: TGraph[A] = TGraphImpl(graph.empty) def nodes : Set[A] = graph.nodes.map(_.value) def extend (ctx : Context[A]): TGraph[A] = { TGraphImpl( ((((graph + ctx.node) /: ctx.succ) {(g,p) => g + Triple(ctx.node,p._1,p._2)} /: ctx.pred) {(g,p) => g + Triple(p._1,p._2,ctx.node)} /: ctx.rels) {(g,p) => g + Triple(p._1,ctx.node,p._2)})} def decomp: Option[(Context[A],TGraph[A])]={ if (graph.isEmpty) None else { val node = nodes.head for { pred Ground(g.mapTGraph(fn)) case Exists(f) => Exists ((x : BNode) => f(x)) } } In the same way, we have defined other common functions like foldRDFGraph.

Inductive Triple Graphs

17

6 Related Work
There are a number of RDF libraries for imperative languages like Jena9 , Sesame10 (Java), dotNetRDF11 (C#), Redland12 (C), RDFLib13 (Python), RDF.rb14 (Ruby), etc. For dynamic languages, most of the RDF libraries are binders to some underlying imperative implementation. banana-RDF15 is an RDF library implementation in Scala. Although the library emphasizes type safety and immutability, the underlying implementations are Jena and Sesame. There are some fuctional implementations of RDF libraries. Most of these employ mutable data structures. For example, scaRDF16 started as a facade of Jena and evolved to implement the whole RDF graph machinery in Scala, employing mutable adjacency maps. There have been several attempts to define RDF libraries in Haskell. RDF4h17 is a complete RDF library implemented using adjacency maps, and Swish18 provides an RDF toolkit with support for RDF inference using a Horn-style rule system. It implements some common tasks like graph merging, isomorphism and partitioning representing an RDf graph as a set of arcs. Martin Erwig introduced the definition of inductive graphs [9]. He gives two possible implementations [8], one using version trees of functional arrays, and the other using balanced binary search trees. Both are implemented in SML. Later, Erwig implemented the second approach in Haskell which has become the FGL library. Jeffrey and Patel-Schneider employ Agda19 to check integrity constraints of RDF [14], and propose a programming language for the semantic web [15]. Mallea et al [16] describe the existential nature of blank nodes in RDF. Our use of existential variables was inspired by Seres and Spivey [19] and Claessen [3]. The representation is known in logic programming as ‘the completion process of predicates’, first described and used by Clark in 1978 [4] to deal with the semantics of negation in definite programs. Our representation of existential variables in RDFGraphs uses a datatype with an embedded function. Fegaras and Sheard [11] describe different approaches to implement folds (also known as catamorphisms) over these kind of datatypes. Their paper contains several examples and one of them is a representation of graphs using a recursive datatype with embedded functions.
9 10 11 12 13 14 15 16 17 18 19

http://jena.apache.org/ http://www.openrdf.org/ http://www.dotnetrdf.org/ http://librdf.org/ http://www.rdflib.net/ http://rdf.rubyforge.org/ http://github.com/w3c/banana-rdf http://code.google.com/p/scardf/ http://protempore.net/rdf4h/ http://bitbucket.org/doug_burke/swish http://github.com/agda/agda-web-semantic

18

Jose Labra et al

The representation of RDF graphs using hypergraphs, and transformations between hypergraphs and bipartite graphs, have been studied by Hayes and Gutiérrez [12]. Recently, Oliveira et al. [18] define structured graphs in which sharing and cycles are represented using recursive binders, and an encoding inspired by parametric higherorder abstract syntax [2]. They apply their work to grammar analysis and transformation. It is future work to check if their approach can also be applied to represent RDF graphs.

7 Conclusions
In this paper, we have presented a simplified representation for inductive graphs that we called Inductive Triple Graphs and that can be applied to represent RDF graphs using existential variables. This representation can be implemented using immutable data structures in purely functional programming languages. A functional programming implementation makes it easier to develop basic recursion operators such as folds and maps for graphs, to obtain programs that run on multiple cores, and to prove properties about functions. We developed two different implementations: one in Haskell and another in Scala. The implementations use only standard libraries as a proof-of-concept without taking possible optimizations into account. In the future, we would like to offer a complete RDF library and to check its availability and scalability in real-time scenarios.

8 Acknowledgments
This work has been partially funded by Spanish project MICINN-12-TIN2011-27871 ROCAS (Reasoning on the Cloud by Applying Semantics) and by the International Excellence Campus grant of the University of Oviedo which allowed the first author to have a research stay at the University of Utrecht.

References
1. J. J. Carroll and G. Klyne. Resource description framework (RDF): Concepts and abstract syntax. W3C recommendation, W3C, Feb. 2004. http://www.w3.org/TR/2004/ REC-rdf-concepts-20040210/. 2. A. J. Chlipala. Parametric higher-order abstract syntax for mechanized semantics. In J. Hook and P. Thiemann, editors, Proceeding of the 13th ACM SIGPLAN international conference on Functional programming, ICFP 2008, Victoria, BC, Canada, September 20-28, 2008, pages 143–156. ACM, 2008. 3. K. Claessen and P. Ljunglöf. Typed logical variables in Haskell. In Proceedings of Haskell Workshop, Montreal, Canada, 2000. University of Nottingham, Technical Report. 4. K. L. Clark. Negation as failure. In H. Gallaire and J. Minker, editors, Logic and Databases, pages 293–322. Eds. Plenum Press, 1978. 5. R. Cyganiak and D. Wood. Resource description framework (RDF): Concepts and abstract syntax. W3C working draft, W3C, Jan. 2013. http://www.w3.org/TR/ rdf11-concepts/.

Inductive Triple Graphs

19

6. E. P. Dave Becket, Tim Berners-Lee and G. Carothers. Turtle, terse RDF triple language. World Wide Web Consortium, Working Draft, WD-Turtle, July 2012. 7. M. Dürst and M. Suignard. Internationalized resource identifiers. Technical Report 3987, IETF, 2005. 8. M. Erwig. Fully persistent graphs - which one to choose? In 9th Int. Workshop on Implementation of Functional Languages, number 1467 in LNCS, pages 123–140. Springer Verlag, 1997. 9. M. Erwig. Functional programming with graphs. SIGPLAN Not., 32(8):52–65, Aug. 1997. 10. M. Erwig. Inductive graphs and functional graph algorithms. J. Funct. Program., 11(5):467– 492, Sept. 2001. 11. L. Fegaras and T. Sheard. Revisiting catamorphisms over datatypes with embedded functions (or, programs from outer space). In Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, POPL ’96, pages 284–294, New York, NY, USA, 1996. ACM. 12. J. Hayes and C. Gutiérrez. Bipartite graphs as intermediate model for RDF. In Third International Semantic Web Conference (ISWC2004), volume 3298 of Lecture Notes in Computer Science, pages 47 – 61. Springer-Verlag, 2004. 13. J. Hughes. Why Functional Programming Matters. Computer Journal, 32(2):98–107, 1989. 14. A. S. A. Jeffrey and P. F. Patel-Schneider. Integrity constraints for linked data. In Proc. Int. Workshop Description Logics, 2011. 15. A. S. A. Jeffrey and P. F. Patel-Schneider. As XDuce is to XML so ? is to RDF: Programming languages for the semantic web. In Proc. Off The Beaten Track: Workshop on Underrepresented Problems for Programming Language Researchers, 2012. 16. A. Mallea, M. Arenas, A. Hogan, and A. Polleres. On blank nodes. In L. Aroyo, C. Welty, H. Alani, J. Taylor, A. Bernstein, L. Kagal, N. F. Noy, and E. Blomqvist, editors, International Semantic Web Conference (1), volume 7031 of Lecture Notes in Computer Science, pages 421–437. Springer, 2011. 17. E. Meijer, M. Fokkinga, R. Paterson, and J. Hughes. Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire. FPCA 1991: Proceedings 5th ACM Conference on Functional Programming Languages and Computer Architecture, 523:124–144, 1991. 18. B. C. Oliveira and W. R. Cook. Functional programming with structured graphs. SIGPLAN Not., 47(9):77–88, Sept. 2012. 19. S. Seres and J. M. Spivey. Embedding Prolog into Haskell. In Proceedings of HASKELL’99. Department of Computer Science, University of Utrecht, 1999.…...

Similar Documents

Premium Essay

Deductive and Inductive Reasoning

...Conclusion: Karen was not able to cheer at the game on Wednesday. Facts Facts Deductive Reasoning Deductive Reasoning Logical Argument Logical Argument Accepted Properties Accepted Properties Definitions Definitions Inductive Reasoning: (Observation) Larry came into work late (Observation) Larry didn’t have his lunch. (Prior Experience) Larry always has his lunch with him when he comes to work. Inductive Reasoning Inductive Reasoning (Conclusion) Larry overslept. Verify/Modify Verify/Modify Conjecture Conjecture Pattern Pattern Compare and contrast inductive and deductive reasoning. Provide an example of each to illustrate the similarities and differences of inductive and deductive reasoning. Because inductive and deductive reasoning can both be used to evaluate a statement, deductive reasoning involves starting with a theory or general statement and then working to get a specific conclusion. Where inductive reasoning takes a series of different observations and then tries to make into a general theory. Both approaches are very different, but it is important to both deductive and inductive reasoning can both end with false results and with this being the case the results are “unsound”. An Example of Inductive Reasoning based on this: All Leopards I have seen have spots. So you might think that all Leopards are spotted. But this is not actually the case, but with just this statement and the information given it seems to be true. So......

Words: 414 - Pages: 2

Free Essay

Graphs

...Programming project 3 Task Title: Implementation of basic command-line interface to GraphApplication Task Description: Implement classes that will instantiate a graph editor. The system should accept various kinds of objects from user by given commands, and respond to these commands by creating node objects, creating arc objects, displaying them or deleting them. Implement the following classes: 1. GraphApplication class that will implement command line interface and interact with the user: This class needs to implement the following commands in its run() method: a. quit – exits the application b. nodes - lists the nodes in the graph c. arcs – lists the arcs in the graph these commands do not need index or parameters d. node - this command requires object for which the node will be created e. dir-arc – this command requires two objects that have nodes and relation name and makes a directed arc between them f. undir-arc – this command requires two objects that are added to nodes and relation name and makes non-directed (symmetric) arc between them these commands can take any object, but for now we will use strings g. printout, delete – these commands require an index or name for the object to be shown or deleted if delete takes two arguments it deletes the corresponding arc, of it gets only one, it deletes a node, if printout takes one argument it prints a node, if it takes two arguments it prints the fact......

Words: 2276 - Pages: 10

Free Essay

Graphs and Trees

...Length: 3 Parts: See Assignment Details    Points Possible: 75 Graphs and Trees Task Background: Graphs and trees provide you with ways to visualize data sets, and the opportunity to do analysis on the data (e.g., shortest path). Knowing the structure of a database enables you to choose a proper algorithm for searching for data within a database. Primary Task Response: Within the Discussion Board area, write up to 3 paragraphs that respond to the following questions with your thoughts, ideas, and comments. This will be the foundation for future discussions by your classmates. Be substantive and clear, and use examples to reinforce your ideas. Part I (25 points – distributed as follows) Trees are somewhat less complicated than graphs, which makes things like data searching easier, when a data has the structure of a tree. However, not all data can be represented by a tree. Give an example of a data set that cannot be represented by a tree, but that can be represented by a more general graph. 1) Create, show, and describe your data set. (5 points) V = {Bill, John, Kim, James, Chris, Destiny, Noah, Paul} E = {(Bill, John), (Kim, James), (Chris, Destiny), (Noah, Paul), (Bill, Kim), (John, Chris), (Destiny, Noah)} These are people that are employees at a store. Some work on the same shift together and associate with each other. 2) Then, show by building a graph, how your data is represented by a graph. (5......

Words: 1054 - Pages: 5

Free Essay

Graph

...Section 9.1: Exercises 6, 12, 20, 28, 32, 50 6.) Explain why each graph is that of a function. * Each graph is that of a function because at each point in a graph we get a value for y corresponding to a value for x. This is just the pictorial reflection of what we get in case of a function. Solve each system by substitution 12.) Solution * 2x + y = 5 * y = 5- 2x Substituting in first equation 4x – 5y = -11 4x – 5(5-2x) = -11 4x – 25 + 10x = -11 14 x = -11 + 25 14x = 14 x = 1 Therefore, we get : So, y = 5-2x = 5 -2*1 = 3 x = 1, y =3 Solve each system by elimination. 20.) Solution 4x +y = -23 ………………………eq 1 x - 2y = -17…………………………….eq 2 Performing 2*eq 1 + eq 2 we get : 8x + 2y = -46 x – 2y = -17 This Gives us : 8x + x = -46 -17 9x = -63 x = -7 So, x – 2y = -17 -7 -2y = -17 2y = 17-7 =10 y = 5 So, X = -7, Y =5 28.) Solution 3x/2 + y/2 = -2 * 3x + y = -4 ……………………………….eq 1 x/2 + y/2 = 0 * x + y = 0 ………………………………………..eq2 Performing eq 1 – eq 2 3x + y = -4 (-)x + (-)y = (-)0 3x – x = -4 * 2x = -4 * X = -2 So, X + y = 0 * -2 + y = 0 * Y = 2 So, x = - 2, y = 2 Solve each system. State whether it is inconsistent or has infinitely many solutions. If the system has infinitely many solutions, write the solution set and y arbitrary. 32) Solution 3x + 2y = 5 ……………….eq 1 6x + 4y = 8 ……………….eq2 * 3x + 2y = 4 ……………………...

Words: 1309 - Pages: 6

Premium Essay

Graph

...heading “Method of Collecting Data”. Mention whether the data was received from different sources, like government agencies or departments within the firm. Also explain each source’s method for reporting data. Explain about the method of accounting analysis for these distinct reporting methods. 5. Title the next section as “Significant Financial Events” and under this section, enlist the events which occurred during the studied time period and which altered results. 6. Proceed with a section titled “Detailed Results” which includes a comprehensive analysis about the investment returns, balance sheets, income statement, and productivity ratios. Also comment on each of these factors in addition to providing support for your statements with graphs and tables. 7. Evaluate results from various quarters in a section titled “Analysis of Variance”. 8. Prepare an appendix for “Financial Revenues” defining how that term was used for preparing the report. Tabulate the revenues over the analysis’ time period. 9. End the report with an appendix for “Observations” discussing any problems faced while performing analysis and thereafter explaining about how research method handled problems. Conclude the report with a statement projecting future performance on the basis of past years’ performance.  BalanceSheet - Apollo Tyres Ltd. | | | | | | | Particulars | Mar'13 | Mar'12 | Mar'11 | Mar'10 | Mar'09 | Liabilities | 12 Months | 12 Months | 12 Months | 12 Months | 12 Months | Share......

Words: 738 - Pages: 3

Premium Essay

Triple H

...Case #1: Triple H Film Productions Part 2: MANAGEMENT ISSUES A. i. What is a company? A voluntary association formed and organized to carry on a business. Types of companies include sole proprietorship, partnership, limited liability, corporation, and public limited company. Implication of Limited Liability: Limited Liability Companies, much like corporation, provide protection for their owners. If the organization has debts that it cannot pay, the individual owners will not be held responsible for those debts. If the organization has to file bankruptcy the individual owners are still not personally responsible for any of the liabilities that the organization has. Owners can choose to have profits distributed anyway they would like. This means, whatever percentage of profits they want to give to each member, they have the flexibility to do so. Reduction in paperwork. The tedious meetings and note-taking that are required by corporate entities are not required by an LLC. There are no board meetings or quarterly meetings required. There are no quarterly or semi-annual reports that are necessary for the IRS. There is no double taxation. You do not have to pay taxes on your corporate profits, as well as on profits that pass through to your members. You only pay taxes once, and that is on those profits that are given to individual members  Longevity of the company is based on the life of the members. The company will dissolve if a member goes bankrupt or......

Words: 2208 - Pages: 9

Free Essay

Graph Colouring

...Koinsber bridge, in 1735. This problem lead to the concept of Eulerian Graph. Euler studied the problem of Koinsberg bridge and constructed a structure to solve the problem called Eulerian graph. In 1840, A.F Mobius gave the idea of complete graph and bipartite graph and Kuratowski proved that they are planar by means of recreational problems. The concept of tree, (a connected graph without cycles [1]) was implemented by Gustav Kirchhoff in 1845, and he employed graph theoretical ideas in the calculation of currents in electrical networks or circuits. In 1852, Thomas Gutherie found the famous four color problem. Then in 1856, Thomas. P. Kirkman and William R.Hamilton studied cycles on polyhydra and invented the concept called Hamiltonian graph by studying trips that visited certain sites exactly once. In 1913, H.Dudeney mentioned a puzzle problem. Eventhough the four color problem was invented it was solved only after a century by Kenneth Appel and Wolfgang Haken. This time is considered as the birth of Graph Theory. Graph theoretical concepts are widely used to study and model various applications, in different areas. They include, study of molecules, construction of bonds in chemistry and the study of atoms. Similarly, graph theory is used in sociology for example to measure actor prestige or to explore diffusion mechanisms. Graph theory is used in biology and conservation efforts where a vertex represents regions where certain species exist and the edges......

Words: 476 - Pages: 2

Free Essay

Misleading Graphs

...Misleading Graphs Paper and Presentation Team A: Roderick Hayes II, Melissa Krol, Ann Leal, Wanda Otey, and Corinn Sanders QNT/273 May 9, 2011 Terry Dunning Misleading Graphs Paper and Presentation Graphs are used to give a visual image of data so readers can analyze and translate it quicker and easier than looking at a mass of numbers. However, incorrectly drawn or disproportionately drawn graphs can lead a reader to incorrect translation of data (Bluman, 2009). This document will describe the problems associated with the graph shown below, explain how they affect readers, and what needs to be done to correct the graph (University of Phoenix, 2010). [pic] (Misleading Graphs, 2011) Problems This bar chart represents sales from the year 1995 -1998, this is an assumption because there is no indication that the figures on the horizontal axis represent years. Charts can be quite useful in explaining many capacities of numbers. In looking at this chart, the boxes seem large because of the 3-D effect, which in this chart makes the 1995 bar seem taller than any of the other bars. The label “number of singles sold” on the vertical axis is unclear. The vertical axis also has no percentages or other numeric values indicating how much was sold and the horizontal axis is vague as it does not indicate what the numbers listed represent (Misleading Graphs, 2011). Effect on Users The chart is not properly set up for users to accurately read......

Words: 924 - Pages: 4

Premium Essay

Deductive/Inductive

...Premise 2: A dangerous substance should not be legalize. Conclusion: Therefore marijuana should not be legalize. b. Convert the argument structure into an equation structure, as done in class. The equation we used in class if A=B, B=C, Therefore A=C Marijuana = A Dangerous substance = B Should not be legalize = C Marijuana (A) = Dangerous substance (B) Dangerous substances (B) = should not be legalized (C) Marijuana (A) = should not be legalized (C) 2. Analyze the argument: a. This argument is a deductive argument because the premises are stated by facts rather than assumptions of uncertainty; key words such as “most likely” would make the argument an inductive argument. In a deductive argument the conclusion is directly reached through logical rules from the premises. Meanwhile, inductive is reached by generalizing the information of the premises. In my argument it states that marijuana is a dangerous substance and dangerous substance shouldn’t be legalize. These are direct statements that don’t give any generalization; leading to its conclusion. Each of these differences makes this argument be a deductive one. b. The logic structure of this argument works. If all the premises are true than the conclusion must also be true. The premises were direct statement without uncertainty. The equation as well can show that this argument works as both variable (B) were cancelled out making the conclusion true. Therefore the argument is valid. 3. Evaluate......

Words: 520 - Pages: 3

Premium Essay

Business Graphs

...Business Graphs Unit 8 focus on business graphs, which is covered in your reading of Chapter 7: “Business Statistics.” Note: In this Assignment you will have both Assignment problems and an essay component. For this Assignment you will write an essay to address the requirements described below. Your essay must be carefully planned and written using well-constructed sentences and paragraphs. Make sure that your grammar and spelling are correct. Points will be awarded for content as well as composition. Your essay must be a minimum of 1 half of a full page in length, with standard 1 inch margins and is required to have at least one reference from a reliable source. This means that you cannot use sites like Wikipedia, Ask.com®, and Yahoo® answers and that only references from reliable sources will earn points. All resources should be cited both as an in-text citation as well as being listed on a reference page in APA format. Assignments must be submitted as a Microsoft® Word® document and uploaded to the Dropbox for Unit 8. Include your essay directly in this document following the instructions. All Assignments are due by Tuesday at 11:59 p.m. ET of the assigned unit. Essay Assignment (40 points) Question 1: (10 Points) a) Create a bar graph or line graph for the following data including labels: Presto Printing Company sales for one week, beginning February 2: $9,300 $7,900 $5,609 $5,876 $5,420 $3,769 $3,900 b) Create a circle graph......

Words: 551 - Pages: 3

Premium Essay

Deductive & Inductive Process

...Inductive process works from specific observations to a broader generalizations and theories and related with qualitative method. It is sometimes being recognized as “bottom up” approach and based on learning from experience. Patterns, regularities and resemblances in experience is vital. Generally speaking, it starts with detailed observation, then developed into pattern, from pattern it will be abstractly generalized into tentative hypothesis, empirical generalizations will developed time by time and will end up with generation of theory which evolved as a result of the observations. For example, in Chicago last month, a nine-year-old boy died of an asthma attack while waiting for emergency aid. After their ambulance was pelted by rocks in an earlier incident, city paramedics wouldn’t risk entering the Dearborn Homes Project (where the boy lived) without a police escort. Thus, based on this example, one could inductively reason that the nine- year-old boy died as a result of having to wait for emergency treatment. Deduction is the process by which we arrive at a reasoned conclusion by logical generalization of a known fact. For instance it works from more general to the more specific. The deductive approach is also recognized as “top-down” approach. A researcher who use deductive reasoning in his works will usually narrow down his topic into more specific area which can be tested. For example a research was conducted on the topic classroom learning environments and the......

Words: 396 - Pages: 2

Premium Essay

Graph

...previous page into the spreadsheet. t'JJ The first issue you have to deal with is the heading "Concentration (mol/L)" is too large to fit in • j cell AI. This must be fixed. You can either increase the column width or wrap text. l'j The second issue is that by default, data in the spreadsheet is not "centered" in the cells as shown in the figure. This must also be fixed. Follow the instructions of your instructor. o Notes: • 3. initial here: • 0 Your spreadsheet should look exactly like that in the example, including capitalization, etc. If it does, 2 " :rQ.e 0~ j Name • Using Spreadsheets and Graphing A Skill-Building Exercise in Excel Goal: To Successfully Create an XY Scatter Chart (Graph) using Microsoft Excel 2013 Introduction This lab exercise will walk you through 20 J 3 and using the available I. Background: In most spreadsheet the process of creating an XY Scatter Chart using Microsoft Excel features to format the Scatter Chart. Entering Data in a Spreadsheet programs, the columns and the rows are labeled with numbers. are labeled with letters 1 2 is called a cell. It is common At the intersection L_ of each row and column is a place where data may be entered and this space to place data in a spreadsheet so that 3 sets of related data values are placed in the same row. An example 4 of this would 5 6 temperature be to put a time......

Words: 1308 - Pages: 6

Premium Essay

Line Graph

...PHY 100 LAB My graph depicts the change in the U.S minimum wage over time. This graph has data starting at the implementation of the minimum wage act in 1938, up to more current data in 2014. The gray bar data represents the nominal value for an unadjusted dollar. The yellow bar accounts for the inflation of the dollar, turning it into a 2014 dollar. This depicts what the minimum wage change would look like in constant data value. Looking at the unadjusted graph, there is a bigger discrepancy between the start and end minimum wage. The gray graph has a slow increase of to minimum wage over time. The adjusted wage data depicts many more fluctuations in the data. The yellow bar depicts a more significant increases in the beginning particularly between 1950 to 1970. There are large decreases to the minimum wage around 1975, the end of 1980 and 2008. These decreases do not populate on the nominal value chart. The yellow data shows that the minimum wage has not been a constant an increase like the nominal data. The adjusted dollar is a more realistic and reliable interpretation to the change in the minimum wage. It's interesting that minimum wage has been "higher" in the past then by 2014's minimum wage value. Graph on Page 2 Citation: Taylor, S. L. (2014, February 1). A Basic Fact About The Minimum Wage. Retrieved February 20, 2016, from http://www.outsidethebeltway.com/a-basic-fact-about-the-minimum-wage/ Velocity Graph Descriptions 1 This graph is at a......

Words: 373 - Pages: 2

Premium Essay

The Triple Constraint

...The Triple Constraints of Projects: Quality, Cost and Schedule The Triple Constraint The challenge of every project is to make it work and be successful within the Triple Constraint; theTriple Constraint being quality (scope), cost (resources) and schedule (time). These three elements of a project are known to work in tandem with one another. Where one of these elements is restricted or extended, the other two elements will then also need to be either extended/increased in some way or restricted/reduced in some way. There is a balancing of the three elements that only when fully understood by the Project Manager, allows for the successful planning, resourcing and execution of a project. At the end of the day, these are the key elements of a successful project and these are the things that will determine whether or not you have successfully managed a project. More on the Triple Constraint Now, you may ask yourself, what is so important about the Triple Constraint and what does it affect in the scheme of things? Let’s look a little more closely at the three components that make up the Triple Constraint: Scope/Quality The scope of a project (often called the Scope of Work) is a clear, specific statement as to what has been agreed to be preformed/achieved in a particular project. In other words, the scope expressly lays out the functions, features, data, content, etc. that will be included in the project at hand. You could also say that the scope clearly......

Words: 856 - Pages: 4

Premium Essay

The Bar Graph

...The Statistical Bar Graph Statistical graphs, charts, and tables are in almost every type of newspaper or journals that are published today. The illustrations are used to make the data easier to understand and read. Although, at times, these graphs, tables, or charts can be confusing. Many types of graphs and charts are used, such as bar graphs, dot plots, pie charts, histograms, and line charts just to name a few. The simplest of these is the bar graph. The bar graph is commonly used for qualitative data and compare the amounts or frequency of occurrence of different characteristics. The display in a bar graph allows a person to compare groups of data and make generalizations about data quickly. Since bar graphs are used to graph frequencies, the height of the bar is important. The longer bar represents a higher frequency. Other areas of interest on the graph are the frequency axis and the axes scale. The frequency axis measures the frequency or amount of the different data, and the axes scale measures the range of values being presented along the frequency axis. In this paper, the bar graph will be addressed using a graph from a study that was found on the internet site theragblog.blogspot.com from an article Health Care Reform: ‘This Won’t Hurt a Bit’ (2010). The bar graph shows the main cause of death is the lack of health insurance, and the article states that health care reform could possibly have an effect on this since everyone would be required to have...

Words: 526 - Pages: 3